一亩三分地论坛

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

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

Google 11/10 onsite MTV

[复制链接] |试试Instant~ |关注本帖
feierqi 发表于 2015-11-20 04:15:30 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 本科 全职@Google - 网上海投 - Onsite |Otherfresh grad应届毕业生

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

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

x
等结果好煎熬啊。recruiter说昨天进hc,但现在还一点信儿都没,发个邮件问也不回,越想越绝望,发个面经缓解一下气氛

本来觉得我面的题不算简单了,结果看最近狗家难题辈出,看来最近不知咋的了,新面的同学们加油啊

第一面:国人哥,find the longestsubstring with at most m distinct characters in a stream that cannot fit intomemory, 用moving window和LRUcache的思路解决
第二面:美国小哥, set(x, y, val), getSum(x,y) in very large table,所以你不能把table存成array的形式,用hashtable也不行,因为求sum的时候没法保证顺序,会loop到一些不需要用的点,所以必须要red-black tree,最后就是twodimensional rb tree解决,做完后问各种怎么解决multithreading,cannot fit into memory, overflow之类的问题
第三面:美国大叔,给两个长方形形找出并求出overlapping的坐标和面积,写出各种testcases,然后各种问如何扩展到很多长方形上,怎么用我写的function来把长方形分成多个长方形之类的
第四面: 美国大叔, 就是给一个无重复的排序数组,给一个rand(),这个function返回随机数在[0, 1)之间,然后让你写一个getRandom,返回一个在数组上下界range里,但是又不在数组里的数,每个这样的数必须被返回的几率相同。

recuiter小哥上周电话说feedback挺好,可进hc,我追问下说三个very good,一个貌似neutral的样子,他说我的case比较promising,但他不能保证肯定通过,我还高兴了一阵儿。。。但现在还没给通知我也感觉有点瞎,说不定他只是安慰我呢= = 看到好多我之后面的都已经过了hc,感觉心好慌,赶紧发个面经压压惊,希望大家给点bless

PS:大家在面试的时候一定要注意简单题,我面的时候第三面是最简单的,code也是基本很快完成了,但是最后的feedback却是最差的,面试官评论貌似是不太能跟上我的思路= =,是说我communication太差了么。。反正大家注意简单题的坑

最后祝大家都拿到好offer



. 1point 3acres 璁哄潧
补充内容 (2015-11-20 04:56):. 1point3acres.com/bbs
刚发完面经10分钟左右,recruiter就打电话来说hc过了,666

补充内容 (2015-12-10 05:09):
不好意思,好久没来了,最近拿offer光顾着玩儿去了,现在上来更新一下,第四题的答案我会post到回帖里,大家看到顶一下就会到最上面了

补充内容 (2015-12-10 05:28):
我写了点答案:第一题的大致思路是在55楼,第四题最优解代码是在52楼,大家可以去参考,如果有不明白的可以再回帖问我,祝大家好运

评分

8

查看全部评分

本帖被以下淘专辑推荐:

 楼主| feierqi 发表于 2015-12-10 05:12:07 | 显示全部楼层
