Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Uber SWE coding round, one problem the whole session. It looked like a jump game variant but had this extra wrinkle with digit-based jumps that took me a minute to even parse correctly.

Questions Asked (1)

You're given an integer array. Starting at index 0, you need to reach the last index. At each index i, you can move to i+1 or jump directly to any index j greater than i where the value at j ends in the digit 3. Your score is the sum of values at all visited indices. Find the maximum possible score.

Algorithms & Data Structures

Author's notes

My first instinct was greedy and it was wrong.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a dynamic programming problem where dp[i] represents the maximum score to reach index i. For each index i, consider transitions from i-1 (always allowed) and from any previous index j where arr[j] ends in 3 (if arr[i] ends in 3). Compute dp values in order and return dp[n-1].

Pro tip: Clarify that the score includes the value at the starting index (index 0) and the ending index, as this is a common ambiguity. Also, mention that if no valid path exists, the problem might be unsolvable, but typically a path exists via i+1 moves.

1. Understand the problem and constraints

Restate the problem: start at index 0, end at last index, moves are to i+1 or to any j>i where arr[j] ends in 3. Score is sum of visited indices. Ask clarifying questions about edge cases (e.g., empty array, single element, negative numbers).

2. Define the DP state and recurrence

Let dp[i] be the maximum score to reach index i. Initialize dp[0] = arr[0]. For i>0, dp[i] = arr[i] + max(dp[i-1], max over j<i where arr[i] ends in 3 of dp[j]). If arr[i] does not end in 3, only consider dp[i-1].

3. Optimize transitions

To avoid O(n^2) time, maintain a variable max_dp_ending_in_3 that stores the maximum dp[j] for all j where arr[j] ends in 3. Update it as you compute dp[i]. This reduces time to O(n).

4. Handle edge cases and return result

Check for empty array (return 0 or handle as per problem). For single element, return arr[0]. After computing dp, return dp[n-1]. Discuss potential integer overflow and use appropriate data types.

5. Analyze complexity and test

State time complexity O(n) and space complexity O(n) (or O(1) if optimized). Walk through a small example to verify correctness, including cases with negative numbers and multiple jumps.

Key Points to Mention

Dynamic programming approach with state dp[i] representing max score to reach index i.
Transition: from i-1 always, and from any j where arr[j] ends in 3 if arr[i] ends in 3.
Optimization using a running maximum to achieve O(n) time.
Edge cases: empty array, single element, negative numbers, no valid path (if applicable).
Score includes starting and ending indices; clarify if needed.
Space optimization possible by keeping only previous dp and running max.

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