Google·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Google SWE coding round with a streaming subarray problem. Not much context shared beyond the problem itself, but it's the kind of question that looks approachable until you actually have to output the answer after every single input.

Questions Asked (1)

Given a stream of integers arriving one at a time, after each new integer is received, find the length of the longest contiguous subarray whose average equals a target value S.

Algorithms & Data Structures

Author's notes

The online part is what makes this tricky.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem constraints and edge cases, then transform the average condition into a prefix sum condition: (prefix[j] - prefix[i]) / (j - i) = S implies prefix[j] - S*j = prefix[i] - S*i. Use a hash map to track the earliest occurrence of each transformed prefix value, and for each new element, check if the current transformed prefix has been seen before to compute the longest valid subarray ending at the current index.

Pro tip: Mention that the transformed prefix values can be non-integers if S is not an integer, so use a hash map with double keys or scale values to avoid floating-point precision issues. Also, note that the longest subarray might not end at the current index, so maintain the global maximum length.

1. Clarify the problem

Ask about constraints: Is S an integer? Can the subarray be empty? What should be returned if no such subarray exists? Confirm that the stream is infinite and we need to answer after each element.

2. Transform the condition

Derive that the average condition is equivalent to (prefix[j] - prefix[i]) = S * (j - i), which rearranges to prefix[j] - S*j = prefix[i] - S*i. Define a transformed prefix value T(k) = prefix[k] - S*k.

3. Design the data structure

Use a hash map to store the first occurrence of each transformed prefix value. Initialize with T(0) = 0 at index 0. For each new element, update the prefix sum and compute T(current index).

4. Process each element

After computing T(i), check if it exists in the hash map. If yes, the subarray from the stored index+1 to i has average S, so update the maximum length. If not, store T(i) with index i.

5. Return the result

After each element, output the current maximum length. If no valid subarray has been found, return 0 or as specified.

Key Points to Mention

Prefix sum transformation to eliminate division and avoid floating-point comparisons.
Hash map storing the earliest index for each transformed prefix value to maximize length.
Time complexity O(1) per element, O(n) total, and space complexity O(n) for the hash map.
Edge cases: S not an integer, negative numbers, empty subarray, and no valid subarray.
Handling floating-point precision by using exact arithmetic or scaling if S is rational.
Maintaining the global maximum length across all processed elements.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.