刷道谷歌泄漏的面試題：面試官想從中考察你什麼？

作者 | Alex Golec

譯者 | 薛命燈

這是“谷歌面試題解析”系列的又一篇文章。在這一系列文章中，我介紹了谷歌面試當中經常用到的一些面試題，不過這些面試題已經被泄露，並禁止在面試中使用。不過，我的損失就是你的收穫，因爲它們被泄露了，我就可以把它們寫下來，供你參考。上篇：

一道泄露並遭禁用的谷歌面試題，背後玄機全解析

問題描述

假設你在運營一個搜索引擎，在搜索引擎日誌中可以看到兩個搜索關鍵詞，比如“obama approval ratings（奧巴馬支持率）”和“obama popularity rate（奧巴馬受歡迎程度）”。雖然這兩個搜索字符串不一樣，但基本上是在搜同一個東西，在計算搜索和顯示結果時應該被認爲是等價的。那麼我們該如何判斷這兩個搜索詞是不是同義的呢？

我們先將這個問題泛化。假設你有兩個輸入，一個是字符串對列表，其中每個字符串對是兩個同義詞。另一個也是字符串對列表，其中每個字符串對是兩個搜索關鍵詞。

下面是輸入示例：

SYNONYMS = [ ('rate', 'ratings'), ('approval', 'popularity'),]QUERIES = [ ('obama approval rate', 'obama popularity ratings'), ('obama approval rates', 'obama popularity ratings'), ('obama approval rate', 'popularity ratings obama')]

你的任務是輸出一個布爾值列表，其中每個布爾值表明相應的搜索關鍵詞對是不是同義的。

理清問題

從表面上看，這是一個很簡單的問題。但是，越是細想，它就越複雜。首先，這個問題的定義不是很明確。單詞可以有多個同義詞嗎？單詞的順序重要嗎？同義詞之間是否具有傳遞性，例如，如果 A 與 B 同義，B 與 C 同義，那麼 A 是否也與 C 同義？同義詞可以跨多個單詞嗎，例如“USA”與“United States of America”同義，還是與“United States”同義？

這種模棱兩可給了優秀候選人一個脫穎而出的機會。好的候選人會先找出這些含糊不清的地方，並試圖解決它們。他們的做法因人而異：有些人會走到白板前，試圖手動解決一些特定的情況，而另一些人一看到問題，就會立即發現其中的“陷阱”。無論如何，關鍵的是要儘早發現這些問題。

我非常看重這個“理解問題”階段。我喜歡將軟件工程稱爲分形學科，這意味着它與分形具有相同的特性，通過放大問題來顯示額外的複雜性。當你認爲你理解了一個問題，仔細一看，就會發現其實忽略了一些細微之處，或者一些可以改進的實現細節，或者有其他新的方法可以用來分析這個問題並揭示出額外的見解。

工程師的能力在很大程度上取決於他們對問題理解的深度。將一個模糊的問題陳述轉化爲一組詳細的需求是這個過程的第零步，像這樣故意向候選人提出不明確問題的做法可以幫助面試官評估候選人應對意外情況的能力。

第 1 部分：簡單的情況

不管候選人是如何進入到這一步的，他們都不可避免地要我回答他們提出的疑問，我總是從最簡單的情況開始：單詞可以有多個同義詞、單詞的順序重要、同義詞不具有傳遞性、同義詞只能從一個單詞映射到另一個。儘管這樣的搜索引擎功能非常有限，但對於一道有趣的面試題來說，已經足夠了。

解決方案大概是這樣的：將搜索關鍵詞分解爲單詞（按照空格進行拆分就可以了），並比較相應的單詞對，看看它們是否相同或者同義。它們看起來像這樣：

實現代碼大概是這樣的：

def synonym_queries(synonym_words, queries): ''' synonym_words: iterable of pairs of strings representing synonymous words queries: iterable of pairs of strings representing queries to be tested for synonymous-ness ''' output = [] for q1, q2 in queries: q1, q2 = q1.split(), q2.split() if len(q1) != len(q2): output.append(False) continue result = True for i in range(len(q1)): w1, w2 = q1[i], q2[i] if w1 == w2: continue elif words_are_synonyms(w1, w2): continue result = False break output.append(result) return output

