這是“谷歌面試題解析”系列的又一篇文章。在這一系列文章中，我介紹了谷歌面試當(dāng)中經(jīng)常用到的一些面試題，不過這些面試題已經(jīng)被泄露，并禁止在面試中使用。不過，我的損失就是你的收獲，因?yàn)樗鼈儽恍孤读?#xff0c;我就可以把它們寫下來，供你參考。上篇：

一道泄露并遭禁用的谷歌面試題，背后玄機(jī)全解析

在介紹新的面試題之前，我先宣布一個(gè)令人興奮的消息：我已經(jīng)離開谷歌了！我現(xiàn)在是 Reddit 的工程經(jīng)理！不過，我還是會(huì)繼續(xù)發(fā)表這一系列的文章，請(qǐng)繼續(xù)關(guān)注。

免責(zé)聲明：雖然面試候選人是我的工作職責(zé)之一，但這篇文章僅代表我的個(gè)人觀察、個(gè)人經(jīng)歷和個(gè)人觀點(diǎn)。如果有任何錯(cuò)誤，請(qǐng)不要將它們歸咎于谷歌、Alphabet、Reddit 或任何其他個(gè)人或組織。

問題描述

假設(shè)你在運(yùn)營一個(gè)搜索引擎，在搜索引擎日志中可以看到兩個(gè)搜索關(guān)鍵詞，比如“obama approval ratings（奧巴馬支持率）”和“obama popularity rate（奧巴馬受歡迎程度）”。雖然這兩個(gè)搜索字符串不一樣，但基本上是在搜同一個(gè)東西，在計(jì)算搜索和顯示結(jié)果時(shí)應(yīng)該被認(rèn)為是等價(jià)的。那么我們?cè)撊绾闻袛噙@兩個(gè)搜索詞是不是同義的呢？

我們先將這個(gè)問題泛化。假設(shè)你有兩個(gè)輸入，一個(gè)是字符串對(duì)列表，其中每個(gè)字符串對(duì)是兩個(gè)同義詞。另一個(gè)也是字符串對(duì)列表，其中每個(gè)字符串對(duì)是兩個(gè)搜索關(guān)鍵詞。

下面是輸入示例：

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

你的任務(wù)是輸出一個(gè)布爾值列表，其中每個(gè)布爾值表明相應(yīng)的搜索關(guān)鍵詞對(duì)是不是同義的。

理清問題

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

這種模棱兩可給了優(yōu)秀候選人一個(gè)脫穎而出的機(jī)會(huì)。好的候選人會(huì)先找出這些含糊不清的地方，并試圖解決它們。他們的做法因人而異：有些人會(huì)走到白板前，試圖手動(dòng)解決一些特定的情況，而另一些人一看到問題，就會(huì)立即發(fā)現(xiàn)其中的“陷阱”。無論如何，關(guān)鍵的是要盡早發(fā)現(xiàn)這些問題。

我非?？粗剡@個(gè)“理解問題”階段。我喜歡將軟件工程稱為分形學(xué)科，這意味著它與分形具有相同的特性，通過放大問題來顯示額外的復(fù)雜性。當(dāng)你認(rèn)為你理解了一個(gè)問題，仔細(xì)一看，就會(huì)發(fā)現(xiàn)其實(shí)忽略了一些細(xì)微之處，或者一些可以改進(jìn)的實(shí)現(xiàn)細(xì)節(jié)，或者有其他新的方法可以用來分析這個(gè)問題并揭示出額外的見解。

工程師的能力在很大程度上取決于他們對(duì)問題理解的深度。將一個(gè)模糊的問題陳述轉(zhuǎn)化為一組詳細(xì)的需求是這個(gè)過程的第零步，像這樣故意向候選人提出不明確問題的做法可以幫助面試官評(píng)估候選人應(yīng)對(duì)意外情況的能力。

第 1 部分：簡單的情況

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

解決方案大概是這樣的：將搜索關(guān)鍵詞分解為單詞（按照空格進(jìn)行拆分就可以了），并比較相應(yīng)的單詞對(duì)，看看它們是否相同或者同義。它們看起來像這樣：

