Lemonade Change

Lemonade Change

What is this problem about?

The "Lemonade Change interview question" is a delightful problem about managing currency. You are running a lemonade stand where each drink costs $5. Customers stand in a queue and pay with either a$5, $10, or$20 bill. You must provide the correct change to each customer. Initially, you have no money. The goal is to determine if you can provide change to every customer in the order they arrive. This "Lemonade Change coding problem" is a classic example of greedy decision-making.

Why is this asked in interviews?

This problem is a staple in entry-level interviews because it tests "Greedy interview pattern" logic and state management. It's simple on the surface but requires you to make the right choice when giving change for a $20 bill. It evaluates whether you can identify that a$10 bill is "less flexible" than two $5 bills and should therefore be used as change first.

Algorithmic pattern used

The Greedy approach is the key. You maintain a count of the $5 and$10 bills you have. When a customer pays:

• **$5 bill:** No change needed. Increment$5 count.
• **$10 bill:** Need$5 change. If you have one, decrement $5 count and increment$10 count. Otherwise, return false.
• **$20 bill:** Need$15 change. You have two options: one $10 + one$5, or three $5s. The greedy choice is to use the$10 bill first because $5 bills are more versatile for future customers.

Example explanation

Queue: [5, 5, 10, 10, 20]

1. **$5:** Have one$5.
2. **$5:** Have two$5s.
3. **$10:** Give one$5 as change. Now have one $5, one$10.
4. **$10:** Give one$5 as change. Now have zero $5s, two$10s.
5. **$20:** Need$15 change. We have two $10s but no$5s. We cannot give change. Result: False.

Common mistakes candidates make

• Poor Greedy Choice: Using three $5 bills to change a$20 when a $10 and a$5 were available.
• **Tracking $20 bills:** Thinking you can use$20 bills to give change (you can't, since the maximum change needed is $15).
• Queue order: Forgetting that you must serve customers in the exact order they appear in the array.

Interview preparation tip

In greedy problems, always ask: "Is there an item that is more valuable to keep for later?" In this case, $5 bills are the most valuable because they can change both$10 and $20 bills, whereas$10 bills can only help with $20 bills.