Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Google SWE coding round, one question the whole time. Sliding window stuff, which I thought I knew until I was actually in the hot seat.

Questions Asked (1)

Given an integer array and a value k, find the length of the shortest contiguous subarray that contains at least k distinct integers. Return -1 if no such subarray exists.

Algorithms & Data Structures

Author's notes

My first instinct was brute force and I kind of just said it out loud before thinking, which wasn't a great look.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a sliding window (two-pointer) technique to maintain a window that contains at least k distinct integers. Expand the right pointer to include more elements, and once the window is valid, shrink from the left to find the shortest valid window. Track the minimum length throughout.

Pro tip: Clarify edge cases upfront, such as when k is greater than the total number of distinct integers in the array, and mention that the algorithm runs in O(n) time with O(k) space, which is optimal.

1. Understand the problem and edge cases

Restate the problem to ensure clarity. Discuss edge cases: empty array, k <= 0, k > total distinct elements, and arrays with all identical elements.

2. Choose the sliding window approach

Explain that a brute-force solution would be O(n^2) or worse, and that a sliding window efficiently finds the shortest subarray by maintaining a window with at least k distinct integers.

3. Define window validity and expansion/shrinking rules

Use a hash map to count frequencies of elements in the window. Expand right pointer to add elements until the window has at least k distinct integers. Then, shrink from the left while the window remains valid to minimize length.

4. Track the minimum length

After each shrink, update the minimum length if the current window is valid and shorter. Continue until the right pointer reaches the end.

5. Return result and analyze complexity

If no valid window is found, return -1. Otherwise, return the minimum length. State that time complexity is O(n) and space complexity is O(k) due to the hash map.

Key Points to Mention

Sliding window technique with two pointers (left and right).
Use a hash map (or dictionary) to track the frequency of elements in the current window.
Maintain a count of distinct integers in the window.
Shrink the window from the left only when the window is valid (distinct count >= k).
Update the minimum length whenever a valid window is found.
Time complexity O(n) and space complexity O(k).

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