脸熟面经 跪了。。

Job Hunting Interview
, , , ,
1

一面跪了。。
先问基本的string match pattern, pattern 里面有’’.’’
然后领扣尔依依, 我用了trie，然后follow up问如果pattern里面有很多’’.’'怎么更efficient，我没答出来然后时间不够了。。

补充内容 (2018-11-3 07:22):
补充一下当时的情景。他说他们在查找用户错误拼写的时候发现大多数人的拼写错误出现在单词结尾，所以搜索的时候把suffix 用 ‘’.’'来代替会很有效，但是阿拉伯语里面suffix是放开头的，这样搜就不efficient了

补充内容 (2018-11-3 07:22):
然后in general如果’’.’'很多的话怎么办

2

可以在children 节点里加上’’.’’

3

没关系继续刷题，楼主不要悲伤

4

请问楼主现在知道怎么优化了吗？ 我感觉我也没有什么头绪。。。

5

没刚面完还沉浸在悲伤中。。我感觉leetcode的discussion里面好像有

6

是不是可以在每个节点存一个后缀和跳过几个连续.的信息 这样就可以可以early terminate 一些case这样?

7

是不是把节点里面的数组长度设成27，其中一个专门用来存 ‘’.’’?

8

我们难道是同一个人面的我昨天也被问了这道题，但是之前没做过Trie，当时很崩溃