Google Onsite 跪经

12.12的onsite，圣诞前收到的拒信，惨淡。写的详细点吧，16年面试全悲剧了，攒人品。

第一轮：墨西哥大叔
Find max length of continuous increasing substring
Ex: 1 3 4 5 7 8
Out: 3 (3, 4, 5)
Follow up1: 在多叉树中寻找这样的路径，不一定是root到leaf的。 遍历一下做出来。
Follow up2: 在DAG中寻找这样的路径，遍历一下做出来。

Follow up3: 如何节约时间，用memorization存一下已经遍历过的节点。

Follow up4: 如果内存装不下怎么办。我给的答案是分开计算，合并答案。如果一个机器，可以分段读，然后最后一个节点和下一个段的root合并下答案。如果是分布式，也差不多。


第二轮：白人小哥
class RangeChecker{
    RangeChecker();
    Virtual void Insert(int start, int end) = 0；
    Virtual bool query(int x) = 0；
}
查询一个数字x在不在插入的区间内。
数据结构，实现rangechecker。

1）当insert频率高的时候，直接用array存区间，insert o(1), query遍历一遍区间 o(n)；

<

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

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

数小于n的树都有了，就不需要deepcopy了，存一下子节点就行了。

leetcode上有一道类似的求bst的个数的题。

这次g家没有任何简历问题，上来就做题，有两轮问题都没问下一轮面试官就来了。所以题做的很多。
碰到的都是树和图的题，backtracking和dfs细节要求很高，可能还需要加强基本功吧。
虽然还是跪的有点不甘心，本来以为假期可以好好放松了... naive
anyway move on move on





补充内容 (2017-1-5 11:34):
挂了可能因为第二轮和第四轮没写好吧，可能误解了面试官的意思，我的答案大家可以摒弃...
第一轮和第三轮面试官比较认可

nano 发表于 2017-1-5 17:48
说说第四轮我的一点看法，
要求是所有拓扑结构的组合，ｄｉｓｒｅｇａｒｄ　ｎｏｄｅｓ＇　ｌａｂｅｌｓ， ...

嗯嗯 用dp做的话应该是不会产生重复结构的 普通backtracking也不会有重复的拓扑结构吧，只要不停地把新节点加到左子树或者右子树

您好！
本帖隐藏的内容需要积分高于 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

觉得楼主面的没问题啊，楼主有要feedback吗

jindulys 发表于 2017-1-5 09:44
觉得楼主面的没问题啊，楼主有要feedback吗

recruiter打了电话发了拒信就不理人了

燃烧男 发表于 2017-1-5 09:45
recruiter打了电话发了拒信就不理人了

感谢楼主！请教一下第二个题需要对overlap的ranges进行merge吗？

laiguojiuhao 发表于 2017-1-5 09:58
感谢楼主！请教一下第二个题需要对overlap的ranges进行merge吗？

不需要 问了 假设不重叠

楼主这么牛都挂了。。。好难

谢谢楼主分享，觉得楼主很厉害了，只是这一次运气不好。祝好云！否极泰来！！

挂了可能因为第二轮和第四轮没写好吧，可能误解了面试官的意思，我的答案大家可以摒弃... 第一轮和第三轮面试官比较认可

觉得答得挺好的，做了这么多题实力肯定够了