Microsoft·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Microsoft coding interview, one question about arrays. Pretty straightforward problem but the edge cases are where things get interesting.

Questions Asked (1)

Given an array, print all sub-arrays that contain only distinct elements.

Algorithms & Data Structures

Author's notes

Spent the first few minutes just making sure I understood what 'distinct' meant in context.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a sliding window with a hash map to track the last occurrence of each element, expanding the right pointer and shrinking the left pointer when a duplicate is found. For each valid window, all subarrays ending at the right pointer and starting from the left pointer to the right pointer are distinct, so print them. This approach efficiently enumerates all distinct-element subarrays in O(n^2) time in the worst case due to output size, but O(n) auxiliary space.

Pro tip: Clarify with the interviewer whether they want to print all subarrays explicitly or just count them, as the output size can be O(n^2) and printing may dominate runtime. Also, mention that the sliding window technique is optimal for this problem and can be adapted to count distinct subarrays in O(n) time.

1. Understand the problem and constraints

Confirm that subarrays are contiguous and that 'distinct elements' means no duplicates within each subarray. Ask about input size, expected output format, and whether to print or return the subarrays.

2. Choose the sliding window approach

Explain that a sliding window with a hash map (or array if elements are bounded) can efficiently track the last occurrence of each element. The window [left, right] always contains distinct elements.

3. Expand and shrink the window

Iterate right from 0 to n-1. If the current element is already in the window, move left to max(left, last_occurrence[element] + 1). Update the last occurrence of the current element.

4. Enumerate all valid subarrays

For each right, all subarrays starting from any index i in [left, right] and ending at right are valid. Print each subarray, either by iterating i from left to right and printing the slice, or by using a more efficient method if only counting is needed.

5. Analyze complexity and edge cases

Discuss time complexity: O(n^2) in the worst case due to printing all subarrays, but O(n) for the sliding window logic itself. Space complexity: O(min(n, k)) for the hash map, where k is the number of distinct elements. Handle edge cases like empty array, all distinct elements, and all duplicates.

Key Points to Mention

Sliding window technique with two pointers (left and right) to maintain a window of distinct elements.
Hash map (or dictionary) to store the last seen index of each element for O(1) lookups.
Time complexity: O(n) for the sliding window traversal, but O(n^2) overall if printing all subarrays because there can be O(n^2) valid subarrays.
Space complexity: O(min(n, k)) where k is the number of distinct elements in the array.
Edge cases: empty array, array with all identical elements, array with all distinct elements.
Alternative: If only counting distinct subarrays is required, the count can be computed in O(n) time by adding (right - left + 1) for each right.

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