Google 2027 Summer Intern VO 两轮纯 Coding：树上岛屿计数 + 子数组和取余

面试概况

Google 实习现场轮，上来直接进入 coding，没有太多自我介绍环节。面试官节奏偏快，非常看重 clarify 边界、复杂度分析、follow-up 的原理推导。

两轮都是 45 分钟背靠背，算法手撕，无 BQ。
Round 1：树结构改编的岛屿连通分量题
Round 2：前缀和 + 取余子数组存在性题

Round 1：Tree-based Island Count（Medium）

题目（口述）

We have a binary tree, each node's value is either 0 or 1. An island is defined as a group of connected 1's. Two 1 nodes are connected only if they are direct parent and child. The island is surrounded by 0 or sits on the tree boundary. Count the total number of islands in this binary tree.

Output: 2（根节点和左孩子是一座岛，右下角的 1 被 0 隔开，是另一座岛）

Clarify（主动确认）

Connection only between parent and direct child, siblings are NOT connected?
A single node with value = 1 counts as one island?
Empty tree should return 0, correct?
Are we allowed to modify node values to mark visited nodes?

解题思路：DFS 连通分量计数

遍历树的所有节点，每遇到一个未访问的、值为 1 的节点，岛屿计数 +1。
DFS 递归，把和当前节点相连的所有 1 都标记为已访问。可以直接改成 0，省掉额外的 visited 集合。
递归继续处理左、右子节点。

def count_islands(root):
    def sink(node):                 # 把整座岛标记为已访问
        if node and node.val == 1:
            node.val = 0
            sink(node.left)
            sink(node.right)

    count = 0
    def walk(node):
        nonlocal count
        if not node:
            return
        if node.val == 1:
            count += 1
            sink(node)
        walk(node.left)
        walk(node.right)

    walk(root)
    return count

Follow-up

Time and Space complexity? —— O(N) time，N 是节点总数；树退化成链时递归栈最坏 O(N) space。
If we cannot modify original tree nodes, how to track visited nodes?
How to avoid stack overflow for an extremely deep tree? —— 提示：用栈做迭代 DFS。
If it becomes an N-ary tree instead of a binary tree, how to adjust the algorithm?

参考思路（Follow-up 2、3、4 一起解决）：树上没有环，每座岛都有唯一的「最高点」，也就是值为 1、且父节点不存在或父节点为 0 的节点。所以只要数出这样的节点个数就行：不用修改节点、不需要 visited 集合，用栈迭代也不会栈溢出，N 叉树只要把左右孩子换成遍历 children。

def count_islands_iterative(root):
    if not root:
        return 0
    count, stack = 0, [(root, 0)]          # (节点, 父节点的值)
    while stack:
        node, parent_val = stack.pop()
        if node.val == 1 and parent_val != 1:
            count += 1                      # 岛的最高点
        for child in (node.left, node.right):   # N 叉树改成 node.children
            if child:
                stack.append((child, node.val))
    return count

Round 2：Subarray Sum Modulo Problem（Medium–Hard）

题目（口述）

Given a positive integer array nums and an integer k. Create a function HasSubarrayKMod6000009. Return true if there exists a non-empty contiguous subarray whose sum modulo 6000009 equals k. Return false otherwise. MOD = 6000009.

Clarify（主动确认）

Subarray must be contiguous and non-empty?
All numbers in nums are positive integers.
k is in range [0, MOD-1]?
Empty input array should return false.

解题思路：前缀和 + 模同余

子数组和 sum[left ... right] = prefix[right + 1] - prefix[left]。

要求 (prefix[right + 1] - prefix[left]) mod MOD = k，变形得到：

prefix[left] ≡ (prefix[right + 1] - k) mod MOD

维护前缀和，每一步计算前缀和对 MOD 的余数。
用 HashSet 保存已经出现过的前缀余数。
遍历到当前前缀余数时，检查集合里是否存在目标余数，找到就返回 True。
遍历完都没找到就返回 False。

MOD = 6000009

def has_subarray_k_mod(nums, k, mod=MOD):
    if not 0 <= k < mod:
        return False
    seen, p = {0}, 0
    for x in nums:
        p = (p + x) % mod
        if (p - k) % mod in seen:      # 先查再加，保证子数组非空
            return True
        seen.add(p)
    return False

Follow-up

Time & space complexity? —— O(n) time，O(n) space。
If the array is massive and we cannot store all remainders in memory, what tradeoff can we make?
If the array can contain negative integers, does the same logic still work? What are the pitfalls?
Edge case when k = 0: what condition do we need to find?

参考思路：

Follow-up 2：余数最多只有 6000009 种，可以用一个长度为 MOD 的 bitset 代替 HashSet，只占约 750 KB，和数组长度无关，而且可以流式读取。

Follow-up 3：逻辑仍然成立，但要保证余数非负。Java / C++ 里要写 ((p + x) % mod + mod) % mod，同时注意前缀和溢出，每一步都要取模。

Follow-up 4：k = 0 时，等价于找到两个相同的前缀余数（包括开头的 0）。

面试总结 / 注意点

Google 重点看 clarify 环节。不要读完题目直接上手写代码，主动问边界条件是加分项。
模运算很容易踩坑，要注意负数取余的数学定义，以及不同编程语言之间的差异。
Follow-up 不是附加题，而是面试的核心打分点，考察你能不能理解算法的底层原理，而不是单纯背题。