一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1299|回复: 14
收起左侧

Google电面

[复制链接] |试试Instant~ |关注本帖
Ziyan 发表于 2015-10-29 06:24:07 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
刚挂电话 。。感觉要悲剧了~ 为什么又碰上了印度面试官       好久没电面了,很紧张,自己都不知道自己在说什么。。。算了,先写面经回馈一下吧先问的是有一个程序,可能跑很多次会有几次fail。。问原因。。
然后是coding。。。 有一个list,里面有很多english words,product = len(word1) * len(word2)。。如果两个word有相同的character,product 就为0,求最大的product...
其实这题在面经中见过。。可是因为紧张,脑子不太转。。后来觉得写的好像有bug。。。比较两个string是否有common character。。我用的是两个int, 然后set bit, 然后再 AND.. 本来说的是把所有words根据长度group一下,然后先比较最长的~ 结果自己紧张没说清,他好像也觉得太麻烦,就跟我说. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
他 ok with just two for loops。。于是我就直接写了brute force的solution。。他也没让我优化也没问时间复杂度,不知道是不是因为早就放弃了。。    后来问了一下他是干嘛的,可惜真心没听懂,所以也接不上话。只能说bye bye了。。。只能祈祷他高抬贵手了. from: 1point3acres.com/bbs

. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2015-10-31 04:10):
HR通知说过了  ~ 希望这一阵能多攒人品

本帖被以下淘专辑推荐:

njjh 发表于 2015-10-29 09:27:47 | 显示全部楼层
Pat,pat. 去年我孩子面试Google时,也遇到了印度面试官,感觉跟你一样,结果也的确不理想。那是四面,后来又参加了第五面。现在已经在谷歌上班了。加油孩子!
回复 支持 1 反对 0

使用道具 举报

snowwolf 发表于 2015-10-29 06:36:46 | 显示全部楼层
跑几次会有几次fail是否跟随机数或者多线程有关?
回复 支持 反对

使用道具 举报

Rudy 发表于 2015-10-29 13:02:33 | 显示全部楼层
patpat,第二个题除了O(n^2)两个For loops,还能怎么优化呢
回复 支持 反对

使用道具 举报

 楼主| Ziyan 发表于 2015-10-29 13:18:19 | 显示全部楼层
snowwolf 发表于 2015-10-29 06:36
跑几次会有几次fail是否跟随机数或者多线程有关?

嗯嗯  对的
回复 支持 反对

使用道具 举报

 楼主| Ziyan 发表于 2015-10-29 13:27:32 | 显示全部楼层
Rudy 发表于 2015-10-29 13:02
patpat,第二个题除了O(n^2)两个For loops,还能怎么优化呢

嗯 我想的是把所有words根据长度group一下,先从长度最长的单词开始找,如果找到了就不用再往下找了  但是面试官说直接两个for loop就够了
回复 支持 反对

使用道具 举报

 楼主| Ziyan 发表于 2015-10-29 13:28:44 | 显示全部楼层
njjh 发表于 2015-10-29 09:27
Pat,pat. 去年我孩子面试Google时,也遇到了印度面试官,感觉跟你一样,结果也的确不理想。那是四面,后来 ...

谢谢你的鼓励   
回复 支持 反对

使用道具 举报

七夜雪 发表于 2015-11-17 09:05:47 | 显示全部楼层
为什么随机数和多线程会使得程序有几次会fail呀@@一直想找这题的解释都没找到
回复 支持 反对

使用道具 举报

QueenieLi 发表于 2015-11-17 11:23:35 | 显示全部楼层
判断两个字符串里是否含有相同字符,可以用一个hashset,比如判断string s1,string s2
HashSet<Character> set=new HashSet<Character>();
for(int i=0;i<s1.length;i++){//把s1所有的不一样的字符先放到set里
    if(!set.contains(s1.charAt(i)))
         set.add(s1.charAt(i));
    else
         continue;
}
for(int j=0;j<s2.length();j++){//检测s2里是否有和s1重复的字符
     if(!set.contains(s2.charAt(j)))
         continue;
     else
          return 0;
}
return s1.length*s2.length;. visit 1point3acres.com for more.
. 1point3acres.com/bbs
这样的时间复杂度是O(n)
不知道这样做对不对,求大神指点
回复 支持 反对

使用道具 举报

eko910817 发表于 2015-11-17 14:29:58 | 显示全部楼层
QueenieLi 发表于 2015-11-16 19:23
判断两个字符串里是否含有相同字符,可以用一个hashset,比如判断string s1,string s2
HashSet set=new Has ...
. more info on 1point3acres.com
但是字典两两对比还是要n^2吧?
回复 支持 反对

使用道具 举报

oneshot 发表于 2015-11-17 23:54:15 | 显示全部楼层
楼主原来的想法是说先把list根据长度sort一下,然后从最长的开始选择?然后面试官让写俩for loop就好?
回复 支持 反对

使用道具 举报

oneshot 发表于 2015-11-18 14:25:18 | 显示全部楼层
public int maxProduct(List<String> list){
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-6 05:14:19 | 显示全部楼层
写了下代码,请问有比brute force更好的办法吗?
  1. public class MaxStringProductWithoutSameCharacter {

  2.         public static void main(String[] args) {
  3.                 List<String> strs = new ArrayList<String>();
  4.                 strs.add("abc");. from: 1point3acres.com/bbs
  5.                 strs.add("cgdsrh");
  6.                 strs.add("egdsrh");
  7.                 strs.add("badgagerwgwe");
  8.                 strs.add("dfaaadfsdfe");
  9.                 strs.add("jtyjukuk");
  10.                 int res = findMaxStringProductWithoutSameCharacter(strs);
  11.                 System.out.println(res);.1point3acres缃
  12.         }. 1point 3acres 璁哄潧
  13.         public static int findMaxStringProductWithoutSameCharacter(List<String> strs) {
  14.                 if (strs == null || strs.size() == 0) {
  15.                         return 0;
  16.                 }
  17.                 int max = 0;
  18.                 for (int i = 0; i < strs.size(); i++) {
  19.                         for (int j = i + 1; j < strs.size(); j++) {
  20.                                 if (!containsSameCharacter(strs.get(i), strs.get(j))) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  21.                                         System.out.println(strs.get(i) + "  " + strs.get(j) + " " + strs.get(i).length() * strs.get(j).length());
  22.                                         max = Math.max(max, strs.get(i).length() * strs.get(j).length());
  23.                                 }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  24.                         }
  25.                 }
  26.                
  27.                 return max;
  28.         }

  29.         private static boolean containsSameCharacter(String str1, String str2) {
  30.                 HashSet<Character> set = new HashSet<Character>();
  31.                 for (char c : str1.toCharArray()) {
  32.                         set.add(c);
  33.                 }
  34.                 for (char c : str2.toCharArray()) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  35.                         if (set.contains(c)) {-google 1point3acres
  36.                                 return true;
  37.                         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  38.                 }
  39.                 return false;
  40.         }
  41. }. Waral 鍗氬鏈夋洿澶氭枃绔,
复制代码
回复 支持 反对

使用道具 举报

cszeus 发表于 2015-12-6 06:08:07 | 显示全部楼层
Ziyan 发表于 2015-10-29 13:27
嗯 我想的是把所有words根据长度group一下,先从长度最长的单词开始找,如果找到了就不用再往下找了  但 ...

感觉从长度最长的开始找,也不一定会找到最长的
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 12:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表