Google 电面两轮

最近三周面的，前两天刚接到电话安排了 onsite，后面的因为 NDA 估计就没法直接贴面经了，争取换个其他形式吧。几个月来窝在地里潜水看了不少面经，也贡献下自己的一份吧，也当攒攒人品~

第一轮电面：

       美国小哥，口音和名字来看应该是个白人 native speaker. 简单问了简历之后就扔出来一道题，LC308. 这题之前我准备过，本来觉得比较合适的是从 1D 的情况然后慢慢过渡到 2D ，从 immutable 过渡到 mutable ，期间你来我往谈笑风生一番。。然而我想多了，小哥直接拍了个 2D mutable 的原题上来，我的内心对这种生硬的开局其实是比较拒绝的。。。。说了

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

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

pointer 的 sliding window， 第一问是找数组中最长的连续子序列，第二问就是 LC340，过渡的比较自然，follow up 是如果输入是 steam of string，内存存不下整个 window 的时候，怎么样还能高效维护当前算法的 window 信息。写完 code 问了下时间复杂度。个人感觉这轮的面试官对题目的设计和准备就合理许多，很顺利就写完了，感谢国人大哥不刁难人~

电话里到底怎么讲BIT才能讲明白啊 太难了

我想了一下要大概能说明问题的Fenwick tree至少要有7个node。我刚刚测了一下画这个图大概花20－30秒（照图抄，如果边想边画可能1分钟吧）。
                        0
                 /      |       \
             1         2         4
                        |         / \
                        3       5   6           
然后分三步讲：
1.先讲父子关系，可以举个例子，比如6的parent是4。
2.然后讲每个node存什么，以及prefix sum怎么算的。可以拿6举个例。
3.然后讲更新叶子结点需要更新哪些非叶结点。定义后继关系，需要拿3，5分别举例子。
到这里Fenwick tree算大致讲完，我刚试了一下，大概5－7分钟吧。但前提是面试官自己是懂的或者不纠缠细节（比如后继为什么是那个bit op)，只是来验证你是不是真懂...碰到不懂还非要问细节的感觉没辙...

当然，直接上来就拍一个2D Fenwick tree的，太不友好了...

xpli521 发表于 2016-8-31 22:04
楼主，你这个解释我没看明白就是说内存里面存不下整个window，不能直接get到window最左边的point ...

假如你当前 window 最左边出现了很多个 'A' ，如 AAAABCD，相对于 A 而言你的窗口向左缩小的过程中，直到删除最后一个 A 之前，其实 window 里面的 number of distinct character 的数量没变化，也不需要存到内存里，所以你只需要记录每个字母在 window 里最靠右的出现位置就行了，你需要维护的信息数量就和字符串的字母表成正比，而不再是 window size，这么解释的话会不会清楚一点 =。=

请问一下，内存存不下整个 window 的时候 该怎么做？？谢谢

zq13667243992 发表于 2016-8-31 06:22
请问一下，内存存不下整个 window 的时候 该怎么做？？谢谢

向右扩张窗口是不受影响的，左面缩减窗口会有影响因为不能像 LC 那样直接找到最左面的 char 然后减去出现次数。所以需要存的信息是相对于 window 里面的每个出现的字母，与位置相关~ 这个 follow up 没有原题难，建议稍微想一下就能想出来了

chestnut9919 发表于 2016-8-31 06:00
电话里到底怎么讲BIT才能讲明白啊 太难了

我也不知道。。我确实尽力了。。

电话第一题直接抛这个，太难了

电话里让你讲BIT，太发指了

mnmunknown 发表于 2016-8-30 15:25
向右扩张窗口是不受影响的，左面缩减窗口会有影响因为不能像 LC 那样直接找到最左面的 char 然后减去出现 ...

楼主，你这个解释我没看明白就是说内存里面存不下整个window，不能直接get到window最左边的pointer然后移动是吧，那你是怎么解决的呢？ “相对于 window 里面的每个出现的字母”是啥意思呢。。