Google 实习 两轮电面＋一轮加面 面经

Google面经
第一面：
三姐，
第一题：给两个相同的string A和B，然后其中一个在某个位置又新插入了一个char，找出这个char。
O(N)扫一遍就找出来了，思路说了然后码代码。
follow up：如果两个string 都被shffule过呢？直接想用两个map。三姐给hint“非要两个map麽”，好吧然后就优化成用一个map，思路说完就开始码代码。
然后自己没话找话，说follow up之前的原题，如果能给一个没有重复字符的假设的话，可以用二分搜索优化成O(logn),三姐说好啊你写写看。然后码代码。
之后问了一些list 和vector区别之类的问题。

第二面：
国人小哥，
聊简历聊了一会，然后说给一堆简历，算每个简历的top k个高频词。
如果词频统计好，其实就是找数组里top k大的元素。我就说有两种方法，quick select和heap。讲了一下两种方法的思路，问了一下时间复杂度，问了一下堆的实现原理，然后就开始code：让我自己选一种方法实现（选了heap的方法）。
写完小哥就一直在看我代码，卡了很久（所以只做了一道题），说有问题，问为什么iterator我用''->"而不用"."，可能小哥平时Java用的多吧。我说iterator是指针要用指针操作符，小哥说感觉还是不对...然后扯了半天，终于move on，说在一百万份简历中想找和当前简历最相似的一份，问怎么做。我说统计高频词，然后比较。小哥说如果名字，邮箱这样词频很低，但能让两份简历相关性提高很多的词怎么办。（我

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

src="static/image/smiley/QQ/em34.gif" smilieid="112" border="0" alt="" />


补充内容 (2016-2-14 07:13):
已match，祝大家都有好的offer！
update一下timeline：
1/6/2016 一面二面
1/22/2016 三面
1/27/2016 进pool
2/11/2016 Match成功

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

lz Find identical subtree

假如已经是2个string的话，用KMP比较的话， 不好不是应该是O(n), 为啥是O(n^2)?

Hash function的输入是什么？ 如果二叉树有变化的（insert或者delettion）的话，怎么update hashcode呢？

谢谢

加面好难

顶~楼主好棒，也是过五关斩六将，leetcode刷了好多的选手啊，赞

恭喜~~~稳稳的match！

LZ Find identical subtree 这个题没弄明白意思==NAIVE的方法为啥是O(N^3)？为什么最后用hashing做？

tong-1324 发表于 2016-2-5 05:53
恭喜~~~稳稳的match！

谢谢JT~

面无表情 发表于 2016-2-5 02:28
顶~楼主好棒，也是过五关斩六将，leetcode刷了好多的选手啊，赞

谢谢LA的大神

哇！求match。。然后就可以帮忙refer了！！