爱彼迎面试

作者: 千寻客 | 来源:发表于2019-08-18 00:28 被阅读0次

今年找工作面试的众多机会之一有爱彼迎。这是一家外企，据说福利待遇很好，而且不要求996。不要求加班这种做法很符合我的观念，因为我觉得一个公司不应该是靠要求员工加班来达到工作效果，而应该靠提升效率来实现。计算机领域是从外国起源的，外国人在这方面有很多心得和方法论，读一些大师巨作可以略知一二。所以我对外企有一种莫名其妙的向往，不是崇洋媚外，因为他们确实比我们先进。用一句老话说，我们不能讳疾忌医。只不过我最后还是没有去成，因为挂在了最后两轮面试上了。

爱彼迎的面试一共有7轮：

第〇轮是在线面试，考一个算法题，题目很贴合他们应用的场景。
第一到四轮是现场技术面试，考题涉及算法和架构。
第五、六轮考核心价值观。「我挂这了」

他们得面试更看重一些基础的能力，比如代码质量，逻辑能力等等，每一轮技术面试都会考核这些基础的点。相反，其他家公司比较看重的高并发高可用这些能力，在他们这儿是当成可选项来看待的。因为他们认为，如果候选者已经有了较好的逻辑能力，那么理解高并发问题并给出应对策略，那也是自然而然能达到的事情（即使现在不行，不久也能行）。

第〇轮：在线面试

我被考核的是一个分页问题，题目大概是这样的：有一个元素列表，每个元素都有一个所属的类别（Elem{value, category}，后面我们会用{a, 1}表示元素a属于类别1），要求把这个列表分页展示，使得每一页中没有类别相同的元素（除了最后几页已经没有更多元素了）。比如有如下的列表，按每页5个进行分页

// 输入一个一维列表
[ 
  {a, 1}, {b, 2}, {c, 1}, {d, 3}, {e, 4},
  {f, 5}, {g, 1}, {h, 2}, {i, 3}, {j, 4},
  {k, 5}, {l, 1} 
]

// 输出一个二维列表，每个子列表表示一页
[
  // {c, 1}因为与{a, 1}属于同一个类别，所以往后移
  [ {a, 1}, {b, 2}, {d, 3}, {e, 4}, {f, 5} ], // page 1
  // {c, 1}移到了本页，导致{g, 1}会与它冲突，将{g, 1}再往后移
  [ {c, 1}, {h, 2}, {i, 3}, {j, 4}, {k, 5} ], // page 2
  // {g, 1}与{l, 1}虽然同属一个类别，但是已经没有更多的页了，所以不再分页
  [ {g, 1}, {l, 1} ] // page 3
]

这个题目还是比较复杂的，不容易一眼看出问题的解，比较考核逻辑能力。这里先用最朴素的思路来解决这个问题。

解决复杂的问题我的思路大概是这样的：首先需要对问题抽丝剥茧，并用最朴素的解决方法（按照题目所说的逻辑一步一步执行直接求解）来描述问题。这样就能得出一个可行解。然后再分析这个可行解是否有可优化空间，进而决定是否要寻找更优解。

对于一个问题来说，如果最朴素的解法都总结不出来，那么这个题目就基本挂了。如果能总结出最朴素的解，那么其实已经达到了最基本的要求。

对于一个解法，分析复杂度和可优化空间是一个基础能力，因为能分析出复杂度和可优化空间，我们才有希望找到更优解。如果能分析出复杂度和可优化的空间，那么即使找不到更优解，其实也已经超越了大多数的人了。

如果能根据分析出的可优化空间，设计算法得到更优化的解；那么这时应该属于优秀这样的一拨人了。因为这些人面对问题不仅能分析出问题的关键点所在，还能给出符合期望的解决方法，那么未来他也必然能处理工作中遇到的各种问题，并带来更多更优的方法使得公司的解决方案越来越优化。

思路一：朴素算法

使用输入列表依次构建出每一个结果页。对于每一页，从头开始遍历输入列表中的元素，跳过那些类别已经在结果页中出现的元素，把未出现的元素从输入列表摘除并添加到结果页中。这样每构建出一个页面，也就有一部分元素从输入列表中摘除了。然后对于变更了的输入，重复这个过程构建下一页。直到构建完成所有的页面。构建过程图示如下：

