為了更瞭解其他人對軟件工程的看法，我開始瘋狂在 YouTube 上追 TechLead 的視頻。在接下來的幾天裡，我為他在 Google 工作時提出的一道面試題想出了各種解決方案。

通過 TechLead 模擬 Google 面試（軟件工程師職位）

TechLead 在 Google 的 100 多次面試中都提出了一個問題，這引起了我對 RxJS 的興趣。本文會討論解決該問題的所有傳統方法。

他問這個問題的真正目的是從應聘者得到下列信息：在編碼之前，他們會問正確的問題嗎？提出的解決方案是否符合項目指南？他甚至指出，是否得到正確的答案一點都不重要，重要的是應聘者的思考方式，以及應聘者是否能夠理解這個問題。

他談到了一些解決方案，包括遞歸方法（受堆棧大小限制）和迭代方法（受內存大小限制）。本文將對這兩個解決方案進行詳細討論。

TechLead 的問題

在 TechLead 的問題中，他要求應聘者在如下網格中，計算出所有顏色相同的最大連續塊的數量。

當看到這個問題時，我的第一反應是，必須做一些 2D 圖像建模才能解決這個問題。聽起來這道題在面試中幾乎不可能回答出來。

但在聽完他的詳細解釋之後，我方知情況並非如此。在這個問題中，我們需要處理的是已經捕獲的數據，而不是解析圖像。

數據建模

在編寫任何代碼之前都需要定義數據模型。對於任何問題，首先要弄清楚我們在處理什麼，並收集業務需求。

在我們案例中，TechLead 為我們定義了許多具體的需求，例如：

彩色方塊或“節點”的概念

數據集中包含 1 萬個節點

節點被組織成行和列，即二維數據

列數和行數可能不同

節點有顏色信息，並具有對“鄰接”這一概念的表示方式

我們還可以從數據中獲得更多信息：

節點不會重疊

節點不會和其自身鄰接

節點不會有重複的鄰接

位於邊角的節點會比其他節點少一個或兩個鄰接

還有一些未知信息，例如：

行數與列數的比

可能的顏色數量

只有一種顏色的可能性

顏色的大致分佈

開發人員的水平越高，其需要問的問題越多。雖然這有所幫助，但如果不能找出未知信息，問題的實際解決還是會存在阻礙。

大部分人並不會想到詢問這些未知信息。在開始研究這個算法之前，我也不知道這些未知信息是什麼。要找到所有的未知信息，需要與業務人員進行反覆的討論才行。

對於 TechLead 的這張照片來說，顏色的分佈似乎是隨機的。他只用了三種顏色，並且沒有提到其他限制，因此我們暫時也做這種假設。另外我們還假設，這些顏色可能是相同的。

為了保證算法的有效性，因此我假設我們使用的是 100x100 的網格，以避免處理1行10000列這樣的極端情況。

在一般情況下，我會在查看數據的最初幾個小時內詢問所有這些問題。這也是 TechLead 真正關心之處。應聘者需要思考，是要從編寫一個隨機解決方案開始，還是要首先找出問題所在。如果提前計劃的話，這些問題將更容易處理。在解決這些問題之後，我們最終只需重寫代碼的一小部分即可。

創建數據模型

我們需要知道數據是如何輸入的，以及我們希望以何種形式來處理這些數據。由於沒有處理數據的系統，因此我們需要自己設計一個可視化的方法。

數據的基本結構如下：

Color

ID

X

Y

需要 ID 的原因在於，我們可能不止一次碰到同一個圖片格。要想防止無限循環的話，就必須標記在這些情況下該圖片格所處的位置。

此外，像這樣的數據通常會分配某些 ID、哈希值或其他值。它是一個唯一的標識符，因此，我們可以通過某種方式來標識特定的節點。如果我們想知道最大的連續塊，就需要知道該塊中有哪些節點。

由於 TechLead 使用網格對數據進標識，我假設我們會得到 X 和 Y 的值。依靠這些屬性，我就能夠生成一些 HTML，並確保生成的內容與他給我們的內容相類似。

這是使用絕對定位來完成的，就像他的例子一樣：

答案：3

這種方法也可以處理更大一些的數據集，如下圖：

答案：18

下面是生成節點的代碼：

我們使用行列信息創建一個一維數組，然後根據這些數據生成節點。

我用的是 colorId 而不是 color 。這樣做有兩個原因，一是隨機化更為簡潔，二是我們通常必須自己查找顏色值。

雖然 TechLead 沒有明確說明，但該題目只用了 3 個顏色值，因此，我將數據集限制為 3 種顏色。我們只需知道它可能有數百種顏色，最終的算法就不需要改變了。

