Google New Grad Interview Question: Subarray Sum Modulo K (Prefix Sum + Hash Set)

I recently helped a candidate review their Google New Grad coding interview, and one of the questions was a classic algorithm disguised with a slightly unusual statement. Although the wording looks different, once you recognize the underlying pattern, the solution becomes straightforward.

The Problem

Given a positive integer array nums and an integer k, determine whether there exists a non-empty contiguous subarray whose sum modulo 6,000,009 equals k.

Key Insight

Whenever you see contiguous subarray sum, think about prefix sums.

Let

prefix[i] = sum of the first i elements

Then the sum of subarray (i, j] is

prefix[j] - prefix[i]

The problem requires

(prefix[j] - prefix[i]) % M == k

where

M = 6,000,009

Rearranging the equation gives

prefix[i] % M == (prefix[j] - k) % M

Therefore, while scanning the array, we only need to keep track of all previously seen prefix sum remainders. For the current remainder cur, if we've already seen

(cur - k) % M

then we've found a valid subarray.

Python Solution

def HasSubarrayKMod(nums, k):
    M = 6_000_009
    k %= M

    seen = {0}      # Empty prefix handles subarrays starting at index 0
    cur = 0

    for x in nums:
        cur = (cur + x) % M

        if (cur - k) % M in seen:
            return True

        seen.add(cur)

    return False

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Common Interview Pitfalls

• Initialize the hash set with remainder 0. Otherwise, you'll miss subarrays that start from the first element.
• Normalize k by taking k %= M before processing.
• Explain why prefix sums work before writing code. Google interviewers care just as much about your reasoning as your implementation.

Interview Tips

Google New Grad coding interviews frequently present classic algorithms in unfamiliar forms. Whenever you encounter phrases like "subarray sum" together with "modulo", your first instinct should be prefix sums + remainder hashing. This pattern appears repeatedly across interview problems and is one of the standard techniques every candidate should master.

Rather than memorizing solutions, practice recognizing patterns such as prefix sums, hash maps, sliding windows, and two pointers under time pressure. Being able to clearly explain your thought process while coding often makes a bigger difference than simply arriving at the correct answer.

---

Need More Google Interview Practice?

If you're preparing for Google New Grad interviews and want realistic mock interviews, coding walkthroughs, or real-time interview assistance, check out Interview Show. Many candidates report significant improvements in problem recognition, communication, and interview performance after targeted preparation.