一道yelp电面题

Job Hunting Interview
, , ,
1

一些店铺名 （如cat, hat, bat, rat bar, cat rat bar）。需要提供一个搜索服务，用户输入单词的prefix（如rat bar），返回最匹配的搜索结果的前4个。
如prefix = “ba”，返回bat, rat bar, cat rat bar。

我想的感觉很复杂。就是建trie，每个phrase里的word都要作为prefix insert一遍。然后找最接近的四个，我想的就是node存所有按长度sorted 的相关word。这样做感觉无论是时间还是空间复杂度都太高了。大家有什么好的想法吗？

2 Likes
2

这题感觉不能用trie, 因为trie只适用于前缀查找。这一个题目返回值里面其实还有substring

5 
// 建立 inverted index map

public class SearchService {

    HashMap<String, HashSet<String>> strToSet;
    
    public SearchService(Set<String> dict) {
        this.strToSet = new HashMap<>();
        
        for (String string : dict) {
            // find all combinations of subStrings
            for (int i = 0; i < string.length(); i ++) {
                for (int j = i + 1; j <= string.length(); j ++) {
                    String subString = string.substring(i, j);
                    
                    if (!strToSet.containsKey(subString)) {
                        HashSet<String> set = new HashSet<>(Arrays.asList(string));
                        strToSet.put(subString, set);
                        continue;
                    }
                    
                    strToSet.get(subString).add(string);
                }
            }
        }
    }

    public List<String> search(String str) {
        if (!strToSet.containsKey(str)) {
            return new ArrayList<String>();
        } 
        
        List<String> result = new ArrayList<String>(strToSet.get(str));
        return result.subList(0, Math.min(result.size(), 4));
    }
}

但是这个方法无法返回最匹配的四个，感觉最匹配是要用nlp去写了吧。

6

怎么算最匹配？

7

其实就是word break以后，把每个单词放到 Trie 里对吧。另外 Trie 的 node 做好 reference，是跟哪个店铺名相关的。总体还是Trie的基础上加了点处理。

8

我理解就是长度最短的

9

感觉他是在考察你如何定义“匹配”
长度的话可以直接按长度sort 一下结果

10

我理解最匹配就是找到的这个“ba”在每个string里出现的位置，最小的即为最匹配

11

嗯嗯，我是这么想的

12

这个我觉得就是正解啊，还能怎么优化？倒是代码能写对就很不错了

13

这难道是把所有可能的prefix substring 都放到map里吗

14

对啊 没必要用trie 既然要word break怎么做都是n * n
trie的话对前缀搜索比较好，这个是搜substring

15

这个定义不错 可以

16

这个也不完全是搜substring吧？因为它找的还是word的前缀，只不过一个店铺名可以有好几个word组成

18

这话不能这么说，那个是preprocess，一次性的
搜索的runtime是处理后的每次调用

19

inverted index: https://www.geeksforgeeks.org/inverted-index/

20

我觉得建trie其实还好，比较有疑问的是reference，如果每个node都有一个reference list的话，感觉空间复杂度很高啊。

21

如果只是找prefix的话，就没必要遍历所有substring了

22

嗯，如果只是找prefix的话，就肯定要用trie了

23

如果出现 abad 这种词，也需要返回吗