一亩三分地论坛

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

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

GOOGLE面经4月20

[复制链接] |试试Instant~ |关注本帖
mzli1989 发表于 2016-4-23 07:52:09 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 博士 全职@Google - Other - Onsite |Otherfresh grad应届毕业生

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

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

x
回馈地里,一直看面经得了不少帮助,也来造福同学们一发
. Waral 鍗氬鏈夋洿澶氭枃绔,
第一面:阿三姐姐,先是FLYING TICKET leetcode原题
然后给一个unsorted slots with numbers,比如:【3,1,0,2,x,4】,x表示位置为空。每次只能移动数字到空的位置,不能直接两数字互换。让排序这个slots,并且唯一的空在最后,比如【0,1,2,3,4,x】。数字只包含 0到n-2-google 1point3acres

第二面:东欧大叔,leetcode sum query 2d mutable变形。设计一个class,给定2d matrix 的大小M*N,实现update,sum(r1,c1,r2,c2)。 follow up是怎么取舍复杂度,优化算法。再Follow up 是M和N是无穷大怎么办。. Waral 鍗氬鏈夋洿澶氭枃绔,

第三面:research

第四面:国人大叔,一直友好和蔼的交谈,整体感觉最放松的一轮。先是一个warm up问了一个guess number的游戏,用最简单的binary search。. 1point3acres.com/bbs
然后follow up:如果给的是一列单词,A心目中有一个目标单词,让B来猜。每次B猜一个单词,A只会告诉他猜中了几个字母。举个栗子,如果A心中的是APPLE,B猜ANGEL,A告诉B猜中了3个字母 (A,L,E,位置无关)。问B如何猜最聪明。
再follow up:如果A会作弊故意刁难B,B知道A会刁难自己,应该如何猜。

第五面:美国小哥带一个小女生shadow。先是一个word search in matrix,leetcode有类似题,题号忘了。然后 course schedule 也是leetcode原题。

总体感觉题目不算难,重在过程的探讨。但经常在探讨中,对面就突然丢出来一个开放式问题,也是没法防备。谷歌给人的感觉总体是挺重视每个面试者的,从出发前到面试到结束一直都有人在帮助问候。.1point3acres缃

希望对大家有帮助。也求自己有好运吧。




补充内容 (2016-5-4 12:13):
今天5/3才收到hr通知进HC送审了。。感觉google效率不高啊。。求人品求人品!!! 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

补充内容 (2016-5-5 23:30):
5/5接到HR电话通知过HC了,并且大约下周给正式offer。。楼主现在心情十分嗨。。也祝地里小伙伴们都有好人品拿好offer!!

评分

4

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 45
nevets 发表于 2016-4-24 18:17:22 | 显示全部楼层
提供一下自己的思路,请各路大神指教:
. From 1point 3acres bbs
1. LC332, 直接dfs。空位排序那题很有意思。最直接的想法是先把空格移到最后,然后正常排序,但是交换的时候用空格作为临时存储。这样的缺点是没有利用只有0 - (n-2)的条件。可以这样做。看样例:
0 1 2 3 4 5 <-index
3 1 0 2 x 4 <-value
第一步:如果a[i] == i || a[i] == x, continue;如果不是的话,不断递归直到a[a[a[..a[i]]]] == i || x:
a[0] != 0, 所以查看:a[a[i]] = a[3] = 2 != 0, 所以继续:a[a[a[i]]] = a[a[3]] = a[2] = 0 == 0,递归停止。
第二步:如果该位为x,立一个flag。回溯,并且每一步将a[cur] = cur。如果flag为真,a[i] = x:
a[2] = 2,回溯,a[3] = 3,回溯,a[0] = 0,flag为假,结束。
这一步可以看作在找环,然后先把环末尾放到空格,然后把环依次前移入位,最后还原空档。.1point3acres缃
第三步:i++接着走,重复第一步,直到结束。
这样做的复杂度是每个数字最多路过两遍,所以是个线性做法。

