Minimum Amount of Damage Dealt to Bob

Minimum Amount of Damage Dealt to Bob

What is this problem about?

In the Minimum Amount of Damage Dealt to Bob problem, Bob is facing multiple enemies simultaneously. Each enemy has a certain damage they deal per second and a certain amount of health. Bob can only attack one enemy at a time, and he deals a constant power damage per second. While Bob is attacking one enemy, all other living enemies continue to deal damage. You need to find the optimal order in which to kill the enemies to minimize the total damage Bob receives.

Why is this asked in interviews?

This is a modern Minimum Amount of Damage Dealt to Bob interview question recently seen at Amazon. It is a "Job Scheduling" optimization problem. It tests the ability to derive a custom sorting criteria based on a "ratio" of costs. It's a great test of whether a candidate can use mathematical proof (exchange arguments) to justify a greedy strategy.

Algorithmic pattern used

The Greedy with Custom Sorting interview pattern is the core here. For any two enemies A and B, should we kill A then B, or B then A?

• If we kill A first, B deals damage for the time it takes to kill A.
• If we kill B first, A deals damage for the time it takes to kill B. The "time to kill" an enemy is ceil(health / power). By comparing the damage/time ratios (or using a cross-multiplication: damageA * timeB vs damageB * timeA), you can sort the enemies in the optimal order.

Example explanation

Bob power = 10. Enemy A: damage = 5, health = 20 (Time to kill = 2s) Enemy B: damage = 10, health = 50 (Time to kill = 5s)

1. Kill A then B:
   • A dies at 2s. Bob takes damage from B for 2s: 10 * 2 = 20.
   • B dies at 7s. Bob takes damage from B for 5s: 10 * 5 = 50. (Wait, Bob only takes damage from enemies alive. While killing A, both A and B hit him. While killing B, only B hits him.)
   • Total Damage = (5+10)*2 + (10)*5 = 30 + 50 = 80.
2. Kill B then A:
   • B dies at 5s. Bob takes damage from both: (5+10)*5 = 75.
   • A dies at 7s. Bob takes damage from A: 5 * 2 = 10.
   • Total Damage = 75 + 10 = 85. Optimal is killing A first because the damage/time ratio is better.

Common mistakes candidates make

• Sorting by Damage only: Thinking you should always kill the strongest enemy first. If they have massive health, the weaker ones will peck you to death while you struggle.
• Sorting by Health only: Thinking you should kill the "fastest" ones first. If they deal almost no damage, it might be better to ignore them and kill a glass cannon first.
• Precision issues: Using floating point division for the ratio instead of cross-multiplying integers, which can lead to errors with very large numbers.

Interview preparation tip

Whenever you encounter a "minimize total cost over time" problem with multiple tasks, try the Exchange Argument. Compare two tasks (A and B) and see which order is better. This will almost always reveal a Sorting interview pattern based on a specific ratio.