Maximum Energy Boost From Two Drinks

Maximum Energy Boost From Two Drinks

1. What is this problem about?

Maximum Energy Boost From Two Drinks is a Dynamic Programming problem where you have two energy drinks, A and B. For each hour, you get a certain boost from drinking A or B. However, if you want to switch from drink A to B (or vice versa), you must skip one hour to make the transition. The goal is to maximize the total energy boost over a fixed number of hours.

2. Why is this asked in interviews?

Microsoft uses this problem to test a candidate's ability to handle state transitions in Dynamic Programming. It's a classic 'decision-making over time' problem. It tests whether you can correctly define the DP state to include not just the current hour, but also which drink you were consuming in the previous hour.

3. Algorithmic pattern used

This problem follows the Dynamic Programming interview pattern. You maintain two DP arrays (or variables): dpA[i] and dpB[i].

• dpA[i] = EnergyBoostA[i] + max(dpA[i-1], dpB[i-2])
• dpB[i] = EnergyBoostB[i] + max(dpB[i-1], dpA[i-2]) This reflects that to have drink A at hour i, you either had it at i-1 or you switched from B, which requires you to have had B at i-2 (skipping i-1).

4. Example explanation

Drink A boosts: [4, 1, 1] Drink B boosts: [1, 1, 5]

• Hour 1: dpA = 4, dpB = 1.
• Hour 2:
  • dpA = 1 + dpA[0] = 1 + 4 = 5.
  • dpB = 1 + dpB[0] = 1 + 1 = 2.
• Hour 3:
  • dpA = 1 + max(dpA[1], dpB[0]) = 1 + max(5, 1) = 6.
  • dpB = 5 + max(dpB[1], dpA[0]) = 5 + max(2, 4) = 9. Maximum boost is 9.

5. Common mistakes candidates make

A frequent error is forgetting the 'skip an hour' rule, leading to a simple greedy choice at each hour. Another is not properly initializing the DP values for the first two hours, which can lead to index-out-of-bounds errors or incorrect base cases. Some might also try to use a 3D DP which is unnecessarily complex.

6. Interview preparation tip

When a problem involves 'switching costs' or 'wait times' between states, think about how the previous state i-k affects the current state i. Drawing a state transition diagram can help clarify which previous values are accessible.