← Uber Interview InsightsSoftware Engineer

Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Jun 2026

Summary

Uber coding round for a software engineer role. One algorithmic problem, felt like a dynamic programming question dressed up in unusual jump rules. Took me a while to even parse what counts as a valid jump.

Questions Asked (1)

Q1

You have an integer array indexed from 0. From any position, you can jump forward either 1 step or exactly x steps, where x is a prime number whose last digit is 3 (like 3, 13, 23, 43, and so on). Each cell holds a value that can be positive or negative. Find the maximum possible sum you can collect by the time you reach the last index.

Algorithms & Data Structures
Author's notes

First thing I did wrong was assume any prime works.

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 sum to reach index i. Precompute all valid jump lengths (primes ending in 3) up to n, then for each index i, consider transitions from i-1 and from i-x for each valid x, taking the maximum. Return dp[n-1] as the answer.

Pro tip: Mention that you can precompute the valid primes once and reuse them, and clarify whether jumps must land exactly on the last index or can overshoot—this shows attention to problem constraints and edge cases.

1. Clarify problem constraints and edge cases

Confirm with the interviewer whether jumps must land exactly on the last index, whether negative sums are allowed, and the array size to determine feasible complexity.

2. Precompute valid jump lengths

Generate all prime numbers ending in 3 up to the array length using a sieve or primality test, storing them in a list for efficient lookup.

3. Define DP state and recurrence

Let dp[i] be the maximum sum to reach index i. Initialize dp[0] = arr[0] and for each i, set dp[i] = max(dp[i-1], max over valid x of dp[i-x]) + arr[i], handling unreachable states.

4. Handle unreachable indices and negative values

Use a sentinel like negative infinity for unreachable states, and ensure the recurrence correctly propagates the best sum even when intermediate values are negative.

5. Analyze complexity and optimize if needed

State time complexity O(n * k) where k is the number of valid primes up to n, and space O(n). Discuss potential optimizations like using a sliding window if k is large.

Key Points to Mention

  • Dynamic programming with state dp[i] representing max sum to reach index i
  • Precomputing primes ending in 3 using sieve of Eratosthenes or trial division
  • Transition from i-1 and from i-x for each valid prime x
  • Handling unreachable states with negative infinity sentinel
  • Time complexity O(n * k) and space complexity O(n)
  • Edge cases: array length 1, no valid jumps, all negative values

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