實(shí)現(xià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 ? ''' ? 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

很簡單，對(duì)嗎？從算法來看，確實(shí)很簡單。沒有動(dòng)態(tài)規(guī)劃，沒有遞歸，沒有特別的數(shù)據(jù)結(jié)構(gòu)，只要使用標(biāo)準(zhǔn)庫操作和線性時(shí)間算法，對(duì)吧？

你可能會(huì)想，但這里的微妙之處比你第一眼看到的要多。到目前為止，這個(gè)算法最復(fù)雜的部分是同義詞比較。雖然易于理解和描述，但同義詞比較很有可能會(huì)出錯(cuò)。

需要明確的是，在我看來，這些錯(cuò)誤都不能說明候選人是不合格的。如果候選人給出了包含錯(cuò)誤的實(shí)現(xiàn)，我會(huì)直接指出來，他們會(huì)調(diào)整他們的解決方案。但是，面試首先是一場與時(shí)間賽跑的競賽。犯錯(cuò)誤、找出錯(cuò)誤和糾正錯(cuò)誤是意料之中的事，但這樣會(huì)消耗原本可以花在其他地方的時(shí)間，比如提出更優(yōu)的解決方案。很少有候選人不犯錯(cuò)誤，但錯(cuò)誤犯得少的候選人會(huì)取得更大的進(jìn)步，因?yàn)樗麄兓ㄔ诩m錯(cuò)上的時(shí)間更少。

這也是為什么我會(huì)喜歡這個(gè)面試題：在解決騎士撥號(hào)器問題時(shí)，需要算法的靈光一現(xiàn)，然后給出一個(gè)簡單的實(shí)現(xiàn)，而這個(gè)問題需要多個(gè)漸進(jìn)式的小步驟，朝著正確的方向逐漸接近答案。每一步都代表了一個(gè)小障礙，候選人可以優(yōu)雅地跳過，也可能會(huì)被絆倒，然后重新站起來。優(yōu)秀的候選人利用他們的經(jīng)驗(yàn)和直覺來避免這些小陷阱，他們會(huì)得到一個(gè)更加完善和正確的解決方案，而較弱的候選人則會(huì)在錯(cuò)誤上浪費(fèi)時(shí)間和精力，通常會(huì)給出包含錯(cuò)誤的代碼。

每次面試都會(huì)出現(xiàn)上述的狀況，這里列出了我看到的更為常見的一小部分。

?意外運(yùn)行時(shí)殺手

首先，一些候選人通過遍歷同義詞列表來實(shí)現(xiàn)同義詞檢查：

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

從表面上看，這樣似乎是合理的。但仔細(xì)一看，就會(huì)發(fā)現(xiàn)這是一個(gè)非常糟糕的主意。如果你不了解 Python，我可以解釋一下：in 關(guān)鍵字是 contains 方法的語法糖，適用于所有標(biāo)準(zhǔn)的 Python 容器。這里的問題在于，synonym_words 是一個(gè)列表，通過線性搜索來實(shí)現(xiàn) in 關(guān)鍵字。Python 用戶很容易犯這個(gè)錯(cuò)誤，因?yàn)?Python 隱藏了類型，不過 C++ 和 Java 用戶偶爾也會(huì)犯類似的錯(cuò)誤。

在我的整個(gè)職業(yè)生涯中，我只寫過幾次使用線性搜索的代碼，而且每次都只涉及不到 24 個(gè)元素的列表，即使是這樣，我也寫了很長的注釋，讓閱讀代碼的人知道我為什么選擇這種似乎不太理想的方法。我認(rèn)為一些候選人之所以使用它，是因?yàn)樗麄儾惶私?Python 標(biāo)準(zhǔn)庫，不知道在列表上使用 in 關(guān)鍵字是如何實(shí)現(xiàn)的。這是一個(gè)很容易犯的錯(cuò)誤，不過這也不是什么大不了事，只是你選擇了自己不熟悉的語言，對(duì)你不是很有利。

實(shí)際上，這是一個(gè)很容易就可以避免的錯(cuò)誤。首先，永遠(yuǎn)不要忘記對(duì)象的類型，即使你使用的是 Python 這種非類型化的語言！其次，請(qǐng)記住，在列表上使用 in 關(guān)鍵字是一種線性搜索。除非這個(gè)列表非常小，否則它將成為性能殺手。

提醒一下候選人，輸入的數(shù)據(jù)結(jié)構(gòu)是列表，這通常就足以讓他們“醒悟”。好的候選人會(huì)立即想辦法對(duì)同義詞進(jìn)行預(yù)處理，這是一個(gè)好的開始。然而，這種方法并非沒有缺陷……

?使用正確的數(shù)據(jù)結(jié)構(gòu)

從上面的代碼可以看出，為了在線性時(shí)間內(nèi)實(shí)現(xiàn)這個(gè)算法，我們需要一種常量時(shí)間的同義詞查找方法，而常量時(shí)間查找需要用到 hashmap 或 hashset。

我感興趣的不是候選人會(huì)選擇使用哪個(gè)，而是他們會(huì)把什么東西放在里面。大多數(shù)候選人會(huì)選擇某種形式的 dict/hashmap。我看到的最常見的錯(cuò)誤是候選人潛意識(shí)里認(rèn)為每個(gè)單詞最多只能有一個(gè)同義詞:

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

我不會(huì)因?yàn)楹蜻x人犯了這個(gè)錯(cuò)誤而懲罰他們。示例中給出的輸入是為了不讓人想起單詞可以有多個(gè)同義詞，一些候選人根本沒有遇到過這種情況。在我指出這個(gè)錯(cuò)誤之后，他們迅速做出糾正。好的候選人會(huì)及早發(fā)現(xiàn)問題，從而避免麻煩，不過這也不會(huì)浪費(fèi)太多時(shí)間。

一個(gè)稍微嚴(yán)重一點(diǎn)的問題是候選人意識(shí)不到同義詞關(guān)系是雙向的。然而，糾正這一點(diǎn)很容易出錯(cuò)。請(qǐng)看下面這個(gè)糾正方法:

... 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

為什么要執(zhí)行兩次插入并使用雙倍的內(nèi)存？其實(shí)完全可以在不使用額外內(nèi)存的情況下進(jìn)行兩次檢查：

... 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

結(jié)論是：總是問自己是否可以少做點(diǎn)工作！事后看來，排列查找顯然是一種可以節(jié)省時(shí)間的方法，但使用次優(yōu)實(shí)現(xiàn)說明候選人沒有想要尋找優(yōu)化方法。我很樂意給他們提示，但如果不需要我給提示會(huì)更好。

?排序？

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

可惜的是，時(shí)間復(fù)雜度還不夠好：排序同義詞列表需要 Nlog(N) 的時(shí)間復(fù)雜度，然后查找每個(gè)同義詞對(duì)需要 log(N) 的時(shí)間復(fù)雜度，而前面描述的預(yù)處理是線性的，在訪問時(shí)使用了常量時(shí)間。另外，候選人在白板上實(shí)現(xiàn)排序和二分查找在我看來是禁忌，因?yàn)榕判蛩惴ㄒ呀?jīng)是眾所周知的東西，而且這些算法非常難搞對(duì)，通常即使是最優(yōu)秀的候選人也會(huì)犯錯(cuò)誤，而這些錯(cuò)誤并不能告訴我他們的編程能力究竟是怎樣的。

每當(dāng)有候選人提供這樣的解決方案，我就會(huì)問他們運(yùn)行時(shí)間復(fù)雜度，以及是否可以做得更好。順便說一句：如果面試官問你是否可以做得更好，大多數(shù)時(shí)候答案都是“是”。

?最后的解決方案

到了這個(gè)時(shí)候，候選人應(yīng)該已經(jīng)能夠給出最佳的解決方案了。下面是線性時(shí)間和線性空間的算法實(shí)現(xià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

一些注意點(diǎn)：

在使用 dict.get() 時(shí)要注意。你可能是想“檢查 dict 中是否存在某個(gè)鍵，然后獲取它”，但這樣有點(diǎn)混亂，這也表明了你對(duì)標(biāo)準(zhǔn)庫的了解情況。

我個(gè)人并不喜歡在代碼中大量使用 continue，一些編碼指南也建議不要這么做。

第 2 部分：加大難度

遇到優(yōu)秀的候選人，我通常還會(huì)剩下十到十五分鐘時(shí)間。所幸的是，我可以繼續(xù)問很多其他問題，但我們不太可能在這段時(shí)間內(nèi)寫很多代碼。但不管怎樣，我認(rèn)為也沒必要寫太多代碼。我想知道關(guān)于候選人的兩件事是：他們可以設(shè)計(jì)算法嗎？他們可以寫代碼嗎？騎士撥號(hào)器問題需要先回答算法設(shè)計(jì)問題，然后再寫代碼，而這個(gè)問題恰好反過來。

當(dāng)候選人完成這個(gè)問題的第一部分時(shí)，他們實(shí)際上已經(jīng)解決了編碼問題。從這一點(diǎn)上看，我可以自信地認(rèn)為他們有設(shè)計(jì)基本算法并將想法轉(zhuǎn)化為代碼的能力，并且他們對(duì)自己喜歡的編程語言和標(biāo)準(zhǔn)庫也一定的了解。既然編碼方面沒有問題，那么我們就可以深入研究算法了。

為此，讓我們回到第一部分的基本假設(shè)：單詞順序很重要、同義詞關(guān)系不具備傳遞性、不能有多個(gè)同義詞。隨著面試的進(jìn)行，我改變了這些約束條件，我和候選人進(jìn)行了純粹的算法討論。在這里，我將通過代碼示例來說明我的觀點(diǎn)，但在實(shí)際的面試中，我是通過純粹的算法術(shù)語和候選人進(jìn)行討論的。

?傳遞性：初級(jí)方法

我想放寬的第一個(gè)約束是關(guān)于傳遞性的約束，也就是說，如果單詞 A 和 B 是同義的，而且單詞 B 和 C 也是同義的，那么單詞 A 和 C 就是同義的。敏銳的候選人很快就會(huì)意識(shí)到，他們需要調(diào)整之前的解決方案，因?yàn)榧s束的放寬導(dǎo)致之前算法的核心邏輯無效。

那么我們?cè)撛趺醋瞿?#xff1f;一種常見的方法是基于傳遞關(guān)系為每個(gè)單詞維護(hù)一組完整的同義詞。每次在同義詞集合中插入一個(gè)單詞時(shí)，也會(huì)將它添加到集合中所有單詞的同義詞集合中：

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)

這個(gè)方法是有效的，但并不是最好的?？梢钥匆幌逻@個(gè)解決方案的空間復(fù)雜度。每次我們添加同義詞時(shí)，不僅要添加到初始單詞的同義詞集合中，還要添加到這個(gè)單詞所有同義詞的集合中。如果它與一個(gè)單詞同義，我們必須添加一個(gè)條目。如果它與 50 個(gè)單詞同義，我們必須再添加 50 個(gè)條目。如圖所示，它看起來像這樣：

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

還有其他的解決方案，但我們關(guān)注的是空間，所以我不打算深入介紹它們。最有意思的一個(gè)解決方案是使用同義詞數(shù)據(jù)結(jié)構(gòu)來構(gòu)造有向圖，然后使用廣度優(yōu)先搜索來查找兩個(gè)單詞之間是否存在路徑。這是一個(gè)很好的解決方案，但查找時(shí)間復(fù)雜度是線性的。因?yàn)槊看尾樵冃枰M(jìn)行多次查找，所以這個(gè)解決方案不是最優(yōu)的。

?傳遞性：使用并查集

事實(shí)證明，我們可以使用一種稱為并查集的數(shù)據(jù)結(jié)構(gòu)，在（幾乎）恒定的時(shí)間內(nèi)查找同義詞關(guān)系。這種數(shù)據(jù)結(jié)構(gòu)是一種集合，但它提供的功能與大多數(shù)人認(rèn)為的“集合”有些不一樣的地方。

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

這個(gè)算法的過程如下所述。集合通過樹來表示，每個(gè)元素都有一個(gè)父元素。因?yàn)槊靠脴涠加幸粋€(gè)根元素（這個(gè)元素的父元素就是它自己)，所以我們可以通過跟蹤兩個(gè)元素的父元素來確定它們是否屬于同一個(gè)集合。我們找到每個(gè)元素的根元素，如果這兩個(gè)根元素是同一個(gè)元素，說明這兩個(gè)元素屬于相同的集合。合并兩個(gè)集合也很簡單：我們只需要找到根元素，并讓其中一個(gè)成為另一個(gè)的根。

到目前為止，一切都很好，但在性能方面還沒看到有什么特別的地方。這種結(jié)構(gòu)的精妙之處在于可以進(jìn)行壓實(shí)。假設(shè)你有這樣的一棵樹：

假設(shè)你想知道“speedy”和“hurry”是否是同義詞。從每個(gè)節(jié)點(diǎn)開始，遍歷父節(jié)點(diǎn)關(guān)系，發(fā)現(xiàn)它們的根節(jié)點(diǎn)都是“fast”，因此它們是同義詞。再假設(shè)你想知道“speedy”和“swift”是否是同義詞。你將再次從每個(gè)節(jié)點(diǎn)開始，一直向上遍歷，直到到達(dá)“fast”。但這次你可能會(huì)注意到，從“speedy”開始的遍歷重復(fù)了?！澳隳鼙苊庵貜?fù)的遍歷嗎?”

事實(shí)證明，可以避免重復(fù)遍歷。因?yàn)檫@棵樹中的每個(gè)元素都注定要到達(dá)“fast”，所以與其多次遍歷樹，不如直接更改每個(gè)元素的父元素，直到“fast”，這樣可以幫我們省下很多工作。這個(gè)過程被稱為壓實(shí)，在一個(gè)并查集中，它發(fā)生在尋根操作過程中。例如，在我們確定“speedy”和“hurry”是同義詞之后，上面的樹將變成這樣：

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

現(xiàn)在，所有后續(xù)的訪問都將在常量時(shí)間內(nèi)完成，因?yàn)闃渲械拿總€(gè)節(jié)點(diǎn)都指向“fast”。分析這個(gè)結(jié)構(gòu)的時(shí)間復(fù)雜度并不容易：它不是常數(shù)，因?yàn)樗Q于樹的深度，但也不會(huì)比常數(shù)差太多，我們姑且認(rèn)為是常數(shù)時(shí)間。

下面是并查集的實(shí)現(xiàn)，它為我們提供了解決這個(gè)問題所需的功能：

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)

通過使用這種結(jié)構(gòu)，我們可以預(yù)處理同義詞，并在線性時(shí)間內(nèi)解決這個(gè)問題。

評(píng)估和說明

到了這個(gè)時(shí)候，我們已經(jīng)達(dá)到了 40 到 45 分鐘的面試極限。如果候選人能夠完成算法介紹，并在描述（不是實(shí)現(xiàn)）并查集解決方案方面取得重大進(jìn)展，我就會(huì)給他們一個(gè)“Strong Hire”評(píng)級(jí)，然后讓他們問我問題。我從未見過哪位候選人到了這一步還能剩下多少時(shí)間。

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

這個(gè)問題很有用，因?yàn)樗试S候選人犯錯(cuò)誤。軟件工程是一個(gè)永無止境的分析、執(zhí)行和改進(jìn)的循環(huán)過程。這個(gè)問題為候選人提供了在每個(gè)階段展示自己能力的機(jī)會(huì)。如果想要獲得“Strong Hire”的面試評(píng)級(jí)，一個(gè)候選人需要具備如下的能力：

分析一個(gè)問題的陳述，找出模糊和不明確的地方，并在尋找解決方案和遇到新問題的過程中一直保持下去。為了提升效率，請(qǐng)盡可能早地完成這個(gè)階段，因?yàn)樵降胶竺?#xff0c;從糾正錯(cuò)誤的成本就越高。

用一種容易理解和解決的方式描述問題。對(duì)于這個(gè)面試題，最重要的一點(diǎn)是觀察到你可以在查詢中排列相應(yīng)的單詞。

實(shí)現(xiàn)你的解決方案。這涉及選擇最佳的數(shù)據(jù)結(jié)構(gòu)和算法，設(shè)計(jì)出可讀且在將來易于修改的邏輯。

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

當(dāng)問題的定義發(fā)生變化時(shí)，重復(fù)這個(gè)過程，并在適當(dāng)?shù)臅r(shí)候調(diào)整你的解決方案。無論是在面試還是在現(xiàn)實(shí)生活中，知道什么時(shí)候做這兩件事都是一項(xiàng)關(guān)鍵的技能。

隨時(shí)掌握數(shù)據(jù)結(jié)構(gòu)和算法知識(shí)。并查集并不是一種常見的數(shù)據(jù)結(jié)構(gòu)，但也不是那么罕見。確保自己了解各種工具的唯一方法是盡可能多地學(xué)習(xí)。

這些技能都無法從教科書上學(xué)到（除了數(shù)據(jù)結(jié)構(gòu)和算法之外）。獲得這些技能的唯一途徑是通過定期和廣泛的實(shí)踐，而這也正是公司所希望的：候選人不僅能夠掌握技能，而且能夠有效地應(yīng)用它們?？疾爝@些候選人是面試的重點(diǎn)，而這個(gè)面試題在很長一段時(shí)間里幫了我大忙。

期 待

既然我寫了這篇文章，說明這個(gè)問題已經(jīng)被泄露了。從那時(shí)起，我一直在使用其他幾個(gè)問題，具體取決于我的心情（一直問一個(gè)問題很無聊）以及之前的面試官已經(jīng)問了哪些問題。其中一些面試題仍然在使用當(dāng)中，所以我會(huì)保密。你可以期待在未來的文章中看到更多的面試題。

英文原文：

https://medium.com/@alexgolec/google-interview-problems-synonymous-queries-36425145387c

總結(jié)

以上是生活随笔為你收集整理的刷道谷歌泄漏的面试题：面试官想从中考察你什么？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。