这次 Google 面试一共考了几道 coding 题，题目之间难度逐步上升，主要覆盖 hash map、DFS、two pointers、heap / k-way merge。整体不是偏数学的怪题，更像 Google 常见的基础数据结构组合题，重点是候选人能不能把题意澄清清楚，并在代码里处理好边界情况。

第一题：比较两个数组的频次差异

面试官先给了两个整数数组 A 和 B，要求返回两个数组 C 和 D。

C 表示：A 中比 B 多出来的元素。
D 表示：B 中比 A 多出来的元素。

这里不是简单的 set difference，因为数组里可能有重复数字，所以必须比较每个数字出现的次数。

例如：

A = [1,4,3,4,2,5,5]
B = [1,2,3,6,5]

1、2、3 在两个数组里出现次数一样，不需要返回。
4 在 A 中出现 2 次，在 B 中出现 0 次，所以 C 里要有两个 4。
5 在 A 中出现 2 次，在 B 中出现 1 次，所以 C 里还要有一个 5。
6 在 B 中出现 1 次，在 A 中出现 0 次，所以 D 里要有一个 6。

所以结果可以是：

C = [4,5,4]
D = [6]

顺序不重要，只要频次正确即可。候选人一开始先说了暴力解法：遍历 A，看每个元素是否在 B 中，再反过来处理 B，但这样复杂度可能达到 O(m*n)。随后优化成使用 hash map / Counter，分别统计 A 和 B 中每个数字的出现次数，再比较两个计数表。

最终解法是：对每个数字 x，如果 countA[x] > countB[x]，就往 C 里加入 countA[x] - countB[x] 个 x；如果 countB[x] > countA[x]，就往 D 里加入差值个数的 x。时间复杂度是 O(m+n)，空间复杂度也是 O(m+n)。

第二题：Binary Tree 中有多少组连续的 1

第二题给一棵二叉树，节点值只有 0 和 1。题目要求返回：树中一共有多少个由 1 组成的 connected group。

这里的 connected group 指的是：如果几个值为 1 的节点通过父子边连在一起，它们就属于同一组。如果中间被 0 隔开，就算不同组。

例如图里的二叉树中，有些 1 是父子相连的，它们组成同一个 group；有些 1 被 0 隔开，就要单独算一组。面试官让候选人判断图中的答案，候选人确认结果是 4 组。

这题可以用 DFS。最干净的判断方式是：当我们访问一个值为 1 的节点时，如果它的父节点不是 1，说明这里开始了一个新的 group，答案加一。

也就是说，DFS 时带一个参数 parentIsOne：

如果当前节点是 1，并且 parentIsOne == false：
    count += 1

然后继续递归左右子树，并把 current.val == 1 传给孩子。

这个做法比在左右子树返回复杂状态更直观，也不容易重复计数。每个节点只访问一次，所以时间复杂度是 O(n)，递归栈空间复杂度是 O(h)，其中 h 是树高。

第三题：Merge Two Sorted Integer Streams

接下来面试官给了一个接口：

interface SortedIntegerStream {
    int next();        // 返回 stream 中下一个整数，顺序从小到大
    boolean hasNext(); // 判断 stream 中是否还有整数
}

每个 stream 都会按从小到大吐出整数。候选人不能直接访问内部数组，只能通过 hasNext() 和 next() 读取数据。比如一个 stream 内部包含 [1, -1, 0]，实际调用 next() 的返回顺序是 -1, 0, 1。

题目要求实现：

public List<Integer> merge(SortedIntegerStream s1, SortedIntegerStream s2)

也就是把两个 sorted stream 中的所有整数合并成一个升序 list。重复数字要保留。候选人确认了只能用公开接口，并且重复元素不能丢。

这题本质是 two pointers merge。虽然没有数组下标，但可以用两个变量缓存 s1 和 s2 当前读到的值。每次比较两个当前值，把较小的加入 result，然后只推进对应的 stream。

关键细节是：next() 会消耗元素，所以不能在比较时反复调用 next()。正确写法是先缓存当前值，比如 v1、v2，比较后再读取对应 stream 的下一个值。

当两个 stream 都还有值时持续比较；如果其中一个 stream 结束，就把另一个 stream 剩下的值全部追加到结果中。时间复杂度是 O(m+n)，额外空间是 O(1)，不包括返回结果。

第四题：Merge 多个 Sorted Integer Streams

最后一题是第三题的扩展。原来只合并两个 stream，现在输入变成：

public List<Integer> merge(List<SortedIntegerStream> streams)

也就是给定多个 sorted integer stream，返回所有数字合并后的整体升序 list。

如果每次都扫描所有 stream 找当前最小值，效率会比较低。候选人很快想到用 min heap。做法是：先从每个非空 stream 中读取一个数字，把 (value, streamIndex) 放进 heap。之后每次从 heap 中弹出最小值，加入 result；再从这个数字所属的 stream 继续读取下一个数字，如果还有，就放回 heap。

heap 中最多保存每个 stream 当前的一个候选值。如果有 m 个 stream，每个 stream 平均有 n 个整数，总共有 m*n 个数字。每个数字进出 heap 一次，每次 heap 操作是 O(log m)，所以总时间复杂度是：

O(m * n * log m)

空间复杂度除结果外是 O(m)。面试辅助稿里也记录了这个复杂度分析：总共有 m*n 个数，heap 大小是 m，每次 pop / push 需要 log(m)。

面试总结

这场 Google 面试整体考得很基础，但每题都有容易失分的细节。第一题不能当 set difference 做，因为重复次数要保留；第二题不能重复计算 connected group，最好用 DFS 判断“当前 1 是否是新 group 的起点”；第三题要注意 next() 会消耗 stream，必须缓存当前值；第四题要自然从 two pointers 推广到 min heap。

从面试表现来看，候选人能够先确认题意，再从暴力解法讲到优化解法，最后补充复杂度分析，这是 Google coding interview 中比较稳的答题节奏。

csoahelp 做的就是这种场景里的实时辅助，题目刚读完就能给出完整思路，现场不用卡壳。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~