Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Uber SWE interview with a permutation problem that looked straightforward on the surface but had some real edge cases hiding underneath. The expected complexity was O(n log n) or better, so brute force was a non-starter.

Questions Asked (1)

Given a permutation of integers 1 through n, for each k from 1 to n determine whether there exists a contiguous subarray of length k that contains exactly the values 1 through k. Return a binary string of length n where position k-1 is '1' if such a subarray exists and '0' otherwise.

Algorithms & Data Structures

Author's notes

My first instinct was a sliding window but the window size changes with k so that doesn't cleanly apply.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem and edge cases. Then, propose an efficient solution using the positions of values 1..k: a contiguous subarray of length k containing exactly 1..k exists iff the maximum position minus the minimum position among values 1..k equals k-1. Maintain the min and max positions incrementally as k increases, and build the binary string.

Pro tip: Mention that this problem is equivalent to checking if the set {1..k} forms a contiguous block in the permutation, and that the min-max trick gives an O(n) solution. Also, discuss how to handle large n and why a naive O(n^2) approach would be too slow.

1. Understand the problem

Restate the problem in your own words and confirm with the interviewer. Clarify that the subarray must contain exactly the values 1 through k, not just any k distinct values.

2. Identify the key condition

Realize that a contiguous subarray of length k containing exactly 1..k exists if and only if the positions of values 1..k form a contiguous range. This means max_pos - min_pos + 1 = k.

3. Design an efficient algorithm

Iterate k from 1 to n, maintaining the minimum and maximum positions of values seen so far. For each k, check if max_pos - min_pos + 1 == k; if so, append '1', else '0'.

4. Analyze complexity and edge cases

The algorithm runs in O(n) time and O(n) space. Discuss edge cases: n=1, already sorted permutation, reverse sorted permutation, and permutations where no such subarray exists for some k.

5. Test with examples

Walk through a small example (e.g., permutation [2,1,4,3]) to verify the logic. For k=1, positions of 1 is 2, so max-min+1=1, result '1'. For k=2, positions of 1 and 2 are 2 and 1, max-min+1=2, result '1', etc.

Key Points to Mention

The condition max_pos - min_pos + 1 == k is necessary and sufficient for the existence of a contiguous subarray of length k containing exactly 1..k.
Maintaining min and max positions incrementally as k increases avoids recomputing from scratch, achieving O(n) time.
The problem can be solved by tracking the range of positions of values 1..k; if the range size equals k, then those values occupy a contiguous block.
Edge cases: k=1 always yields '1' because a single element 1 is a subarray of length 1 containing exactly 1. For k=n, it's '1' only if the entire permutation is sorted.
Space complexity can be O(n) for storing positions, but we only need to store the position array and update min/max on the fly.
Alternative approaches like sliding window or segment trees are less efficient; the min-max method is optimal.

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