Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I was asked this interview question at a top internet website company recently.

Certain 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 litre, 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 basically tried to find a math solution(e.g Pascals triangle) to it. The interviewer said not to because it'd get tough quickly(damn). So I said let me consider 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 , he said that you can't add parameters(damn).All this led me to think that I missed something obvious, some trick, did I? It seemed like he was more confused about how to solve it than I was, which is never good in an interview.

share|improve this question
18  
I wouldn't want to work in a company where management's problems are about champagne fountains... –  mouviciel Jan 28 '13 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. –  GlenPeterson Jan 28 '13 at 13:30
4  
@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 '13 at 14:20
1  
Also, this reminds me of Pascal's Triangle.. –  Brad Jan 28 '13 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. –  Slartibartfast Jan 28 '13 at 16:05

5 Answers 5

up vote 33 down vote accepted

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.

share|improve this answer
16  
+1 for the great observation that this is not a tree. –  Mihai Danila Jan 28 '13 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. –  Tom Panning Jan 28 '13 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 '13 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 –  Slartibartfast Jan 28 '13 at 16:08
1  
How do you find left and right glasses? –  kiewic Feb 4 '13 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;
        default:
            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;
        default:
            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.

share|improve this answer
5  
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. –  Luigi Massa Gallerano Jan 28 '13 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. –  GlenH7 Jan 28 '13 at 11:59
    
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 '13 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
        else:
            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)
share|improve this answer

Interesting.

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 = 
{1, 
 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.

share|improve this answer

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.

share|improve this answer
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. –  Winston Ewert Jan 27 '13 at 23:36
    
Time is not part of the simulation, and it won't affect the end results. –  DeadMG Jan 28 '13 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. –  Winston Ewert Jan 28 '13 at 1:19
3  
-1, This is wrong. Levels won't be filled uniformly. –  dan_waterworth Jan 28 '13 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 '13 at 13:55

protected by ChrisF Oct 8 '13 at 18:01

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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