聊聊跟三哥三姐面试和共事的经历

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 2818|回复: 11
收起左侧

Google实习三轮电面面经

[复制链接] |试试Instant~ |关注本帖
exthrash 发表于 2015-1-26 01:28:23 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类General 硕士 实习@Google - 内推 - 技术电面  | Fail |

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

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

x
大概去年十月找人内推的,约了12月面试
比较意外的是他们排了3 round的phone interview (一般都是2 round)
. 一亩-三分-地,独家发布
第一round是个美国小哥,口音纯正,问怎么判断valid parenthesis input
(google) rocks
(goo) (gle) () rocks. 牛人云集,一亩三分地
goo (( gle )) rocks. visit 1point3acres for more.

都是valid的

google ((rocks ) 不valid

给了一个用stack的解法,遇到(就push进去,但这边不小心犯了低级错误. From 1point 3acres bbs
把一个condition里面的 || 写成了 &&
抓bug抓了有点久时间,估计是跪在这里
问有没有別的解法,回答recursive,但时间不够没有写代码,大概讲思路. 1point 3acres 论坛
看地里有人这题答到第三个follow-up是输出所有可能的parenthesis combination (cc150题)
因为前面bug抓了有点久,没有写到这里

另一题忘了,应该是因为也不难所以记不起来. 围观我们@1point 3 acres

第二round也是美国小哥,做machine learning的。因为我resume上面有放ML,自己也说对ML感兴趣,就问了一些ML的问题,像是怎么test your model (答cross validation), 聊了聊他们的ML在做啥,好像还问了一些dimension reduction (PCA) 还是feature selection的问题,聊到这边已经15分钟了还没做题
.1point3acres网
接下来上题: . 1point3acres
一个array,element只有A, B, C三种可能,sort it
非常简单,就用counting sort

还有一个follow-up忘了,也是不难,写写test case,就结束了,面到这里感觉非常良好

第三round是美国小妹,做google fit的,是一款记录personal health data的新产品
上来问了两题,第一题也是忘记了 (sorry 过了几个月想不太起来,但也是不难。顶多CC150水準,不及LeetCode)
.留学论坛-一亩-三分地
另一题比较有趣,问一群朋友去电影院,有一些是情侣有一些不是,一开始都乱坐在同一排座位,要怎么样用minimum swap把情侣排在一起

说了一下暴力解是O(n^2),但是当然不会给出暴力解代码,所以继续想
后来说就是counting sort (把input 想成 characters 同一个char就代表这一对是情侣)
所以一开始的input可能像这样  A B A D E B F
counting sort之后变成 A A B B D E F
他问有没有別的解法,我说那就quicksort,他说他没想过可以用sorting解,所以估计这题应该还有其他方法可以解,不过我说quicksort的时候也快45min了,所以也差不多结束问了些问题. 1point 3acres 论坛
.留学论坛-一亩-三分地
大致上感觉运气不错,遇到简单的题,印象中每题也都给了两种解法并且分析time/space complexity
本来感觉良好,后来还是掛了,估计第一面犯了低级错误可能扣了不少分

希望大家都能找到好工作!求大米



评分

6

查看全部评分

tintinmonkey 发表于 2015-1-26 16:13:26 | 显示全部楼层
好文 Thanks for sharing! good luck
回复 支持 1 反对 0

使用道具 举报

Washingtonwei 发表于 2015-1-26 07:47:52 | 显示全部楼层
第三题,或许用HashMap?记录Character和该字符第二次出现index
回复 支持 反对

使用道具 举报

mk01 发表于 2015-2-20 10:30:46 | 显示全部楼层
感觉可能是第三题错了,个人感觉用哈希表可以到O(N)。
  1. import java.util.HashMap;
  2. import java.util.Map;

  3. public class Couple {
  4.     public static void main(String[] args) {
  5.         int[] arr = new int[]{2, 1, 3, 1, 3, 2, 4, 4};
  6.         
  7.         System.out.println(coupleSort(arr));.本文原创自1point3acres论坛
  8.     }
  9.    
  10.     public static int coupleSort(int[] arr) {
  11.         int numSwaps = 0;
  12.         Map<Integer, Integer> int2index = new HashMap<>();.留学论坛-一亩-三分地
  13.         for (int i = 0; i < arr.length; i++) {
  14.             if (!int2index.containsKey(arr[i])) {.留学论坛-一亩-三分地
  15.                 int2index.put(arr[i], i);
  16.             }
  17.             else {
  18.                 if (i % 2 == 1 && int2index.get(arr[i]) == i - 1) {
  19.                     continue;
  20.                 }
  21.                 else {
  22.                     // swapping
  23.                     if (int2index.get(arr[i]) % 2 == 0) {. more info on 1point3acres
  24.                         swap(i, int2index.get(arr[i]) + 1, arr);
  25.                     }. 一亩-三分-地,独家发布
  26.                     else {. 围观我们@1point 3 acres
  27.                         swap(i, int2index.get(arr[i]) - 1, arr);
  28.                     }
  29.                     
  30.                     numSwaps++;
  31.                     int2index.remove(arr[i]);.1point3acres网
  32.                     i--;.留学论坛-一亩-三分地
  33.                 }. 1point3acres
  34.             }
  35.         }
  36.         
  37.         return numSwaps;
  38.     }
  39.    
  40.     public static void swap(int i, int j, int[] arr) {
  41.         int tmp = arr[i];. From 1point 3acres bbs
  42.         arr[i] = arr[j];
  43.         arr[j] = tmp;
  44.     }
  45. }
复制代码
回复 支持 反对

使用道具 举报

agneshanlu 发表于 2015-8-21 03:30:43 | 显示全部楼层
mk01 发表于 2015-2-20 10:30
感觉可能是第三题错了,个人感觉用哈希表可以到O(N)。

请问可以详细讲一下吗?为什么会分index的奇偶讨论呢?谢谢!
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-8-31 04:01:07 | 显示全部楼层
mk01 发表于 2015-2-20 10:30. from: 1point3acres
感觉可能是第三题错了,个人感觉用哈希表可以到O(N)。

大牛,这个题目可以麻烦你再讲详细点嘛?谢谢了。
回复 支持 反对

使用道具 举报

danchou 发表于 2015-8-31 12:12:07 | 显示全部楼层
第三题怎么做。。Greedy可行吗?
回复 支持 反对

使用道具 举报

mileschen2008 发表于 2015-10-5 09:49:09 | 显示全部楼层
mk01 发表于 2015-2-20 10:30
感觉可能是第三题错了,个人感觉用哈希表可以到O(N)。

Couple swap确实很难啊,能讲讲思路以及为啥是minimum swap么?
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

怪兽岛 发表于 2015-10-6 06:53:07 | 显示全部楼层
没看懂楼上的Couple Sort的解法,感觉这个解法是在数一种swap的方案有多少次交换,但没能解释是否是最优。因为似乎该答案是碰到重复的看第一次出现的字母是奇数index还是偶数index,奇数向前换偶数向后换,这样的话以下这个例子就不成立了:FABCCDDAB。A是第一个需要swap的,而由于第一次出现的A是index == 1,是奇数,所以它会换到F处,而最优解应该是AB相换。
. Waral 博客有更多文章,
回复 支持 反对

使用道具 举报

雀巢咖啡extra 发表于 2015-10-21 08:08:40 | 显示全部楼层
感觉是不是这样就可以了
用一个map存char及它首次出现的position;
对于每个char,如果它之前没有出现过,就把它存到map里;如果出现过,就将它与之前出现过的该char后面一个char互换。
  1.         public void minimumSwap(char[] chars){
  2.                 Map<Character, Integer> map = new HashMap();
  3.                 for(int i = 0; i < chars.length; i ++){
  4.                         if(! map.containsKey(chars[i])).1point3acres网
  5.                                 map.put(chars[i], i);
  6.                         else{
  7.                                 char c = chars[i];
  8.                                 int index = map.get(c);. From 1point 3acres bbs
  9.                                 chars[i] = chars[index + 1];
  10.                                 chars[index+1] = c;. Waral 博客有更多文章,
  11.                                 map.put(chars[i], i);
  12.                         }
  13.                 }
  14.         }
复制代码
回复 支持 反对

使用道具 举报

mileschen2008 发表于 2015-10-22 08:04:49 | 显示全部楼层
雀巢咖啡extra 发表于 2015-10-21 08:08
感觉是不是这样就可以了
用一个map存char及它首次出现的position;
对于每个char,如果它之前没有出现过, ...

能保证是minimum swap么?
回复 支持 反对

使用道具 举报

mgccl 发表于 2015-10-24 06:09:52 | 显示全部楼层
couple swap怎么做到的? 我到现在还没见到过多项式时间的解法.
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-22 18:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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