Jump Game Prime - Uber Coding — OA Interview

The "Jump Game Prime" problem (also referred to as "Max-score jump game with special prime jumps") is a common hard-level online assessment (OA) question used by Uber. It combines array traversal with dynamic programming and prime number constraints. 5 0

Full Problem Prompt

You are given an integer array arr of length nn𝑛. You start at index 0 and must reach the final index n-1. Your score is the sum of the values in arr at all indices you visit during your journey. 5 1 7

From any current index ii𝑖, you can make two types of jumps:

• Standard Jump: Move to index 𝑖+1.
• Special Prime Jump: Move to index 𝑖+𝑝, where pp𝑝 is a prime number that ends in 3 (i.e., 𝑝(mod10)=3), such as 3, 13, 23, 43, etc.

The target is to find the maximum possible score to reach the end. If the end index is unreachable, you must return -1. 1 8

Constraints

• Array Length (nn𝒏): Typically up to 2×105.
• Element Values: Values in arr[i] can be negative.
• Time Limit: Solutions generally must run in 𝑂(𝑛×number of valid primes) or better. Because the number of primes 𝑝≡3(mod10) is relatively small compared to nn𝑛, DP is the expected approach.

Examples

Example 1:

• Input: arr = [10, -2, -5, 20]
• Output: 25
• Explanation: Start at index 0 (Score: 10). Jump 𝑝=3 (3 is prime and 3(mod10)=3) to index 3 (Score: 10+20=30). Alternatively, jumping to 𝑖+1 (index 1) then to index 3 might result in a lower score due to the negative values.

Example 2:

• Input: arr = [1, -10, -10, 1]
• Output: 2
• Explanation: Jump from index 0 directly to index 3 using 𝑝=3. The total score is 1+1=2.

Key Strategy Hints 💡

• Prime Sieve: Use the Sieve of Eratosthenes to pre-calculate all primes up to nn𝑛, then filter for those ending in 3.
• DP State: Define dp[i] as the maximum score to reach index i.
• Transitions: For each index i, dp[i] = arr[i] + max(dp[i-1], dp[i-p1], dp[i-p2], ...) where pp𝑝 are the valid special primes.
• Initialization: Set all dp values to a very small number (or −∞negative infinity−∞) and dp[0] = arr[0].

To prepare for similar Uber challenges, would you like to explore other DP variations like the "Optimal Strategy for a Game" or graph-based problems involving DSU? 4 3

[0] - Uber | OA | Hard | Tree | Math | Coding Questions and ... [1] - Solve 12 coding interview problems | Uber Coding Question [2] - Solve 12 coding interview problems - Uber Questions - PracHub [3] - Interview Experience | SDE2 | Uber | Nov 2025 - Discuss [4] - My Uber SDE-2 Interview Experience (Not Selected, but Worth ... [5] - Solve 12 coding interview problems - Uber Questions - PracHub [6] - Solve 12 coding interview problems - Uber Questions - PracHub [7] - 3629. Minimum Jumps to Reach End via Prime Teleportation [8] - 55. Jump Game - In-Depth Explanation - AlgoMonster