Champagne Tower

Champagne Tower

What is this problem about?

The "Champagne Tower interview question" is a simulation of liquid flowing through a pyramid of glasses. Champagne is poured into the top glass. Once a glass is full (holding 1 unit), any excess champagne flows equally into the two glasses below it. Given the total amount of champagne poured and a specific glass location (row and index), you need to find how much champagne is in that glass.

Why is this asked in interviews?

Google and TikTok use the "Champagne Tower coding problem" to test a candidate's ability to implement a "Dynamic Programming" or "Simulation" approach. It requires careful state management and an understanding of how value distributes across a 2D structure. It evaluates "Array interview pattern" skills, specifically handling boundaries and overflow.

Algorithmic pattern used

This problem uses Dynamic Programming or Iterative Simulation.

1. Grid Representation: Represent the tower as a 2D array or a list of lists where row i has i+1 glasses.
2. Initial State: Place all poured champagne into the glass at (0, 0).
3. Flow Down: Iterate through each row and each glass. If a glass at (r, c) has more than 1 unit:
   • Calculate the overflow: extra = (amount - 1) / 2.0.
   • Add this extra to the two glasses below: (r+1, c) and (r+1, c+1).
4. Boundary: Stop after processing the requested row.

Example explanation

Pour 2 units.

• Glass (0,0): Holds 2 units. Overflow = $(2 - 1) / 2 = 0.5$.
• Glass (1,0): Receives 0.5.
• Glass (1,1): Receives 0.5. Result: Glass (0,0) has 1.0, Glass (1,0) has 0.5, Glass (1,1) has 0.5.

Common mistakes candidates make

• One-at-a-time Simulation: Trying to simulate the flow of champagne drop-by-drop. This is highly inefficient. The DP approach processes the entire volume in one pass through the rows.
• Index Errors: Miscalculating the indices of the children glasses in the pyramid.
• Negative Values: Forgetting to cap the amount in a glass at 1.0 when returning the result (the DP state stores the total that passed through, but the glass can only hold up to 1.0).

Interview preparation tip

Pyramid-shaped problems are common in "Dynamic Programming" interviews. Practice mapping the relationship between dp[i][j] and its children dp[i+1][j] and dp[i+1][j+1]. This pattern is also seen in problems like Pascal's Triangle.