上周刚结束的电⾯，就⼀个⼀个算法题。开始⾯试官迟到了，后来找了 hr 协调之后，等了 15 分钟才上来。上来之后和我说35 分钟之后要他要开会，所以就直奔题⽬了。
题⽬就是设计⼀个输⼊⾃动补全功能，然后什么具体情况都没说，我就各种 assume 了，⽤ trie tree 写了下⾯的算法。写完之后还有 10 分钟左右，就follow up: 字典⽆限⼤怎么设计，怎么优化算法，怎么把这个算法应⽤到实际产品中。
class TrieNode():
def __init__(self):
self.children = {};
self.isWord = False;
class Trie():
def __init__(self):
self.root = TrieNode();
def buildTree(self, dictionary):
for word in dictionary:
self.insert(word);
def insert(self, word):
node = self.root;
for i in range(len(word)):
if word[i] not in node.children:
node.children[word[i]] = TrieNode();
node = node.children[word[i]];
node.isWord = True;
def search(self, word):
node = self.root;
for i in range(len(word)):
if word[i] not in node.children:
return False;
node = node.children[word[i]];
if node.isWord:
return True;
return False;
def getSuggestions_recurrsion(self, word):
node = self.root;
for i in range(len(word)):
if (word[i] not in node.children):
return 0, [];
node = node.children[word[i]];
if len(node.children) == 0:
return -1, [];
def dfs(path, node, wordList):
if node.isWord:
wordList.append(path);
for newCh, newNode in node.children.items():
dfs(path + newCh, newNode, wordList);
wordList = [];
dfs(word, node, wordList);
return 1, wordList;
if __name__ == "__main__":
dictionary = ["hello", "dog", "hell", "cat", "a", "hel", "help", "helps", "helping"]
words = ["hel", "d", "a", "g", "c"]
trie = Trie()
trie.buildTree(dictionary)
# autocompleting the given key using trie structure.
for word in words:
print("----------------- word is %s -------------------" % (word));
ret, words = trie.getSuggestions_recurrsion(word)
if (ret == 1):
for word in words:
print(word);
elif ret == -1:
print("No other strings found with this prefix\n")
elif ret == 0:
print("No string found with this prefix\n")