0717-7821348
新闻中心

彩乐乐遗漏

您现在的位置: 首页 > 新闻中心 > 彩乐乐遗漏
我敢打赌,谷歌这道面试题你解不出来!
2019-05-31 22:40:22

全文共6793字,估计学习时长30分钟或更长


在YouTube上,TechLead关于软件工程的视频十分受欢迎。其间一期视频中,TechLead提到了他在谷歌100屡次面试中提出的一个问题。

他提问题首要意图是想了解:应聘者是否会在编程之前提出适宜的问题?提出的处理方法是否契合项目攻略?他乃至说,能否答复出正确答案并不重要,仅仅想要探明你怎样考虑,亦或你是否正确了解问题所在。

或许你会很猎奇,怎样处理这个问题?TechLead谈到了几个处理计划,一个是递归式(受仓库巨细的约束),一个是迭代式(受内存巨细的约束)。本文将会对这两个问题进行更多的研讨!

Techlead的问题


Techlead提出的问题是:在这张网格图中,核算最大的同色相连方块数量。




当听到这个问题时,我边看图边想,“天呐,我得用二维模型来答复了。”这听起来简直便是个近乎不行能在面试中能够答复的问题。

跟着解说的深化,我意识到问题并未如此简略。前面的解法事实上仅仅在运转已抓取的数据而不是解析图画。我意识到,图画这个词,其实是用词不当的。

数据建模


在开端编程之前,需求界说好数据模型。这件事再怎样着重也不为过。在编写如此高档的代码之前,首要要弄清楚自己正在处理什么,一同搜集好事务需求。

在本文所举的比如里,TechLead给咱们界说了许多要求:

五颜六色方块的概念,或许称之为“节点”。

此数据会集有10K节点。

节点被安排成行和列二维)。

行数和列数或许不均匀。

节点有色彩和表明邻接的方法。

从数据中还能得到更多的信息:

恣意两个节点不会堆叠。

节点永久不会和本身相邻。

一个节点永久不会重复相邻。

坐落边和角上的节点将别离丢掉一个或两个邻接。

不知道的是:

队伍比值

或许的色彩数量

只需一种色彩的概率

色彩的大略散布

作为开发者,等级越高,越清楚应该问哪些问题。当然这也不全是过往经历所能赋予的。尽管有所协助,可是如若不能找出这些不知道量,处理问题时仍是会遇到困难。

咱们并不期望世人能够找出这些不知道量。在脑海中核算这个算法之前,我对其也一窍不通。要找到这些不知道量需求必定的时刻,需求通过重复与事务人员进行许多的评论来找到这傍边的症结。

图片里色块的散布看起来似乎是随机的。他除了说只用了3种色彩,并没有说其他,所以咱们也能够这么做。一同,做个假定:有一种或许状况是一切的色彩都有相同数量。

由于它或许会损坏算法,因而,假定正在处理一个100*100的网格图。这样就不需求处理奇数行和10K列的状况。

一般来说, 我会在数据探究的开端几个小时内问这些问题,而这才是TechLead 真实关怀之处。你会先编写一个随机解仍是先找出问题呢?

在数据建模的时分你应该会犯过错,我第一次写文章的时分就犯了过错。但假如你能够提早考虑到问题并有所防备,这些问题或许处理起来会愈加简略。横竖其时我终究不得不重写一部分代码。

创立数据模型

为了树立模型,咱们需求知道数据是怎样输入以及期望怎样处理。由于没有恰当的体系来处理数据,因而需求自己进行可视化处理。

数据的根本构成是这样的:

色彩

ID号码

X

Y

为什么需求ID? 由于处理时有或许不止一次遇到相同的方块。想要防止无限循环,则需求符号在这些状况下该方块所在的方位。

一同,像这样的数据,一般会配有某种ID、散列或许其他值。它是一个绝无仅有的标识符,因而咱们有方法能辨认那个特定的节点。假如想知道最大的相连方块,咱们需求知道该方块上有哪些节点。

由于TechLead用网格表明数据,咱们假定会得到X, Y的值。仅运用这些特点,能够生成一些HTML, 以保证所生成的内容与他给定的内容相似。

这是用肯定定位完结的,如他的比如那样:



答案:3

在更大的网格图中,这个方法也能够运用:




答案:18

这是他用于生成节点的代码:

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),
}))
)


取行和列,从项的数量中创立一个一维数组,然后依据这些数据生成节点。

在这儿用的不是色彩,而是colorID。这样做的原因有两个,一是随机化更简洁;二是色彩值一般需求自己查找。