输入
[ 
  {a, 1}, {b, 2}, {c, 1}, {d, 3}, {e, 4},
  {f, 5}, {g, 1}, {h, 2}, {i, 3}, {j, 4},
  {k, 5}, {l, 1} 
]

构建第一页：
[ 
  [ {a, 1}, {b, 2}, {d, 3}, {e, 4}, {f, 5} ]
]
// 输入变更为
[ {c, 1}, {g, 1}, {h, 2}, {i, 3}, {j, 4}, {k, 5}, {l, 1} ]

构建完第二页
[ 
  [ {a, 1}, {b, 2}, {d, 3}, {e, 4}, {f, 5} ],
  [ {c, 1}, {h, 2}, {i, 3}, {j, 4}, {k, 5} ]
]
// 素材库变更为
[ {g, 1}, {l, 1} ]

构建完第三页
[ 
  [ {a, 1}, {b, 2}, {d, 3}, {e, 4}, {f, 5} ],
  [ {c, 1}, {h, 2}, {i, 3}, {j, 4}, {k, 5} ],
  [ {g, 1}, {l, 1} ]
]
// 输入变更为
[]

复杂度分析

算法写完之后一定要对算法的复杂度进行分析，一般这个分析过程也是考核比较多的。

假设页长为 $k$ ，输入列表长度为 $n$ 。由于每次遍历只需要把当前页装满就结束了，而不需要遍历整个完整的输入列表。所以如果分散性比较好，那么每页构建的复杂度是 $O(ck) = O(k)$ , 其中 $c$ 为常数，页数为 $\lceil n/k\rceil$ ，所以期望复杂度是 $O(\lceil n/k\rceil) * O(ck) = O(n)$ 。

最坏的情况下，构建一页可能需要遍历完整个输入列表，复杂度是 $O(n)$ ，所以最坏复杂度是 $\lceil n/k\rceil O(n)= O(n^2/k)$ 。

但是在最坏的情况下，这里其实有重复的计算。比如当前页中缺少某类元素，需要遍历到输入的末尾才能找到，那么这一页之后的剩下的页如果也缺少这一类元素，那么它也一定要遍历到素材库的末尾才能找到。但是我们的算法中没有利用这个结论，下一页如果还需要这个元素，也难以避免的要从输入的头开始遍历到末尾。这中间的遍历过程就是重复计算。

这种重复的计算就是可优化空间。如果想要优化算法的复杂度，那就是要消除这中间的重复计算。于是有了下面一种思路。

思路二：消除重复计算

根据输入的列表长度 $n$ 和页大小 $k$ ，其实能知道最后结果会分成多少页，每一页多大。我们可以尝试遍历输入列表中的每个元素，并把它填到结果页列表中。因为这样的化，我们可能能使用一些方法简单定位每个元素应该添加到哪一页中。如果这种简单判定方法 $F$ 的复杂度是 $f_i$ ，那么总的复杂度就是 $\sum_{0\le i\lt n} f_i = n \overline{f_i}$ ，我们只要 $O(\overline{f_i}) \lt O(n)$ ，算法就有优化。

// 对于输入
[
  {a, 1}, {b, 2}, {c, 1}, {d, 3}, {e, 4},
  {f, 5}, {g, 1}, {h, 2}, {i, 3}, {j, 4},
  {k, 5}, {l, 1} 
]
// 结果页结构如下
[
  [?, ?, ?, ?, ?],
  [?, ?, ?, ?, ?],
  [?, ?]
]

// 这使假设遍历到{e, 4}，就是往下面这样的结构中添加{e, 4}，
// 很显然我们知道{e, 4}应该加入到第一页中
[
  [ {a, 1}, {b, 2}, {d, 3}, ?, ?],
  [ {c, 1}, ?, ?, ?, ?],
  [?, ?]
]

对于这个解法，我们能看到很多特征和结论，这里将这些特征都依次表述为各个命题。

每个命题都能总结出一些约束（即不会出现什么情况），借此我们设计算法时可以想办法避免这些不符合约束的计算。这些不符合约束的计算就是之前算法中存在的重复的计算。避免它们这些计算就是优化。

所以对于能总结出来的命题，只要它是真命题，能带来之前我们所不知道的约束，那么这个命题就是有用的。直接给我们的算法提供帮助，或者能帮助我们发现更容易使用的命题。

