Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Uber SWE interview with a permutation problem that looked deceptively simple at first glance. The core challenge was figuring out an efficient way to check prefix completeness across all k values simultaneously.

Questions Asked (1)

You're given a permutation of length n containing exactly the elements 1 through n with no duplicates. For each value k from 1 to n, determine whether k is 'balanced', meaning there exists some contiguous subarray whose elements are exactly the set {1, 2, ..., k}. Return a binary string of length n where 1 means balanced and 0 means not.

Algorithms & Data Structures

Author's notes

My first instinct was to brute force it: for each k, slide a window of size k and check if the min is 1 and max is k with no gaps.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Track the minimum and maximum positions of values 1..k as you iterate k from 1 to n. For each k, check if the span (maxPos - minPos + 1) equals k; if so, the subarray between those positions contains exactly k elements, and since it includes all values 1..k, it must be exactly the set {1..k}. This yields an O(n) solution.

Pro tip: Mention that the condition span == k is both necessary and sufficient: if the span equals k, the subarray has k distinct elements all within 1..k, so it must be exactly {1..k}. This avoids any need for explicit set checking.

1. Understand the problem and define balanced

Clarify that a value k is balanced if there exists a contiguous subarray containing exactly the numbers 1 through k. Note that the subarray must have length k and contain all these values.

2. Identify key observation

Realize that for a given k, the only possible subarray that can contain all values 1..k is the one spanning from the minimum position to the maximum position among these values. If its length equals k, it must be exactly the set {1..k}.

3. Design an O(n) algorithm

Create an array pos where pos[v] is the index of value v. Iterate k from 1 to n, maintaining minPos and maxPos of values seen so far. For each k, check if maxPos - minPos + 1 == k; if yes, mark balanced.

4. Build the result string

Initialize a string of length n with '0's. For each k that satisfies the condition, set the k-th character to '1'. Return the string.

5. Analyze complexity and edge cases

The algorithm runs in O(n) time and O(n) space. Handle n=1 correctly (always balanced). Discuss why the condition is sufficient and necessary.

Key Points to Mention

The subarray must have length exactly k and contain all values 1..k.
The minimal spanning subarray for values 1..k is from min position to max position.
If the span length equals k, then the subarray contains exactly k distinct elements, all from 1..k, so it must be exactly {1..k}.
Maintain min and max positions incrementally as k increases.
Time complexity O(n) and space complexity O(n) using a position array.
Edge case: k=1 is always balanced because the subarray containing just 1 has length 1.

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