下面是一個更簡單的例子，這是一個 2x2 的節點列表：

數據處理

我們希望知道每個節點的鄰接關係，但僅靠 X 和 Y 的值無法做到。所以，給定 X 和 Y，我們還需要找出如何找出相鄰的 X 和 Y 值。其實很簡單，我們只需在 X 和 Y 上找到 +1 和 -1 的節點即可。

我為此寫了一個函數：

我們用來生成節點的方式，實際上是一種計算相鄰節點 ID 的數學方法。而在這一步中，我將採取一個與之相反的思路，即假設節點將以隨機順序輸入。

我通過再次遍歷所有節點來添加鄰接關係：

這個預處理代碼中，我儘量避免了任何不必要的優化。它不會影響算法的最終性能，只會有助於簡化我們的算法。

接下來，我將 colorId 換成 color 。這對於我們的算法而言其實沒有必要，這一步只是為了更好的可視化。

我們為每組相鄰的 X 和 Y 值調用 getNodeAtLocation 函數，並找到我們的 northId 、 eastId 、 southId 和 westId 。在此步驟中，我們不會對 X 和 Y 的值進行參數傳遞。

獲取基本 ID 之後，再將它們轉換為一個 adjacentIds 數組，這個數組只包含那些具有值的鄰接數組。如此一來，如果我們有邊角的話，就不用擔心檢查這些 ID 是不是為空。它還允許我們對數組進行循環，而無需在算法中手工記錄每個基本 ID。

下面是另一個 2x2 網格的示例，這裡我們使用了一組新的節點，並通過 addAdjacencies 來運行：

優化預處理過程

為了簡化本文的算法，我添加了另一個優化過程。該算法將刪除與當前節點顏色不匹配的相鄰 ID。

重寫 addAdjacencies 函數，如下：

我在添加更多功能的同時簡化了 addAdjacencies 。

通過刪除顏色不匹配的節點，我們的算法可以 100% 確定 adjacentIds 屬性中的任何 ID 都是鄰接的節點。

最後，我刪除了所有不具有相同顏色鄰接的節點，這進一步簡化了我們的算法。這樣，我們就將節點縮減為只有我們關心的那些節點。

錯誤的方式：遞歸

TechLead 指出，我們無法遞歸地執行這個算法，因為我們會遇到堆棧溢出的問題。

雖然在一定程度上，他這麼說是對的，但有幾種方法可以緩解這個問題。我們可以使用迭代或者尾遞歸（tail recursion），但 JavaScript 不再將尾遞歸作為自帶功能。

儘管我們仍然可以用 JavaScript 來寫一個尾遞歸函數，但為使得算法更加簡單，我仍然選擇了創建一個典型的遞歸函數。

在編寫代碼之前，我們需要先找到算法。對於遞歸，使用深度優先搜索是合理的。“不要擔心別人不明白計算機科學術語。”在我向一位同事展示我想出的不同解決方案時，他如此說道。

算法

我們將從一個節點開始，儘可能向下搜索，直到到達一個端點。然後我們將返回並採取下一個分支路徑，直到我們掃描完整個連續塊為止。在此過程中，我們還必須記錄我們搜索過的部分，以及最大的連續塊的長度。

我將函數分成了兩部分。其中一個函數將保存最大列表和先前掃描的 ID，同時至少循環每個節點一次。另一個函數則將從未掃描的根節點開始，進行深度優先遍歷。

代碼如下所示：

下面，我們將逐步進行分析。

• 遞歸函數

getContiguousIds 是遞歸函數，在每個節點調用一次。在該函數每次返回結果時，我們都會得到一個連續節點的更新列表。

這個函數只有一個判斷條件：節點是否已在列表中？如果沒有，則再次調用getContiguousIds 。當該函數返回結果時，我們會獲得一個更新的連續節點列表，該列表會被返回到 reducer ，並用作下一個 adjacentId 的狀態。

每當我們用 concat 將當前節點連接到 contiguousIds 時，都要向 contiguousIds 傳入值。每次進一步遞歸時，我們都要確保在循環執行 adjacentIds 之前，當前節點已經被添加到 contiguousIds 列表中。這可以確保我們不會無限地遞歸。

• 循環

該函數的後半部分也會遍歷每個節點一次。遞歸函數使用 reducer來檢查代碼是否已被掃描。若已被掃描，就繼續循環，直到找到一個沒有循環的節點，或者直到退出循環為止。

