一亩三分地论坛

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

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

Google Phone Interview (发面经求大米)

[复制链接] |试试Instant~ |关注本帖
pdkk2004 发表于 2016-7-15 04:16:29 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 博士 全职@Google - 猎头 - 技术电面 |Pass在职跳槽

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

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

x
Google Kirkland office Phone Screen. 美国小伙,上来就做题。
1. warm up.非常简单,找出unsorted数组中的第一个duplicate number. HashSet 或Map 的解法就行。. From 1point 3acres bbs

2. Validate 一个二维整数矩阵n * n 从top left to bottom right, 是否斜着的每一条line上数字都相等。比如下面的矩阵,就是一个valid矩阵。. from: 1point3acres.com/bbs
1 2 3 4. more info on 1point3acres.com
5 1 2 3
6 5 1 2
7 6 5 1-google 1point3acres
. Waral 鍗氬鏈夋洿澶氭枃绔,
Follow up 1, 如果矩阵很大不能完整读到memory中,但是可以读至少一行怎么办?. 1point 3acres 璁哄潧
Follow up 2, 如果连一整行都读不到memory中怎么办,只能partially的读入一行的一部分怎么办?

3. 给一个blacklist 含有一些整数[0, N) 中,写一个function 返回 [0, N)的随机数,但是不要返回任何包含在blacklist的数,要求uniform distribution, 且尽可能减少call 系统Math.random() 的次数。

感觉google的店面还挺有意思的,不是只考coding,更多的是考problem solving,交流和思维。

评分

2

查看全部评分

本帖被以下淘专辑推荐:

william_gong 发表于 2016-7-15 11:27:48 | 显示全部楼层
您好,请问2的followup2怎么解呢?
还有第三题您是怎么解的呢?
多谢
回复 支持 反对

使用道具 举报

frederickyl 发表于 2016-7-15 11:58:13 | 显示全部楼层
2. 按指定方向比较就行。.鐣欏璁哄潧-涓浜-涓夊垎鍦
follow up1: 分两步,先处理上三角,读入每行后其实就知道第二行是啥了,同理处理下三角。
例如:1 2 3 4, 后面必须是 1 2 3, 1 2, 1...
follow up2: 没想到比较好的方法...

3. 蓄水池抽样
回复 支持 反对

使用道具 举报

 楼主| pdkk2004 发表于 2016-7-15 12:06:46 | 显示全部楼层
2. follow up 2: 逐行算rolling hash, 每往下读一行,rolling hash的计算向右shift一位开始计算,然后比较挨着的两行rolling hash值是否相等。

3. 开个辅助数组,size 为 N - blacklist.size, 然后把不在blacklist的数依次放到辅助数组中,然后每次call 的话 调用一次 Math.random() * (辅助数组的size), 生成的随机数用作辅助数组的index,然后返回对应的值。我面完后在板上其他面经看到同样的题了
回复 支持 反对

使用道具 举报

frederickyl 发表于 2016-7-15 13:34:50 | 显示全部楼层
pdkk2004 发表于 2016-7-15 12:06
2. follow up 2: 逐行算rolling hash, 每往下读一行,rolling hash的计算向右shift一位开始计算,然后比较 ...

不用开辅助数组吧,用蓄水抽样就行,这和fb的random max那道题一样的思路。
回复 支持 反对

使用道具 举报

 楼主| pdkk2004 发表于 2016-7-15 14:00:48 来自手机 | 显示全部楼层
蓄水抽样是可以做。这题主要要求每一次call 尽可能减少使用random function的次数,并且会大量重复调用。从性能考虑,我感觉面试官想用辅助数组的方法。我最开始先说的reservoir sampling, 面试官引导我说用data structure, 所以我觉得应该用辅助数组是他想要的。数组只用初始化一次就行了,所以重复调用就是O(1)
回复 支持 反对

使用道具 举报

mkcing 发表于 2016-7-15 14:21:11 | 显示全部楼层
frederickyl 发表于 2016-7-15 11:58
2. 按指定方向比较就行。.鏈枃鍘熷垱鑷1point3acres璁哄潧
follow up1: 分两步,先处理上三角,读入每行后其实就知道第二行是啥了,同理处 ...

可以解释下蓄水池抽样怎样解决第3题吗?
回复 支持 反对

使用道具 举报

frederickyl 发表于 2016-7-15 14:34:03 | 显示全部楼层
mkcing 发表于 2016-7-15 14:21. From 1point 3acres bbs
可以解释下蓄水池抽样怎样解决第3题吗?

res;
count;

for each element x in A:
if(x not in black list) :
.1point3acres缃  if(count == 0):. 1point3acres.com/bbs
    res = x; count=1;
  else
    count++;
    if(rand() % count + 1 == 1) res = x;
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-15 20:22:18 | 显示全部楼层
第二题为什么读到内存里? 第二题如果特别大, 就存成Map<<row,col>,value>, 然后map reduce..因为这种对比, 每次对比的数据和上次的对比的数据没有依赖关系...所以不比的数据都可以存硬盘
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-15 20:27:30 | 显示全部楼层
第三题的black list:

