Empty glasses of water are arranged in the following order:

enter image description here

When you pour liquid into the 1st glass if it's full, then the extra liquid would be flown into the glasses 2 and 3 in equal quantities. When glass 2 is full, the extra liquid would be flown into 4 and 5 and so on.

Given an N liters of liquid and maximum capacity of each glass is 1 liter, give the amount of liquid present in any glass if you empty N liters of liquid by pouring into glass by filling out the function getWaterInBucket(int N, int X) where X is the glass number. So for example if I want have 4 liters at the beginning and I want to find the water in glass 3 the function is getWaterInBucket(4, 3)

How do I solve this programmatically? I tried to find a math solution using Pascal's triangle. This did not work. I considered it to be a tree so I can add a parameter like this getWaterInBucket(BTree root, int N, int X) and then try some recursive solution for each level, but parameters are not allowed in this problem. Is there something obvious, some trick?

  • 18
    I wouldn't want to work in a company where management's problems are about champagne fountains...
    – mouviciel
    Jan 28, 2013 at 9:29
  • Can you ever pour into a glass other than glass 1? If not, each tier will have equal amounts of water in each glass. Thus, you will have full tiers whenever you pour 1, 3, 6, 10 ... liters. If you pour 7 litres, then the fourth row has 4 glasses so each will be 1/4 full. All the tiers above it will be full. Jan 28, 2013 at 13:30
  • 5
    @GlenPeterson From how I'm reading it I don't think they would fill equally. Yes, 2 & 3 would fill equally because they only have one thing pouring into them but once they are full 2 pours equally into 4/5 and 3 pours equally into 5/6, thus 5 gets filled at twice the rat of 4/6. The center cups are always filling faster than the outer cups. by the time 4/6 are full 8/9 are 25% full and 7/10 are still empty.
    – Brad
    Jan 28, 2013 at 14:20
  • 1
    Also, this reminds me of Pascal's Triangle..
    – Brad
    Jan 28, 2013 at 15:03
  • @mouviciel Haha GlenPeterson - The first glass to be poured is always glass 1 . The interviewer also said to use this information. He seemed more confused than I was about the right answer to this problem. Jan 28, 2013 at 16:05

5 Answers 5


You just need to simulate the pouring, something like

void pour(double glasses[10], int glass, double quantity)
    glasses[glass] += quantity;
    if(glasses[glass] > 1.0)
         double extra = glasses[glass] - 1.0;
         pour( glasses, left_glass(glass), extra / 2 );
         pour( glasses, right_glass(glass), extra / 2 );
         glasses[glass] = 1.0;

double getWaterInGlass(int N, int X)
    double glasses[10] = {0,0,0,0,0,0};
    pour(glasses, 0, X);
    return glasses[N];

As it stands, this is not a tree. Because different glasses pour into the same glasses, that prevents it from being a tree.

  • 16
    +1 for the great observation that this is not a tree. Jan 28, 2013 at 0:31
  • 2
    Good answer. In an interview, you should say that this could have scalability problems because it calculates the contents of all glasses. Also, you need to handle the case where water pours out of the bottom row of glasses. And you want to return glasses[N-1], because the glass numbers start at 1 instead of 0. Jan 28, 2013 at 14:45
  • 1
    I think the challenging part might be figuring out the indexes of the left and right children. If you presented this the interviewer is just going to ask you implement those functions. There may be an explicit formula.
    – James
    Jan 28, 2013 at 15:47
  • That is a really elegant solution . Thanks. I'd be grateful if you could edit it to add comments to lines of code to explain what each step signifies in the thought process. Also the number of glasses is not restricted to 10. It could be anything Jan 28, 2013 at 16:08
  • 1
    How do you find left and right glasses?
    – kiewic
    Feb 4, 2013 at 8:21

Here's how I would answer this question in an interview situation (I haven't seen this question before, and I didn't look at the other answers until I had my solution):

First, I tried to just figure it out (which you called the "math solution") and when I got to glass 8 I realized that it would be tougher than it seemed because glass 5 starts to overflow before glass 4. At that point I decided to go down the recursion route (just an FYI, a lot of programming interview questions require recursion or induction to solve).

Thinking recursively, the problem becomes much easier: How much water is in glass 8? Half of the amount that has spilled out of glasses 4 and 5 (until it is full). Of course, that means we have to answer how much has spilled out of glasses 4 and 5, but it turns out that's not too hard either. How much has spilled out of glass 5? Half of however much spilled out of glasses 2 and 3, minus the liter that stayed in glass 5.

Solving this completely (and messily) gives:

#include <iostream>
#include <cmath>
using namespace std;