第四题的答案,time complexity lgN的最优解,大家可以拿的去参考:
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  1. package google;

  2. import java.util.HashMap;
  3. import java.util.Map;. From 1point 3acres bbs
  4. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  5. public class Onsite {
  6.         . 1point 3acres 璁哄潧
  7.         public static void main(String[] args){
  8.                 int[] testArray = {1, 6, 8, 11};
  9.                 Map<Integer, Integer> resultMap = new HashMap<Integer, Integer>();
  10.                 int runningTime = 10000000;. visit 1point3acres.com for more.
  11.                 for(int i = 0; i < runningTime; i++){
  12.                         int res = getRandomInMissingRange(testArray);
  13.                         if(!resultMap.containsKey(res)){
  14.                                 resultMap.put(res, 1);
  15.                         }
  16.                         else{
  17.                                 resultMap.put(res, resultMap.get(res) + 1);
  18.                         }
  19.                 }
  20.                 System.out.println("Total running time is " + runningTime);
  21.                 for(int rand : resultMap.keySet()){
  22.                         System.out.println("Missing number " + rand + " occurred frequency is" + resultMap.get(rand) + "/" + runningTime);
  23.                 }
  24.         }-google 1point3acres
  25.        
  26.         public static int getRandomInMissingRange(int[] array){
  27.                 if(array == null || array.length == 0){
  28.                         return 0;
  29.                 }
  30.                 int totalWeight = getWeight(array, array.length - 1);
  31.                 int randWeight = (int) (rand() * totalWeight);
  32.                 int left = 0, right = array.length - 1;. From 1point 3acres bbs
  33.                 int currWeight = 0;
  34.                 while(left <= right){
  35.                         int mid = left + (right - left) / 2;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  36.                         currWeight = getWeight(array, mid);. more info on 1point3acres.com
  37.                         if(currWeight == randWeight){
  38.                                 return array[mid] + 1;
  39.                         }. From 1point 3acres bbs
  40.                         else if(currWeight > randWeight){
  41.                                 right = mid - 1;-google 1point3acres
  42.                         }. visit 1point3acres.com for more.
  43.                         else{
  44.                                 left = mid + 1;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  45.                         }
  46.                 }
  47.                 int diff = randWeight - getWeight(array, left);
  48.                 return array[left] + diff;
  49.         }
  50.        
  51.         private static int getWeight(int[] array, int index){. 鍥磋鎴戜滑@1point 3 acres
  52.                 return array[index] - array[0] - index;. From 1point 3acres bbs
  53.         }
  54.        
  55.         //Note: This is the only random Function you can you in this problem, generate random from [0, 1)
  56.         private static double rand(){. Waral 鍗氬鏈夋洿澶氭枃绔,
  57.                 return Math.random();
  58.         }. more info on 1point3acres.com
  59.        
  60. }
复制代码
回复 支持 3 反对 0

使用道具 举报

 楼主| feierqi 发表于 2015-12-10 05:19:45 | 显示全部楼层
LifeGoesOn 发表于 2015-11-27 09:04
楼主能不能讨论一下:

补充内容 (2015-11-27 09:07):

不好意思,好久没来,回复的晚了。第一题因为是cannot fit into memory,所以要用LRU cache来remove最早见到的character(如果当前substring超过m个characters的时候),然后根据那个character的位置来move window,所以就是要一个doubly linked list还有hash map存char和它的位置,随时update
回复 支持 1 反对 0

使用道具 举报

 楼主| feierqi 发表于 2015-11-20 05:03:51 | 显示全部楼层
shuishuimiao 发表于 2015-11-20 04:33
楼主面的好难啊 能说一说第四面的思路吗

第四题好多解法,我已开始说了个brute force的就是类似missing range然后找random,time是O(range of array element),被嘲讽了,说这题好多解法,我这个最差,最优解是O(lgN)的,据说只有一个人做出来过 = =。后来lz灵机一动竟然想出来了。。。说起来有点麻烦,大致就是用missing number的数目来确定每个range的weight,然后随意一个number,用binary search来确定这个number在哪个range里,然后就可以找出randNum是哪个了,我哪天写个完整版的。。描述能力有限啊 = =
回复 支持 1 反对 0

使用道具 举报

winterOfChicago 发表于 2015-11-20 04:27:28 | 显示全部楼层
请问 lz 第四题怎么做的?
回复 支持 反对

使用道具 举报

shuishuimiao 发表于 2015-11-20 04:33:03 | 显示全部楼层
楼主面的好难啊 能说一说第四面的思路吗
回复 支持 反对

使用道具 举报

doudoujiejie 发表于 2015-11-20 04:43:47 | 显示全部楼层
楼主 想问一下第三题扩展到多个长方形怎么做啊? 祝福楼主拿到大offer
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-20 04:46:56 | 显示全部楼层
请问长方形那题多个长方形overlap  lz是怎么回答的?
回复 支持 反对

使用道具 举报

 楼主| feierqi 发表于 2015-11-20 05:09:35 | 显示全部楼层
doudoujiejie 发表于 2015-11-20 04:43
楼主 想问一下第三题扩展到多个长方形怎么做啊? 祝福楼主拿到大offer

