一亩三分地论坛

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

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

Google实习三轮电面面经

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

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

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

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

x
大概去年十月找人内推的,约了12月面试
比较意外的是他们排了3 round的phone interview (一般都是2 round)

第一round是个美国小哥,口音纯正,问怎么判断valid parenthesis input
. Waral 鍗氬鏈夋洿澶氭枃绔,(google) rocks. 1point 3acres 璁哄潧
(goo) (gle) () rocks
goo (( gle )) rocks

都是valid的

google ((rocks ) 不valid

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

另一题忘了,应该是因为也不难所以记不起来

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 第二round也是美国小哥,做machine learning的。因为我resume上面有放ML,自己也说对ML感兴趣,就问了一些ML的问题,像是怎么test your model (答cross validation), 聊了聊他们的ML在做啥,好像还问了一些dimension reduction (PCA) 还是feature selection的问题,聊到这边已经15分钟了还没做题. From 1point 3acres bbs

接下来上题:
一个array,element只有A, B, C三种可能,sort it
非常简单,就用counting sort. more info on 1point3acres.com

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

第三round是美国小妹,做google fit的,是一款记录personal health data的新产品
上来问了两题,第一题也是忘记了 (sorry 过了几个月想不太起来,但也是不难。顶多CC150水準,不及LeetCode). visit 1point3acres.com for more.

另一题比较有趣,问一群朋友去电影院,有一些是情侣有一些不是,一开始都乱坐在同一排座位,要怎么样用minimum swap把情侣排在一起 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
.1point3acres缃
说了一下暴力解是O(n^2),但是当然不会给出暴力解代码,所以继续想
后来说就是counting sort (把input 想成 characters 同一个char就代表这一对是情侣) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
所以一开始的input可能像这样  A B A D E B F.鏈枃鍘熷垱鑷1point3acres璁哄潧
counting sort之后变成 A A B B D E F
他问有没有別的解法,我说那就quicksort,他说他没想过可以用sorting解,所以估计这题应该还有其他方法可以解,不过我说quicksort的时候也快45min了,所以也差不多结束问了些问题. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

大致上感觉运气不错,遇到简单的题,印象中每题也都给了两种解法并且分析time/space complexity
本来感觉良好,后来还是掛了,估计第一面犯了低级错误可能扣了不少分

希望大家都能找到好工作!求大米. 1point 3acres 璁哄潧

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

评分

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.         . 鍥磋鎴戜滑@1point 3 acres
  7.         System.out.println(coupleSort(arr));
  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) {
  24.                         swap(i, int2index.get(arr[i]) + 1, arr);
  25.                     }
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  26.                     else {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  27.                         swap(i, int2index.get(arr[i]) - 1, arr);
  28.                     }
  29.                     
  30.                     numSwaps++;
  31.                     int2index.remove(arr[i]);
  32.                     i--;
  33.                 }
  34.             }
  35.         }
  36.         
  37.         return numSwaps;
  38.     }
  39.    
  40.     public static void swap(int i, int j, int[] arr) {
  41.         int tmp = arr[i];.1point3acres缃
  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)。
. visit 1point3acres.com for more.
请问可以详细讲一下吗?为什么会分index的奇偶讨论呢?谢谢!
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-8-31 04:01:07 | 显示全部楼层
mk01 发表于 2015-2-20 10:30
感觉可能是第三题错了,个人感觉用哈希表可以到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么?
回复 支持 反对

使用道具 举报

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

回复 支持 反对

使用道具 举报

雀巢咖啡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]))
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  5.                                 map.put(chars[i], i);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  6.                         else{
    . From 1point 3acres bbs
  7.                                 char c = chars[i];
  8.                                 int index = map.get(c);
  9.                                 chars[i] = chars[index + 1];
  10.                                 chars[index+1] = c;. more info on 1point3acres.com
  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;.1point3acres缃
对于每个char,如果它之前没有出现过, ...

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

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 06:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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