求问一道autocomplete的题目

给定了一个dictionary.txt, 里面大概有百万个单词。
Q1:

input:"lun" 
output:"lunch" (lunch 是dict里面的)

我想的是用dict来构造trie,进行prefix search
Q2:

input: "lun me"
output: "lunch menu"

两个词的话先分别prefix match每个词,然后在组合吗?
Q3:

input: "unc"
output: "lunch"

这个真的不会了。。这个给一部分词,然后匹配出来该怎么做?


看面经面试官有提到elasticsearch的原理,求问大家有没有好的解法和思路?谢谢

1 Like

这是什么公司?

quip的一道上机题

这里的partial match是要求substring还是subsequence

如果是substring的话可以考虑 suffix tree

这个一般是说 reverted index吧

是substring。 我查了一下感觉suffix tree可解,此前没接触过。那X老师,第二问

" lun me" -> "lunch menu"

这个该怎么做呢?分词等搜索后再组合?

如果面试官说word break是space,可以这么做
但是2个词合在一起是否要求有意义?如果要求,你这样简单的搜索是不对的

" lun me" -> “lunch menu” 某种意义上是 subsequence match,而且需要把 “lunch menu” 作为一个词保存

要是subsequence match我真的就跪了。。 如果是subsequence match,我把lunch menu作为一个词保存,那该怎么match呢?

这样乱猜要求没有意义,而且应该会加constraints

嗯嗯,有道理。还是要现场和面试官沟通

百万单词,这是系统设计题吧。用elasticsearch吧

估计会问系统设计,但是要求上机敲代码实现出来的