May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1685|回复: 14
收起左侧

Google电面

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
刚挂电话 。。感觉要悲剧了~ 为什么又碰上了印度面试官       好久没电面了,很紧张,自己都不知道自己在说什么。。。算了,先写面经回馈一下吧先问的是有一个程序,可能跑很多次会有几次fail。。问原因。。.鏈枃鍘熷垱鑷1point3acres璁哄潧
然后是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了。。。只能祈祷他高抬贵手了


补充内容 (2015-10-31 04:10):
HR通知说过了  ~ 希望这一阵能多攒人品

本帖被以下淘专辑推荐:

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

使用道具 举报

snowwolf 发表于 2015-10-29 06:36:46 | 显示全部楼层
关注一亩三分地微博:
Warald
跑几次会有几次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
. from: 1point3acres.com/bbs 跑几次会有几次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时,也遇到了印度面试官,感觉跟你一样,结果也的确不理想。那是四面,后来 ...

. more info on 1point3acres.com谢谢你的鼓励   
回复 支持 反对

使用道具 举报

七夜雪 发表于 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;
}. from: 1point3acres.com/bbs
for(int j=0;j<s2.length();j++){//检测s2里是否有和s1重复的字符
     if(!set.contains(s2.charAt(j)))
         continue;. From 1point 3acres bbs
     else
          return 0;
}
return s1.length*s2.length;. 鍥磋鎴戜滑@1point 3 acres

这样的时间复杂度是O(n)
不知道这样做对不对,求大神指点
回复 支持 反对

使用道具 举报

eko910817 发表于 2015-11-17 14:29:58 | 显示全部楼层
QueenieLi 发表于 2015-11-16 19:23
判断两个字符串里是否含有相同字符,可以用一个hashset,比如判断string s1,string s2
HashSet set=new Has ...

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

  30.         private static boolean containsSameCharacter(String str1, String str2) {
  31.                 HashSet<Character> set = new HashSet<Character>();
  32.                 for (char c : str1.toCharArray()) {
  33.                         set.add(c);
  34.                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  35.                 for (char c : str2.toCharArray()) {
  36.                         if (set.contains(c)) {
  37.                                 return true;
  38.                         }
  39.                 }
  40.                 return false;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  41.         }
  42. }. from: 1point3acres.com/bbs
复制代码
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-25 22:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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