Google·Machine Learning Engineer·Technical Phone Screen·Senior

Senior

Apr 2026

Summary

Google ML engineer interview with a streaming data problem that looked like a straightforward average question but had a neat reduction hiding underneath. Not the most brutal round I've had but it required you to actually think before coding.

Questions Asked (1)

You're receiving a stream of integers one at a time. For each new element added, find the length of the longest contiguous subarray so far whose average equals a given fixed value S. Your solution needs to handle updates efficiently as the stream grows.

Algorithms & Data Structures

Author's notes

I stared at the average condition for a bit too long before realizing you can just subtract S from every element and now you're looking for the longest subarray with sum zero.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Transform the average condition into a prefix sum condition: for subarray (i+1..j) to have average S, we need prefix[j] - prefix[i] = S*(j-i), which rearranges to (prefix[j] - S*j) = (prefix[i] - S*i). Thus, maintain a hash map from the transformed prefix value (prefix[k] - S*k) to the earliest index where it occurred, and for each new element, check if the current transformed value exists in the map to compute the longest subarray ending at the current index. Keep track of the maximum length seen so far.

Pro tip: Emphasize that the hash map stores the earliest occurrence of each transformed prefix value, which is crucial for maximizing subarray length. Also, mention that this approach handles streaming updates in O(1) amortized time per element, making it efficient for large streams.

1. Understand the problem and constraints

Clarify that we need to process a stream of integers one by one and after each addition, report the length of the longest contiguous subarray seen so far with average exactly S. Note that the subarray must be contiguous and within the stream seen so far.

2. Derive the prefix sum transformation

Show 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). This transformation reduces the problem to finding two equal values in the transformed prefix array.

3. Design the data structure

Use a hash map to store the first occurrence of each transformed prefix value. Initialize with the transformed prefix value 0 at index -1 (before the start). Also maintain variables for the current prefix sum and the maximum length found so far.

4. Process each new element

For each new integer, update the prefix sum, compute the transformed value (prefix - S*index), and check if it exists in the hash map. If it does, compute the length from the stored index to the current index and update the maximum length. If not, store the current index as the first occurrence.

5. Return the result after each addition

After processing each element, output the current maximum length. This gives the longest subarray with average S seen so far in the stream.

Key Points to Mention

Prefix sum transformation: (prefix[j] - S*j) = (prefix[i] - S*i)
Hash map storing earliest index for each transformed prefix value
Time complexity: O(1) amortized per element, O(n) total for n elements
Space complexity: O(n) for the hash map in the worst case
Handling of integer overflow: use appropriate data types (e.g., long) for prefix sums and transformed values
Edge cases: empty stream, no subarray found, S not integer? (but S is fixed value, likely integer)

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