尽管他从来没有清晰阐明他只运用了3个色彩值,这儿也将数据集约束为3种色彩。只需知道它能够有数百种色彩,终究的算法就不需求改动。

举个更简略的比如,这儿有一个2x2节点列表:

[ 
{ 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 },
]


数据处理


不管运用什么方法,咱们都期望得到这儿每个节点的相邻值。X和Y的值并不能满足要求。

因而,给定一个X和Y,相对应需求找出X和Y的相邻值。当然,这很简略,只需求在X和Y上找到+ 1和- 1的节点就能够了。

为此,我写了一个辅佐函数:

Const getNodeAtLocation = ({ 
nodes,
x: requiredX,
y: requiredY,
}) => (
(
nodes
.find(({
x,
y,
}) => (
x === requiredX
&& y === requiredY
))
|| {}
)
.id
)


相反,假定节点会随机进入体系。

生成节点的方法,其实确有一种能够推算出相邻节点ID的数学方法。但我不这么做,相反我假定节点会随机进入体系。

在第二轮遍历,一切节点时参加相邻节点:

Const getNodeAtLocation
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,
}))
)


防止在这个预处理器代码中进行任何不用要的优化。它不会影响终究的功用计算,只会协助简化算法。

接着,继续把colorID变成一种色彩。尽管关于这儿的算法来说这彻底没有必要,可是我想让它更好地可视化。

为每组相邻的X和Y值调用getNodeAtLocation,并找到northId、eastId、southId和westId。这儿不再传递X和Y值,由于它们不再是必需的。

在取得根本ID之后,将它们转换为一个邻接数组,该数组只包括那些具有数值的邻接数组。这样,只需有角和边,就不用担心所查看id是否为空。它还答应循环一个数组,而不用在算法中手艺记载每个根本ID。

下面是另一个2我敢打赌,谷歌这道面试题你解不出来!x2示例,它运用一组新的节点遍历addAdjacencies:

[ 
{ 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 },
]


处理优化

由于想大力简化本文的算法,所以我在另一个优化过程中增加了该算法。该操作会删去与当时节点色彩不匹配的相邻id。

重写了addAdjacencies函数后,现在能得到:

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。

通过删去色彩不匹配的节点,算法能够100%确认adjacentids实体中的任何id都是相邻节点。

终究,删去一切没有相同色彩邻接的节点。这进一步简化了算法,将节点总数减缩剩所需的节点。

过错的方法—递归法


TechLead说不能递归地做这个算法,由于会碰到仓库溢出。

尽管在必定程度上是正确的,但有几种方法能够缓解这个问题。要么用迭代法要么运用尾部递归。下面将看到迭代的比如,可是JavaScript不再将尾部递归作为一种本地言语特性。

尽管仍能够在JavaScript中模仿尾部递归,但这儿将坚持这种简略性,并创立一个典型的递归函数。

编写代码之前要弄清楚算法。关于递归,运用深度优先查找也行得通。“即便不知道核算机科学术语也不要紧。” 当我向一位搭档展现想出来的不同处理计划时,他如是说。

算法

先从一个节点开端,然后一向延续下去直到到达结尾。然后再回来并采纳下一个分支途径,直到扫描到整个接连块停止。

这是其间一部分。此外也有必要追寻所在方位和最大接连块的长度。

这儿做的是把函数分红两段。其间一个将保存最大列表,以及给每个节点进行至少一次循环时扫描过的ID。另一个则从一个未扫描的根节点开端,并履行深度优先遍历。

函数如下所示:

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,
} = prevState
return {
largestContiguousIds: (
contiguousIds.length
> largestContiguousIds.length
? contiguousIds
: largestContiguousIds
),
scannedIds: (
scannedIds
.concat(contiguousIds)
),
}
},
{
largestContiguousIds: [],
scannedIds: [],
},
)
.largestContiguousIds
)


是不是很夸大?原本不想把编码放上去,由于看起来实在是太乱了。

下面将一步一步将其简化。

递归函数

getContiguousIds 是递归函数,每个节点都会用到一次。该函数每次回来成果时,都会得到接连节点更新后的列表。

该函数只需一个条件,那便是:节点是否在列表里了?假如不是,那就再用一遍getContiguousIds。当它回来时,就会得到接连节点更新后的列表。而这列表也将回到减缩器,用作下一个adjacentId的状况。

你或许会困惑,为什么要给contiguousIds加值。当咱们concat当时节点到contiguousIds时都要给其加值。而每次递归下去,都要保证给adjacentIds进行循环时,将当时节点加到contiguousIds的列表中。

一向增加当时节点是为了保证递归不会无限进行。

