你解得出這道Google面試題嗎？

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

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

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

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

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

TechLead 的問題

在 TechLead 的問題中，他要求應(yīng)聘者在如下網(wǎng)格中，計(jì)算出所有顏色相同的最大連續(xù)塊的數(shù)量。

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

但在聽完他的詳細(xì)解釋之后，我方知情況并非如此。在這個(gè)問題中，我們需要處理的是已經(jīng)捕獲的數(shù)據(jù)，而不是解析圖像。

數(shù)據(jù)建模

在編寫任何代碼之前都需要定義數(shù)據(jù)模型。對(duì)于任何問題，首先要弄清楚我們?cè)谔幚硎裁?，并收集業(yè)務(wù)需求。

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

彩色方塊或“節(jié)點(diǎn)”的概念

數(shù)據(jù)集中包含 1 萬個(gè)節(jié)點(diǎn)

節(jié)點(diǎn)被組織成行和列，即二維數(shù)據(jù)

列數(shù)和行數(shù)可能不同

節(jié)點(diǎn)有顏色信息，并具有對(duì)“鄰接”這一概念的表示方式

我們還可以從數(shù)據(jù)中獲得更多信息：

節(jié)點(diǎn)不會(huì)重疊

節(jié)點(diǎn)不會(huì)和其自身鄰接

節(jié)點(diǎn)不會(huì)有重復(fù)的鄰接

位于邊角的節(jié)點(diǎn)會(huì)比其他節(jié)點(diǎn)少一個(gè)或兩個(gè)鄰接

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

行數(shù)與列數(shù)的比

可能的顏色數(shù)量

只有一種顏色的可能性

顏色的大致分布

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

大部分人并不會(huì)想到詢問這些未知信息。在開始研究這個(gè)算法之前，我也不知道這些未知信息是什么。要找到所有的未知信息，需要與業(yè)務(wù)人員進(jìn)行反復(fù)的討論才行。

對(duì)于 TechLead 的這張照片來說，顏色的分布似乎是隨機(jī)的。他只用了三種顏色，并且沒有提到其他限制，因此我們暫時(shí)也做這種假設(shè)。另外我們還假設(shè)，這些顏色可能是相同的。

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

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

創(chuàng)建數(shù)據(jù)模型

我們需要知道數(shù)據(jù)是如何輸入的，以及我們希望以何種形式來處理這些數(shù)據(jù)。由于沒有處理數(shù)據(jù)的系統(tǒng)，因此我們需要自己設(shè)計(jì)一個(gè)可視化的方法。

數(shù)據(jù)的基本結(jié)構(gòu)如下：

Color

ID

X

Y

需要 ID 的原因在于，我們可能不止一次碰到同一個(gè)圖片格。要想防止無限循環(huán)的話，就必須標(biāo)記在這些情況下該圖片格所處的位置。

此外，像這樣的數(shù)據(jù)通常會(huì)分配某些 ID、哈希值或其他值。它是一個(gè)唯一的標(biāo)識(shí)符，因此，我們可以通過某種方式來標(biāo)識(shí)特定的節(jié)點(diǎn)。如果我們想知道最大的連續(xù)塊，就需要知道該塊中有哪些節(jié)點(diǎn)。

由于 TechLead 使用網(wǎng)格對(duì)數(shù)據(jù)進(jìn)標(biāo)識(shí)，我假設(shè)我們會(huì)得到 X 和 Y 的值。依靠這些屬性，我就能夠生成一些 HTML，并確保生成的內(nèi)容與他給我們的內(nèi)容相類似。

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

答案：3

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

答案：18

下面是生成節(jié)點(diǎn)的代碼：

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)

我們使用行列信息創(chuàng)建一個(gè)一維數(shù)組，然后根據(jù)這些數(shù)據(jù)生成節(jié)點(diǎn)。

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

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

下面是一個(gè)更簡單的例子，這是一個(gè) 2x2 的節(jié)點(diǎn)列表：

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]

數(shù)據(jù)處理

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

我為此寫了一個(gè)函數(shù)：

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

我們用來生成節(jié)點(diǎn)的方式，實(shí)際上是一種計(jì)算相鄰節(jié)點(diǎn) ID 的數(shù)學(xué)方法。而在這一步中，我將采取一個(gè)與之相反的思路，即假設(shè)節(jié)點(diǎn)將以隨機(jī)順序輸入。

我通過再次遍歷所有節(jié)點(diǎn)來添加鄰接關(guān)系：

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)

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

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

我們?yōu)槊拷M相鄰的 X 和 Y 值調(diào)用 getNodeAtLocation 函數(shù)，并找到我們的 northId 、 eastId 、 southId 和 westId 。在此步驟中，我們不會(huì)對(duì) X 和 Y 的值進(jìn)行參數(shù)傳遞。

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

