Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Uber SWE coding round, one algorithmic problem that looks simple but requires a clean insight to get right. Not a brutal interview but the kind where you either see it or you don't.

Questions Asked (1)

Given a permutation of integers 1 to n, determine for each value k (from 1 to n) whether there exists a contiguous subarray that is exactly a permutation of 1 to k. Output 1 if yes, 0 if no, for each k.

Algorithms & Data Structures

Author's notes

My first instinct was to brute force check all subarrays for each k and I started explaining that before catching myself.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

For each k from 1 to n, we need to check if there is a contiguous subarray that is a permutation of 1..k. This is equivalent to finding a subarray of length k whose elements are exactly {1,2,...,k}. We can precompute the positions of each value and use a sliding window or track the minimum and maximum positions of values 1..k to determine if they form a contiguous block. Specifically, for each k, let minPos and maxPos be the minimum and maximum positions among values 1..k. If maxPos - minPos + 1 == k, then the subarray from minPos to maxPos is exactly a permutation of 1..k, so answer is 1; otherwise 0.

Pro tip: Mention that this approach runs in O(n) time by incrementally updating minPos and maxPos as k increases, which is optimal. Also, clarify that the subarray must be contiguous and contain each number exactly once, so the condition maxPos - minPos + 1 == k is both necessary and sufficient.

1. Understand the problem

Restate the problem: For each k, determine if there exists a contiguous subarray that is a permutation of 1..k. Note that the subarray must have length k and contain all integers from 1 to k exactly once.

2. Key observation

The set of values {1..k} must occupy a contiguous block of positions. If we know the minimum and maximum positions of these values, the block length is maxPos - minPos + 1. This block is exactly a permutation of 1..k if and only if its length equals k.

3. Algorithm design

Precompute an array pos where pos[v] is the index of value v in the permutation. Initialize minPos = n+1 and maxPos = -1. Iterate k from 1 to n: update minPos = min(minPos, pos[k]) and maxPos = max(maxPos, pos[k]). If maxPos - minPos + 1 == k, output 1; else output 0.

4. Complexity analysis

The algorithm runs in O(n) time and O(n) space for the pos array. This is optimal because we must at least read the input and produce n outputs.

5. Edge cases and verification

Consider edge cases: k=1 always works because any single element equal to 1 forms a permutation of 1. For k=n, it works only if the entire permutation is 1..n in order? Actually, for k=n, the whole array is a permutation of 1..n, so it always works. Verify with small examples.

Key Points to Mention

The condition maxPos - minPos + 1 == k is necessary and sufficient for the existence of a contiguous subarray that is a permutation of 1..k.
Precomputing positions of each value allows O(1) updates for minPos and maxPos as k increases.
The algorithm processes k from 1 to n in order, maintaining the range of positions of values 1..k.
Time complexity is O(n) and space complexity is O(n), which is optimal.
For k=1, the answer is always 1 because the value 1 itself is a permutation of 1.
For k=n, the answer is always 1 because the entire permutation is a permutation of 1..n.

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