如果我們的節點尚未被掃描，則調用 getContiguousIds，並繼續遍歷，直到掃描完成。這是同步的，但可能需要一些時間。

每當函數返回一個 contignousIds 列表，都對照 largestContiguousIds 進行檢查，如果該列表的返回值更大的話，就存儲返回值。

同時，我們將把這些 contiguousIds 添加到我們的 scannedIds 列表中，以標記我們搜索的節點。

• 執行

就算我們有 10000 個項目，這個算法也不會遇到 3 種隨機顏色的堆棧溢出問題。如果我把所有的都改成單一顏色，就可能會遇到堆棧溢出的問題，這是因為我們的遞歸函數經歷了 10000 次的遞歸。

• 順序迭代

由於內存比函數調用的堆棧要大，所以我的下一個想法是在一個循環中完成整個事情。我們將跟蹤節點列表的列表。我們將不斷添加它們，並將它們鏈接在一起，直到退出循環。

這個方法要求在完成循環之前，將所有可能的節點列表保存在內存中。在遞歸示例中，我們只將最大的列表保存在內存中。

另一個想法是，從頂部開始遍歷，並將每個節點循環一次。到在此過程總，我們必須檢查 ID 是否存在於節點列表的列表 contiguousIdsList 中。

如果它不存在於任何 contiguousIds 列表中，我們就將添加該列表和 adjacenIds 。這樣，在循環時，就會有其他的內容鏈接到它。

如果我們的節點在其中一個列表之中，那麼節點就可能也存在於其中相當多的列表中。我們想要把所有這些都鏈接在一起，並從 contiguousIdsList 中刪除未鏈接的那些節點。在我們得到節點列表的列表之後，檢查哪個列表是最大的，這個算法就完成了。

• 執行

與遞歸版本不同的是，當所有 10000 個項目都是相同的顏色時，這個算法能夠完成任務。但該算法的一個缺陷是，它執行得相當慢。在上述代碼的性能評估中，我沒有考慮到循環列表的列表的情況，這顯然對性能有很大的影響。

• 隨機迭代

我想採用遞歸方法背後的思路，並以迭代方式進行應用。這一算法的目標是精確命中每個節點一次，並且只存儲最大的連續塊：

這裡，我們沒有將節點添加到先前掃描的 ID 列表，而是從 remainingNodes 數組中拼接出值來，但是我不建議大家這樣做。

• 分解

我把上述代碼分成 3 個部分，用 if 語句分開。

讓我們從中間部分開始。首先查看 queuedIds 。如果該對象有值，就對隊列中的內容進行循環，看看它們是否存在於 remainingNodes 中。

第三部分的內容取決於第二部分的結果。如果 queuedIds 對象為空，並且 remainingNodesIndex 是 -1 的話，那麼我們就已經完成了這個節點列表，並需要從一個新的根節點開始。新的根節點始終位於索引 0 處，因為我們正在對 remaininigNodes 進行拼接。

現在再來看循環的頂部。我可以使用 while (true) ，但是需要留一個跳出條件，以防止出錯。這在調試時很有用，因為要弄清楚無限循環可能是件痛苦的事情。

之後，我們將拼接節點。我們將節點添加到 contiguousIds 列表中，並將 adjacentIds 添加到隊列中。

• 執行

這一算法幾乎和遞歸版本一樣快。當所有節點都是相同顏色時，它是所有算法中速度最快的。

針對數據的優化

• 對相似的顏色進行分組

由於我們只知道有兩種藍色，所以我們可以將類似顏色的節點分組在一起，用於順序迭代版本。

通過將節點拆分成 3 個更小的數組，我們可以減少內存佔用，以及需要在列表的列表中執行的循環次數。儘管如此，這並不能解決所有顏色都相同的情況下會出現的問題，因此我們並不會使用此方法修改遞歸版本。這也意味著我們可以對操作進行多線程處理，將執行時間縮短近三分之一。

如果我們按順序執行這些命令，只需先運行三個中最大的一個。如果最大值比另外兩個值大，就無需檢查它們。

• 可能存在的最大數據集的大小

我們可以檢查每一次迭代，而不是在特定時間間隔檢查是否有最大的列表。如果最大節點集合的規模大於或等於可用節點的一半（5000 或更高），那麼，很顯然我們已經有了最大的列表。

若使用隨機迭代版本的話，我們可以找到迄今為止最大的列表大小，並查看剩餘的節點數量，如果沒有比最大的節點集合大小還小的數值，那麼就可以說明，我們已經有最大的列表了。

• 使用遞歸