循环

函数的下半段也会通过每个节点至少一次。

递归函数被减缩器包围着,减缩器会查看编码是否有被扫描过。假如有的话,就会继续循环直到遇到一个未被扫描的节点或许退出循环停止。

假如节点还未被扫描,就用getContiguousIds然后比及扫描完毕。这是同步进行的,但也会花上一点时刻。

当它得到一个contiguousIds的列表后,将其对着largestContiguousIds列表进行比较。然后将较大的那个值保存下来。

一同,把contiguousIDs加到scannedIds的列表中,以符号开展。

把这些列出来后,看起来就简略多了。

履行

就算运用了10K项,在三个随机色彩下它仍然没有仓库溢出。假如换成是同色,那就会构成仓库溢出。那是由于该递归函数通过的是10K的递归。

次序迭代

由于内存大于函数调用栈,下一步应该在一个循环中完结整个操作。

这儿将会把一切的节点列表记载下,并在跳出循环前继续将其增加和链接在一同。

这个方法要求在完结循环之前,将一切或许的节点列表保存在内存中。而递归版别中,只需最大的列表被保武星武艺存在内存中。

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
))
)


要不测验另一个更张狂的方法?能够测验从上往下拆开。将每个节点循环一次。可是现在有必要查看id是否在节点列表的列表contiguousIdsList中。

假如它不在contiguousIds的任何列表中,就将它和它的adjacentIDs增加进去。这样,在循环时,其他东西也就会和它衔接上。

假如节点在列表中,那它也有或许存在于其它列表中。有必要把它们悉数衔接起来,并从contiguousIdsList移除未衔接的节点。

就这样。

得到一切节点列表后,查看看哪个最大,就完结了。

履行

与递归版别不同的是,当一切10K项都是同个色彩时,这个方法是会完毕的。

除了这一点之外,这个方法比较慢,比原先估计的还慢。而这儿忘了考虑到一点,便是在功用评价中考虑对列表中的列表进行循环这一要素,由于这明显对功用有必定的影响。

随机迭代

这儿的主意是选用递归方法背面的概念,将其以迭代的方法进行运用。

我在花了一晚上大部分时刻企图想起来怎样动态地改动循环中的索引后,才想到了while(true) 。

有了这个“兵器”后,便打开“进犯”。由于花了许多时刻测验加速observable版别,终究决议了“抄小路”,以传统的方法改动数据。

该算法的意图是射中每个节点各一次,并只保存最大的接连块:

const getLargestContiguousNodes = ( 
nodes,
) => {
let contiguousIds = []
let largestContiguousIds = []
let queuedIds = []
let remainingNodesIndex = 0
let remainingNodes = (
nodes
.slice()
)
while (remainingNodesIndex < remainingNodes.length) {
const [node] = (
remainingNodes
.splice(
remainingNodesIndex,
1,
)
)
const {
adjacentIds,
id,
} = node
contiguousIds
.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 = 0
if (
remainingNodes
.length === 0
) {
break
}
}
}
return largestContiguousIds
}
module.exports = getLargestContiguousNodesIterative2


这儿不在列表增加从前扫描过的ID,而是从remainingNodes数组剪接数值。

其实不主张这么做,仅仅在做这些实例时我现已快失掉耐性,所以想测验不相同的东西。

详解

在这儿运用if块将它分红三个部分。

先从中心部分开端。查看有没有queuedIds。假如有的话,就进行一个循环使其透过已行列项,看它们是否在remainingNodes里。

而第三部分取决于第二部分的成果。假如没有任何queuedIds,而remainingNodesIndes为-1,那该节点列表就能够放一边了,并开端一个新的根节点。新根节的索引一直为0,由于remainingNodes正在进行剪接中。

回到第一个循环,其实能够运用while(true) ,可是为以防万一需求想一个方法。这在扫除过错时很有协助,由于有时分无限循环很难被判别出来。

之后,将节点剪接出来。将其参加contiguousIds的列表,然后将adjac我敢打赌,谷歌这道面试题你解不出来!entIds参加行列中。

履行

成果是这个方法简直和递归版别相同快。当一切节点是同一个色彩时,它是一切算法中最快的。

针对数据的优化


按色彩分组

已然已知蓝色会和蓝色同组,那在序列迭代版别中就能够将相似色彩的节点分组在一同。

将其分红三个更小的数组,会削减对内存的占用和对列表进行循环的次数。可是,这仍然处理不了一切色彩相同的状况下的问题。所以这并无法批改上述的递归版别。

此外,这也代表能够通过多线程操作,削减三分之二所需的履行时刻。

