Microsoft·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Microsoft SWE interview with a permutation problem that looked deceptively clean on the surface. One algorithmic question, fairly focused session.

Questions Asked (1)

Given a permutation of length n, for each k from 1 to n determine whether the elements {1, 2, ..., k} appear as a contiguous subarray. Output a binary string of length n where position k is '1' if such a subarray exists and '0' otherwise. Aim for better than brute force.

Algorithms & Data Structures

Author's notes

My first instinct was to just check all subarrays and I literally started coding that before catching myself.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use the positions of each value in the permutation to track the minimum and maximum indices of the set {1..k}. For each k, the set forms a contiguous subarray if and only if maxPos - minPos + 1 equals k. This yields an O(n) solution.

Pro tip: Mention that this is a classic problem where maintaining the range of positions is key, and explicitly state the O(n) time and O(n) space complexity to show efficiency awareness.

1. Understand the problem

Clarify that we need to check for each k whether the values 1 through k occupy a contiguous block in the permutation. The output is a binary string of length n.

2. Preprocess positions

Create an array pos where pos[value] = index of that value in the permutation. This allows O(1) lookup of any value's position.

3. Track min and max positions

Initialize minPos and maxPos to the position of 1. Iterate k from 1 to n, updating minPos and maxPos with the position of k.

4. Check contiguity

For each k, if maxPos - minPos + 1 == k, then the set {1..k} is contiguous; append '1' to the result, else '0'.

5. Analyze complexity

Explain that the algorithm runs in O(n) time and uses O(n) extra space, which is optimal for this problem.

Key Points to Mention

The condition for contiguity: maxPos - minPos + 1 == k.
Using an array to store positions for O(1) access.
Single pass after preprocessing to compute the answer.
Time complexity O(n) and space complexity O(n).
Edge cases: k=1 always yields '1'; k=n always yields '1'.
Alternative approach: using a segment tree or union-find, but not necessary.

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