← Uber Interview Insights

Uber·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate
May 2026

Summary

Uber SWE online assessment, one algorithmic problem that looks deceptively simple until you actually sit down to implement it cleanly.

Questions Asked (1)

Q1

Given a permutation of integers 1 through n, for each k from 1 to n determine whether the values 1 through k appear as a contiguous subarray. Return a binary string of length n where position k is '1' if they do and '0' if not.

Algorithms & Data Structures
Author's notes

The core insight took me longer than i'd like to admit: if you track where each value sits in the array, then 1..k forms a contiguous block if and only if the spread of those positions (max minus min plus one) equals k.

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 through the permutation. For each k, check if maxPos - minPos + 1 == k; if so, the values form a contiguous subarray. This yields an O(n) solution.

Pro tip: Mention that this works because the values are a permutation of 1..n, so the set {1..k} has exactly k distinct elements. Also, clarify that 'contiguous subarray' means a contiguous segment of the original array, not necessarily starting at index 0.

1. Clarify the problem

Confirm that 'contiguous subarray' means a contiguous segment of the original permutation, and that the binary string should have '1' at position k if values 1..k appear together in some order.

2. Identify key insight

Realize that for a set of k distinct integers to occupy a contiguous subarray, the difference between their maximum and minimum positions must be exactly k-1.

3. Design algorithm

Iterate through the permutation, maintaining the minimum and maximum indices seen so far for values 1..k. At each step k, check if maxIndex - minIndex + 1 == k.

4. Implement and test

Write code to build the binary string, and test with small cases (e.g., n=1, n=3) and edge cases (e.g., already sorted, reverse sorted).

5. Analyze complexity

State that the algorithm runs in O(n) time and O(n) space (for storing positions or the result string), which is optimal.

Key Points to Mention

  • The condition maxPos - minPos + 1 == k is necessary and sufficient for values 1..k to be contiguous.
  • Since the permutation contains distinct integers, the set {1..k} has exactly k elements.
  • We can precompute the position of each value in the permutation to allow O(1) updates.
  • The algorithm processes k from 1 to n in a single pass, updating min and max positions.
  • Edge cases: k=1 always yields '1'; k=n always yields '1' because the whole array is contiguous.
  • Time complexity O(n) and space complexity O(n) are optimal for this problem.

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