Two sigma 三轮游

最近貌似爱出新题了，不再是那三套了。呜呜，求下周onsite好运。
第一轮：word search, 给一个target string和一个list string dictionary，求dictionary中的单词，该单词是target string的substring。有可能target string会非常长。
解法：不要insert target string到trie，应该insert dictionary中所有单词。然后遍历target string，注意在search的时候不需要用java

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

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

，geohash找最近的k个巴士站。白板implement dijkstra's。如果一条巴士线有很多站，则需要用到binary search找到离source最近的巴士站点。

debug 冰箱producer and consumer。其实就是让你加锁。我加了mutex，但是面试官觉得不满意。问了各种multi thread概念。

endofunctor 发表于 2017-9-9 12:51
请问楼主第三轮的第二问，除了mutex用了condition variable了吗？

补充内容 (2017-9-9 12:55):

冰箱那道题，记得是2个producer，三个consumer，冰箱里每个item有上限和下限。每个producer和consumer有自己的preference，优先满足preference，不满足条件就对别的item里面操作。

kingcarry 发表于 2017-9-11 07:40
假设字典里的单词平均长度是m，那么trie树的深度也就是m啦，所以根本不可能找一个特别长的substring。你 ...

楼主,你的这个第一题, 你的思路我还是不太明白. 你说的对, 如果target string超机长, 暴力把target string的所有substring都去trie里面寻找,不是优化的解.但是我不知道你怎么避免这个问题. 你帖子给的函数signature是: search(TrieNode node, String targetString, int index), (index是递增的, 从targetString.charAt(index)作为开始，向后面搜). 你的具体思路是? 谢谢!

补充内容 (2017-11-25 12:48):
OK. 我现在知道你的解法了. 谢谢!

同学，
我在准备它家的这个面试。第三轮那个设计google地图，你提到的之前面筋的方法。请问能否提供下连接。我看了大部门面经，没有看到之前详细的方法。
第三轮的第二题应该就是生产者和消费者这样的多线程问题了，应该是用blockqueue和加锁的方法吧？但是这个题目比一般的要复杂。
这里有多个生产者，他们有自己的喜好，而且冰箱分层了。好难呀！他们提供的代码规模有多大呀？看代码、加锁估计时间都很紧吧。谢谢！

很详细，感谢楼主分享，赞赞！！

请问这面经是onsite的面经还是电面面经呢？ 谢谢~

楼主可以分享一下timeline嘛？非常感谢！祝楼主找工一切顺利！

请问楼主第三轮的第二问，除了mutex用了condition variable了吗？

补充内容 (2017-9-9 12:55):
第一轮第一问除了Trie爆搜之外，貌似可以用N-KMP或者AC自动机做，不知道面试官想要哪个。。。

endofunctor 发表于 2017-9-9 12:51
请问楼主第三轮的第二问，除了mutex用了condition variable了吗？

补充内容 (2017-9-9 12:55):

我觉得Trie就够了吧。如果字典里单词平均长度是m，target word长度是n，那么搜索的时间复杂度就是m*n。而不是n方。多线程那道题，记得面试官说推荐用semaphore，具体怎么弄就不记得了。

candudu 发表于 2017-9-9 12:21
楼主可以分享一下timeline嘛？非常感谢！祝楼主找工一切顺利！

上午十点面到中午一点，吃个中饭2点回来，就闪人了。

kingcarry 发表于 2017-9-9 22:24
冰箱那道题，记得是2个producer，三个consumer，冰箱里每个item有上限和下限。每个producer和consumer有 ...

面试很难啊...

楼主店面之后多久有消息的呢？等待中…谢谢楼主！