若按序列履行,只需求先运转三个数组中最大的那个。假如其他两个合起来仍然小过最大的那个,就不需求查看它们。

最大或许巨细

其实不需求在特定距离查看最大的列表,主张每次迭代都查看一次。

假如最大组大于或等于可用节点的一半(5K或以上),那很明显手中的列表便是最大的。

运用随机迭代版别,能够找到现在停止最大的列表和剩下的节点量。假如后者小于前者,那就代表已取得最大列表。

运用递归

尽管递归有其局限性,但仍然可被运用。所需做的就仅仅查看剩下节点的数量。若它们低于堆叠上限,就可转换去更快的递归版别。这方法尽管有危险,但跟着循环的深化,履行时刻也肯定会缩短。

运用 ‘for’ 循环

已然已知最大项数,从reduce函数切换到传统的for循环会带来一个微优点。

不知为啥,Array.protoype方法与for循环比起来,速度慢得很。

运用尾递归

相同的,这篇文章没有评论到observable版别,由于尾递归需求另一篇文章进行解说。

尾递归要评论的当地许多,尽管这个方法能够让递归版别运转,但它一直不如幻想中那样比while循环速度快。

RxJS:可保护性和功用

要重写这些函数有几种方法,可使它们更简略了解和保护。首要想到的首要处理计划便是运用Redux-Observable式的RxJS,但不运用Redux。

这其实是写这篇文章时面临的难题。原本的主意是以惯例方法编码,然后运用RxJS来传输数据,看看功用能够提高到什么水平。

这儿在RxJS制作了3个版别,并且加速了履行时刻。与之前关于变换器的文章不同的是,即便增加了行和列,这三个版其他速度都变得更慢了。

那个星期的每一晚简直都在构思处理这个问题的方法,乃至细心查阅每一条代码。每一次,认为有了更好的主意,可总是遭到JavaScript速度的约束。

当然其实能够进行许多优化方法,但价值是代码的可读性。这不是我想要的。

终究总算得到了一个Observable的处理计划,并且现在是最快的,所需时刻是其它计划的一半。这是全体上最大的改善。

唯有在每个节点是同个色彩时,才能用observable战胜占内存的序列迭代。没有其他时分了。严格来说,这也胜过递归版别,由于在那个状况下会仓库溢出。

终究数据


总的来说,最大的接连快平均在30-80个节点间。

以下是本篇文章所取得的数据:

随机色彩

同色


不管运转了多少次测验,每个方法的相对方位都是不变的。

能够发现,Redux-Observable方法在一切节点同色时就无法运转了。尽管我已测验许多方法来加速它的速度,可是终究杯水车薪。

游戏开发


在我的职业生涯中,曾两次遇过这种代码。那个时分我正在运用Lua开发我的独立游戏Pulsen,但那时的代码短许多。

有一次,我正在制作一张世界地图。它现已有预界说的节点列表,而我实时处理这个列表。这样的话,通过点击[LEFT], [RIGHT], [UP] 和 [DOWN] 键,就能够在世界地图上移动,即便视点略有误差。

我还编写了一个节点生成器,负责处理含有X和Y值的不知道项列表。听起来是不是很熟悉?那时有必要把屏幕上的网格居中,在HTML比在游戏引擎中更简略做到这一点。尽管如此,要会集一堆肯定定位的div也并不简略。

在这两个状况下,实时的履行时刻并不重要,由于在加载游戏时现已做了许多预处理。

这儿想着重的是,你或许会在职业生涯碰上TechLead的这个问题。或许,可是在典型的JavaScript运用程序中,速度并不是首要要素。

依据TechLeads的其它视频,可看出他在谷歌时运用的是Java。我猜想他面试的职位应该很垂青履行速度。他们很或许有一堆worker使命负责处理许多的数据,所以才会需求这样的一个处理计划。

可是呢,也有或许这仅仅一份关于HTML和CSS的作业,他或许仅仅在和应聘者恶作剧,谁知道呢!

正如终究数据显现的那样,看起来最糟糕的编码其实是运转最快的,并且还到达了一切需求。要保护它,就祝你好运了!

依据之前的经历,开发非RxJS版别花了更长的时刻。这或许是由于更快的版别需求通过全面的考虑。而Redux-Observable能够从小细节想起。

这是一个十分风趣但又让人抓破头的问题。起先,看起来真的很杂乱,可是把它拆成几个部分来看后,渐渐就有条理了~

留言 点赞 重视

咱们一同共享AI学习与开展的干货

欢迎重视全渠道AI垂类自媒体 “读芯术”