Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Uber SWE interview with a graph/simulation problem that looks deceptively straightforward but has a real O(n) constraint baked in. The problem is clean but the follow-up on time complexity is where things get interesting.

Questions Asked (1)

You're given an integer array where each element tells you how far to jump from the current index (positive = right, negative = left). Starting from some index s, you keep jumping until you either go out of bounds on the left (index < 0), exit on the right (index >= n), or loop forever. Find the smallest starting index from which you never go out of bounds on the left. Return -1 if none exists. Aim for O(n) time.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was brute force, just simulate from every index and track visited states to catch cycles.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the jumps as a functional graph where each index points to its next index. Use memoization to determine for each index whether it eventually exits left, exits right, or loops, then find the smallest index that exits right or loops without ever exiting left. Alternatively, process indices from left to right, using a visited state array to avoid redundant work and achieve O(n) time.

Pro tip: Clarify that 'never go out of bounds on the left' means the path may exit right or loop, but must not hit index < 0. This distinction is crucial and shows you pay attention to edge cases.

1. Clarify the problem and edge cases

Confirm that 'never go out of bounds on the left' means the path may exit right or loop, but must not hit index < 0. Discuss edge cases like empty array, all jumps left, or immediate exit.

2. Model as a functional graph

Treat each index as a node with a directed edge to i + arr[i]. The problem reduces to finding the smallest node whose path never reaches a node < 0.

3. Design an O(n) algorithm using memoization

Use a state array (e.g., 0=unvisited, 1=visiting, 2=safe, 3=left-exit) and DFS with cycle detection to classify each index. Alternatively, process indices from left to right, propagating states to achieve linear time.

4. Implement and test

Write code that iterates through indices, skipping already classified ones, and returns the smallest index that is safe (exits right or loops without left exit). Test with examples and edge cases.

5. Analyze time and space complexity

Explain that each index is visited at most once, giving O(n) time and O(n) space for the state array. Discuss potential optimizations or trade-offs.

Key Points to Mention

Functional graph representation and cycle detection
Memoization to avoid redundant traversal and achieve O(n)
Distinction between exiting left, exiting right, and infinite loops
Handling of edge cases: empty array, all left jumps, immediate exit
Time and space complexity analysis
Potential for iterative solution with state propagation

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