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.

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.

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.

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.

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.