1) 从[0,n) 随意找一个数
2) sort black list
3) 遍历blacklist, 如果这个数比blacklist的数大, +1
4) 返回这个数.

以上是一个paper....我忘了哪里看的

补充内容 (2016-7-15 21:25):
[0,n-blacklist.size()) sorry...
回复 支持 反对

使用道具 举报

say543 发表于 2016-7-17 13:28:31 | 显示全部楼层

. from: 1point3acres.com/bbs
有点不懂怎么做到uniform distribution 能在说明一下吗?
回复 支持 反对

使用道具 举报

jimmyzzxhlh 发表于 2016-7-20 00:52:09 | 显示全部楼层
第三题可不可以这么做:
1. 开一个大小为N的数组,元素是0..N-1
2. 把所有的blacklist里的数交换到最前面. 1point 3acres 璁哄潧
3. 随机一个index,范围在[blackList.size(), N - 1],取数组里的那个index所对应的数即可
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-20 01:04:34 | 显示全部楼层
jimmyzzxhlh 发表于 2016-7-20 00:52
第三题可不可以这么做:
1. 开一个大小为N的数组,元素是0..N-1
2. 把所有的blacklist里的数交换到最前面 ...

复杂度太高了..
一般随机一个数, 都需要是random access
回复 支持 反对

使用道具 举报

jwwxx 发表于 2016-7-27 07:04:48 | 显示全部楼层
店面45min,楼主做了3题啊,效率好高!
回复 支持 反对

使用道具 举报

lcn 发表于 2016-7-28 03:38:58 | 显示全部楼层
pdkk2004 发表于 2016-7-15 12:06
2. follow up 2: 逐行算rolling hash, 每往下读一行,rolling hash的计算向右shift一位开始计算,然后比较 ...

这题应该可以用binary search和binary search tree。比如N为1~8,black list为{2, 3, 5},这时候剩下的数字是{1, 4, 6, 7 ,8}。随机数生成的是{1, 2, 3, 4, 5},和前述数值之间有个对应关系 rand = x - L(x),其中L(x)是候选数x在black list里面小于(没有等于)它的数的个数。比如候选是6,L(6)=3,因为2, 3和5都小于6,这时候rand = 3。但是这里我们不知道候选数,而是知道rand,这时候我们可以用binary search。比如rand是4,我们猜候选数是6,6-L(6)=3<4,表面6是猜小了,再猜8,那么8 - L(8)=5 > 4,又太大,所以最后候选数是7。
这里对N进行binary search,而L函数需要用binary search tree。复杂度是O(log(N) * log(blacklist.size)),但是随机数生成只需要一次。
回复 支持 反对

使用道具 举报

lcn 发表于 2016-7-28 10:15:40 | 显示全部楼层
pdkk2004 发表于 2016-7-15 12:06
2. follow up 2: 逐行算rolling hash, 每往下读一行,rolling hash的计算向右shift一位开始计算,然后比较 ...

Rolling hash相等没办法保证等于关系呀,还是需要每个字母比较。感觉应该能利用locality性质,每个局部matrix都还是要满足题设性质。
回复 支持 反对

使用道具 举报

 楼主| pdkk2004 发表于 2016-7-28 12:54:09 | 显示全部楼层
lcn 发表于 2016-7-28 10:15
Rolling hash相等没办法保证等于关系呀,还是需要每个字母比较。感觉应该能利用locality性质,每个局部ma ...
.1point3acres缃
是的,hash没办法保证100%正确性。面试官当时mention了可以允许小概率的错误,我也是在他提示下想到用rolling hash的。我感觉面试官本来是想用checksum之类的比较document是否相同的方法的。
回复 支持 反对

使用道具 举报

feifly2009 发表于 2016-7-29 03:40:09 | 显示全部楼层
楼主,请问电面的时候,题目是interviewer口述出来的,还是share给你一份文档?我担心口述的话,会听不懂他说的意思。
回复 支持 反对

使用道具 举报

 楼主| pdkk2004 发表于 2016-7-29 04:00:21 来自手机 | 显示全部楼层
都有,比较复杂的题会给你举个例子写在文档里,然后辅以口头描述。不用太担心的
回复 支持 反对

使用道具 举报

feifly2009 发表于 2016-7-29 04:28:44 | 显示全部楼层
pdkk2004 发表于 2016-7-29 04:00
都有,比较复杂的题会给你举个例子写在文档里,然后辅以口头描述。不用太担心的

谢谢楼主这么快就回复了。
再请问一下,文档是怎么发送给您看的?是用email传过来,还是在线有一个share 文档的地方?
我马上就要电面了,还没怎么准备,有些紧张!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 16:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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