Here's the coding task:
You are commanding a team of robots. Each robot:
Can carry a certain number of blocks per second (carry[i])
Has a battery with some initial level (battery[i])
You also have a zapper that can target one robot per second, reducing its battery by k units. If a robot’s battery reaches 0 or below, it stops working and no longer contributes to the block carrying.
Each second:
You zap one robot (your choice).
All working robots carry blocks.
The goal is to zap robots in such a way that the total number of blocks carried before they all shut down (plus one final block to finish the mission) is minimized.
Example:
n = 2
carry = [3, 4]
battery = [4, 6]
k = 3
One possible strategy:
Time Blocks Carried Zapped Robot New Battery
1 3 + 4 = 7 B 6 → 3
2 3 + 4 = 7 B 3 → 0 ❌
3 3 A 4 → 1
4 3 A 1 → -2 ❌
5 1 (final) — —
Total blocks carried: 7 + 7 + 3 + 3 + 1 = 21
Rules: You can zap one robot per second
Robots stop working when battery ≤ 0
All working robots carry blocks every second
After all robots stop, you must carry one final block to complete the mission
Constraints:
1 ≤ n ≤ 10^5 (number of robots)
1 ≤ carry[i], battery[i] ≤ 5000
1 ≤ k ≤ 5000
This is an interview question asked in hackerrank, I dn't have a link of it to share here.
This is what I tried, but my code passed only 5 test cases out of 15 and remaining 10 test cases failed with wrong answer.
import java.util.*;
public class Main {
public static long solve(List<Integer> carry, List<Integer> battery, int k) {
int n = carry.size();
List<int[]> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
int c = carry.get(i);
int b = battery.get(i);
int t = (b + k - 1) / k; // ceil(h / k)
list.add(new int[]{c, t});
}
list.sort((a, b) -> Integer.compare(b[0], a[0]));
long result = 0;
long currentActiveTime = 0;
for (int[] e : list) {
currentActiveTime += e[1];
result += e[0] * currentActiveTime;
}
// Add the final concluding point
result += 1;
return result;
}
public static void main(String[] args) {
System.out.println(solve(Arrays.asList(3, 4), Arrays.asList(4, 6), 3)); // Should print 21
System.out.println(solve(Arrays.asList(1, 2, 3), Arrays.asList(3, 2, 1), 2)); // Should print 12
System.out.println(solve(Arrays.asList(75,45,81,29,2,25,84,56,2,37,39,11,6,68,16,63,49,10,68,80),
Arrays.asList(26,72,47,97,75,82,17,32,28,57,18,79,40,68,40,93,91,55,31,57), 18)); // wrong output 17712
}
}
I added some test cases in the main method with the expected answer, I added one sample test case, which is failing:
System.out.println(solve(Arrays.asList(75,45,81,29,2,25,84,56,2,37,39,11,6,68,16,63,49,10,68,80),
Arrays.asList(26,72,47,97,75,82,17,32,28,57,18,79,40,68,40,93,91,55,31,57), 18)); // wrong output 17712
In log messages, I just found the input and output values, but the actual expected output is hidden for this test case.
Question: How can I minimize the total number of blocks carried before all robots stop (including the one final block)? Is there an efficient greedy or priority queue-based approach to solve this?
Consider 2 robots. The first has carrying capacity c1 and takes b1 zaps to kill. The second has carrying capacity c2 and take b2 zaps to kill.
If we kill robot 1 first, and then immediately kill robot 2, the total blocks carried by those robots during the killing time is:
c1 * b1 + c2 * (b1 + b2)
On the other hand, if will kill robot 2 first and then immediately kill robot 1, the total blocks carried is:
c1 * (b1 + b2) + c2 * b2
It's advantageous to kill robot 1 first if:
c1 * b1 + c2 * (b1 + b2) < c1 * (b1 + b2) + c2 * b2
<=> c2 * b1 < c1 * b2
<=> c1/b1 > c2/b2
So for any two robots killed adjacently, we should kill the one with the highest capacity:battery ratio first, where battery is measured in zaps-to-kill.
Since this relation is transitive (c1/b1 < c2/b2 and c2/b2 < c3/b3 => c1/b1 < c3/b3), establishing the proper order for each adjacent pair establishes the proper order for the whole list...
Sort the robots in order of decreasing capacity:battery ratio, and kill them in that order.