【面試】簡易實做 AutoComplete - Python

這大概是我有經驗來最神奇的面試經驗了(●▼●;)
面試時間一個小時,基本上就是就一個人寫code,另外一個人一直看著寫code..XD。想當然爾,面試結果想當然是被考官狠狠洗臉了 QAQ

就一個人寫code,另外一個人一直看著寫code

(圖片來源: Heraklion Innovation Map


大概會好一陣忘不了這次面是的考題 AutoComplete 吧…


Ultimate Autocomplete

那天面試官一開始就直接跳過自我介紹,端主菜了上個道 Design and Implement Question 給我 - 實做一個 Ultimate Autocomplete

Ultimate Autocomplete
在最短的時間和空間內以良好的順序輸出預測的單詞列表,在理想情況下,列表的第一個單詞是正確的選擇。



概念陳述

trip


在寫程式碼之前,面試官要求先用文字寫下演算法後再進行實作。 聽到這個題目,第一反應是使用 字典樹(Trie) 實做,先用目前使用者的輸入做為 prefix,進行搜尋找出所有以該詞為字首的單詞,再將取出的結果進行排序。


實作分幾個階段

  1. 將字典中的單字建成字典樹
    1. 從字典取出每個單字變成 char stream
    2. 將 char stream 由根節點往深度方向尋訪,依序建出子樹
      • 根節點為空字元,不應該寫入任何字元
      • 若該節點為單字結尾,該節點應加上標記,並寫入額外資訊,例如:詞頻、詞性…等
    3. 重複步驟 1.1 與 1.2,直到字典中所有單字都建立完畢。

  2. 尋訪字典樹,找出所有符合的清單
    1. 將使用者的輸入做為 prefix,進行搜尋找出目前所在節點
    2. 使用深度優先,尋訪該節點的所有子樹
    3. 回傳尋訪結果 結果包含完整單字(即由根節點到被標記為單字結尾節點的路徑所組成的字串)、詞頻、詞性…等額外資訊。

  3. 將結果進行排序後輸出
    • 排序時,可再加入如歷史資訊等訊息,使預測結果更符合使用者的需求
    • 回傳結果應去除額外資訊



實作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
from collections import defaultdict
class Node:
   def __init__(self):
      ## 簡單起見,額外資訊僅記錄詞頻
      self.childs = defaultdict(Node)
      self.is_word_end = False
      self.frequency = 0

class Trie:
   def __init__(self):
      self.root = Node()

   def insert(self, word, freq):
      word = word.lower()
      
      current = self.root
      for char in word:
         current = current.childs[char]
      
      current.is_word_end = True
      current.frequency = freq

   def complete(self, prefix):
      prefix = prefix.lower()
      
      current = self.root
      for char in prefix:
         current = current.childs.get(char)
         if current == None:
            return  []

      results = self.find(current,list(prefix),[])
      results.sort(key=lambda x: x[1],reverse=True)
      return  [w for w,f in results]

     
   def find(self, node, prefix, results):
      if node.is_word_end:
         results.append(("".join(prefix),node.frequency))
    
      if len(node.childs) <= 0  :
         return results

      for char, next_node in node.childs.items():
         prefix.append(char)
         results = self.find(next_node,prefix,results)
         prefix.pop(-1)

      return results

trip = Trie()
words = [('this',40),  ('that',80),  ('there',70),  ('what',60),  ('where',50),  ('when',11)]

for w,f in words:
   trip.insert(w,f)

prefix = 'whe'
suggest_words = trip.complete(prefix)

print(suggest_words)



感想

果然靜下心來寫,陳述的會比較有條理些… 為啥面試的時候可以卡成那樣 Orz 然後 LeetCode 要乖乖刷阿,這次時間太趕根本來不及準備,LeetCode No. 208 是建 Trie 的阿阿阿阿