Bloomberg·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Bloomberg coding round with a simulation-style problem that looks straightforward until you actually try to implement it cleanly.

Questions Asked (1)

Given a champagne tower where you pour a certain number of cups into the top glass and each glass overflows equally to the two glasses below it, how full is the glass at a specific row and position?

Algorithms & Data Structures

Author's notes

Took me longer than it should have to realize you just simulate the whole thing row by row, tracking overflow.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the champagne tower as a 2D grid where each glass's overflow is distributed equally to the two glasses below. Use dynamic programming to compute the amount poured into each glass row by row, starting from the top, and then determine the fullness of the target glass.

Pro tip: Clarify that you only need to track rows up to the target row, as overflow beyond that doesn't affect the answer. This shows you understand the problem's boundaries and can optimize space and time.

1. Understand the problem and constraints

Confirm the pouring amount, target row and glass position (0-indexed or 1-indexed), and that overflow is split equally. Clarify that glasses have a capacity of 1 cup.

2. Define the DP state and recurrence

Let dp[i][j] be the amount poured into glass at row i, position j. The recurrence: dp[i][j] = max(0, (dp[i-1][j-1] - 1)/2) + max(0, (dp[i-1][j] - 1)/2), with dp[0][0] = poured.

3. Iterate row by row

Compute dp for rows from 0 to target row, updating only the glasses that can receive overflow. Stop at the target row to save computation.

4. Return the result

The fullness of the target glass is min(1, dp[target_row][target_glass]). If dp is less than 1, that's the amount; otherwise, it's full (1 cup).

Key Points to Mention

Dynamic programming approach with state representing the amount poured into each glass.
Overflow calculation: each glass can hold 1 cup, and any excess is split equally to the two glasses below.
Time complexity O(row^2) and space complexity O(row) if optimized to use a 1D array.
Handling edge cases: target row 0 (top glass), negative or zero poured amount, and glasses that receive no champagne.
Clarify indexing (0-indexed vs 1-indexed) and confirm with the interviewer.
Potential optimization: only compute up to the target row, not the entire tower.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.