下面列举了一系列的命题和推论。这些命题和推论不是一下子都看出来的，而是先看到最简单最明显的命题。有了前面的命题和推论，才容易发现后面的命题和推论。这样才一步步找到能帮助解决问题的命题和推论。

命题0-1：遍历到某一步的时候，结果页列表中有一些页已经填满了（已满），有一些页已经填了一部分元素（部分满），而有一些页可能还是空的。这些页的顺序符合下面两个特征

所有已满的页都出现在部分满的页前面；
所有部分满的页都排在所有空页的前面。

看到这些特征的时候需要证明一下，避免猜测错误。我们都可以用反证法来证明我们的结论。

证：对于第一个特征，假设有页不符合这个特征，即存在已满的页排在了部分满页的后面。我们知道已满页里面的元素属于不同类别，所以已满页中的元素类别数量就是 $k$ ，他前面的部分满的页面里面的元素数量小于 $k$ ，元素类别数量也肯定小于 $k$ ，所以后面的这个已满页中一定存在至少一个元素，它跟前一页中的所有元素都不属于同一类别（抽屉原理）。根据题目的规则，这个元素就不应该放在后面的已满页中，而应该排在前面的部分满的页面里面。所以这种情况是不合理的，也就是说部分满的页面后面不应该存在已满的页面。

证：对于第二个特征，假设空页后面存在部分满的页面，我们知道部分满页面里面的所有元素都应该往空页中挪。所以这种排列也是不合理的，即空页后面不应该存在有元素的页面。

所以处理输入元素的任何一个时刻，页表的结构都是下面这样的，不会乱序。

[ 已满，...，已满，部分满，...，部分满，空，...，空]

命题0-2：任何一个新的元素都只可能往部分满和第一个空的页面添加。
命题0-3：排在后面的部分满的页面的元素类别集合，是它前面所有部分满页面的元素类别集合的子集。这很容易理解，因为任何一个元素，只有它与前一个部分满的页面中的某个元素类别相同，他才可能被放置到后一个页面中。
命题0-3推论：前一个部分满的页面可以接受的元素，能被它后面所有部分满页面所接受。很容易证明：假设某个元素可以被某个部分满的页面接受，那就意味着这个元素的类别与该页中的所有元素的类别都不相同。由命题3我们知道后一个部分满页的元素类别集合是前一个部分满页的元素类别集合的子集，所以刚才的元素的类别一定也不与后面的部分满页中的元素相同，所以后面的页面也能接受这个元素。得证。

根据命题0-3推论，我们知道任何一个元素在部分满的页面列表中，必然有一个特殊页，它之前的所有部分满页都不能接受这个元素，它、包括它之后的所有部分满页都能接受这个元素。此时这个元素应该加入到这一个分界点的部分满页中。所以我们可以用二分法找出这个位置所在。到这里我们可以描述一下具体算法：

算法说明

维护两个指针：指向第一个未满的页面和第一个空页，遍历输入列表，对于每个元素，用二分法找出能接受这个元素的分界点页面。如果找到了这样的页面，那就把元素加这个页面中；如果找不到这样的页面，那就意味着这个元素与所有的页面都有冲突了（页中存在同类别的元素），那么就按照规则把它加到第一个未满的页面中。直到遍历完输入列表中的每个元素，就构建出结果页表了。

[ 已满，...，已满，部分满(left)，...，部分满，空(right)，...，空]

复杂度分析

假设部分满页面的数量为 $l$ ，有 $(l \le n)$ 。用二分法找到适当的页面需要的计算量是 $\log l$ ，那么总的计算复杂度是 $\sum_{0\le i\lt n} {\log l_i} \le \sum_{0\le i\lt n} {\log n} = n \log n = O(n\log n)$ ，所以最坏情况下的计算复杂度是 $O(n\log n)$ ，比第一种算法已经有了明显的优化。

第一轮现场面试：算法

给定一棵树，每个节点都有两种状态a/b，两种状态之间可以翻转。这棵树的每个子节点上都可以做flip操作，flip操作会把该节点为根的子树从根节点开始所有隔层节点的状态都做翻转（a->b，或者b->a）。如图1：