很簡單，對嗎？從算法來看，確實很簡單。沒有動態規劃，沒有遞歸，沒有特別的數據結構，只要使用標準庫操作和線性時間算法，對吧？

你可能會想，但這裏的微妙之處比你第一眼看到的要多。到目前爲止，這個算法最複雜的部分是同義詞比較。雖然易於理解和描述，但同義詞比較很有可能會出錯。

需要明確的是，在我看來，這些錯誤都不能說明候選人是不合格的。如果候選人給出了包含錯誤的實現，我會直接指出來，他們會調整他們的解決方案。但是，面試首先是一場與時間賽跑的競賽。犯錯誤、找出錯誤和糾正錯誤是意料之中的事，但這樣會消耗原本可以花在其他地方的時間，比如提出更優的解決方案。很少有候選人不犯錯誤，但錯誤犯得少的候選人會取得更大的進步，因爲他們花在糾錯上的時間更少。

這也是爲什麼我會喜歡這個面試題：在解決騎士撥號器問題時，需要算法的靈光一現，然後給出一個簡單的實現，而這個問題需要多個漸進式的小步驟，朝着正確的方向逐漸接近答案。每一步都代表了一個小障礙，候選人可以優雅地跳過，也可能會被絆倒，然後重新站起來。優秀的候選人利用他們的經驗和直覺來避免這些小陷阱，他們會得到一個更加完善和正確的解決方案，而較弱的候選人則會在錯誤上浪費時間和精力，通常會給出包含錯誤的代碼。

每次面試都會出現上述的狀況，這裏列出了我看到的更爲常見的一小部分。

意外運行時殺手

首先，一些候選人通過遍歷同義詞列表來實現同義詞檢查：

...elif (w1, w2) in synonym_words: continue...

從表面上看，這樣似乎是合理的。但仔細一看，就會發現這是一個非常糟糕的主意。如果你不瞭解 Python，我可以解釋一下：in 關鍵字是 contains 方法的語法糖，適用於所有標準的 Python 容器。這裏的問題在於，synonym_words 是一個列表，通過線性搜索來實現 in 關鍵字。Python 用戶很容易犯這個錯誤，因爲 Python 隱藏了類型，不過 C++ 和 Java 用戶偶爾也會犯類似的錯誤。

在我的整個職業生涯中，我只寫過幾次使用線性搜索的代碼，而且每次都只涉及不到 24 個元素的列表，即使是這樣，我也寫了很長的註釋，讓閱讀代碼的人知道我爲什麼選擇這種似乎不太理想的方法。我認爲一些候選人之所以使用它，是因爲他們不太瞭解 Python 標準庫，不知道在列表上使用 in 關鍵字是如何實現的。這是一個很容易犯的錯誤，不過這也不是什麼大不了事，只是你選擇了自己不熟悉的語言，對你不是很有利。

實際上，這是一個很容易就可以避免的錯誤。首先，永遠不要忘記對象的類型，即使你使用的是 Python 這種非類型化的語言！其次，請記住，在列表上使用 in 關鍵字是一種線性搜索。除非這個列表非常小，否則它將成爲性能殺手。

提醒一下候選人，輸入的數據結構是列表，這通常就足以讓他們“醒悟”。好的候選人會立即想辦法對同義詞進行預處理，這是一個好的開始。然而，這種方法並非沒有缺陷……

使用正確的數據結構

從上面的代碼可以看出，爲了在線性時間內實現這個算法，我們需要一種常量時間的同義詞查找方法，而常量時間查找需要用到 hashmap 或 hashset。

我感興趣的不是候選人會選擇使用哪個，而是他們會把什麼東西放在裏面。大多數候選人會選擇某種形式的 dict/hashmap。我看到的最常見的錯誤是候選人潛意識裏認爲每個單詞最多隻能有一個同義詞:

...synonyms = {}for w1, w2 in synonym_words: synonyms[w1] = w2...elif synonyms[w1] == w2: continue