下面是另一個(gè) 2x2 網(wǎng)格的示例，這里我們使用了一組新的節(jié)點(diǎn)，并通過 addAdjacencies 來運(yùn)行：

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]

優(yōu)化預(yù)處理過程

為了簡化本文的算法，我添加了另一個(gè)優(yōu)化過程。該算法將刪除與當(dāng)前節(jié)點(diǎn)顏色不匹配的相鄰 ID。

重寫 addAdjacencies 函數(shù)，如下：

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)

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

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

最后，我刪除了所有不具有相同顏色鄰接的節(jié)點(diǎn)，這進(jìn)一步簡化了我們的算法。這樣，我們就將節(jié)點(diǎn)縮減為只有我們關(guān)心的那些節(jié)點(diǎn)。

錯(cuò)誤的方式：遞歸

TechLead 指出，我們無法遞歸地執(zhí)行這個(gè)算法，因?yàn)槲覀儠?huì)遇到堆棧溢出的問題。

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

盡管我們?nèi)匀豢梢杂?JavaScript 來寫一個(gè)尾遞歸函數(shù)，但為使得算法更加簡單，我仍然選擇了創(chuàng)建一個(gè)典型的遞歸函數(shù)。

在編寫代碼之前，我們需要先找到算法。對(duì)于遞歸，使用深度優(yōu)先搜索是合理的?！安灰獡?dān)心別人不明白計(jì)算機(jī)科學(xué)術(shù)語?！痹谖蚁蛞晃煌抡故疚蚁氤龅牟煌鉀Q方案時(shí)，他如此說道。

算法

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

我將函數(shù)分成了兩部分。其中一個(gè)函數(shù)將保存最大列表和先前掃描的 ID，同時(shí)至少循環(huán)每個(gè)節(jié)點(diǎn)一次。另一個(gè)函數(shù)則將從未掃描的根節(jié)點(diǎn)開始，進(jìn)行深度優(yōu)先遍歷。

代碼如下所示：

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

下面，我們將逐步進(jìn)行分析。

遞歸函數(shù)

getContiguousIds 是遞歸函數(shù)，在每個(gè)節(jié)點(diǎn)調(diào)用一次。在該函數(shù)每次返回結(jié)果時(shí)，我們都會(huì)得到一個(gè)連續(xù)節(jié)點(diǎn)的更新列表。

這個(gè)函數(shù)只有一個(gè)判斷條件：節(jié)點(diǎn)是否已在列表中？如果沒有，則再次調(diào)用getContiguousIds 。當(dāng)該函數(shù)返回結(jié)果時(shí)，我們會(huì)獲得一個(gè)更新的連續(xù)節(jié)點(diǎn)列表，該列表會(huì)被返回到 reducer ，并用作下一個(gè) adjacentId 的狀態(tài)。

每當(dāng)我們用 concat 將當(dāng)前節(jié)點(diǎn)連接到 contiguousIds 時(shí)，都要向 contiguousIds 傳入值。每次進(jìn)一步遞歸時(shí)，我們都要確保在循環(huán)執(zhí)行 adjacentIds 之前，當(dāng)前節(jié)點(diǎn)已經(jīng)被添加到 contiguousIds 列表中。這可以確保我們不會(huì)無限地遞歸。

循環(huán)

該函數(shù)的后半部分也會(huì)遍歷每個(gè)節(jié)點(diǎn)一次。遞歸函數(shù)使用 reducer來檢查代碼是否已被掃描。若已被掃描，就繼續(xù)循環(huán)，直到找到一個(gè)沒有循環(huán)的節(jié)點(diǎn)，或者直到退出循環(huán)為止。

如果我們的節(jié)點(diǎn)尚未被掃描，則調(diào)用 getContiguousIds，并繼續(xù)遍歷，直到掃描完成。這是同步的，但可能需要一些時(shí)間。

每當(dāng)函數(shù)返回一個(gè) contignousIds 列表，都對(duì)照 largestContiguousIds 進(jìn)行檢查，如果該列表的返回值更大的話，就存儲(chǔ)返回值。

同時(shí)，我們將把這些 contiguousIds 添加到我們的 scannedIds 列表中，以標(biāo)記我們搜索的節(jié)點(diǎn)。

執(zhí)行

就算我們有 10000 個(gè)項(xiàng)目，這個(gè)算法也不會(huì)遇到 3 種隨機(jī)顏色的堆棧溢出問題。如果我把所有的都改成單一顏色，就可能會(huì)遇到堆棧溢出的問題，這是因?yàn)槲覀兊倪f歸函數(shù)經(jīng)歷了 10000 次的遞歸。

