One of two problems in the 90-min Hack2Hire OA. Variant of LeetCode 1696 (Jump Game VI). From index 0 of an integer array, at each step you may jump +1 or jump +k where k is a prime ending in digit 3 (3, 13, 23, 43, 53, 73, 83, …). Maximize the sum of values landed on, finishing at index n−1.

Requirements - Input: integer array arr of length n, where arr[i] is the score at index i. Values may be negative (-10⁴ ≤ arr[i] ≤ 10⁴, 1 ≤ n ≤ 10⁵), so the maximum path is not simply "land on everything" — negative indices must sometimes be skipped over. - Start at index 0. The starting index is already landed on, so arr[0] is always included in the total. - Standard scoring is the sum of arr[i] for each index landed on (including start and end). - At each step you may jump only to the right by +1 or by +k for any prime k whose units digit is 3 (so 3, 13, 23, 43, 53, 73, 83, 103, …; note 33, 63, 93 are excluded because they are not prime). - All jumps must stay within bounds. You must finish exactly at index n − 1. - Output: the maximum total sum reachable. Examples - arr = [5, -100, 4, 10] → 15. Jump 0 → 3 with a 3-step jump: 5 + 10 = 15 (skips the -100). - arr = [4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 20] → 24. A 13-step jump (13 is prime, ends in 3) goes 0 → 13 directly: 4 + 20 = 24. - arr = [7] → 7. Already on the last index, so the answer is just arr[0]. Notes - Pre-sieve the set of prime numbers up to n − 1 (limit = n is enough), then filter to those ending in 3. The valid jump-set is small ( n / (ln n) candidates filtered by % 10 == 3, so typically dozens at most for n ≤ 10⁵). - Classic DP: dp[i] = arr[i] + max(dp[i − j]) for every valid jump length j ≤ i. The +1 step is always available; the prime-3 jumps are added on top. - A naive O(n²) solution passes the small visible tests but times out on the hidden cases — the grader runs the solution on large inputs (n near 10⁵). - To get full credit, fall back to a sieve precomputation + bounded DP, or precompute prefix maxima over the jump candidates. - The platform shows 2–3 visible test cases. You must add your own large random input before submitting — the hidden grader runs offline. - Corner case: n == 1 returns arr[0] directly (no jumps needed). Preparation - Drill LC 1696 (Jump Game VI) and LC 55 / 45 (Jump Game I / II) until DP transitions feel automatic. - Code a sieve of Eratosthenes from memory; practice extracting the % 10 == 3 subset. - Pre-write a 5-line test harness that generates an n = 10⁵ random array so you can sanity-check your DP runtime in the editor before submitting.

OA: Jump Game with Prime-3 Steps — Uber Interview Question

Requirements

Input: integer array arr of length n, where arr[i] is the score at index i. Values may be negative (-10⁴ ≤ arr[i] ≤ 10⁴, 1 ≤ n ≤ 10⁵), so the maximum path is not simply "land on everything" — negative indices must sometimes be skipped over.
Start at index 0. The starting index is already landed on, so arr[0] is always included in the total.
Standard scoring is the sum of arr[i] for each index landed on (including start and end).
At each step you may jump only to the right by +1 or by +k for any prime k whose units digit is 3 (so 3, 13, 23, 43, 53, 73, 83, 103, …; note 33, 63, 93 are excluded because they are not prime).
All jumps must stay within bounds. You must finish exactly at index n − 1.
Output: the maximum total sum reachable.

def max_jump_score(arr: list[int]) -> int: ...
    # arr[i] is the score at index i; arr[0] always counts (start is pre-landed).
    # From i you may move only forward: to i+1, or to i+p for any prime p ending in 3.
    # Must end exactly at index n-1; return the max total score.
    # n == 1 -> return arr[0] (start is already the last index).

Examples

arr = [5, -100, 4, 10] → 15. Jump 0 → 3 with a 3-step jump: 5 + 10 = 15 (skips the -100).
arr = [4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 20] → 24. A 13-step jump (13 is prime, ends in 3) goes 0 → 13 directly: 4 + 20 = 24.
arr = [7] → 7. Already on the last index, so the answer is just arr[0].

Notes

Pre-sieve the set of prime numbers up to n − 1 (limit = n is enough), then filter to those ending in 3. The valid jump-set is small (~n / (ln n) candidates filtered by % 10 == 3, so typically dozens at most for n ≤ 10⁵).
Classic DP: dp[i] = arr[i] + max(dp[i − j]) for every valid jump length j ≤ i. The +1 step is always available; the prime-3 jumps are added on top.
A naive O(n²) solution passes the small visible tests but times out on the hidden cases — the grader runs the solution on large inputs (n near 10⁵).
To get full credit, fall back to a sieve precomputation + bounded DP, or precompute prefix maxima over the jump candidates.
The platform shows ~2–3 visible test cases. You must add your own large random input before submitting — the hidden grader runs offline.
Corner case: n == 1 returns arr[0] directly (no jumps needed).

Preparation

Drill LC 1696 (Jump Game VI) and LC 55 / 45 (Jump Game I / II) until DP transitions feel automatic.
Code a sieve of Eratosthenes from memory; practice extracting the % 10 == 3 subset.
Pre-write a 5-line test harness that generates an n = 10⁵ random array so you can sanity-check your DP runtime in the editor before submitting.

Requirements

Examples

Notes

Preparation

Comments