我不會因爲候選人犯了這個錯誤而懲罰他們。示例中給出的輸入是爲了不讓人想起單詞可以有多個同義詞，一些候選人根本沒有遇到過這種情況。在我指出這個錯誤之後，他們迅速做出糾正。好的候選人會及早發現問題，從而避免麻煩，不過這也不會浪費太多時間。

一個稍微嚴重一點的問題是候選人意識不到同義詞關係是雙向的。然而，糾正這一點很容易出錯。請看下面這個糾正方法:

...synonyms = defaultdict(set)for w1, w2 in synonym_words: synonyms[w1].append(w2) synonyms[w2].append(w1)...elif w2 in synonyms.get(w1, tuple()): continue

爲什麼要執行兩次插入並使用雙倍的內存？其實完全可以在不使用額外內存的情況下進行兩次檢查：

...synonyms = defaultdict(set)for w1, w2 in synonym_words: synonyms[w1].append(w2)...elif (w2 in synonyms.get(w1, tuple()) or w1 in synonyms.get(w2, tuple())): continue

結論是：總是問自己是否可以少做點工作！事後看來，排列查找顯然是一種可以節省時間的方法，但使用次優實現說明候選人沒有想要尋找優化方法。我很樂意給他們提示，但如果不需要我給提示會更好。

排序？

一些比較聰明的候選人會考慮對同義詞列表進行排序，然後使用二分查找來確定兩個單詞是否同義。這種方法的主要優點是除了輸入同義詞列表之外不需要任何額外的空間（假設可以修改輸入列表）。

可惜的是，時間複雜度還不夠好：排序同義詞列表需要 Nlog(N) 的時間複雜度，然後查找每個同義詞對需要 log(N) 的時間複雜度，而前面描述的預處理是線性的，在訪問時使用了常量時間。另外，候選人在白板上實現排序和二分查找在我看來是禁忌，因爲排序算法已經是衆所周知的東西，而且這些算法非常難搞對，通常即使是最優秀的候選人也會犯錯誤，而這些錯誤並不能告訴我他們的編程能力究竟是怎樣的。

每當有候選人提供這樣的解決方案，我就會問他們運行時間複雜度，以及是否可以做得更好。順便說一句：如果面試官問你是否可以做得更好，大多數時候答案都是“是”。

最後的解決方案

到了這個時候，候選人應該已經能夠給出最佳的解決方案了。下面是線性時間和線性空間的算法實現：

def synonym_queries(synonym_words, queries): ''' synonym_words: iterable of pairs of strings representing synonymous words queries: iterable of pairs of strings representing queries to be tested for synonymous-ness ''' synonyms = defaultdict(set) for w1, w2 in synonym_words: synonyms[w1].add(w2) output = [] for q1, q2 in queries: q1, q2 = q1.split(), q2.split() if len(q1) != len(q2): output.append(False) continue result = True for i in range(len(q1)): w1, w2 = q1[i], q2[i] if w1 == w2: continue elif ((w1 in synonyms and w2 in synonyms[w1]) or (w2 in synonyms and w1 in synonyms[w2])): continue result = False break output.append(result) return output

一些注意點：

在使用 dict.get() 時要注意。你可能是想“檢查 dict 中是否存在某個鍵，然後獲取它”，但這樣有點混亂，這也表明了你對標準庫的瞭解情況。

我個人並不喜歡在代碼中大量使用 continue，一些編碼指南也建議不要這麼做。

第 2 部分：加大難度

遇到優秀的候選人，我通常還會剩下十到十五分鐘時間。所幸的是，我可以繼續問很多其他問題，但我們不太可能在這段時間內寫很多代碼。但不管怎樣，我認爲也沒必要寫太多代碼。我想知道關於候選人的兩件事是：他們可以設計算法嗎？他們可以寫代碼嗎？騎士撥號器問題需要先回答算法設計問題，然後再寫代碼，而這個問題恰好反過來。

