How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Solve Prime Jumps and Pipeline Scaling

Quick Overview

This question evaluates algorithmic problem-solving skills in constrained path optimization and resource-allocation throughput maximization, including concepts such as graph modelling with prime-step constraints, dynamic programming, number-theoretic reasoning, and combinatorial optimization.

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

An online assessment contains two independent coding problems. Solve both. ### Problem 1: Prime-Constrained Score Jump You are given an integer array `score` of length `n` and an integer `k`. You start at index `0`, and your initial total is `score[0]`. On each move, you may jump from index `i` to index `j` only if: - `j > i`, - `j - i <= k`, and - `j - i` is a prime number. When you land on an index, you add `score[j]` to your total. Return the maximum total score you can obtain when reaching index `n - 1`. If index `n - 1` cannot be reached, return `null`. Assume `score` may contain negative values. ### Problem 2: Maximize Pipeline Throughput You are given a serial processing pipeline with `n` services. Service `i` has: - base throughput `t[i]`, and - expansion cost `cost[i]`. The pipeline throughput is the minimum throughput among all services. You may expand any service any nonnegative integer number of times. If service `i` is expanded `x` times, then: - its throughput becomes `t[i] * (1 + x)`, and - the total money spent on that service is `x * cost[i]`. Given a total budget `budget`, return the maximum possible overall pipeline throughput.

Quick Answer: This question evaluates algorithmic problem-solving skills in constrained path optimization and resource-allocation throughput maximization, including concepts such as graph modelling with prime-step constraints, dynamic programming, number-theoretic reasoning, and combinatorial optimization.

Part 1: Prime-Constrained Score Jump

You are given an integer array score and an integer k. You start at index 0 with an initial total equal to score[0]. On each move, you may jump from index i to index j only if j > i, j - i <= k, and j - i is a prime number. When you land on an index, you add score[j] to your total. Return the maximum total score obtainable when reaching index len(score) - 1. If the last index cannot be reached, return None. The score array may contain negative values.

Constraints

1 <= len(score) <= 5000
-100000 <= score[i] <= 100000
0 <= k <= 5000
A jump length must be prime, so length 1 is not allowed.

Examples

Input: ([5, -2, 4, 10, -1], 3)

Expected Output: 8

Explanation: Valid jump lengths are 2 and 3. The only way to reach index 4 is 0 -> 2 -> 4, giving 5 + 4 - 1 = 8.

Input: ([10, -100, -5, 20, 1, 50], 3)

Expected Output: 80

Explanation: The best path is 0 -> 3 -> 5 using jumps of length 3 and 2, for a total of 10 + 20 + 50 = 80.

Input: ([7, 5], 3)

Expected Output: None

Explanation: The only distance to the last index is 1, which is not prime, so the last index is unreachable.

Input: ([-5], 1)

Expected Output: -5

Explanation: The start index is already the last index, so the answer is score[0].

Input: ([1, 2, 3], 1)

Expected Output: None

Explanation: No prime jump length is at most 1, so no move can be made from index 0.

Hints

First generate all prime jump lengths up to min(k, len(score) - 1).
Use dynamic programming: let dp[i] be the best total score achievable when landing on index i.

Part 2: Maximize Pipeline Throughput

You are given a serial processing pipeline with n services. Service i has base throughput t[i] and expansion cost cost[i]. The pipeline throughput is the minimum throughput among all services. You may expand any service any nonnegative integer number of times. If service i is expanded x times, its throughput becomes t[i] * (1 + x), and the money spent on that service is x * cost[i]. Given a total budget, return the maximum possible overall pipeline throughput.

Constraints

1 <= len(t) == len(cost) <= 100000
1 <= t[i] <= 1000000
1 <= cost[i] <= 1000000
0 <= budget <= 1000000000000
Each service can be expanded only an integer number of times.

Examples

Input: ([10, 20, 30], [5, 10, 15], 10)

Expected Output: 20

Explanation: Spend 5 to expand the first service once, raising it to 20. Reaching 25 or more would require also expanding the second service and would exceed the budget.

Input: ([7], [3], 10)

Expected Output: 28

Explanation: With one service, spend at most 10 on expansions costing 3 each. Three expansions are possible, so throughput is 7 * 4 = 28.

Input: ([5, 8, 3], [2, 2, 2], 0)

Expected Output: 3

Explanation: With zero budget, no expansions are possible, so the throughput remains the minimum base throughput, 3.

Input: ([4, 7], [5, 100], 20)

Expected Output: 7

Explanation: The first service can be raised to at least 7, but raising the second service above 7 costs 100, which is not affordable.

Input: ([3, 5, 10], [4, 6, 100], 18)

Expected Output: 10

Explanation: Target 10 costs 12 for the first service and 6 for the second service, exactly using the budget. Target 11 would require expanding the third service, which is too expensive.

Hints

For a proposed target throughput X, compute the minimum number of expansions each service needs to reach at least X.
The feasibility of a target throughput is monotonic: if X is affordable, then every smaller target is also affordable.

Quick Overview