第一题就觉得有点要跪 :(

2. Fenwick tree (binary indexed tree,树状数组)或者线段树都可以解,经典题。难点在于followup。一个显而易见的优化是,可以把sum的query cache起来,然后每次update清空cache,这样可以省一些计算。第二要看update和sum的比例,如果update十分少,其实用最基础的那种加加减减的做法最快,毕竟是O(1)的query。假设总query一共M次,update一共p次,那么采用基础做法的复杂度:pnm + N - p,采用树做法:N(lognlogm)。那么基础做法优于树做法得到:p(nm - 1) < N(lognlogm - 1) => p/N < (lognlogm - 1)/(nm - 1)。也就是说,当update的比率小于(lognlogm - 1)/(nm - 1)时直接采用基础做法即可。还有就是利用分块的思想。实际应用中,update可能集中于某一块小区域(hotspot),而一部分区域很少有update(coldspot)。这样的话在hotspot用树,coldspot用基础做法,效果更好。以上3种做法可以结合起来用,具体效果要看benchmark。如果无穷大,也可以进行分块,对于边界特殊处理一下即可。

第二题果然厉害了,都开始不是线性做法了。好慌

3. research跳过。

4. 开放性题目,首先要clarify单词的定义。这里先假定AB手上有同一个dictionary,单词只限于dict上的字符串。二分查找给我们的启发是,尽可能多的排除掉可能性。所以我们可以先预处理出几个单词,这些单词尽可能没有重复的字母并且尽量短(如26个字母表就是一个极端的例子)。然后遍历这个表,记录下每个单词对应的正确字母个数。淘汰掉所有miss的单词所包含的字母,剩下的字母就是potential的了。这时候可以开始dfs可能的字母组合,剪枝条件就是满足所有当前的单词匹配字母信息。

第四题简直是大写的懵逼,还是国人出的难

5. search word经典dfs回溯,course schedule拓扑排序。

第五题还算给了点台阶下。。
回复 支持 2 反对 0

使用道具 举报

menderr 发表于 2016-4-23 08:06:34 | 显示全部楼层
楼主这是new graduate? 祝好运~~
回复 支持 反对

使用道具 举报

 楼主| mzli1989 发表于 2016-4-23 08:09:45 | 显示全部楼层
menderr 发表于 2016-4-23 08:06
楼主这是new graduate? 祝好运~~

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴对的。新毕业**,所以没问什么系统设计。就欧洲大叔那一轮简单地发散讨论了一下怎么解决scalability issue
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-23 08:09:48 | 显示全部楼层
考到lc类似题,祝楼主好运呀
回复 支持 反对

使用道具 举报

Alice0701 发表于 2016-4-23 08:20:48 | 显示全部楼层
这个猜字母的题是先统计每个character的频率吗?楼主能透露下具体思路嘛
回复 支持 反对

使用道具 举报

 楼主| mzli1989 发表于 2016-4-23 08:28:38 | 显示全部楼层
Alice0701 发表于 2016-4-23 08:20
这个猜字母的题是先统计每个character的频率吗?楼主能透露下具体思路嘛

我的方法是先建立Graph,用hashset,每个word是一个key。Graph[word]是一个array,在第i个位置上代表跟word有i个相同字母的单词的个数。然后根据tree search的理论,平均search depth最低的建立树的方法是balanced tree,我们这里要找的就是variance最低的那个word。

我不知道标准答案是什么,但感觉面试官对这方法还挺满意的,一个劲夸,希望不是反话。。。
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-4-23 12:02:02 | 显示全部楼层
research是什么题目呀?
回复 支持 反对

使用道具 举报

 楼主| mzli1989 发表于 2016-4-23 21:06:29 | 显示全部楼层
陈润鹏 发表于 2016-4-23 12:02
research是什么题目呀?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
并不是题目。就聊自己的研究经历和项目背景,就一次presentation w/o ppt,对方随时抛出问题,讨论作答。感觉这轮更看重沟通和对自己项目的了解吧。
回复 支持 反对

使用道具 举报

New613Life 发表于 2016-4-24 01:01:43 | 显示全部楼层
mzli1989 发表于 2016-4-23 08:28
我的方法是先建立Graph,用hashset,每个word是一个key。Graph[word]是一个array,在第i个位置上代表跟wo ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
楼主这题是纯聊思想,还是需要写code?
回复 支持 反对

使用道具 举报

fyh8238865 发表于 2016-4-24 03:01:49 | 显示全部楼层
mzli1989 发表于 2016-4-23 08:28
我的方法是先建立Graph,用hashset,每个word是一个key。Graph[word]是一个array,在第i个位置上代表跟wo ...

楼主能具体称述一下吗?没太看明白...word是指B每次猜的,那个维护的graph里面,array表示的是之前猜的与这个这次B猜的word有多少个字符相同的word的个数吗?
回复 支持 反对

使用道具 举报

yijingzeng 发表于 2016-4-24 03:28:32 | 显示全部楼层
请问楼主在哪里面的?谢谢
回复 支持 反对

使用道具 举报

Effiel 发表于 2016-4-24 07:31:05 | 显示全部楼层
New613Life 发表于 2016-4-24 01:01
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴楼主这题是纯聊思想,还是需要写code?

同问?带code这可是很多呀。
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-4-24 13:27:40 | 显示全部楼层
mzli1989 发表于 2016-4-23 08:28
我的方法是先建立Graph,用hashset,每个word是一个key。Graph[word]是一个array,在第i个位置上代表跟wo ...

楼主相当厉害。
另一种想法:
尽量猜短的词,比如‘a’,如果他算一个此的话。。。
然后从短的词猜长一点的,逐渐增加字母,这种能不能加大概率。。。
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-4-24 13:30:02 | 显示全部楼层
弱弱的问第一题有什么trick吗?是只有一个空荡吗?
是不是就是如果算法用到swap,那写swap时要小心。不过,swap不会改变空荡的位置。所以可以把swap放在helper function里
除了这些是不是就可以用quick sort或者别的什么了
回复 支持 反对

使用道具 举报

在浙里 发表于 2016-4-24 22:43:27 | 显示全部楼层
祝楼主早日拿到offer
回复 支持 反对

使用道具 举报

 楼主| mzli1989 发表于 2016-4-25 00:44:21 | 显示全部楼层
Effiel 发表于 2016-4-24 07:31
同问?带code这可是很多呀。

先讲思路,再写code。分几部分写的,先写一个函数,给两个单词返回int代表他们有几个字母相同。再基于这个函数去写怎么建立graph来做搜索。其实分开写并不会很多,45分钟刚好写得完
回复 支持 反对

使用道具 举报

 楼主| mzli1989 发表于 2016-4-25 00:47:23 | 显示全部楼层
tcomein2009 发表于 2016-4-24 13:27
楼主相当厉害。
另一种想法:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
尽量猜短的词,比如‘a’,如果他算一个此的话。。。

其实当时我跟面试官探讨过。因为即使是每次选取最balance的单词作为子节点,你也不能保证就一定最快猜到答案。比如,你猜一个最不balance的节点,但是get lucky一次就中了呢。所以我猜他想问的就是做tree search怎么能保证最坏情况搜索深度最低。. 鍥磋鎴戜滑@1point 3 acres
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
有时候答案可能很多都对,但咱还是得猜猜面试官想考咱什么点,去凑他的胃口吧。比较把他逗开心比较重要哈哈
回复 支持 反对

使用道具 举报

 楼主| mzli1989 发表于 2016-4-25 00:54:55 | 显示全部楼层
tcomein2009 发表于 2016-4-24 13:30
弱弱的问第一题有什么trick吗?是只有一个空荡吗?
是不是就是如果算法用到swap,那写swap时要小心。不过 ...

我一开始的算法就是写一个swap,然后用一个指针从0开始,去让每个数字跟他本身属于的位置做swap。每当i位置上的数字本身就是i,或者是空,我们就i+1.复杂度是O(n)因为每个数字最多只用swap一次。. more info on 1point3acres.com
之后发觉做swap会额外多操作一次,比如swap(i,j),我们实际上是先把i移到空,j移到i,i再从空移到j。但实际上我们只需要把相应位置原本占有者移到空位,再把目标数字移到他应在的位置,同时记录现在的空位变化到哪里了。这样就可以节省操作。实际上也是O(n)的复杂度,但肯定操作的数量是更少的。
其实还有更好的解法,回来挺同学说貌似可以用recursive的方法做,但是当时紧张之下没想到。还好面试官貌似买账了,也没提如何继续做优化,就直接拍照片了。
回复 支持 反对

使用道具 举报

 楼主| mzli1989 发表于 2016-4-25 00:58:46 | 显示全部楼层
nevets 发表于 2016-4-24 18:17
提供一下自己的思路,请各路大神指教:

1. LC332, 直接dfs。空位排序那题很有意思。最直接的想法是先把 ...

感谢分享思路!!
大牛同学们也来多讨论下,不吝赐教
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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