當候選人完成這個問題的第一部分時，他們實際上已經解決了編碼問題。從這一點上看，我可以自信地認爲他們有設計基本算法並將想法轉化爲代碼的能力，並且他們對自己喜歡的編程語言和標準庫也一定的瞭解。既然編碼方面沒有問題，那麼我們就可以深入研究算法了。

爲此，讓我們回到第一部分的基本假設：單詞順序很重要、同義詞關係不具備傳遞性、不能有多個同義詞。隨着面試的進行，我改變了這些約束條件，我和候選人進行了純粹的算法討論。在這裏，我將通過代碼示例來說明我的觀點，但在實際的面試中，我是通過純粹的算法術語和候選人進行討論的。

傳遞性：初級方法

我想放寬的第一個約束是關於傳遞性的約束，也就是說，如果單詞 A 和 B 是同義的，而且單詞 B 和 C 也是同義的，那麼單詞 A 和 C 就是同義的。敏銳的候選人很快就會意識到，他們需要調整之前的解決方案，因爲約束的放寬導致之前算法的核心邏輯無效。

那麼我們該怎麼做呢？一種常見的方法是基於傳遞關係爲每個單詞維護一組完整的同義詞。每次在同義詞集合中插入一個單詞時，也會將它添加到集合中所有單詞的同義詞集合中：

synonyms = defaultdict(set)for w1, w2 in synonym_words: for w in synonyms[w1]: synonyms[w].add(w2) synonyms[w1].add(w2) for w in synonyms[w2]: synonyms[w].add(w1) synonyms[w2].add(w1)

這個方法是有效的，但並不是最好的。可以看一下這個解決方案的空間複雜度。每次我們添加同義詞時，不僅要添加到初始單詞的同義詞集合中，還要添加到這個單詞所有同義詞的集合中。如果它與一個單詞同義，我們必須添加一個條目。如果它與 50 個單詞同義，我們必須再添加 50 個條目。如圖所示，它看起來像這樣：

請注意，我們已經從 3 個鍵和 6 個條目變成了 4 個鍵和 12 個條目。一個包含 50 個同義詞的單詞將需要 50 個鍵和近 2500 個條目。表示一個單詞所需的空間與同義詞數量的大小呈二次方式增長，這非常浪費空間。

還有其他的解決方案，但我們關注的是空間，所以我不打算深入介紹它們。最有意思的一個解決方案是使用同義詞數據結構來構造有向圖，然後使用廣度優先搜索來查找兩個單詞之間是否存在路徑。這是一個很好的解決方案，但查找時間複雜度是線性的。因爲每次查詢需要進行多次查找，所以這個解決方案不是最優的。

傳遞性：使用並查集

事實證明，我們可以使用一種稱爲並查集的數據結構，在（幾乎）恆定的時間內查找同義詞關係。這種數據結構是一種集合，但它提供的功能與大多數人認爲的“集合”有些不一樣的地方。

通常的集合（如 hashset、treeset）是一種容器對象，可以讓你快速地知道一個對象是否存在集合中。而並查集解決了一個非常不一樣的問題：它可以讓你知道兩個對象是否屬於同一集合。更重要的是，它的時間複雜度是 O(a(n))，其中 a(n) 是 Ackerman 函數的逆。除非你上過高級算法課程，否則不知道這個函數也是情有可原的。對於所有合理的輸入，它幾乎都是常數時間。

這個算法的過程如下所述。集合通過樹來表示，每個元素都有一個父元素。因爲每棵樹都有一個根元素（這個元素的父元素就是它自己)，所以我們可以通過跟蹤兩個元素的父元素來確定它們是否屬於同一個集合。我們找到每個元素的根元素，如果這兩個根元素是同一個元素，說明這兩個元素屬於相同的集合。合併兩個集合也很簡單：我們只需要找到根元素，並讓其中一個成爲另一個的根。

到目前爲止，一切都很好，但在性能方面還沒看到有什麼特別的地方。這種結構的精妙之處在於可以進行壓實。假設你有這樣的一棵樹：

假設你想知道“speedy”和“hurry”是否是同義詞。從每個節點開始，遍歷父節點關係，發現它們的根節點都是“fast”，因此它們是同義詞。再假設你想知道“speedy”和“swift”是否是同義詞。你將再次從每個節點開始，一直向上遍歷，直到到達“fast”。但這次你可能會注意到，從“speedy”開始的遍歷重複了。“你能避免重複的遍歷嗎?”

