Google电面, 求人品

前几天的Google电面, 一位印度口音的小哥, 一上来就问我有什么问题, 我说没问题, 他说那好我们直接上题. 题目如下:

写一个class, 有以下两个函数:
addFilter(String filter), 作用是在一个词库里加入一些单词(filter),
boolean isWordBlacklisted(String word), 作用是判断word跟词库里面的单词有没有match的, match的规则为:

filter可以包含*, *可以match任何0个或多个字符, 例如在词库里面加入以下两个filter:
h*o
fo*d

然后以下word的match结果为:
food -> true
hello ->

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

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

我看手机上没有未接来电啊, 后来又试了下, 手机可以正常接电话, 不知道是不是他打的时候信号不好, 后来他直接发邮件叫我下一轮继续电面, 被加面了. 然后约了二月初的电面. 先来报个面经, 求人品. 不知道加面一般会不会问很难的题.

bigbearlake 发表于 2017-1-18 02:04
可以说一下大概思路吗？

就是建个trie暴力搜的；如果这个词的当前字母不匹配，就检查‘*’在不在：不在返回错，否则用'*'依次替代1～len(rest of word)长度的字母继续搜

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

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

1. class TrieNode(object):
   
2.     def __init__(self):
   
3.         self.kids = {}
   
4.         self.end = False
   
5. 
   
6. 
   
7. def insert(root, word):
   
8.     if root is None:
   
9.         root = TrieNode()
   
10.     cur = root
    
11.     for ch in word:
    
12.         if ch not in cur.kids:
    
13.             cur.kids[ch] = TrieNode()
    
14.         cur = cur.kids[ch]
    
15.     cur.end = True
    
16.     return root
    
17. 
    
18. 
    
19. def isWordBlacklisted(root, word):
    
20.     if not word:
    
21.         return root.end
    
22.     if word[0] not in root.kids:
    
23.         if '*' not in root.kids:
    
24.             return False
    
25.         return any(
    
26.             isWordBlacklisted(root.kids['*'], word[idx:])
    
27.             for idx in range(len(word)+1)
    
28.         )
    
29.     return isWordBlacklisted(root.kids[word[0]], word[1:])
    
30. 
    
31. 
    
32. if __name__ == '__main__':
    
33.     root = TrieNode()
    
34.     root = insert(root, 'fo*de')
    
35.     assert(isWordBlacklisted(root, 'foaide'))
    
36.     root = insert(root, 'h*o')
    
37.     root = insert(root, 'fo*d')
    
38.     assert(isWordBlacklisted(root, 'food'))
    
39.     assert(isWordBlacklisted(root, 'hello'))
    
40.     assert(not isWordBlacklisted(root, 'foo'))
    
41.     assert(isWordBlacklisted(root, 'fod'))
    
42.     assert(isWordBlacklisted(root, 'foood'))
    
43.     assert(isWordBlacklisted(root, 'focfd'))
    

复制代码

这题应该是tire tree做吧

这道题能不能把每个trie node的子节点加一个‘*’的情况，指向node自己，然后dfs?这样follow up的问题应该也可以解决：比如fliter是fo*de, word是fodede，先按fode的顺序匹配，然后匹配不成功返回到‘o’对应的那个node，走‘*’那条路指向自己，走两次，再匹配“de”和“de”，匹配成功这样？不知道我说没说清楚。

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

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

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

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

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

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

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

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

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

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

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

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