多谢多谢啦先。第三题扩展到多个长方形没让写code,就是讨论,所以不要太过担心,其实就是用写的那个找overlap的function找到所有overlap的坐标,然后求不overlap的面积和就好了,这里就是为何要问如何分割长方形,以便求面积
回复 支持 反对

使用道具 举报

 楼主| feierqi 发表于 2015-11-20 05:16:07 | 显示全部楼层
winterOfChicago 发表于 2015-11-20 04:27
请问 lz 第四题怎么做的?

刚才在另一个回复里大致说了下。我哪天写个完整版的,这题真不太好描述。。
回复 支持 反对

使用道具 举报

 楼主| feierqi 发表于 2015-11-20 05:17:55 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-20 04:46
请问长方形那题多个长方形overlap  lz是怎么回答的?

还是利用自己写的两个长方形overlap的function,找出所有不overlap的edge coordinate就好了,这题主要讨论,不用写code。。所以不用怕的
回复 支持 反对

使用道具 举报

doudoujiejie 发表于 2015-11-20 05:19:00 | 显示全部楼层
feierqi 发表于 2015-11-20 05:09
多谢多谢啦先。第三题扩展到多个长方形没让写code,就是讨论,所以不要太过担心,其实就是用写的那个找ov ...

谢谢楼主回复~~~~
回复 支持 反对

使用道具 举报

杰西Jesse 发表于 2015-11-20 05:20:32 | 显示全部楼层
表示第四题可以这么做么? 一开始直接用random(min,max), 然后看这个数有木有,如果有了就产生random(min,num) 和random(num,max),然后继续递归?
回复 支持 反对

使用道具 举报

 楼主| feierqi 发表于 2015-11-20 05:23:33 | 显示全部楼层
杰西Jesse 发表于 2015-11-20 05:20
表示第四题可以这么做么? 一开始直接用random(min,max), 然后看这个数有木有,如果有了就产生random(min,n ...

额。。感觉你这么做对于每个元素应该不是uniform possibility
回复 支持 反对

使用道具 举报

juslun 发表于 2015-11-20 05:28:46 | 显示全部楼层
求问面完多久hr电话说进hc的?
回复 支持 反对

使用道具 举报

杰西Jesse 发表于 2015-11-20 05:31:55 | 显示全部楼层
feierqi 发表于 2015-11-20 05:23
额。。感觉你这么做对于每个元素应该不是uniform possibility
. visit 1point3acres.com for more.
但是一开始的元素是随机的0.0 所以就算后面的不是,但是每个元素的总的概率是一样的?话说楼主后来写出的复杂度是avg 是lgn么?感觉worst case应该都是O(n)?
回复 支持 反对

使用道具 举报

 楼主| feierqi 发表于 2015-11-20 05:32:57 | 显示全部楼层
juslun 发表于 2015-11-20 05:28
求问面完多久hr电话说进hc的?

我上周二面完,周五打电话说集齐了feedback,周三进hc,不过这个也看情况,看面试官给feedback的速度啦
回复 支持 反对

使用道具 举报

 楼主| feierqi 发表于 2015-11-20 05:33:17 | 显示全部楼层
. Waral 鍗氬鏈夋洿澶氭枃绔,
多谢多谢~
回复 支持 反对

使用道具 举报

juslun 发表于 2015-11-20 05:43:17 | 显示全部楼层
feierqi 发表于 2015-11-20 05:32
我上周二面完,周五打电话说集齐了feedback,周三进hc,不过这个也看情况,看面试官给feedback的速度啦

好的 谢谢啦 :) 恭喜楼主!!
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-20 05:49:06 | 显示全部楼层
feierqi 发表于 2015-11-20 05:17
还是利用自己写的两个长方形overlap的function,找出所有不overlap的edge coordinate就好了,这题主要讨 ...

嗯嗯,谢回复,请问能不能先把所有的面积和加起来,然后再减去overlap的面积这样算呢?还有第一题的多线程需要写代码吗?
回复 支持 反对

使用道具 举报

iihaw 发表于 2015-11-20 06:22:31 | 显示全部楼层
Cong!Cong!Cong!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 03:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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