Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Uber coding round, one algorithmic problem on permutations. Pretty clean problem once you see the trick, but I didn't see it immediately.

Questions Asked (1)

Given a permutation of 1 through n, for each k from 1 to n, determine whether some contiguous subarray is a permutation of 1 through k. Return a binary string where position k is '1' if such a subarray exists and '0' otherwise.

Algorithms & Data Structures

Author's notes

My first instinct was something like sorting or a set membership check per k, which would've been way too slow.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

For each k, a contiguous subarray that is a permutation of 1..k must contain exactly the elements 1..k and have length k. Track the minimum and maximum positions of elements 1..k as you iterate k from 1 to n; if the difference between max and min positions equals k-1, then the elements occupy a contiguous block, so the answer is '1'. This yields an O(n) solution.

Pro tip: Mention that the condition is both necessary and sufficient: if the span of positions of 1..k is exactly k-1, the elements must be exactly 1..k (since they are distinct), so no additional checks are needed. This shows you understand the invariant and avoids overcomplicating the solution.

1. Understand the problem

Clarify that a contiguous subarray that is a permutation of 1..k must contain each number from 1 to k exactly once, and thus its length is k. The subarray can be anywhere in the permutation.

2. Identify key invariant

For a given k, the elements 1..k occupy positions that must form a contiguous block of length k. This means the difference between the maximum and minimum positions of these elements must be exactly k-1.

3. Design incremental algorithm

Precompute the position of each value in the permutation. Iterate k from 1 to n, maintaining the minimum and maximum positions of elements 1..k. For each k, check if maxPos - minPos == k-1; if so, append '1', else '0'.

4. Analyze complexity and edge cases

The algorithm runs in O(n) time and O(n) space. Handle edge cases like n=1 (always '1') and ensure the logic works when the subarray is at the beginning or end.

5. Test with examples

Walk through a small example (e.g., permutation [2,1,3]) to verify the output. For k=1, positions of 1 is 2, span 0 -> '1'; k=2, positions of 1 and 2 are 2 and 1, span 1 -> '1'; k=3, positions 2,1,3 span 2 -> '1'. Output '111'.

Key Points to Mention

The subarray must contain exactly the numbers 1..k, so its length is k.
The positions of elements 1..k must form a contiguous range, i.e., max position - min position = k-1.
Precompute the position array to allow O(1) updates for each k.
Maintain running min and max positions as k increases.
Time complexity O(n) and space complexity O(n).
The condition is necessary and sufficient because the elements are distinct.

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