Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Uber SWE coding round, one algorithmic problem about permutations and sliding windows. Tricky enough that I had to think out loud for a while before anything clicked.

Questions Asked (1)

Given a permutation of integers 1 through n, return a binary array of length n where the value at index w indicates whether any contiguous subarray of length w contains exactly the elements {1, 2, ..., w}.

Algorithms & Data Structures

Author's notes

Took me an embarrassingly long time to see the key insight: a subarray of length w contains {1..w} if and only if its max element equals w and all elements are distinct (which is guaranteed by permutation).

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

For each window length w, check if the subarray of length w containing the elements 1..w is contiguous. Use the positions of each number to compute the minimum and maximum indices for the set {1..w} and verify that max - min + 1 == w. This can be done efficiently in O(n) by incrementally updating min and max as w increases.

Pro tip: Mention that the condition is equivalent to the positions of 1..w forming a contiguous block, and emphasize the O(n) solution using prefix min/max of positions. This shows you can optimize beyond brute force.

1. Understand the problem

Clarify that for each w from 1 to n, we need to determine if there exists a contiguous subarray of length w that contains exactly the numbers 1 through w.

2. Brute force approach

For each w, check all subarrays of length w to see if they contain exactly {1..w}. This is O(n^3) or O(n^2) with sets, which is inefficient.

3. Optimize using positions

Precompute the position of each number in the permutation. For a given w, the set {1..w} occupies a contiguous block if and only if the maximum position minus the minimum position among these numbers equals w-1.

4. Incremental computation

Iterate w from 1 to n, maintaining the minimum and maximum positions of numbers 1..w. At each step, check if max - min + 1 == w. If true, set result[w-1] = 1, else 0.

5. Analyze complexity

The algorithm runs in O(n) time and O(n) space, which is optimal. Discuss potential edge cases, such as w=1 and w=n.

Key Points to Mention

The condition for a valid window of length w is that the positions of numbers 1..w form a contiguous range.
Using the positions array, we can check the condition in O(1) per w by tracking min and max positions.
The overall time complexity is O(n), which is optimal since we must output n values.
Edge cases: w=1 always true (since any single element 1 is a subarray of length 1 containing {1}), and w=n is true only if the entire permutation is 1..n in order? Actually, for w=n, the whole array contains all numbers 1..n, so it's always true. Wait, the condition is that any contiguous subarray of length w contains exactly {1..w}. For w=n, the only subarray of length n is the whole array, which contains all numbers 1..n, so it's always true. So result[n-1] is always 1.
The problem can be solved by checking if the subarray from min_pos to max_pos has length w, which implies it contains exactly w distinct numbers, and since it includes 1..w, it must be exactly that set.
Mention that this approach avoids explicitly checking all subarrays, reducing complexity from O(n^2) to O(n).

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