Microsoft·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate

May 2026

Summary

Microsoft SWE online assessment, one algorithmic problem that looks deceptively clean until you actually try to implement it efficiently. The core idea is straightforward but the efficient path took me a while to see.

Questions Asked (1)

Given a permutation of length n, an index k is called 'balanced' if some contiguous subarray contains exactly the elements {1, 2, ..., k}. For each k from 1 to n, output '1' if k is balanced and '0' otherwise.

Algorithms & Data Structures

Author's notes

My first instinct was to just scan for each k and check all subarrays, which is obviously too slow.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

For each k, the elements {1..k} must form a contiguous subarray. This is equivalent to the condition that the maximum position among elements 1..k minus the minimum position among elements 1..k equals k-1. We can compute this efficiently by iterating k from 1 to n, maintaining the min and max positions seen so far, and checking the condition in O(1) per k, giving O(n) total time.

Pro tip: Mention that the condition is necessary and sufficient because a set of k distinct integers occupies k consecutive positions if and only if the difference between the maximum and minimum positions is exactly k-1. This insight shows you understand the underlying combinatorial property and can avoid more complex data structures.

1. Understand the problem

Restate the definition: for each k, check if there exists a contiguous subarray containing exactly the numbers 1 through k. Clarify that the subarray must contain all these numbers and no others from the permutation.

2. Derive the condition

Observe that since the numbers 1..k are distinct, they form a contiguous block if and only if the difference between their maximum and minimum positions is k-1. This is because k distinct positions within an interval of length k must exactly fill that interval.

3. Design the algorithm

Iterate k from 1 to n. Maintain the minimum and maximum positions of the elements 1..k seen so far. For each k, update these with the position of k, then check if maxPos - minPos == k-1. If true, output '1'; else '0'.

4. Analyze complexity

The algorithm runs in O(n) time and O(n) space to store the permutation and positions. This is optimal since we must read the input and produce n outputs.

5. Test with examples

Walk through a small example, such as permutation [2,4,1,3] for n=4, to verify the condition and outputs. For k=1: pos of 1 is 3, max-min=0, balanced. k=2: positions 3 and 1, diff=2, not balanced. k=3: positions 3,1,4, diff=3, balanced. k=4: positions 3,1,4,2, diff=3, balanced. Output: 1 0 1 1.

Key Points to Mention

The condition maxPos - minPos == k-1 is both necessary and sufficient for the elements {1..k} to be contiguous.
Maintaining running min and max positions allows O(1) update per k, leading to O(n) total time.
The algorithm requires only a single pass over k from 1 to n, using the positions of each value.
Space complexity is O(n) to store the permutation and its inverse (positions).
Edge cases: k=1 is always balanced (single element is contiguous); k=n is always balanced (whole array).
The approach avoids explicitly checking all subarrays, which would be O(n^3) or O(n^2) with optimization.

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