狗家超短电面

一个叫安德鲁的小哥，搜索组的，上来二话不说直接怼题，题不难感觉运气超好

[hide=150]
1. 热身题 直接用的google doc上的提示语 给一个空格分割的text t="please use this Google doc to doing your interview" 然后给一个list of words = ['please', 'inter

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

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

写完，小哥说我就准备了这一道题，不过我还能想起别的题如果你想做，我乖乖认怂说不了不了一道挺好的，小哥也乐了。小哥做NLP里面的QA系统的，LZ也有点NLP背景然后跟他聊了五分钟，挂掉电话看一共半个小时。
求onsite！！

followup的一些解法，错了请指正。。。。

假设len(text)=m, len(words)=k, 一个word的长度为n
对于以下所有方法，由于允许跨过空格的搜索，所以直接把空格忽略掉即可
方法1：
对每个word在text里进行kmp，复杂度是m+kn (kmp算法的复杂度原本是m，但那主要是由于有一个建表的过程需要O(m)复杂度，然后再搜索需要O(n)复杂度。这题只要建一次表，所以是m+kn)

方法2：
给words做一个trie，然后对于text的每个前缀（即text[0:], text[1:], text[2:], text[3:]等）找trie有没有这个词
复杂度=nk+mn 空间26**n （但是一般词不会出现这么大的空间复杂度的）

方法3：
把text里的每一个substring（即text[0:], text[1:], text[2:], text[3:]….，text[0:-1], text[1: -1], text[2: -1], text[3: -1]…等）存进hashset, 然后在set里搜索words里的每个word是否存在
复杂度m**2+k 空间：m**2

reliveinfire 发表于 2018-11-15 10:46
请问如果用　trie 复杂度怎么分析?

我的想法是 words,每个字长度L, M个, text t 长度N

如果text长度是n的话，对于每一个位置，在trie里搜索需要的最坏时间为失败查找长度，失败查找长度应该是被words里面最长word长度bound住的，那么如果words最长的为L，可以是nL，当然如果你text特别短也可以直接被n bound住了

PhantomFan 发表于 2018-11-28 04:52
那样的话复杂度也是NL？N是text长度，L是word_dict最长词长度。Trie的话如果匹配失败可以提前退出性能会 ...

如果用哈希表的话，我其实不知道时间复杂度有多大，我感觉是O(n). 因为你会把word字符串编码然后变成哈希表的key value. 这样也许查询为O(1). 但是相比于trie 存储空间上去了是肯定的。

请问如果用　trie 复杂度怎么分析?

我的想法是 words,每个字长度L, M个, text t 长度N
复杂度会是　　Ｎ + L*M

这样分析正确吗?

不知道fellowup可不可以用kmp做？

rooooooo1 发表于 2018-11-16 02:07
不知道fellowup可不可以用kmp做？

KMP对于查找一个pattern在一个长text里有帮助(其实不是特意造出来的样例，实际上也不一定比brute force快很多)，但是对于很多pattern，trie可以同时比较所有的pattern。所以看数据规模吧。

想请问下str[i:]应该怎么写呀？谢谢楼主！

跳过空格搜索的复杂度如果不用kmp，似乎和brutal force一样？

楼主你好，有个地方不太理解

补充内容 (2018-11-27 04:27):
一个小的细节是words里面可能有词是另外词的前缀，所以trie的查询应该是返回所有的词而不是找到就return。
这种情况为什么要特别注意呢？我认为用isEndOfWord来查看就可以了。还是说我想的有问题？
谢谢~

补充内容 (2018-11-27 04:33):
还有个地方，就是用trie的话 我们是要对text的每个位置都要searh一遍吧？
比如text是abcd，我们就要在trie里面找abcd,bcd,cd,d,是这样吗?
如果是的话复杂度应该是O(N*L)?

为啥不建个哈希表直接搜索word是否存在哈希表中。

雨雪霏霏 发表于 2018-11-27 04:26
楼主你好，有个地方不太理解

补充内容 (2018-11-27 04:27):

嗯我也觉得是NL，然后我说的那个意思是，search for prefix的接口应该是找全所有存在于trie中的prefix，而不是找到任意一个。