Google 2027 Summer Intern VO, Two Pure Coding Rounds: Islands in a Tree + Subarray Sum Modulo

Overview

Google intern final rounds jump straight into coding with barely any introduction. The pace was fast, and the interviewers cared a lot about clarifying edge cases, complexity analysis and reasoning through follow-ups.

• Two back-to-back 45-minute algorithm rounds, no behavioral.
• Round 1: an island-counting problem adapted to a tree
• Round 2: a prefix sum + modulo subarray existence problem

Round 1: Tree-based island count (Medium)

Problem (verbal)

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.

        1
       / \
      1   0
     /     \
    0       1

Output: 2 (the root and its left child form one island; the 1 at the bottom right is cut off by a 0 and forms another)

Clarify (ask proactively)

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

Approach: count connected components with DFS

1. Visit every node; each time you find an unvisited node with value 1, increment the island count.
2. DFS from it and mark every connected 1 as visited — you can set them to 0 and skip a separate visited set.
3. Continue recursing into the left and right children.

def count_islands(root):
    def sink(node):                 # mark the whole island as visited
        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-ups

1. Time and Space complexity? — O(N) time, N = number of nodes; O(N) worst-case recursion stack for a skewed tree.
2. If we cannot modify original tree nodes, how to track visited nodes?
3. How to avoid stack overflow for an extremely deep tree? — Hint: iterative DFS with a stack.
4. If it becomes an N-ary tree instead of a binary tree, how to adjust the algorithm?

Reference idea (solves follow-ups 2, 3 and 4 at once): a tree has no cycles, so every island has a unique "top" node — a node with value 1 whose parent is missing or 0. Just count those nodes: no mutation, no visited set, an iterative stack avoids overflow, and for an N-ary tree you iterate over children instead of left/right.

def count_islands_iterative(root):
    if not root:
        return 0
    count, stack = 0, [(root, 0)]          # (node, parent's value)
    while stack:
        node, parent_val = stack.pop()
        if node.val == 1 and parent_val != 1:
            count += 1                      # top-most node of an island
        for child in (node.left, node.right):   # for an N-ary tree use node.children
            if child:
                stack.append((child, node.val))
    return count

Round 2: Subarray sum modulo (Medium–Hard)

Problem (verbal)

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 (ask proactively)

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

Approach: prefix sums + modular congruence

A subarray sum is sum[left ... right] = prefix[right + 1] - prefix[left].

We need (prefix[right + 1] - prefix[left]) mod MOD = k, which rearranges to:

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

1. Maintain the prefix sum and take it modulo MOD at each step.
2. Keep a HashSet of prefix remainders seen so far.
3. At each position, check whether the target remainder is in the set; if so, return True.
4. If the scan finishes without a match, return 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:      # check before inserting so the subarray is non-empty
            return True
        seen.add(p)
    return False

Follow-ups

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

Reference ideas:

• Follow-up 2: there are at most 6000009 remainders, so a bitset of length MOD can replace the HashSet — about 750 KB regardless of the array length, and it works on a stream.
• Follow-up 3: the logic still holds, but remainders must be non-negative. In Java / C++ write ((p + x) % mod + mod) % mod, and take the modulo at every step to avoid prefix-sum overflow.
• Follow-up 4: with k = 0 you need two equal prefix remainders (including the initial 0).

Takeaways

1. Google weighs the clarify step heavily. Don't start coding right after reading the problem — asking about edge cases earns points.
2. Modular arithmetic is full of traps: mind how negative remainders are defined and how languages differ.
3. Follow-ups aren't extras — they're the core of the score, testing whether you understand why the algorithm works rather than reciting it.