← Uber Interview Insights

Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026

Summary

Uber SWE interview with a sliding window / sorted structure problem. Not the hardest question I've seen but the constraints tripped me up more than I expected.

Questions Asked (1)

Q1

Given an array of integers and a number N, find the length of the longest contiguous subarray where the difference between any two elements is less than N.

Algorithms & Data Structures
Author's notes

My first instinct was a brute force O(n^2) scan and I actually started coding it before catching myself.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints and edge cases, then propose an efficient solution using a sliding window with a monotonic deque to track the min and max in the current window. Explain how the window expands and shrinks to maintain the condition that max - min < N, and analyze the time and space complexity.

Pro tip: Mention that the condition 'difference between any two elements is less than N' is equivalent to max - min < N, and highlight that using two deques gives O(n) time, which is optimal. Also, proactively discuss how to handle negative numbers and large inputs.

1. Clarify the problem

Restate the problem in your own words and ask clarifying questions about constraints, input size, and edge cases (e.g., empty array, N <= 0, duplicates).

2. Discuss brute force and optimize

Start with a brute-force O(n^2) approach to check all subarrays, then identify the inefficiency and propose a sliding window with deques for O(n) time.

3. Explain the sliding window with deques

Describe how to maintain a window [left, right] and use two deques to track indices of min and max. Expand right, update deques, and while max - min >= N, move left and remove out-of-window indices.

4. Walk through an example

Trace the algorithm on a small example to demonstrate correctness, showing how the window adjusts and the length is updated.

5. Analyze complexity and edge cases

State that each element is added and removed from deques at most once, giving O(n) time and O(n) space. Discuss handling of negative numbers and large N.

Key Points to Mention

  • The condition 'difference between any two elements < N' is equivalent to max - min < N.
  • Sliding window technique with two monotonic deques to track min and max in O(1) amortized time.
  • Time complexity O(n) and space complexity O(n) due to deques.
  • Handling edge cases: empty array, N <= 0, all elements equal, and negative numbers.
  • Comparison with brute force O(n^2) to justify optimization.
  • Potential follow-up: what if the array is a stream? (Use a similar approach with a queue and deques.)

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