TwoSigma 电面新题

这次Two Sigma的电面，因为最近朋友说又面到地里原题，于是又好好复习了一下地里的面经。不得不说还是有帮助的，前几个问题帮我回答到了， 但是Coding Problem却是新出现的题（也可能是我没有遍历所有面经）。
前几个问题，都是地里面经有的陈年老问题：

• 讲自己最chanllenging的project。 我就给他讲了现在工作正在做的事，他很有兴趣又细问了几个问题，花了些时间。
• Process vs Thread， Process 怎么communicate
• Latency vs ThroughPut，他们的变化和相互的影响。（在现实生活中改变一个对另一个并没有一定的影响）
  

接下来就是coding了

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

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

按照这样的做法，initialize需要O（N），UpdateRange O(N), getRandom O(1).  30分钟内要做完coding，自己写test和跑test时间还是比较紧张的。不确定是否是最优解，应该可以再优化，但在big O time上似乎已经没法做到更好了。结束之后问我假如用BST或者hashmap的话会有什么区别， 似乎是还有更好的解。但我分析之后认为不管用什么DS，Initialize和UpdateRange似乎没法做到比O（N）更好。如果地里有想到更好解法的大神，请务必让我知道。


最后说下感受，总的来说感觉2s电面的professionalism还是差了点，尤其是和谷歌比。大多数问题都是问了很多年的原题，可以看出他们的题库也就这么点而且没动力更新。面试官全程基本没什么反馈，我跟他说我的想法他就只会说ok那你写写看，很多时候干脆不说话，估计是在干别的，于是后来楼主也不说话了。写出来了以后，感觉他也无法判断对错，只能通过跑test的结果。有点好笑的是面试结束之后楼主没有关页面，看到他自己留在那个hackarank页面上各种写和跑test。我觉得一个有足够水平的面试官，熟悉问题、肉眼判断解法对错是基本的吧。


希望能过，同时也求各位看官给点大米，不然做什么都好不方便啊。

居然审核了这么久才出来。。

内容干货满满！感谢楼主！

类似LC380？最后那个确实比较搞，可能面试官还没遇到过这种解法，一时没有消化。

你这个第二个list，要用set，不然就不是O（N)了，所以你后面的方法，调换是行不通的

optimisea 发表于 2019-4-5 10:42
你这个第二个list，要用set，不然就不是O（N)了，所以你后面的方法，调换是行不通的

第二个list仅是记录，不存在lookup操作，所以并不一定要用set。调换只是一个小优化，也不影响BigOTime，做不做都无所谓的。

干货满满！感谢楼主！

谢谢分享！

想问一下为什么不能直接返回Random的值？check一下在不在range里就好了？

第二问的优化，可以参考 蠡口 齐腰林，从O(N) 变成 O(N - removed.size())