事實證明，可以避免重複遍歷。因爲這棵樹中的每個元素都註定要到達“fast”，所以與其多次遍歷樹，不如直接更改每個元素的父元素，直到“fast”，這樣可以幫我們省下很多工作。這個過程被稱爲壓實，在一個並查集中，它發生在尋根操作過程中。例如，在我們確定“speedy”和“hurry”是同義詞之後，上面的樹將變成這樣：

“speedy”和“fast”路徑上的每個單詞的父元素都被更新了，“hasty”到“fast”之間的路徑也是如此。

現在，所有後續的訪問都將在常量時間內完成，因爲樹中的每個節點都指向“fast”。分析這個結構的時間複雜度並不容易：它不是常數，因爲它取決於樹的深度，但也不會比常數差太多，我們姑且認爲是常數時間。

下面是並查集的實現，它爲我們提供瞭解決這個問題所需的功能：

class DisjointSet(object): def __init__(self): self.parents = {} def get_root(self, w): words_traversed = [] while self.parents[w] != w: words_traversed.append(w) w = self.parents[w] for word in words_traversed: self.parents[word] = w return w def add_synonyms(self, w1, w2): if w1 not in self.parents: self.parents[w1] = w1 if w2 not in self.parents: self.parents[w2] = w2 w1_root = self.get_root(w1) w2_root = self.get_root(w2) if w1_root < w2_root: w1_root, w2_root = w2_root, w1_root self.parents[w2_root] = w1_root def are_synonymous(self, w1, w2): return self.get_root(w1) == self.get_root(w2)

通過使用這種結構，我們可以預處理同義詞，並在線性時間內解決這個問題。

評估和說明

到了這個時候，我們已經達到了 40 到 45 分鐘的面試極限。如果候選人能夠完成算法介紹，並在描述（不是實現）並查集解決方案方面取得重大進展，我就會給他們一個“Strong Hire”評級，然後讓他們問我問題。我從未見過哪位候選人到了這一步還能剩下多少時間。

這個問題還有一些待解決的地方，即單詞順序不重要、同義詞可以跨多個單詞。這些問題的解決方案都頗具挑戰性，也很有趣，我將在後續的文章中討論它們。

這個問題很有用，因爲它允許候選人犯錯誤。軟件工程是一個永無止境的分析、執行和改進的循環過程。這個問題爲候選人提供了在每個階段展示自己能力的機會。如果想要獲得“Strong Hire”的面試評級，一個候選人需要具備如下的能力：

分析一個問題的陳述，找出模糊和不明確的地方，並在尋找解決方案和遇到新問題的過程中一直保持下去。爲了提升效率，請儘可能早地完成這個階段，因爲越到後面，從糾正錯誤的成本就越高。

用一種容易理解和解決的方式描述問題。對於這個面試題，最重要的一點是觀察到你可以在查詢中排列相應的單詞。

實現你的解決方案。這涉及選擇最佳的數據結構和算法，設計出可讀且在將來易於修改的邏輯。

回過頭來嘗試找出錯誤。這些可能是實際的錯誤，比如我忘記在上面插入“continue”語句，或者是性能問題，比如使用了不正確的數據結構。

當問題的定義發生變化時，重複這個過程，並在適當的時候調整你的解決方案。無論是在面試還是在現實生活中，知道什麼時候做這兩件事都是一項關鍵的技能。

隨時掌握數據結構和算法知識。並查集並不是一種常見的數據結構，但也不是那麼罕見。確保自己瞭解各種工具的唯一方法是儘可能多地學習。

這些技能都無法從教科書上學到（除了數據結構和算法之外）。獲得這些技能的唯一途徑是通過定期和廣泛的實踐，而這也正是公司所希望的：候選人不僅能夠掌握技能，而且能夠有效地應用它們。考察這些候選人是面試的重點，而這個面試題在很長一段時間裏幫了我大忙。