順序迭代

由于內(nèi)存比函數(shù)調(diào)用的堆棧要大，所以我的下一個(gè)想法是在一個(gè)循環(huán)中完成整個(gè)事情。我們將跟蹤節(jié)點(diǎn)列表的列表。我們將不斷添加它們，并將它們鏈接在一起，直到退出循環(huán)。

這個(gè)方法要求在完成循環(huán)之前，將所有可能的節(jié)點(diǎn)列表保存在內(nèi)存中。在遞歸示例中，我們只將最大的列表保存在內(nèi)存中。

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)

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

如果它不存在于任何 contiguousIds 列表中，我們就將添加該列表和 adjacenIds 。這樣，在循環(huán)時(shí)，就會(huì)有其他的內(nèi)容鏈接到它。

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

執(zhí)行

與遞歸版本不同的是，當(dāng)所有 10000 個(gè)項(xiàng)目都是相同的顏色時(shí)，這個(gè)算法能夠完成任務(wù)。但該算法的一個(gè)缺陷是，它執(zhí)行得相當(dāng)慢。在上述代碼的性能評(píng)估中，我沒有考慮到循環(huán)列表的列表的情況，這顯然對(duì)性能有很大的影響。

隨機(jī)迭代

我想采用遞歸方法背后的思路，并以迭代方式進(jìn)行應(yīng)用。這一算法的目標(biāo)是精確命中每個(gè)節(jié)點(diǎn)一次，并且只存儲(chǔ)最大的連續(xù)塊：

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

這里，我們沒有將節(jié)點(diǎn)添加到先前掃描的 ID 列表，而是從 remainingNodes 數(shù)組中拼接出值來，但是我不建議大家這樣做。

分解

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

讓我們從中間部分開始。首先查看 queuedIds 。如果該對(duì)象有值，就對(duì)隊(duì)列中的內(nèi)容進(jìn)行循環(huán)，看看它們是否存在于 remainingNodes 中。

第三部分的內(nèi)容取決于第二部分的結(jié)果。如果 queuedIds 對(duì)象為空，并且 remainingNodesIndex 是 -1 的話，那么我們就已經(jīng)完成了這個(gè)節(jié)點(diǎn)列表，并需要從一個(gè)新的根節(jié)點(diǎn)開始。新的根節(jié)點(diǎn)始終位于索引 0 處，因?yàn)槲覀冋趯?duì) remaininigNodes 進(jìn)行拼接。

現(xiàn)在再來看循環(huán)的頂部。我可以使用 while (true) ，但是需要留一個(gè)跳出條件，以防止出錯(cuò)。這在調(diào)試時(shí)很有用，因?yàn)橐宄o限循環(huán)可能是件痛苦的事情。

之后，我們將拼接節(jié)點(diǎn)。我們將節(jié)點(diǎn)添加到 contiguousIds 列表中，并將 adjacentIds 添加到隊(duì)列中。

執(zhí)行

這一算法幾乎和遞歸版本一樣快。當(dāng)所有節(jié)點(diǎn)都是相同顏色時(shí)，它是所有算法中速度最快的。

針對(duì)數(shù)據(jù)的優(yōu)化

對(duì)相似的顏色進(jìn)行分組

由于我們只知道有兩種藍(lán)色，所以我們可以將類似顏色的節(jié)點(diǎn)分組在一起，用于順序迭代版本。

通過將節(jié)點(diǎn)拆分成 3 個(gè)更小的數(shù)組，我們可以減少內(nèi)存占用，以及需要在列表的列表中執(zhí)行的循環(huán)次數(shù)。盡管如此，這并不能解決所有顏色都相同的情況下會(huì)出現(xiàn)的問題，因此我們并不會(huì)使用此方法修改遞歸版本。這也意味著我們可以對(duì)操作進(jìn)行多線程處理，將執(zhí)行時(shí)間縮短近三分之一。

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

可能存在的最大數(shù)據(jù)集的大小

我們可以檢查每一次迭代，而不是在特定時(shí)間間隔檢查是否有最大的列表。如果最大節(jié)點(diǎn)集合的規(guī)模大于或等于可用節(jié)點(diǎn)的一半（5000 或更高），那么，很顯然我們已經(jīng)有了最大的列表。

若使用隨機(jī)迭代版本的話，我們可以找到迄今為止最大的列表大小，并查看剩余的節(jié)點(diǎn)數(shù)量，如果沒有比最大的節(jié)點(diǎn)集合大小還小的數(shù)值，那么就可以說明，我們已經(jīng)有最大的列表了。

使用遞歸

