為了更了解其他人對軟件工程的看法，我開始瘋狂在 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

下面是生成節點的代碼：

1constgenerateNodes=({ 2numberOfColumns, 3numberOfRows, 4})=>( 5Array( 6numberOfColumns 7*numberOfRows 8) 9.fill()10.map((11item,12index,13)=>({14colorId:(15Math16.floor(17Math.random()*318)19),20id:index,21x:index%numberOfColumns,22y:Math.floor(index/numberOfColumns),23}))24)

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

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

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

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

1[2{colorId:2,id:0,x:0,y:0},3{colorId:1,id:1,x:1,y:0},4{colorId:0,id:2,x:0,y:1},5{colorId:1,id:3,x:1,y:1},6]

數據處理

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

我為此寫了一個函數：

1constgetNodeAtLocation=({ 2nodes, 3x:requiredX, 4y:requiredY, 5})=>( 6( 7nodes 8.find(({ 9x,10y,11})=>(12x===requiredX13&&y===requiredY14))15||{}16)17.id18)

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

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

1constaddAdjacencies=( 2nodes, 3)=>( 4nodes 5.map(({ 6colorId, 7id, 8x, 9y,10})=>({11color:colors[colorId],12eastId:(13getNodeAtLocation({14nodes,15x:x+1,16y,17})18),19id,20northId:(21getNodeAtLocation({22nodes,23x,24y:y-1,25})26),27southId:(28getNodeAtLocation({29nodes,30x,31y:y+1,32})33),34westId:(35getNodeAtLocation({36nodes,37x:x-1,38y,39})40),41}))42.map(({43color,44id,45eastId,46northId,47southId,48westId,49})=>({50adjacentIds:(51[52eastId,53northId,54southId,55westId,56]57.filter((58adjacentId,59)=>(60adjacentId!==undefined61))62),63color,64id,65}))66)

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

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

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

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

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

1[2{adjacentIds:[1,2],color:'red',id:0},3{adjacentIds:[3,0],color:'grey',id:1},4{adjacentIds:[3,0],color:'blue',id:2},5{adjacentIds:[1,2],color:'blue',id:3},6]

優化預處理過程

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

重寫 addAdjacencies 函數，如下：

1constaddAdjacencies=( 2nodes, 3)=>( 4nodes 5.map(({ 6colorId, 7id, 8x, 9y,10})=>({11adjacentIds:(12nodes13.filter(({14x:adjacentX,15y:adjacentY,16})=>(17adjacentX===x+118&&adjacentY===y19||(20adjacentX===x-121&&adjacentY===y22)23||(24adjacentX===x25&&adjacentY===y+126)27||(28adjacentX===x29&&adjacentY===y-130)31))32.filter(({33colorId:adjacentColorId,34})=>(35adjacentColorId36===colorId37))38.map(({39id,40})=>(41id42))43),44color:colors[colorId],45id,46}))47.filter(({48adjacentIds,49})=>(50adjacentIds51.length>052))53)

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

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

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

錯誤的方式：遞歸

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

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

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

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

算法

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

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

代碼如下所示：

1constgetContiguousIds=({ 2contiguousIds=[], 3node, 4nodes, 5})=>( 6node 7.adjacentIds 8.reduce( 9(10contiguousIds,11adjacentId,12)=>(13contiguousIds14.includes(adjacentId)15?contiguousIds16:(17getContiguousIds({18contiguousIds,19node:(20nodes21.find(({22id,23})=>(24id25===adjacentId26))27),28nodes,29})30)31),32(33contiguousIds34.concat(35node36.id37)38),39)40)41constgetLargestContiguousNodes=(42nodes,43)=>(44nodes45.reduce(46(47prevState,48node,49)=>{50if(51prevState52.scannedIds53.includes(node.id)54){55returnprevState56}575859constcontiguousIds=(60getContiguousIds({61node,62nodes,63})64)656667const{68largestContiguousIds,69scannedIds,70}=prevState717273return{74largestContiguousIds:(75contiguousIds.length76>largestContiguousIds.length77?contiguousIds78:largestContiguousIds79),80scannedIds:(81scannedIds82.concat(contiguousIds)83),84}85},86{87largestContiguousIds:[],88scannedIds:[],89},90)91.largestContiguousIds

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

遞歸函數

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

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

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

循環

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

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

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

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

執行

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

順序迭代

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

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

1constgetLargestContiguousNodes=( 2nodes, 3)=>( 4nodes 5.reduce( 6( 7contiguousIdsList, 8{ 9adjacentIds,10id,11},12)=>{13constlinkedContiguousIds=(14contiguousIdsList15.reduce(16(17linkedContiguousIds,18contiguousIds,19)=>(20contiguousIds21.has(id)22?(23linkedContiguousIds24.add(contiguousIds)25)26:linkedContiguousIds27),28newSet(),29)30)313233return(34linkedContiguousIds35.size>036?(37contiguousIdsList38.filter((39contiguousIds,40)=>(41!(42linkedContiguousIds43.has(contiguousIds)44)45))46.concat(47Array48.from(linkedContiguousIds)49.reduce(50(51linkedContiguousIds,52contiguousIds,53)=>(54newSet([55...linkedContiguousIds,56...contiguousIds,57])58),59newSet(adjacentIds),60)61)62)63:(64contiguousIdsList65.concat(66newSet([67...adjacentIds,68id,69])70)71)72)73},74[newSet()],75)76.reduce((77largestContiguousIds=[],78contiguousIds,79)=>(80contiguousIds.size81>largestContiguousIds.size82?contiguousIds83:largestContiguousIds84))85)

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

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

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

執行

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

隨機迭代

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

1constgetLargestContiguousNodes=( 2nodes, 3)=>{ 4letcontiguousIds=[] 5letlargestContiguousIds=[] 6letqueuedIds=[] 7letremainingNodesIndex=0 8 910letremainingNodes=(11nodes12.slice()13)141516while(remainingNodesIndex039){40queuedIds41.push(...adjacentIds)42}434445if(46queuedIds47.length>048){49do{50constqueuedId=(51queuedIds52.shift()53)545556remainingNodesIndex=(57remainingNodes58.findIndex(({59id,60})=>(61id===queuedId62))63)64}65while(66queuedIds.length>067&&remainingNodesIndex===-168)69}7071if(72queuedIds.length===073&&remainingNodesIndex===-174){75if(76contiguousIds.length77>largestContiguousIds.length78){79largestContiguousIds=contiguousIds80}8182contiguousIds=[]83remainingNodesIndex=08485if(86remainingNodes87.length===088){89break90}91}92}9394returnlargestContiguousIds95}9697module.exports=getLargestContiguousNode

這里，我們沒有將節點添加到先前掃描的 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 個節點。

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

隨機顏色

執行時間	方法
229.481ms	遞歸
272.303ms	迭代隨機
323.011ms	迭代序列
391.582ms	Redux-Observable 并發
686.198ms	Redux-Observable 隨機
807.839ms	Redux-Observable 順序

一種顏色

執行時間	方法
1061.028ms	迭代隨機
1462.143ms	Redux-Observable 隨機
1840.668ms	Redux-Observable 順序
2541.227ms	迭代序列

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

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

游戲制作

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

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

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

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

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

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

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

結語

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

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

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