Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Uber SWE interview with a permutation-based array problem. Nothing too wild but the question had some edge cases worth thinking through carefully.

Questions Asked (1)

Given a permutation of integers 1 through N, for each value of k from 1 to N, check whether the elements with values 1 through k all appear as a contiguous block in the array. Return a binary string where each character represents whether the condition holds for that k.

Algorithms & Data Structures

Author's notes

My first instinct was to track the min and max positions of elements seen so far as I iterated k from 1 to N.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

For each k, the elements 1..k form a contiguous block iff max(positions[1..k]) - min(positions[1..k]) + 1 == k. Precompute the positions of each value, then iterate k from 1 to N, maintaining the running min and max of positions to check the condition in O(1) per k, yielding an overall O(N) solution.

Pro tip: Mention that this O(N) approach is optimal because you must at least read the input, and explicitly state the invariant: the block is contiguous exactly when the span of positions equals the number of elements. This shows you understand the mathematical insight and can communicate it clearly.

1. Understand the problem and clarify constraints

Restate the problem: for each k, check if values 1..k occupy a contiguous subarray. Confirm that the permutation contains each integer exactly once and that N can be large (e.g., up to 10^5 or more), so an O(N^2) solution is too slow.

2. Map values to positions

Create an array pos of size N+1 where pos[v] is the index of value v in the permutation. This allows O(1) lookup of any value's position.

3. Iterate and maintain min/max positions

Initialize minPos = N, maxPos = 0. For k from 1 to N, update minPos = min(minPos, pos[k]) and maxPos = max(maxPos, pos[k]). Check if maxPos - minPos + 1 == k; if true, append '1' to the result, else '0'.

4. Return the binary string

After the loop, return the constructed string of length N. Optionally, discuss edge cases like N=1 and verify with a small example.

Key Points to Mention

The condition for contiguity: max position - min position + 1 equals the number of elements (k).
Using an auxiliary array to store positions of each value for O(1) access.
Maintaining running min and max of positions as k increases, avoiding recomputation.
Time complexity O(N) and space complexity O(N) for the position array and result string.
Handling edge cases: k=1 always true, k=N always true (since the whole array is contiguous).
Potential alternative approaches (e.g., using a set or sorting) and why they are less efficient.

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