狗家电面

刚刚面完狗家，back to back的电面。
第一轮的面试官比较和善，问的问题也没有太刁难，利口吴柳奇。让我介绍了项目，大概10分钟，然后开始coding。我没有用滑窗去解，h

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

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

等。转专业刷Leetcode的楼主表示很受伤，被问得一丝不挂，非科班鉴定完毕。
面试完基本是喜忧参半

这个问题很tricky啊，这个叫StreamObserver是因为流很大没有办法在内存存完全部的流吗？
初步思路是对字典倒序建Trie, 然后在内存中用LinkedList来作为队列缓存Stream的一部分，队列的最大size为字典中最大单词的长度，类中再定义一个叫matched的hashSet，每次put的时候向队列末尾push这个char, 队列容量超限后pop第一个char,用Trie做一个后缀搜索，找到的单词加到matched里面去,将matched作为ArrayList返回即可。这样put的复杂就是O(size),还算可以接受且不违背内存限制。

解释一下第二道题，有点类似于Trie，但好像又不是。比方说我有一个字符串，让你判断字符串里是否存在关键词。但是这里的字符串变成了单个连续输入的字符。例如我连续输入‘a’,'b','b','c','a',我的字符串组里面有bbc，当我输入c的时候就返回bbc。字符串匹配的问题，就是形式让我比较捉鸡。

楼组第二题和这里面的第四题一样吗？ http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=303144&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311

唔 第二题没有看太懂，能否麻烦楼主详细解释一下题目的意思？谢谢了。

马克一下 谢谢楼主！

johnsysu 发表于 2017-12-7 22:19
解释一下第二道题，有点类似于Trie，但好像又不是。比方说我有一个字符串，让你判断字符串里是否存在关键词 ...

那就建立suffix tree吧

hychin 发表于 2017-12-7 22:43
那就建立suffix tree吧

貌似不需要你直接把input cache起来 查的时候按照逆序去trie里面查就ok

trie建立的时候也是正逆序都建一个

感谢楼主分享！