← Uber Interview Insights

Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Uber coding round for a software engineer role, one algorithmic question that looked like a simple DP problem but had a twist that made me second-guess my whole approach for a few minutes.

Questions Asked (1)

Q1

You're at index 0 of an array and need to reach the last index. At each position you can move to the next index, or jump directly to any future index whose value ends in the digit 3. Your score is the sum of values at every index you land on. Find the maximum possible score.

Algorithms & Data Structures
Author's notes

Took me longer than it should have to see the structure.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize this as a dynamic programming problem where the maximum score to reach index i depends on the best score from index i-1 or any previous index j where arr[j] % 10 == 3. Compute dp[i] = arr[i] + max(dp[i-1], max_{j < i, arr[j]%10==3} dp[j]), and optimize the second term by maintaining the running maximum of dp[j] for indices with value ending in 3.

Pro tip: Clarify edge cases upfront: if the array has only one element, the score is just that element; also confirm whether you must land on the last index (yes) and whether you can skip indices (only via the jump rule). This shows attention to detail and prevents wrong assumptions.

1. Define the DP state

Let dp[i] be the maximum score to reach index i. The answer will be dp[n-1] where n is the array length.

2. Establish base case and transition

Base: dp[0] = arr[0]. Transition: dp[i] = arr[i] + max(dp[i-1], best_so_far) where best_so_far is the maximum dp[j] for j < i with arr[j] % 10 == 3.

3. Optimize with running maximum

Maintain a variable best_so_far that stores the maximum dp[j] seen so far for indices j where arr[j] % 10 == 3. Update it after computing each dp[i] if arr[i] % 10 == 3.

4. Iterate and compute

Iterate from i = 1 to n-1, compute dp[i] using the transition, and update best_so_far accordingly. Return dp[n-1].

5. Analyze complexity and edge cases

Time complexity O(n), space O(1) if we only keep the previous dp and best_so_far. Handle n=1, negative numbers, and ensure best_so_far is initialized to -infinity if no valid jump source exists.

Key Points to Mention

  • Dynamic programming formulation with state dp[i] representing max score to reach index i.
  • Transition using the previous index and the best previous index with value ending in 3.
  • Optimization by maintaining a running maximum of dp for indices with value % 10 == 3.
  • Time and space complexity: O(n) time, O(1) space with optimization.
  • Edge cases: single-element array, negative values, and no valid jump source.
  • Correctness argument: optimal substructure and overlapping subproblems.

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