雖然遞歸有其侷限性，但我們仍可以使用它。我們需要做的事情就是檢查剩餘節點的數量。如果它沒有超出堆棧的限制，我們就可以使用更快的遞歸版本。這麼做的風險是很大，但隨著循環的深入，這一方法會縮短執行時間。

• 使用 for 循環

在知道節點最大數量的情況下，我們可以使用 for 循環編寫 reduce 函數。無論何時，與 for 循環相比， Aray.prototype 方法都非常慢。

• 使用尾遞歸

我沒有在本文中討論相關算法，因為我認為尾遞歸需要一篇單獨的文章來闡述。這是一個很大的主題，很多地方都需要解釋。另外，雖然它使用了遞歸結構，但它可能並不會想你所期望的那樣比while循環還快。

RxJS：可維護性與性能

有一些方法可以重寫這些函數，這樣你就可以更輕鬆地理解並維護它們。我想出的主要解決方案是使用 Redux-Observable 風格的 RxJS，但並不使用 Redux。

接下來，我想以常規的方式來編寫代碼，然後使用 RxJS 流式傳輸數據，看看能將算法性能提升多少。

我使用 RxJS 做了 3 個版本的算法，並做了一些修改來加快執行速度。與我之前的文章不同的是，即使增加了行和列，所有的三個版本都會變慢。

我本來可以做很多優化，但要以代碼的可讀性為代價，這不是我想要的。

最終，我終於找到了一個可行的解決方案，該方案目前是最快的，只需一半的執行時間。這已經是總體上最好的改進了。

只有當每個節點都是相同的顏色時，我才能用可觀察到的數據擊敗內存佔用較多的順序迭代。從技術上來講，這一算法也優於遞歸方法，因為在這種情況下，遞歸算法會出現堆棧溢出的問題。

在研究如何使用 RxJS 流數據之後，我意識到該方法對本文來說實在過於複雜了。希望以後會有文章詳細介紹這些代碼示例。

如果希望查看詳細代碼，可以查看如下 GitHub 項目地址：

https://github.com/Sawtaytoes/JavaScript-Performance-Interview-Question

最終統計數據

一般來說，最大的連續塊平均有 30~80 個節點。

下面展示了相關算法的評估數據：

• 隨機顏色

• 一種顏色

無論我進行了多少次測試，每種方法的相對排名位置都保持不變。

當所有節點顏色都相同時，Redux-Observable 併發方法受到了影響，我試過很多方法嘗試提高這個方法的運行速度，但是沒有成功。

遊戲製作

在我的職業程序員生涯中，我曾兩次遇到過這段代碼。其中一次是我在開發獨立遊戲《Pulsen》時使用 Lua 編寫的代碼，代碼長度要小得多。

還有一次是在我繪製一張世界地圖的時候，該地區有一個預定義的節點列表，我對其進行了實時處理。這使得使用者可以通過鍵盤上的方向鍵來移動世界地圖。

我還為具有 X 和 Y 值的未知項列表編寫了一個節點生成器。聽起來是不是很熟悉？我同樣需要使網格位居屏幕中央。不過，要做到這點，在 HTML 中比在遊戲引擎中要更容易實現。儘管如此，將一堆絕對定位的 div 放在中央位置也並不容易。

在這個案例中，實時執行時間並不怎麼很重要，因為我在加載遊戲時就進行了大量的預處理。

我想強調的是，TechLead 的問題可能是你會在職業生涯中遇到的問題，但在典型的 JavaScript 應用程序中，往往不太需要考慮程序的速度。

TechLead 在 Google 使用的是 Java ，我猜他面試的職位都很關心執行速度。他們有可能有一堆工作任務要處理大量的數據，因此像這樣的解決方案可能是必要的。

但是，這個視頻也有可能是關於 HTML 和 CSS 的職位的，誰知道呢！

結語

正如你在最終統計數據中所看到的那樣，讀起來最槽糕的代碼幾乎是最快的，並且還完成了我們所有的要求。

據我自己的經驗，我花了更長的時間來開發非 RxJS 版本的代碼。我認為，這是因為更快的版本需要全面的思考。Redux-Observable 能夠讓你以化整為零的方式進行思考。

這是一道非常有趣的問題。它起初看起來似乎很難，但是將它分解成幾塊之後，問題就迎刃而解了。

【寫在最後】：請大家點贊關注並轉發，先謝謝大家啦，需要資料就私信我吧。

小哥哥小姐姐們私信肉絲兒發送【“資料”】二字，可以獲取到一些整理好的編程資料（java，python，web前端，大數據，人工智能），有視頻還有一些電子書，需要的趕快私信起來。