double howMuchSpilledOutOf(int liters, int bucketId) {
    double spilledInto = 0.0;
    switch (bucketId) {
        case 1:
            spilledInto = liters; break;
        case 2:
            spilledInto = 0.5 * howMuchSpilledOutOf(liters, 1); break;
        case 3:
            spilledInto = 0.5 * howMuchSpilledOutOf(liters, 1); break;
        case 4:
            spilledInto = 0.5 * howMuchSpilledOutOf(liters, 2); break;
        case 5:
            spilledInto = 0.5 * howMuchSpilledOutOf(liters, 2) + 0.5 * howMuchSpilledOutOf(liters, 3); break;
        case 6:
            spilledInto = 0.5 * howMuchSpilledOutOf(liters, 3); break;
            cerr << "Invalid spill bucket ID " << bucketId << endl;
    return max(0.0, spilledInto - 1.0);

double getWaterInBucket(int liters, int bucketId) {
    double contents = 0.0;
    switch (bucketId) {
        case 1:
            contents = liters; break;
        case 2:
            contents = 0.5 * howMuchSpilledOutOf(liters, 1); break;
        case 3:
            contents = 0.5 * howMuchSpilledOutOf(liters, 1); break;
        case 4:
            contents = 0.5 * howMuchSpilledOutOf(liters, 2); break;
        case 5:
            contents = 0.5 * howMuchSpilledOutOf(liters, 2) + 0.5 * howMuchSpilledOutOf(liters, 3); break;
        case 6:
            contents = 0.5 * howMuchSpilledOutOf(liters, 3); break;
        case 7:
            contents = 0.5 * howMuchSpilledOutOf(liters, 4); break;
        case 8:
            contents = 0.5 * howMuchSpilledOutOf(liters, 4) + 0.5 * howMuchSpilledOutOf(liters, 5); break;
        case 9:
            contents = 0.5 * howMuchSpilledOutOf(liters, 5) + 0.5 * howMuchSpilledOutOf(liters, 6); break;
        case 10:
            contents = 0.5 * howMuchSpilledOutOf(liters, 6); break;
            cerr << "Invalid contents bucket ID" << bucketId << endl;
    return min(1.0, contents);

int main(int argc, char** argv)
    if (argc == 3) {
        int liters = atoi(argv[1]);
        int bucket = atoi(argv[2]);
        cout << getWaterInBucket(liters, bucket) << endl;
    return 0;

At this point (or as I was writing this out), I would tell the interviewer that this isn't the ideal solution in production: there's duplicate code between howMuchSpilledOutOf() and getWaterInBucket(); there should be a central location that maps buckets to their "feeders". But in an interview, where speed and accuracy of implementation are more important that speed of execution and maintainability (unless otherwise indicated), this solution is preferable. Then I would offer to refactor the code to be closer to what I consider production-quality, and let the interviewer decide.

Final note: I'm sure my code has a typo in it somewhere; I would mention that to the interviewer too and say that I would feel more confident in it after either refactoring it or unit-testing it.

  • 6
    This solution is hard-coded for the example. Adding glasses means adding "case" to the switch... I don't think it's a good solution. Jan 28, 2013 at 8:20
  • 2
    @LuigiMassaGallerano - that's ok in this case as it's an interview question; it's not supposed to be a perfect solution. The interviewer is trying to get a better understanding of the candidate's thought process. And Tom already points out that this isn't the ideal solution.
    – user53019
    Jan 28, 2013 at 11:59
  • 1
    It honestly isn't. I can assure you this scenario wasn't intended to be hard coded. If I asked an interview question and laid out a test case scenario which the interviewee presented a hard coded solution he better be prepared to offer a general solution or he probably isn't going to pass the interview.
    – Rig
    Oct 8, 2013 at 17:27

Thinking about this as a tree problem is a red-herring, it's really a directed graph. But forget all about that.

Think of a glass anywhere below the top one. It will have one or two glasses above it that can overflow into it. With the appropriate choice of coordinate system (don't worry, see the end) we can write a function to get the "parent" glasses for any given glass.

Now we can think about an algorithm to get the amount of liquid poured into a glass, irrespective of overflow from that glass. The answer is however much liquid is poured into each parent minus the amount stored in each parent glass, divided by 2. Just sum that for all parents. Writing this as a python fragment of the body of an amount_poured_into() function:

# p is coords of the current glass
amount_in = 0
for pp in parents(p):
    amount_in += max((amount_poured_into(total, pp) - 1.0)/2, 0)

The max() is to ensure we don't get a negative amount of overflow.

We are almost finished! We choose a coordinate system with 'y' down the page, first row glasses is 0, second row is 1, etc. The 'x' coordinates have a zero under the top row glass and the second row have x coordinates of -1 and +1, third row -2, 0, +2, and so on. The important point is that the left or right-most glass in level y will have abs(x) = y.

Wrapping all that up into python (2.x), we have:

def parents(p):
    """Get parents of glass at p"""

    (x, y) = p
    py = y - 1          # parent y
    ppx = x + 1         # right parent x
    pmx = x - 1         # left parent x

    if abs(ppx) > py:
        return ((pmx,py),)
    if abs(pmx) > py:
        return ((ppx,py),)
    return ((pmx,py), (ppx,py))

def amount_poured_into(total, p):
    """Amount of fluid poured into glass 'p'"""

    (x, y) = p
    if y == 0:    # ie, is this the top glass?
        return total

    amount_in = 0
    for pp in parents(p):
        amount_in += max((amount_poured_into(total, pp) - 1.0)/2, 0)

    return amount_in

def amount_in(total, p):
    """Amount of fluid left in glass p"""

    return min(amount_poured_into(total, p), 1)

So to get the amount actually in a glass at p, use amount_in(total, p).

It's not clear from the OP, but the bit about "you cant add parameters" may mean the original question has to be answered in terms of the glass numbers shown. This is solved by writing a mapping function from the show glass numbers to the internal coordinate system used above. It's fiddly, but either an iterative or mathematical solution can be used. An easy to understand iterative function:

def p_from_n(n):
    """Get internal coords from glass 'number'"""

    for (y, width) in enumerate(xrange(1, n+1)):
        if n > width:
            n -= width
            x = -y + 2*(n-1)
            return (x, y)

Now just rewrite the amount_in() function above to accept a glass number:

def amount_in(total, n):
    """Amount of fluid left in glass number n"""

    p = p_from_n(n)
    return min(amount_poured_into(total, p), 1)


This takes the simulation approach.

private void test() {
  double litres = 6;
  for ( int i = 1; i < 19; i++ ) {
    System.out.println("Water in glass "+i+" = "+getWater(litres, i));

private double getWater(double litres, int whichGlass) {
  // Don't need more glasses than that.
   * NB: My glasses are numbered from 0.
  double[] glasses = new double[whichGlass];
  // Pour the water in.
  pour(litres, glasses, 0);
  // Pull out the glass amount.
  return glasses[whichGlass-1];

// Simple non-math calculator for which glass to overflow into.
// Each glass overflows into this one and the one after.
// Only covers up to 10 glasses (0 - 9).
int[] overflowsInto = 
 3, 4, 
 6, 7, 8, 
 10, 11, 12, 13, 
 15, 16, 17, 18, 19};

private void pour(double litres, double[] glasses, int which) {
  // Don't care about later glasses.
  if ( which < glasses.length ) {
    // Pour up to 1 litre in this glass.
    glasses[which] += litres;
    // How much overflow.
    double overflow = glasses[which] - 1;
    if ( overflow > 0 ) {
      // Remove the overflow.
      glasses[which] -= overflow;
      // Split between two.
      pour(overflow / 2, glasses, overflowsInto[which]);
      pour(overflow / 2, glasses, overflowsInto[which]+1);

which prints (for 6 liters):

Water in glass 1 = 1.0
Water in glass 2 = 1.0
Water in glass 3 = 1.0
Water in glass 4 = 0.75
Water in glass 5 = 1.0
Water in glass 6 = 0.75
Water in glass 7 = 0.0
Water in glass 8 = 0.25
Water in glass 9 = 0.25
Water in glass 10 = 0.0

which seems to be about right.


This is the binomial function. The ratio of the water between the glasses of level N can be discovered using nCr for each glass in the level. In addition, the total number of glasses prior to level N is the sum of 1 to (N - 1), a formula for which you should be able to find available fairly easily. Thus, given X, you should be able to determine it's level, and use nCr to check the ratios of the glasses for that level, and thus determine how much water is in X, if there are enough liters to go down to X anyway.

Secondly, your idea of using the BTree is fine, it's just that the BTree is an internal variable, not an external parameter.

IOW, if you've covered this mathematics in your education (here in the UK it's taught prior to university) then you should be able to solve this without too much problem.

  • 1
    I don't think it is the binomial function. It reaches the third level in proportions of 1,2,1 as the binomial function would suggest, but the middle glass fills up first and the pattern is broken after that. Jan 27, 2013 at 23:36
  • Time is not part of the simulation, and it won't affect the end results.
    – DeadMG
    Jan 28, 2013 at 1:12
  • 4
    since its modeling liquid filling up and flowing out of glasses I'd have to maintain that time is implicitly part of the simulation. At 5 litres, 4 & 6 will be half full, and 5 will be all full. When the sixth litre is added, it will start pouring into 8 & 9, but 7 & 10 will receive no water because 4 & 6 have not yet hit capacity. Thus, the binomial function won't predict the correct values. Jan 28, 2013 at 1:19
  • 3
    -1, This is wrong. Levels won't be filled uniformly. Jan 28, 2013 at 7:50
  • You're right, I didn't consider it. But after I thought about it for a while, I realized that you were correct. Not sure how to adjust the formula to take this into account.
    – DeadMG
    Jan 28, 2013 at 13:55

Not the answer you're looking for? Browse other questions tagged or ask your own question.