Google SDE 2027 Intern: Subarray Sum Modulo Equals k + Three Follow-ups

Overview

Google went straight into coding — no warm-up! The interviewer was strict: after I explained the idea she didn't let me code until we'd covered the first follow-up. Three follow-ups in total.

Problem

Given an array of positive integers nums and an integer k, write a function that decides whether there is a non-empty contiguous subarray whose sum modulo 700001 equals k.

Approach: prefix-sum remainders + hash set

Let P[i] = nums[0] + ... + nums[i-1]. The subarray nums[i..j-1] sums to P[j] - P[i].

The condition is (P[j] - P[i]) mod M == k, i.e. P[i] mod M == (P[j] - k) mod M.

While scanning, keep the set of prefix remainders seen so far and check at each position whether (P[j] - k) mod M is in it. Time O(n).

M = 700001

def has_subarray_mod_k(nums, k, m=M):
    if not 0 <= k < m:
        return False
    seen, p = {0}, 0           # the empty prefix has remainder 0
    for x in nums:
        p = (p + x) % m
        if (p - k) % m in seen:    # check before inserting so the subarray is non-empty
            return True
        seen.add(p)
    return False

Follow-up 1: negatives are now allowed — does it still work?

If the original solution used a sliding window, it breaks: with negatives the window sum is no longer monotonic.

The prefix-remainder approach still holds; you just need non-negative remainders. Python's % already returns a non-negative result; in Java / C++ write ((p + x) % m + m) % m.

Follow-up 2: length of the shortest such subarray

Replace the set with a hash map storing the most recent index of each remainder. The shortest subarray ending at j has length j - last[(P[j] - k) mod M]:

def shortest_subarray_mod_k(nums, k, m=M):
    if not 0 <= k < m:
        return -1
    last, p, best = {0: -1}, 0, float("inf")
    for j, x in enumerate(nums):
        p = (p + x) % m
        i = last.get((p - k) % m)
        if i is not None:
            best = min(best, j - i)
        last[p] = j                # update after the lookup so we use an earlier index
    return -1 if best == float("inf") else best

Follow-up 3: length around 10⁶, limited memory, streaming input

The algorithm is already a single pass that never looks back: the only state is the current prefix remainder p and the remainder table.

There are only M = 700001 possible remainders, so the table holds at most 700001 entries — memory is O(M), independent of the array length. You can even replace the hash map with an integer array of size M to save more memory.

Takeaway

The key insight is that the modulo turns the problem into pairing prefix remainders. These questions are demanding — try writing it yourself and think through how you'd answer each follow-up. Happy to discuss solutions!