|
【新智元導讀】最近，一道谷歌面試題火了。這是TechLead在谷歌100多次面試中提到的問題，這引起了本文作者Kevin Ghadyani的極大興趣，并討論了解決該問題的所有傳統(tǒng)方法。 為了更了解其他人對軟件工程的看法，我開始瘋狂在 YouTube 上追 TechLead 的視頻。在接下來的幾天里，我為他在 Google 工作時提出的一道面試題想出了各種解決方案。 通過 TechLead 模擬 Google 面試（軟件工程師職位） TechLead 在 Google 的 100 多次面試中都提出了一個問題，這引起了我對 RxJS 的興趣。本文會討論解決該問題的所有傳統(tǒng)方法。 他問這個問題的真正目的是從應(yīng)聘者得到下列信息：在編碼之前，他們會問正確的問題嗎？提出的解決方案是否符合項目指南？他甚至指出，是否得到正確的答案一點都不重要，重要的是應(yīng)聘者的思考方式，以及應(yīng)聘者是否能夠理解這個問題。 他談到了一些解決方案，包括遞歸方法（受堆棧大小限制）和迭代方法（受內(nèi)存大小限制）。本文將對這兩個解決方案進行詳細討論。 TechLead 的問題在 TechLead 的問題中，他要求應(yīng)聘者在如下網(wǎng)格中，計算出所有顏色相同的最大連續(xù)塊的數(shù)量。 當看到這個問題時，我的第一反應(yīng)是，必須做一些 2D 圖像建模才能解決這個問題。聽起來這道題在面試中幾乎不可能回答出來。 但在聽完他的詳細解釋之后，我方知情況并非如此。在這個問題中，我們需要處理的是已經(jīng)捕獲的數(shù)據(jù)，而不是解析圖像。 數(shù)據(jù)建模在編寫任何代碼之前都需要定義數(shù)據(jù)模型。對于任何問題，首先要弄清楚我們在處理什么，并收集業(yè)務(wù)需求。 在我們案例中，TechLead 為我們定義了許多具體的需求，例如：
我們還可以從數(shù)據(jù)中獲得更多信息：
還有一些未知信息，例如：
開發(fā)人員的水平越高，其需要問的問題越多。雖然這有所幫助，但如果不能找出未知信息，問題的實際解決還是會存在阻礙。 大部分人并不會想到詢問這些未知信息。在開始研究這個算法之前，我也不知道這些未知信息是什么。要找到所有的未知信息，需要與業(yè)務(wù)人員進行反復的討論才行。 對于 TechLead 的這張照片來說，顏色的分布似乎是隨機的。他只用了三種顏色，并且沒有提到其他限制，因此我們暫時也做這種假設(shè)。另外我們還假設(shè)，這些顏色可能是相同的。 為了保證算法的有效性，因此我假設(shè)我們使用的是 100x100 的網(wǎng)格，以避免處理1行10000列這樣的極端情況。 在一般情況下，我會在查看數(shù)據(jù)的最初幾個小時內(nèi)詢問所有這些問題。這也是 TechLead 真正關(guān)心之處。應(yīng)聘者需要思考，是要從編寫一個隨機解決方案開始，還是要首先找出問題所在。如果提前計劃的話，這些問題將更容易處理。在解決這些問題之后，我們最終只需重寫代碼的一小部分即可。 創(chuàng)建數(shù)據(jù)模型我們需要知道數(shù)據(jù)是如何輸入的，以及我們希望以何種形式來處理這些數(shù)據(jù)。由于沒有處理數(shù)據(jù)的系統(tǒng)，因此我們需要自己設(shè)計一個可視化的方法。 數(shù)據(jù)的基本結(jié)構(gòu)如下：
需要 ID 的原因在于，我們可能不止一次碰到同一個圖片格。要想防止無限循環(huán)的話，就必須標記在這些情況下該圖片格所處的位置。 此外，像這樣的數(shù)據(jù)通常會分配某些 ID、哈希值或其他值。它是一個唯一的標識符，因此，我們可以通過某種方式來標識特定的節(jié)點。如果我們想知道最大的連續(xù)塊，就需要知道該塊中有哪些節(jié)點。 由于 TechLead 使用網(wǎng)格對數(shù)據(jù)進標識，我假設(shè)我們會得到 X 和 Y 的值。依靠這些屬性，我就能夠生成一些 HTML，并確保生成的內(nèi)容與他給我們的內(nèi)容相類似。 這是使用絕對定位來完成的，就像他的例子一樣： 答案：3 這種方法也可以處理更大一些的數(shù)據(jù)集，如下圖： 答案：18 我們使用行列信息創(chuàng)建一個一維數(shù)組，然后根據(jù)這些數(shù)據(jù)生成節(jié)點。 我用的是 colorId 而不是 color 。這樣做有兩個原因，一是隨機化更為簡潔，二是我們通常必須自己查找顏色值。 雖然 TechLead 沒有明確說明，但該題目只用了 3 個顏色值，因此，我將數(shù)據(jù)集限制為 3 種顏色。我們只需知道它可能有數(shù)百種顏色，最終的算法就不需要改變了。 數(shù)據(jù)處理我們希望知道每個節(jié)點的鄰接關(guān)系，但僅靠 X 和 Y 的值無法做到。所以，給定 X 和 Y，我們還需要找出如何找出相鄰的 X 和 Y 值。其實很簡單，我們只需在 X 和 Y 上找到 +1 和 -1 的節(jié)點即可。 我們用來生成節(jié)點的方式，實際上是一種計算相鄰節(jié)點 ID 的數(shù)學方法。而在這一步中，我將采取一個與之相反的思路，即假設(shè)節(jié)點將以隨機順序輸入。 這個預處理代碼中，我盡量避免了任何不必要的優(yōu)化。它不會影響算法的最終性能，只會有助于簡化我們的算法。 接下來，我將 colorId 換成 color 。這對于我們的算法而言其實沒有必要，這一步只是為了更好的可視化。 我們?yōu)槊拷M相鄰的 X 和 Y 值調(diào)用 getNodeAtLocation 函數(shù)，并找到我們的 northId 、 eastId 、 southId 和 westId 。在此步驟中，我們不會對 X 和 Y 的值進行參數(shù)傳遞。 獲取基本 ID 之后，再將它們轉(zhuǎn)換為一個 adjacentIds 數(shù)組，這個數(shù)組只包含那些具有值的鄰接數(shù)組。如此一來，如果我們有邊角的話，就不用擔心檢查這些 ID 是不是為空。它還允許我們對數(shù)組進行循環(huán)，而無需在算法中手工記錄每個基本 ID。 優(yōu)化預處理過程為了簡化本文的算法，我添加了另一個優(yōu)化過程。該算法將刪除與當前節(jié)點顏色不匹配的相鄰 ID。 我在添加更多功能的同時簡化了 addAdjacencies 。 通過刪除顏色不匹配的節(jié)點，我們的算法可以 100% 確定 adjacentIds 屬性中的任何 ID 都是鄰接的節(jié)點。 最后，我刪除了所有不具有相同顏色鄰接的節(jié)點，這進一步簡化了我們的算法。這樣，我們就將節(jié)點縮減為只有我們關(guān)心的那些節(jié)點。 錯誤的方式：遞歸 TechLead 指出，我們無法遞歸地執(zhí)行這個算法，因為我們會遇到堆棧溢出的問題。 雖然在一定程度上，他這么說是對的，但有幾種方法可以緩解這個問題。我們可以使用迭代或者尾遞歸（tail recursion），但 JavaScript 不再將尾遞歸作為自帶功能。 盡管我們?nèi)匀豢梢杂?JavaScript 來寫一個尾遞歸函數(shù)，但為使得算法更加簡單，我仍然選擇了創(chuàng)建一個典型的遞歸函數(shù)。 在編寫代碼之前，我們需要先找到算法。對于遞歸，使用深度優(yōu)先搜索是合理的。“不要擔心別人不明白計算機科學術(shù)語。”在我向一位同事展示我想出的不同解決方案時，他如此說道。 算法 我們將從一個節(jié)點開始，盡可能向下搜索，直到到達一個端點。然后我們將返回并采取下一個分支路徑，直到我們掃描完整個連續(xù)塊為止。在此過程中，我們還必須記錄我們搜索過的部分，以及最大的連續(xù)塊的長度。 我將函數(shù)分成了兩部分。其中一個函數(shù)將保存最大列表和先前掃描的 ID，同時至少循環(huán)每個節(jié)點一次。另一個函數(shù)則將從未掃描的根節(jié)點開始，進行深度優(yōu)先遍歷。 下面，我們將逐步進行分析。 遞歸函數(shù) getContiguousIds 是遞歸函數(shù)，在每個節(jié)點調(diào)用一次。在該函數(shù)每次返回結(jié)果時，我們都會得到一個連續(xù)節(jié)點的更新列表。 這個函數(shù)只有一個判斷條件：節(jié)點是否已在列表中？如果沒有，則再次調(diào)用getContiguousIds 。當該函數(shù)返回結(jié)果時，我們會獲得一個更新的連續(xù)節(jié)點列表，該列表會被返回到 reducer ，并用作下一個 adjacentId 的狀態(tài)。 每當我們用 concat 將當前節(jié)點連接到 contiguousIds 時，都要向 contiguousIds 傳入值。每次進一步遞歸時，我們都要確保在循環(huán)執(zhí)行 adjacentIds 之前，當前節(jié)點已經(jīng)被添加到 contiguousIds 列表中。這可以確保我們不會無限地遞歸。 循環(huán) 該函數(shù)的后半部分也會遍歷每個節(jié)點一次。遞歸函數(shù)使用 reducer來檢查代碼是否已被掃描。若已被掃描，就繼續(xù)循環(huán)，直到找到一個沒有循環(huán)的節(jié)點，或者直到退出循環(huán)為止。 如果我們的節(jié)點尚未被掃描，則調(diào)用 getContiguousIds，并繼續(xù)遍歷，直到掃描完成。這是同步的，但可能需要一些時間。 每當函數(shù)返回一個 contignousIds 列表，都對照 largestContiguousIds 進行檢查，如果該列表的返回值更大的話，就存儲返回值。 同時，我們將把這些 contiguousIds 添加到我們的 scannedIds 列表中，以標記我們搜索的節(jié)點。 執(zhí)行 就算我們有 10000 個項目，這個算法也不會遇到 3 種隨機顏色的堆棧溢出問題。如果我把所有的都改成單一顏色，就可能會遇到堆棧溢出的問題，這是因為我們的遞歸函數(shù)經(jīng)歷了 10000 次的遞歸。 順序迭代 由于內(nèi)存比函數(shù)調(diào)用的堆棧要大，所以我的下一個想法是在一個循環(huán)中完成整個事情。我們將跟蹤節(jié)點列表的列表。我們將不斷添加它們，并將它們鏈接在一起，直到退出循環(huán)。 這個方法要求在完成循環(huán)之前，將所有可能的節(jié)點列表保存在內(nèi)存中。在遞歸示例中，我們只將最大的列表保存在內(nèi)存中。另一個想法是，從頂部開始遍歷，并將每個節(jié)點循環(huán)一次。到在此過程總，我們必須檢查 ID 是否存在于節(jié)點列表的列表 contiguousIdsList 中。 如果它不存在于任何 contiguousIds 列表中，我們就將添加該列表和 adjacenIds 。這樣，在循環(huán)時，就會有其他的內(nèi)容鏈接到它。 如果我們的節(jié)點在其中一個列表之中，那么節(jié)點就可能也存在于其中相當多的列表中。我們想要把所有這些都鏈接在一起，并從 contiguousIdsList 中刪除未鏈接的那些節(jié)點。在我們得到節(jié)點列表的列表之后，檢查哪個列表是最大的，這個算法就完成了。 執(zhí)行 與遞歸版本不同的是，當所有 10000 個項目都是相同的顏色時，這個算法能夠完成任務(wù)。但該算法的一個缺陷是，它執(zhí)行得相當慢。在上述代碼的性能評估中，我沒有考慮到循環(huán)列表的列表的情況，這顯然對性能有很大的影響。 隨機迭代 我想采用遞歸方法背后的思路，并以迭代方式進行應(yīng)用。這一算法的目標是精確命中每個節(jié)點一次，并且只存儲最大的連續(xù)塊。這里，我們沒有將節(jié)點添加到先前掃描的 ID 列表，而是從 remainingNodes 數(shù)組中拼接出值來，但是我不建議大家這樣做。 分解 我把上述代碼分成 3 個部分，用 if 語句分開。 讓我們從中間部分開始。首先查看 queuedIds 。如果該對象有值，就對隊列中的內(nèi)容進行循環(huán)，看看它們是否存在于 remainingNodes 中。 第三部分的內(nèi)容取決于第二部分的結(jié)果。如果 queuedIds 對象為空，并且 remainingNodesIndex 是 -1 的話，那么我們就已經(jīng)完成了這個節(jié)點列表，并需要從一個新的根節(jié)點開始。新的根節(jié)點始終位于索引 0 處，因為我們正在對 remaininigNodes 進行拼接。 現(xiàn)在再來看循環(huán)的頂部。我可以使用 while (true) ，但是需要留一個跳出條件，以防止出錯。這在調(diào)試時很有用，因為要弄清楚無限循環(huán)可能是件痛苦的事情。 之后，我們將拼接節(jié)點。我們將節(jié)點添加到 contiguousIds 列表中，并將 adjacentIds 添加到隊列中。 執(zhí)行 這一算法幾乎和遞歸版本一樣快。當所有節(jié)點都是相同顏色時，它是所有算法中速度最快的。 錯誤的方式：遞歸 對相似的顏色進行分組 由于我們只知道有兩種藍色，所以我們可以將類似顏色的節(jié)點分組在一起，用于順序迭代版本。 通過將節(jié)點拆分成 3 個更小的數(shù)組，我們可以減少內(nèi)存占用，以及需要在列表的列表中執(zhí)行的循環(huán)次數(shù)。盡管如此，這并不能解決所有顏色都相同的情況下會出現(xiàn)的問題，因此我們并不會使用此方法修改遞歸版本。這也意味著我們可以對操作進行多線程處理，將執(zhí)行時間縮短近三分之一。 如果我們按順序執(zhí)行這些命令，只需先運行三個中最大的一個。如果最大值比另外兩個值大，就無需檢查它們。 可能存在的最大數(shù)據(jù)集的大小 我們可以檢查每一次迭代，而不是在特定時間間隔檢查是否有最大的列表。如果最大節(jié)點集合的規(guī)模大于或等于可用節(jié)點的一半（5000 或更高），那么，很顯然我們已經(jīng)有了最大的列表。 若使用隨機迭代版本的話，我們可以找到迄今為止最大的列表大小，并查看剩余的節(jié)點數(shù)量，如果沒有比最大的節(jié)點集合大小還小的數(shù)值，那么就可以說明，我們已經(jīng)有最大的列表了。 使用遞歸 雖然遞歸有其局限性，但我們?nèi)钥梢允褂盟?。我們需要做的事情就是檢查剩余節(jié)點的數(shù)量。如果它沒有超出堆棧的限制，我們就可以使用更快的遞歸版本。這么做的風險是很大，但隨著循環(huán)的深入，這一方法會縮短執(zhí)行時間。 使用 for 循環(huán) 在知道節(jié)點最大數(shù)量的情況下，我們可以使用 for 循環(huán)編寫 reduce 函數(shù)。無論何時，與 for 循環(huán)相比， Aray.prototype 方法都非常慢。 使用尾遞歸 我沒有在本文中討論相關(guān)算法，因為我認為尾遞歸需要一篇單獨的文章來闡述。這是一個很大的主題，很多地方都需要解釋。另外，雖然它使用了遞歸結(jié)構(gòu)，但它可能并不會想你所期望的那樣比while循環(huán)還快。 RxJS：可維護性與性能 有一些方法可以重寫這些函數(shù)，這樣你就可以更輕松地理解并維護它們。我想出的主要解決方案是使用 Redux-Observable 風格的 RxJS，但并不使用 Redux。 接下來，我想以常規(guī)的方式來編寫代碼，然后使用 RxJS 流式傳輸數(shù)據(jù)，看看能將算法性能提升多少。 我使用 RxJS 做了 3 個版本的算法，并做了一些修改來加快執(zhí)行速度。與我之前的文章不同的是，即使增加了行和列，所有的三個版本都會變慢。 我本來可以做很多優(yōu)化，但要以代碼的可讀性為代價，這不是我想要的。 最終，我終于找到了一個可行的解決方案，該方案目前是最快的，只需一半的執(zhí)行時間。這已經(jīng)是總體上最好的改進了。 只有當每個節(jié)點都是相同的顏色時，我才能用可觀察到的數(shù)據(jù)擊敗內(nèi)存占用較多的順序迭代。從技術(shù)上來講，這一算法也優(yōu)于遞歸方法，因為在這種情況下，遞歸算法會出現(xiàn)堆棧溢出的問題。 在研究如何使用 RxJS 流數(shù)據(jù)之后，我意識到該方法對本文來說實在過于復雜了。希望以后會有文章詳細介紹這些代碼示例。 如果希望查看詳細代碼，可以查看如下 GitHub 項目地址： https://github.com/Sawtaytoes/JavaScript-Performance-Interview-Question 無論我進行了多少次測試，每種方法的相對排名位置都保持不變。 當所有節(jié)點顏色都相同時，Redux-Observable 并發(fā)方法受到了影響，我試過很多方法嘗試提高這個方法的運行速度，但是沒有成功。 游戲制作 在我的職業(yè)程序員生涯中，我曾兩次遇到過這段代碼。其中一次是我在開發(fā)獨立游戲《Pulsen》時使用 Lua 編寫的代碼，代碼長度要小得多。 還有一次是在我繪制一張世界地圖的時候，該地區(qū)有一個預定義的節(jié)點列表，我對其進行了實時處理。這使得使用者可以通過鍵盤上的方向鍵來移動世界地圖。 我還為具有 X 和 Y 值的未知項列表編寫了一個節(jié)點生成器。聽起來是不是很熟悉？我同樣需要使網(wǎng)格位居屏幕中央。不過，要做到這點，在 HTML 中比在游戲引擎中要更容易實現(xiàn)。盡管如此，將一堆絕對定位的 div 放在中央位置也并不容易。 在這個案例中，實時執(zhí)行時間并不怎么很重要，因為我在加載游戲時就進行了大量的預處理。 我想強調(diào)的是，TechLead 的問題可能是你會在職業(yè)生涯中遇到的問題，但在典型的 JavaScript 應(yīng)用程序中，往往不太需要考慮程序的速度。 TechLead 在 Google 使用的是 Java ，我猜他面試的職位都很關(guān)心執(zhí)行速度。他們有可能有一堆工作任務(wù)要處理大量的數(shù)據(jù)，因此像這樣的解決方案可能是必要的。 但是，這個視頻也有可能是關(guān)于 HTML 和 CSS 的職位的，誰知道呢！ 結(jié)語 正如你在最終統(tǒng)計數(shù)據(jù)中所看到的那樣，讀起來最槽糕的代碼幾乎是最快的，并且還完成了我們所有的要求。 據(jù)我自己的經(jīng)驗，我花了更長的時間來開發(fā)非 RxJS 版本的代碼。我認為，這是因為更快的版本需要全面的思考。Redux-Observable 能夠讓你以化整為零的方式進行思考。 這是一道非常有趣的問題。它起初看起來似乎很難，但是將它分解成幾塊之后，問題就迎刃而解了。 原文鏈接： https://medium./bet-you-cant-solve-this-google-interview-question-4a6e5a4dc8ee |
|
|
