← Uber Interview Insights

Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Apr 2026

Summary

Uber SWE coding round, one algorithmic question on prefix subarrays. Pretty clean problem once you see the trick, but I fumbled the explanation a bit under pressure.

Questions Asked (1)

Q1

You're given an array of length n that is a permutation of 1 through n. For each prefix of length k, determine whether that prefix contains exactly the numbers 1 through k (in any order). Return a binary array of your results.

Algorithms & Data Structures
Author's notes

The naive approach is obvious: for each k, sort the prefix or check a set.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Track the maximum value seen so far in the prefix and compare it to the prefix length. If the maximum equals the length, then the prefix contains exactly the numbers 1 through k; otherwise, it does not. This yields an O(n) time and O(1) extra space solution.

Pro tip: Mention that since the array is a permutation, the condition max(prefix) == k is both necessary and sufficient. This avoids unnecessary data structures like sets or hash maps, showing you understand the problem's constraints.

1. Understand the problem

Clarify that the array is a permutation of 1..n, so all numbers are distinct and within range. The goal is to check for each prefix whether it contains exactly the set {1,2,...,k}.

2. Identify the key condition

Realize that a prefix of length k contains exactly 1..k if and only if the maximum value in that prefix is k. Since all numbers are distinct, if the max is k, then the prefix must contain all numbers from 1 to k.

3. Design the algorithm

Iterate through the array while maintaining the maximum value seen so far. For each index i (0-based), update the max and set result[i] = (max == i+1).

4. Analyze complexity

The algorithm runs in O(n) time and uses O(1) extra space (besides the output array). This is optimal because we must read the entire input.

5. Test with examples

Walk through a small example, e.g., [1,3,2,4], to verify the logic: prefixes [1] -> true, [1,3] -> false, [1,3,2] -> true, [1,3,2,4] -> true.

Key Points to Mention

  • The array is a permutation, so all elements are distinct and in the range 1..n.
  • The condition max(prefix) == k is necessary and sufficient for the prefix to contain exactly 1..k.
  • Time complexity: O(n) single pass.
  • Space complexity: O(1) extra space (output array not counted).
  • Edge cases: k=1 (always true if first element is 1), and k=n (always true).
  • Alternative approaches like using a set or frequency array are less efficient (O(n) space) and unnecessary.

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