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