雖然遞歸有其局限性，但我們?nèi)钥梢允褂盟?。我們需要做的事情就是檢查剩余節(jié)點(diǎn)的數(shù)量。如果它沒有超出堆棧的限制，我們就可以使用更快的遞歸版本。這么做的風(fēng)險(xiǎn)是很大，但隨著循環(huán)的深入，這一方法會(huì)縮短執(zhí)行時(shí)間。

使用 for 循環(huán)

在知道節(jié)點(diǎn)最大數(shù)量的情況下，我們可以使用 for 循環(huán)編寫 reduce 函數(shù)。無論何時(shí)，與 for 循環(huán)相比， Aray.prototype 方法都非常慢。

使用尾遞歸

我沒有在本文中討論相關(guān)算法，因?yàn)槲艺J(rèn)為尾遞歸需要一篇單獨(dú)的文章來闡述。這是一個(gè)很大的主題，很多地方都需要解釋。另外，雖然它使用了遞歸結(jié)構(gòu)，但它可能并不會(huì)想你所期望的那樣比while循環(huán)還快。

RxJS：可維護(hù)性與性能

有一些方法可以重寫這些函數(shù)，這樣你就可以更輕松地理解并維護(hù)它們。我想出的主要解決方案是使用 Redux-Observable 風(fēng)格的 RxJS，但并不使用 Redux。

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

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

我本來可以做很多優(yōu)化，但要以代碼的可讀性為代價(jià)，這不是我想要的。

最終，我終于找到了一個(gè)可行的解決方案，該方案目前是最快的，只需一半的執(zhí)行時(shí)間。這已經(jīng)是總體上最好的改進(jìn)了。

只有當(dāng)每個(gè)節(jié)點(diǎn)都是相同的顏色時(shí)，我才能用可觀察到的數(shù)據(jù)擊敗內(nèi)存占用較多的順序迭代。從技術(shù)上來講，這一算法也優(yōu)于遞歸方法，因?yàn)樵谶@種情況下，遞歸算法會(huì)出現(xiàn)堆棧溢出的問題。

在研究如何使用 RxJS 流數(shù)據(jù)之后，我意識(shí)到該方法對(duì)本文來說實(shí)在過于復(fù)雜了。希望以后會(huì)有文章詳細(xì)介紹這些代碼示例。

如果希望查看詳細(xì)代碼，可以查看如下 GitHub 項(xiàng)目地址：

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

最終統(tǒng)計(jì)數(shù)據(jù)

一般來說，最大的連續(xù)塊平均有 30~80 個(gè)節(jié)點(diǎn)。

下面展示了相關(guān)算法的評(píng)估數(shù)據(jù)：

隨機(jī)顏色

執(zhí)行時(shí)間	方法
229.481ms	遞歸
272.303ms	迭代隨機(jī)
323.011ms	迭代序列
391.582ms	Redux-Observable 并發(fā)
686.198ms	Redux-Observable 隨機(jī)
807.839ms	Redux-Observable 順序

一種顏色

執(zhí)行時(shí)間	方法
1061.028ms	迭代隨機(jī)
1462.143ms	Redux-Observable 隨機(jī)
1840.668ms	Redux-Observable 順序
2541.227ms	迭代序列

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

當(dāng)所有節(jié)點(diǎn)顏色都相同時(shí)，Redux-Observable 并發(fā)方法受到了影響，我試過很多方法嘗試提高這個(gè)方法的運(yùn)行速度，但是沒有成功。

游戲制作

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

還有一次是在我繪制一張世界地圖的時(shí)候，該地區(qū)有一個(gè)預(yù)定義的節(jié)點(diǎn)列表，我對(duì)其進(jìn)行了實(shí)時(shí)處理。這使得使用者可以通過鍵盤上的方向鍵來移動(dòng)世界地圖。

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

在這個(gè)案例中，實(shí)時(shí)執(zhí)行時(shí)間并不怎么很重要，因?yàn)槲以诩虞d游戲時(shí)就進(jìn)行了大量的預(yù)處理。

我想強(qiáng)調(diào)的是，TechLead 的問題可能是你會(huì)在職業(yè)生涯中遇到的問題，但在典型的 JavaScript 應(yīng)用程序中，往往不太需要考慮程序的速度。

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

但是，這個(gè)視頻也有可能是關(guān)于 HTML 和 CSS 的職位的，誰知道呢！

結(jié)語

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

據(jù)我自己的經(jīng)驗(yàn)，我花了更長的時(shí)間來開發(fā)非 RxJS 版本的代碼。我認(rèn)為，這是因?yàn)楦斓陌姹拘枰娴乃伎?。Redux-Observable 能夠讓你以化整為零的方式進(jìn)行思考。

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