如果在1号节点上flip，那么5, 6, 7, 12, 13, 14这些节点状态都会发生翻转；
如果在3号节点上flip，那么9, 10, 11号节点会发生翻转。

图1: 树节点flip操作

现在给一棵树，并告知一个状态需要翻转（起始状态与结束状态不同）的节点集合，问将对这棵树最少需要多少次flip操作，才能实现这个状态的变更？

分析

按照题意，每个节点只有两个状态，每次状态翻转就是两个状态互切。所以对于任意一个节点，很容易得出结论：

命题1-1：节点状态被翻转的总次数如果为奇数次，那么这个节点最终状态就被翻转了；偶数次（包含0次），那么最终这个节点状态就保持不变。

命题1-1推论1：最优解中每个节点被执行flip的次数最多1次。

证：因为假设有某个最优解中存在节点 $n_i$ 被执行了多于1次flip操作，即flip操作的次数 $\ge 2$ 。取这个节点上的2次flip操作进行分析，我们知道这两次操作导致状态被翻转的节点集合是一致的（由逐层孙子节点组成的集合），所以这2次flip操作会导致这些受影响的节点的状态被翻转了2次。由命题1-1我们知道如果没有这2次flip操作，节点的最终状态与假设中的最优解的状态是一致的，即它也是一个可行解。而且它的flip次数更少，所以它是一个更优解，这与前面提到的存在的最优解的假设相互矛盾，所以假设不成立，即：不能存在最优解需要在节点上执行多余1次的flip操作。得证。

我们可以将最优解的工作过程描述成这样的一个过程：输入的树中所有节点的某个子集按照一定的顺序依次执行flip操作，使最后结果中的需要翻转的节点状态都被翻转了奇数次，不需要翻转的节点状态都被翻转了偶数次。

命题1-1推论2：最优解中需要flip操作的各节点的flip操作的顺序是无关的。即按照各节点按照任意顺序flip，都能得到最优解。即最优解可以描述成一个需要执行flip操作的节点集合。长度最短的集合就是最优解。

这一点由命题1-1中的状态翻转的奇偶性容易得证，这里不再详述。

flip操作是隔层翻转节点状态，父节点上的flip不影响子节点，而是影响孙子节点。这个规则其实很复杂，很影响我们判断flip操作带来的影响。如果我们把一棵树所有路径按照隔层节点重新组织，比如a->b->c->d->e->f，就变成a->c->e和b->d->f两条路径，一棵树就可以重新构造成一个森林。比如图1中的树结构，我们就可以构造出如下的森林：

图2：隔层重组

对于这个森林，我们将flip操作重新定义成：在某个节点上flip，则翻转以该节点为根的整棵子树的所有节点的状态。为了区分森林中新定义的flip操作和原始问题中的flip操作，我们将原始问题中flip操作记为 $f$ ，森林中按照新规则flip记为 $f'$ 。容易看到：

命题1-2：对于任意节点，执行 $f$ 操作和执行 $f'$ 操作，造成状态翻转的节点集合是完全相同的。

命题1-2推论1：对于任意一个问题输入，执行 $f$ 操作的最优解与执行 $f'$ 操作的最优解是相同的。

证：由命题1-2我们知道对于任意一个节点集合，这些节点执行 $f$ 操作造成节点状态翻转的情况（任意一个节点状态被翻转了多少次）与在执行 $f'$ 操作是完全一致的。所以如果存在一个需要翻转的节点集合对于 $f$ 操作是可行解，那么对于 $f'$ 操作也就是可行解；反之亦然。即 $f$ 与 $f'$ 的解空间是一致的，所以他们的最优解也是一致的。

森林是由一棵棵独立的树构成的，对森林中的节点做 $f'$ 操作导致状态被翻转的节点一定也在当前树里面。最终需要被翻转的节点都分散这些树中，我们能知道，每棵树中需要翻转的节点的状态翻转都靠当前树中节点的 $f'$ 操作实现。即整体的大问题可以分解成每棵树的子问题来解决。

命题1-3：如果每棵树 $T_i$ 的子问题的最优解需要执行 $f'$ 的节点集是 $S_i$ ，那么 $S = S_1 \cup S_2 \cup ... \cup S_n$ 是整个森林的大问题的最优解。

