狗家intern conversion interview onsite 挂经

七月底在Kirkland的onsite，因为是Intern conversion interview所以只有两轮
1. 人非常好的白人小哥哥。一上来会让我讲讲实习做了什么，听得非常有耐心也很肯定我的实习工作。coding: 设计一个数据结构，constructor传一个参数int k，add(int x) 添加一个整数，get() 返回最近添加的k个数的乘积。这个其实是lc出现过的题，谷歌的高频面经。关键是处理好0的情况，一个做法是用类似sliding window的方法维持最近k个数的乘积（把0替换成1），同时记录最近一次0出现的index，用来判断call get()的时候会不会被0影响

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

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

该不错（虽然没具体问过），proj也做的可以，面试第一轮聊得非常好，第二轮虽然不好但是一开始以为只是followup应该问题不大，因为有同学说自己面试两轮都差但是还是过了HC，就更加难理解了。。有可能是阿三黑了我或者自己proj做的并不好。。。anyway just move on

祝大家好运。

我觉得第二题的follow up是可以O(n)做的吧？再开一个数组维护dp[i]的prefix_sum, 更新dp[i]的时候只需要check dp[i-1] 以及dp[i - k2] ~ dp[i - k1]直接有没有可以到达的点，可以用prefix_sum O(1)时间复杂度判断。

aliwithtaozi 发表于 2019-9-11 15:21
我coversion也没过 没事 楼主加油再面别的
组里给我写的feedback都特别好 大组里还有个hc的人 当时做projec ...

一开始很伤心，后来就释怀了，你也加油！

Candela 发表于 2019-9-11 16:18
我觉得第二题的follow up是可以O(n)做的吧？再开一个数组维护dp的prefix_sum, 更新dp的时候只需要check dp  ...

是的，其实还不用存所有的presum, 只要维持一个window就好了，就是我帖子里说的那样。不过当时脑袋有点糊，dp[]一开始是boolean value, 没有想到这么改

楼主加油 我conversion被加面了 我怀疑是因为现在招得少了，所以过hc难度变大了

eeveewyc 发表于 2019-9-11 11:02
楼主加油 我conversion被加面了 我怀疑是因为现在招得少了，所以过hc难度变大了

祝你好运！

第二题 我也遇到了  面试官叫我用dp 和 dfs + memo 实现
怎么避免k1~ k2 的循环复杂度？

个人感觉一般这种题都可用binarysearch来优化。这里我想到了一个O(nlgn)的方法：
例如，有一个array为[0,1,0,0,1,0,0,0,1,0,1], 把对应值为1的index取下生成一个新的array，是[1,4,8,10]。
因为这是一个sorted的array， 我们可以从第一个元素开始用bs搜索青蛙可以从这里跳到的范围，然后再可以调到的范围里，依次搜索迭代下去。。
=======================
这道题leetcode有不少类似的，例如frog jump，split array max sum之类的

zezed 发表于 2019-9-11 14:49
个人感觉一般这种题都可用binarysearch来优化。这里我想到了一个O(nlgn)的方法：
例如，有一个array为[0,1 ...

虽然搜到左右端点的时间为O(lgn)，但是范围内的数需要遍历一遍才能继续bfs啊，这还是有个O(k)复杂度。
并且bfs每一层的“范围”可能还有重叠，所以每个点不止访问一次，最差复杂度是O(n k log(n))吧。。
如理解不正确，求代码解释

我coversion也没过 没事 楼主加油再面别的
组里给我写的feedback都特别好 大组里还有个hc的人 当时做project还给了我一个peer bonus 这都没用 还被加试了
感觉就是今年招人少了 bar提高了

补充内容 (2019-9-11 15:23):
最后挂在一道tricky question上：random二叉树找局部最小，时间必须是log n。最后想出答案的我哭笑不得，我一个做视觉的，考这个有什么用？

5290 发表于 2019-9-11 15:21
虽然搜到左右端点的时间为O(lgn)，但是范围内的数需要遍历一遍才能继续bfs啊，这还是有个O(k)复杂度。
...

这样讲吧，如果你对每一个元素都做binarysearch，就能找到每一个元素可以跳到的范围了吧。所以worst是O(nlgn)。（注意：这里是用bs找到比当前值加k1大的最小的数，以及比当前值加k2小的最大的数）
===========
OK，我明白你的意思了，即使有重叠，但我们每一个元素的bs只做一次，过去做过，在遇到的时候，自然不用做啊。