打賭你無法解決這個Google面試題
英文 |??https://medium.com/free-code-camp/bet-you-cant-solve-this-google-interview-question-4a6e5a4dc8ee
TechLead 的問題
當我聽到他的問題并看到圖片時，我在想：“天哪，我必須做一些2D圖像建模才能弄清楚這一點”，而這在面試中是幾乎不可能的。
但是在他進一步解釋之后，我發(fā)現(xiàn)事實并非如此。我們需要處理的是圖像的數(shù)據(jù)，而不需要解析圖像并轉(zhuǎn)化為數(shù)據(jù)。
數(shù)據(jù)模型
在編寫代碼之前，我們需要定義數(shù)據(jù)模型。
在我們的案例中，TechLead 給了我們這些限制：
我們將其稱為彩色正方形或“節(jié)點”的概念
我們的數(shù)據(jù)集中有1萬個節(jié)點
節(jié)點分為列和行（2D）
列和行的數(shù)量可以不均勻
節(jié)點具有顏色和某種表示鄰接的方式
我們還可以從數(shù)據(jù)中獲取更多信息：
沒有兩個節(jié)點會重疊
節(jié)點永遠不會與它們自己相鄰
節(jié)點永遠不會有重復的鄰接關系
位于側(cè)面和角落的節(jié)點將分別缺少一兩個相鄰關系
我們不知道的是：
行與列的比例
可能的顏色數(shù)
所有節(jié)點只有一種顏色的機會
顏色的粗略分布
職級越高，您將要問的問題越多。這也不是經(jīng)驗問題。雖然這樣做有幫助，但是如果您不能挑出未知數(shù)，也不會使您變得更好。
我并沒有指望大多數(shù)人都能發(fā)現(xiàn)這些未知項。直到我開始研究算法時，我也不全都知道。未知項需要時間才能弄清楚。需要與人進行大量討論并來回查閱題目。
看他的圖像，似乎分布是隨機的。他只使用了3種顏色，并且從不說其他任何東西，所以我們也一樣。我們還將假設所有顏色都可能相同。
由于它可能會破壞我們的算法，因此我假設我們正在使用 100x100 的網(wǎng)格。這樣，我們不必處理1行和 10K 列的極端情況。
在典型的情況下，我會在問題提出的最初幾個小時內(nèi)發(fā)現(xiàn)所有這些問題。這就是 TechLead 真正關心的問題。你講直接開始編碼？還是會先分析題目找出問題所在？
創(chuàng)建數(shù)據(jù)模型
我們數(shù)據(jù)的基本模塊：
顏色
ID
X
Y
ID是干什么的？它是每個網(wǎng)格的唯一標志。
由于是在網(wǎng)格中整理數(shù)據(jù)，因此我假設我們將使用X和Y值描述數(shù)據(jù)。僅使用這些屬性，我就能生成一些HTML，以確保我們生成的內(nèi)容就像 TechLead 給我們的一樣。
我們使用絕對定位來完成：
也適用于更大的數(shù)據(jù)集：
這里是代碼：
const generateNodes = ({numberOfColumns,numberOfRows,}) => (Array(numberOfColumns* numberOfRows).fill().map((item,index,) => ({colorId: (Math.floor(Math.random() * 3)),id: index,x: index % numberOfColumns,y: Math.floor(index / numberOfColumns),})))
我們?nèi)〕隽泻托?，從項目?shù)量中創(chuàng)建一維數(shù)組，然后根據(jù)該數(shù)據(jù)生成節(jié)點。
我使用的是 colorId，而不是 color。首先，因為隨機化比較容易。其次，我們通常必須自己檢查顏色值。
盡管他從未明確聲明，但他只使用了3種顏色值。我也將數(shù)據(jù)集限制為3種顏色。只需知道它可能是數(shù)百種顏色，并且最終的算法就無需更改。
舉一個簡單的例子，這里是2x2節(jié)點列表：
[{ colorId: 2, id: 0, x: 0, y: 0 },{ colorId: 1, id: 1, x: 1, y: 0 },{ colorId: 0, id: 2, x: 0, y: 1 },{ colorId: 1, id: 3, x: 1, y: 1 },]
數(shù)據(jù)處理
無論我們要使用哪種方法，我們都想知道每個節(jié)點的鄰接關系。X和Y值不會減少。
因此，給定X和Y，我們需要弄清楚如何找到相鄰的X和Y值。這很簡單。我們只需在X和Y上找到正負1的節(jié)點即可。
我為此邏輯編寫了一個輔助函數(shù)：
const getNodeAtLocation = ({nodes,x: requiredX,y: requiredY,=> ((nodes.find(({x,y,=> (x === requiredXy === requiredY)){}).id)
我們生成節(jié)點的方式實際上是一種數(shù)學方法，用來找出相鄰節(jié)點的ID。相反，我假設節(jié)點將以隨機順序進入我們的系統(tǒng)。
我通過第二遍運行所有節(jié)點以添加鄰接關系：
const addAdjacencies = (nodes,=> (nodes.map(({colorId,id,x,y,=> ({color: colors[colorId],eastId: (getNodeAtLocation({nodes,x: x + 1,y,})),id,northId: (getNodeAtLocation({nodes,x,y: y - 1,})),southId: (getNodeAtLocation({nodes,x,y: y + 1,})),westId: (getNodeAtLocation({nodes,x: x - 1,y,})),})).map(({color,id,eastId,northId,southId,westId,=> ({adjacentIds: ([eastId,northId,southId,westId,].filter((adjacentId,=> (adjacentId !== undefined))),color,id,})))
我避免在此預處理程序代碼中進行任何不必要的優(yōu)化。它不會影響我們的最終性能數(shù)據(jù)，只會幫助簡化算法。
我繼續(xù)將 colorId 更改為另一種顏色。對于我們的算法而言，這完全沒有必要，但我想使其更易于可視化。
我們?yōu)槊拷M相鄰的X和Y值調(diào)用 getNodeAtLocation并找到我們的northId，eastId，southId和westId。不再傳遞X和Y值，因為它們不再需要。
在獲得基本ID后，我們將其轉(zhuǎn)換為一個僅包含值的ID數(shù)組。這樣，如果我們有邊角，就不必擔心檢查這些ID是否為空。它還允許我們循環(huán)一個數(shù)組，而不是手動注釋算法中的每個基本ID。
這是另一個2x2的示例，該示例使用通過 addAdjacencies 運行的一組新節(jié)點：
[{ adjacentIds: [ 1, 2 ], color: 'red', id: 0 },{ adjacentIds: [ 3, 0 ], color: 'grey', id: 1 },{ adjacentIds: [ 3, 0 ], color: 'blue', id: 2 },{ adjacentIds: [ 1, 2 ], color: 'blue', id: 3 },]
處理優(yōu)化
我想大大簡化本文的算法，因此添加了另一個優(yōu)化過程。這將刪除與當前節(jié)點顏色不匹配的相鄰ID。
重寫addAdjacencies函數(shù)之后，現(xiàn)在是這樣的：
const addAdjacencies = (nodes,) => (nodes.map(({colorId,id,x,y,}) => ({adjacentIds: (nodes.filter(({x: adjacentX,y: adjacentY,}) => (adjacentX === x + 1&& adjacentY === y|| (adjacentX === x - 1&& adjacentY === y)|| (adjacentX === x&& adjacentY === y + 1)|| (adjacentX === x&& adjacentY === y - 1))).filter(({colorId: adjacentColorId,}) => (adjacentColorId=== colorId)).map(({id,}) => (id))),color: colors[colorId],id,})).filter(({adjacentIds,}) => (adjacentIds.length > 0)))
我減少了 addAdjacencies 的代碼量，同時添加了更多功能。
通過刪除顏色不匹配的節(jié)點，我們的算法可以100％確保 adjacentIds 中的ID都是連續(xù)的節(jié)點。
最后，我刪除了沒有相同顏色鄰接關系的所有節(jié)點。這進一步簡化了我們的算法，并且將總節(jié)點縮減為僅關心的節(jié)點。
錯誤的方式—遞歸
TechLead 表示我們無法遞歸執(zhí)行此算法，因為我們遇到了堆棧溢出的情況。
盡管他部分正確，但有幾種方法可以緩解此問題。迭代或使用尾遞歸。我們將以迭代示例為例，但是JavaScript不再具有尾部遞歸作為本機語言功能。
雖然我們?nèi)匀豢梢栽贘avaScript中模擬尾部遞歸，但我們將保持這種簡單性，而是創(chuàng)建一個典型的遞歸函數(shù)。
在編寫代碼之前，我們需要弄清楚我們的算法。對于遞歸，使用深度優(yōu)先搜索是有意義的。不必擔心知道計算機科學術語。當我向他展示我想出的不同解決方案時，一位同事說過。
算法
我們將從節(jié)點開始，并盡我們所能直到到達終點。然后，我們將返回并采用下一個分支路徑，直到我們掃描了整個連續(xù)塊。
這就是其中的一部分。我們還必須跟蹤我們?nèi)ミ^的地方以及最大的連續(xù)街區(qū)的長度。
我所做的就是將我們的功能分為兩部分。一個將擁有最大的列表和先前掃描的ID，同時至少每個節(jié)點循環(huán)一次。另一個將從未掃描的根節(jié)點開始，然后進行深度優(yōu)先遍歷。
函數(shù)長這樣：
const getContiguousIds = ({contiguousIds = [],node,nodes,}) => (node.adjacentIds.reduce((contiguousIds,adjacentId,) => (contiguousIds.includes(adjacentId)? contiguousIds: (getContiguousIds({contiguousIds,node: (nodes.find(({id,}) => (id=== adjacentId))),nodes,}))),(contiguousIds.concat(node.id)),))const getLargestContiguousNodes = (nodes,) => (nodes.reduce((prevState,node,) => {if (prevState.scannedIds.includes(node.id)) {return prevState}const contiguousIds = (getContiguousIds({node,nodes,}))const {largestContiguousIds,scannedIds,} = prevStatereturn {largestContiguousIds: (contiguousIds.length> largestContiguousIds.length? contiguousIds: largestContiguousIds),scannedIds: (scannedIds.concat(contiguousIds)),}},{largestContiguousIds: [],scannedIds: [],},).largestContiguousIds)
瘋了吧？這個代碼簡直太長了。
接下來我們一步步來縮減代碼
遞歸函數(shù)
getContiguousIds 是我們的遞歸函數(shù)，每個節(jié)點調(diào)用一次。每次都會返回更新的連續(xù)節(jié)點列表。
此功能只有一個條件：列表中是否已存在我們的節(jié)點？如果不是，請再次調(diào)用
getContiguousIds。返回時，我們將獲得一個更新的連續(xù)節(jié)點列表，該列表將返回到化簡器，并用作下一個相鄰ID的狀態(tài)。
您可能想知道我們在哪里向contiguousIds添加值。當我們將當前節(jié)點連接到contiguousIds上時，就會發(fā)生這種情況。每次進一步遞歸時，我們都確保在循環(huán)其相鄰ID之前將當前節(jié)點添加到contiguousId列表中。
始終添加當前節(jié)點可確保我們不會無限遞歸。
循環(huán)
此功能的后半部分還將遍歷每個節(jié)點一次。
我們在遞歸函數(shù)周圍使用了reducer。此人檢查我們的代碼是否已被掃描。如果是這樣，請繼續(xù)循環(huán)，直到找到一個尚未存在的節(jié)點，或者直到退出循環(huán)為止。
如果尚未掃描我們的節(jié)點，請調(diào)用getContiguousIds并等待完成。這是同步的，但可能需要一些時間。
返回帶有contiguousIds的列表后，請對照largestantContiguousIds列表進行檢查。如果更大，則存儲該值。
同時，我們將這些contiguousId添加到我們的scandIds列表中，以標記我們?nèi)ミ^的地方。
當您看到所有布局時，這非常簡單。
執(zhí)行
即使有1萬個節(jié)點+3種隨機顏色，也不會遇到堆棧溢出問題。但如果只有一種顏色，那么將會將遇到堆棧溢出的情況。那是因為我們的遞歸函數(shù)要進行1萬次遞歸。
順序迭代
由于內(nèi)存大于函數(shù)調(diào)用堆棧，因此我的下一個想法是在單個循環(huán)中完成整個操作。
我們將跟蹤節(jié)點列表列表。我們將繼續(xù)添加它們并將它們鏈接在一起，直到脫離循環(huán)為止。
此方法要求我們將所有可能的節(jié)點列表保留在內(nèi)存中，直到完成循環(huán)為止。在遞歸示例中，我們僅在內(nèi)存中保留了最大的列表。
const getLargestContiguousNodes = (nodes,) => (nodes.reduce((contiguousIdsList,{adjacentIds,id,},) => {const linkedContiguousIds = (contiguousIdsList.reduce((linkedContiguousIds,contiguousIds,) => (contiguousIds.has(id)? (linkedContiguousIds.add(contiguousIds)): linkedContiguousIds),new Set(),))return (linkedContiguousIds.size > 0? (contiguousIdsList.filter((contiguousIds,) => (!(linkedContiguousIds.has(contiguousIds)))).concat(Array.from(linkedContiguousIds).reduce((linkedContiguousIds,contiguousIds,) => (new Set([...linkedContiguousIds,...contiguousIds,])),new Set(adjacentIds),))): (contiguousIdsList.concat(new Set([...adjacentIds,id,]))))},[new Set()],).reduce((largestContiguousIds = [],contiguousIds,) => (contiguousIds.size> largestContiguousIds.size? contiguousIds: largestContiguousIds)))
另一個瘋狂的。讓我們從頂部開始進行分解。我們將每個節(jié)點循環(huán)一次。但是現(xiàn)在我們必須檢查我們的id是否在節(jié)點列表的列表中：contiguousIdsList。
如果它不在任何contiguousId列表中，我們將添加它及其相鄰ID。這樣，在循環(huán)時，其他東西將鏈接到它。
如果我們的節(jié)點在其中一個列表中，則可能其中有很多。我們希望將所有這些鏈接在一起，并從contiguousIdsList中刪除未鏈接的鏈接。
而已。
提出節(jié)點列表列表后，我們檢查最大的節(jié)點列表，然后完成。
執(zhí)行
與遞歸版本不同，當所有10K項都具有相同的顏色時，該函數(shù)確實會完成。
除此之外，它非常慢；比我最初預期的要慢得多。我忘了在效果評估中考慮循環(huán)列表列表，這顯然會對性能產(chǎn)生影響。
隨機迭代
我想將方法學放在遞歸方法的后面，并迭代地應用它。
我花了一整夜的時間試圖記住如何動態(tài)更改循環(huán)中的索引，然后想起了while（true）。
自從我寫了傳統(tǒng)的循環(huán)已經(jīng)很久了，我完全忘記了它。
現(xiàn)在我有了武器，我就開始進攻了。由于我花了很多時間試圖加快可觀察版本的速度（稍后會詳細介紹），因此我決定將數(shù)據(jù)懶散地進行老式修改。
該算法的目標是精確擊中每個節(jié)點一次，并且僅存儲最大的連續(xù)塊：
const getLargestContiguousNodes = (nodes,) => {let contiguousIds = []let largestContiguousIds = []let queuedIds = []let remainingNodesIndex = 0let remainingNodes = (nodes.slice())while (remainingNodesIndex < remainingNodes.length) {const [node] = (remainingNodes.splice(remainingNodesIndex,1,))const {adjacentIds,id,} = nodecontiguousIds.push(id)if (adjacentIds.length > 0) {queuedIds.push(...adjacentIds)}if (queuedIds.length > 0) {do {const queuedId = (queuedIds.shift())remainingNodesIndex = (remainingNodes.findIndex(({id,}) => (id === queuedId)))}while (queuedIds.length > 0&& remainingNodesIndex === -1)}if (queuedIds.length === 0&& remainingNodesIndex === -1) {if (contiguousIds.length> largestContiguousIds.length) {largestContiguousIds = contiguousIds}contiguousIds = []remainingNodesIndex = 0if (remainingNodes.length === 0) {break}}}return largestContiguousIds}module.exports = getLargestContiguousNodesIterative2
即使我像大多數(shù)人一樣寫了這篇文章，但到目前為止，它的可讀性最差。我什至無法告訴您這是怎么回事，除非自己先自上而下地進行。
我們沒有添加到以前掃描的ID列表中，而是從剩余的Nodes數(shù)組中拼接出了值。
懶！我永遠不會建議自己這樣做，但是我在創(chuàng)建這些樣本的最后階段想嘗試一些不同的嘗試。
性能對比
隨機顏色
| 耗時 | 方法 |
|---|---|
| 229.481ms | Recursive |
| 272.303ms | Iterative Random |
| 323.011ms | Iterative Sequential |
| 391.582ms | Redux-Observable Concurrent |
| 686.198ms | Redux-Observable Random |
| 807.839ms | Redux-Observable Sequential |
單一顏色
| 耗時 | 方法 |
|---|---|
| 1061.028ms | Iterative Random |
| 1462.143ms | Redux-Observable Random |
| 1840.668ms | Redux-Observable Sequential |
| 2541.227ms | Iterative Sequential |
本文完~