证：替换法。假设对于整个大问题存在另一个另一个最优解 $S'$ ，该最优解在树 $T_i$ 中的节点集合为 $S'_i$ ，那么可以肯定 $S'_i$ 是 $T_i$ 的可行解。由于 $S_i$ 是 $T_i$ 的最优解，所以 $|S_i| \le |S'_i|$ 。如果我们把最优解 $S'$ 中 $S'_i$ 替换成 $S_i$ 得到 $S'_{ri} = (S' - S'_i) \cup S_i$ 也是一个可行解。对于任意 $i \not = j$ ，我们知道 $S'_i \cap S'_j = \varnothing$ ，且 $S_i \cap S'_j = \varnothing$ ，所以 $|S'| = \sum_i |S'_i|$ 。替换后 $|S'_{ri}| = (\sum_{j \not = i} |S'_j|) + |S_i| \le |S'|$ 。由于 $S'$ 是最优解，所以 $S'_{ri}$ 也是最优解。经过这样对每棵树的集合进行替换，最后就得到了 $|S = S_1 \cup S_2 \cup ... \cup S_n| \le |S'|$ ，所以 $S$ 就是整个大问题的最优解。

命题1-4：树不会有多于一个符合命题1-1推论1特征（每个节点最多执行1次 $f'$ ）的可行解。

证：反证法。假设存在不止一个符合命题1-1推论1的可行解，我们假设有两个符合调节的可行解 $S_1$ 和 $S_2$ ，那么 $S_1 \not= S_2$ 。假设 $A=S_1-S_2$ ， $B = S_2-S_1$ ，有 $A \cap B = \varnothing$ 。两个解都是可行解，就要求对 $A$ 中所有节点做 $f'$ 操作与对 $B$ 中所有节点做 $f'$ 操作造成的节点状态翻转情况相同（假设推论1）。

我们从 $A$ 和 $B$ 中任选一个节点 $n_j$ ，从这个节点一直往树的根上寻找，直到找到某个节点 $n_i \in A \cup B$ ，但是它的任意一个祖先节点 $n_x \notin A \cup B$ 。我们可以肯定 $n_i$ 只属于 $A$ 和 $B$ 中的某一个集合，而不属于另一个集合。我们假设 $n_i \in A, n_i \notin B$ 。那么 $A$ 中对 $n_i$ 做 $f'$ 操作就会造成 $n_i$ 节点的状态被翻转；但是该节点不是 $B$ 中任何节点的子节点，所以 $B$ 中所有节点都执行了 $f'$ 之后也不会导致 $n_i$ 的状态被翻转。所以分别对 $A$ 和 $B$ 执行 $f'$ 造成的翻转情况时不相同的，即假设推论1不成立，所以最初的假设不成立，即：不存在多个不同的最优解。得证。

假设树存在1个符合命题1-1推论1特征的可行解，根据命题1-1推论1的结论，这个可行解就是最优解。所以我们只需要构建出一个符合这种特征的可行解就行。按照如下规则我们就可以构建符合特征的可行解（解1）。

如果树 $T$ 的根节点 $n_{r}$ 需要翻转状态，那么最优解中在它上面就需要 $f'$ 操作；如果不需要翻转状态，那就不需要 $f'$ 操作。
树中每个非根节点，如果它的是否需要翻转的需求与它的父节点不同，那么最优解中它就需要 $f'$ 操作；如果与父节点相同，那就不需要 $f'$ 操作。

算法

Algorithm: min-flip
input：
    T tree 
    N (nodes in T whose state should be flipped)
output：
    F: min flip operations

F <- transform(T)
result <- 0
for t <- F.anyTree()
    F <- F - {t}
    result <- result + flip(t)

return result

其中

transform是将树 $T$ 转换成命题1-2中提及的森林。只需要对树节点遍历一次就可以完成，复杂度是 $O(n)$ 。
flip操作是按照解1中所述的规则算森林中的一棵树的结果，返回该树需要的最少flip次数。假设该树的节点个数为 $k$ ，那么这部操作的复杂度是 $O(k)$ 。整个循环的flip的总复杂度是 $O(\sum_i k_i) = O(n)$ 。

所以算法的总复杂度是 $O(n)$

<<未完待续>>

爱彼迎面试

第〇轮：在线面试

思路一：朴素算法

思路二：消除重复计算

第一轮现场面试：算法

分析

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读