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 hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Mistral AI.

What role is this question designed for?

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

Compute Remaining GPUs With Switching Limits

Quick Overview

This question evaluates a candidate's ability to perform time-series aggregation, array manipulation, and constrained optimization for selecting resources across multiple clusters and days.

Compute Remaining GPUs With Switching Limits

Company: Mistral AI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Suppose you manage `n` GPU clusters with fixed daily capacities `capacity[i]`. Each day starts fresh with the full capacity, because all GPUs are returned overnight. You are given a list of usage records with the fields: - `day`: integer day number - `cluster`: 0-based cluster index - `gpu`: number of GPUs consumed by that usage on that day Assume all records are valid and the total usage for any cluster on any day never exceeds its capacity. Answer the following related questions: 1. For every distinct day that appears in the input, in increasing day order, compute the remaining GPUs in each cluster at the end of that day. Return a 2D array where each row contains the remaining capacity of every cluster for one day. 2. A new workload can run on exactly one cluster per day and may switch to any cluster between days with no limit. What is the maximum total number of GPUs it can access across all days? 3. Now suppose that workload may switch clusters at most `K` times over the whole time horizon. A switch occurs when the chosen cluster on one day differs from the chosen cluster on the next day. Compute the maximum total GPUs it can access. Example: - `capacity = [10, 20]` - daily remaining capacities might be `[[5, 7], [10, 12], [8, 18]]` For part 2, the best total is `7 + 12 + 18 = 37`.

Quick Answer: This question evaluates a candidate's ability to perform time-series aggregation, array manipulation, and constrained optimization for selecting resources across multiple clusters and days.

Part 1: Daily Remaining GPUs by Cluster

You are given the GPU capacity of each cluster and a list of usage records. Each usage record is a tuple (day, cluster, gpu_used). At the start of every day, all clusters reset to their full capacity because GPUs are returned overnight. Compute how many GPUs remain in each cluster at the end of every day. Usage records may be unsorted, and multiple records may refer to the same day and cluster. Their GPU usage should be added together.

Constraints

0 <= num_days <= 10000
0 <= len(capacities) <= 200
0 <= len(usages) <= 200000
0 <= gpu_used
For every day and cluster, total gpu_used does not exceed that cluster's capacity

Examples

Input: ([10, 20], 3, [(2, 0, 2), (0, 1, 13), (1, 1, 8), (2, 1, 2), (0, 0, 5)])

Expected Output: [[5, 7], [10, 12], [8, 18]]

Explanation: Usages are unsorted. Day 0 leaves [5, 7], day 1 leaves [10, 12], and day 2 leaves [8, 18].

Loading coding console...

Part 2: Maximum Usable GPUs with Unlimited Switching

You are given the GPU capacity of each cluster and a list of daily usage records. A new workload runs once per day. On each day, it may choose exactly one cluster, and it may switch clusters freely between days. The number of GPUs it can use on that day equals the remaining GPUs in the chosen cluster after that day's other usage is subtracted. Each day starts from the original capacities because GPUs reset overnight. Compute the maximum total GPUs this workload can use across all days.

Constraints

0 <= num_days <= 10000
0 <= len(capacities) <= 200
0 <= len(usages) <= 200000
0 <= gpu_used
For every day and cluster, total gpu_used does not exceed that cluster's capacity

Examples

Input: ([10, 20], 3, [(0, 0, 5), (0, 1, 13), (1, 1, 8), (2, 0, 2), (2, 1, 2)])

Expected Output: 37

Explanation: Daily remaining GPUs are [5, 7], [10, 12], and [8, 18]. Take the daily maximums: 7 + 12 + 18 = 37.

Input: ([4, 6], 2, [])

Expected Output: 12

Explanation: Each day the best cluster has 6 GPUs, so the total is 6 + 6.

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

Expected Output: 8

Explanation: Only one cluster exists. Remaining GPUs are 3, 0, and 5.

Input: ([], 3, [])

Expected Output: 0

Explanation: There are no clusters to choose from.

Hints

First compute the remaining GPUs for every day and cluster.
With unlimited switching, the best choice for each day is independent of all other days.

Part 3: Maximum Usable GPUs with At Most K Switches

You are given the GPU capacity of each cluster and a list of daily usage records. A new workload runs once per day for num_days days. On each day, it must choose exactly one cluster, and it can use all GPUs remaining in that cluster after that day's other usage is subtracted. The workload may switch from one cluster to another between consecutive days, but it can do so at most k times in total. Staying on the same cluster does not count as a switch. Each day starts from the original capacities because GPUs reset overnight. Compute the maximum total GPUs the workload can use across all days.

Constraints

0 <= num_days <= 500
0 <= len(capacities) <= 100
0 <= len(usages) <= 200000
0 <= k
0 <= gpu_used
For every day and cluster, total gpu_used does not exceed that cluster's capacity

Examples

Input: ([10, 20], 4, [(0, 1, 15), (1, 0, 8), (2, 1, 15), (3, 0, 8)], 1)

Expected Output: 55

Explanation: Daily remaining GPUs are [10, 5], [2, 20], [10, 5], [2, 20]. With one switch, the best plan is cluster 0 on day 0, then cluster 1 on days 1 to 3: 10 + 20 + 5 + 20 = 55.

Input: ([10, 20], 4, [(0, 1, 15), (1, 0, 8), (2, 1, 15), (3, 0, 8)], 3)

Expected Output: 60

Explanation: With three switches, you can alternate clusters every day and take 10 + 20 + 10 + 20 = 60.

Input: ([10, 20], 4, [(0, 1, 15), (1, 0, 8), (2, 1, 15), (3, 0, 8)], 0)

Expected Output: 50

Explanation: With no switches, pick one cluster for all days. Cluster 1 gives 5 + 20 + 5 + 20 = 50, which is better than staying on cluster 0.

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

Expected Output: 12

Explanation: Only one cluster exists, so switching does not matter. Remaining GPUs are 5, 7, and 0.

Input: ([3, 4], 0, [], 2)

Expected Output: 0

Explanation: There are no days to schedule.

Hints

First convert the raw usage list into a day-by-day remaining GPU table.
Use dynamic programming with state based on day, current cluster, and how many switches have been used so far. To optimize transitions, keep the best and second-best previous values for each switch count.