NVIDIA SDE Internship On-Campus

Round 1

Questions: We need to manage a robotic warehouse where N storage racks hold various packages. Each rack has a specific capacity (given in an array), which represents the number of packages stored in it. There are K autonomous robots tasked with moving the packages to a different location. Each robot takes 1 unit of time to move 1 package.

Given the number of robots, number of racks, and capacity of each rack, your task is to determine the minimum time required for all the robots to move all the packages.

Constraints:

1. Given rack capacities [1, 2, 3, 4, 5, 6], each robot can only transport packages from a continuous range of racks. For example, one robot can move packages from racks [2, 3, 4] or racks [5, 6], but it cannot handle non-continuous racks like [1, 3, 4].
2. Rack capacities would be in sorted order.
3. The objective is to ensure that the maximum time taken by any one robot is minimized.
4. Assume that the work is optimally distributed.
5. Assign the racks to each robot so that the longest time taken by any single robot is minimized.
6. If it is not possible to move all packages, please return -1.

Example:

If there are K=2 robots and N=5 racks with capacities [1, 2, 3, 4, 5], the minimum time required for all the robots to move all packages would be 9.

Input:

• N: Number of racks
• K: Number of robots
• capacities: Array of integers where each element represents the capacity of a rack (sorted in non-decreasing order)

Output:

• The minimum time required for all robots to move all packages. If it is not possible to move all packages, return -1.

Above problem similar to: https://leetcode.com/problems/split-array-largest-sum/description/