Filling Wine Glasses Interview Question

Introduction

This is another interesting interview question and took me sometime to think for an answer. The problem statement goes as follow:

“There are wine glasses stacked such that the top level has one glass, the second level has two glasses, the third one has three glasses and so on.
Imaging that the levels are deep enough. Each of the glass in the stack has volume u. Now given a jug of volume V full of wine such that V >= u, find the lowest level where wine can reach.”

Analyzing the problem statement

Here is a supporting image for the problem statement.
Filling Wine Glasses Interview Question
Now I pick up the jug and start pouring the wine into the top one glass. The moment the glass gets filled, it will start overflowing and spill wine in both the glasses at level 2 uniformly. Once the glasses at level two gets filled, it will start spilling the wine in the three glasses at level 3.

Note : Looking at the glasses at level 2, the first glass at level 2 will uniformly spill wine in the first and second glass at level 3. The second glass at level two will uniformly spill wine in glass two and three at level 3. This means that the glass two will get twice the wine as glass one or three in level 3. This alternatively means the the center glass will be filled faster than the other two.

Filling Wine Glasses Interview Question
The same is the case with the second and third glass at level 4. This precisely means that it is not necessary to fill level N completely to start spilling for level N+1. Also, this means that the glasses which are in the centers will fill faster than the ones at the side and so, the level at which wine reaches in the central glasses will be more deep than the side ones.

So ideally the glasses will be filled in the below manner. Thanks to the image on Google Images which clearly shows how. Looking at this, we see the glasses which are in the middle are filled faster and to much deeper levels in the stack.

So, we need to find the maximum level to which wine reaches in volume V.

Solution – Filling Wine Glasses Interview Question

If we analyze this problem it is basically a structure where we have a tree such that each node has exactly two children and except for the side nodes, rest of the nodes have exactly two parents.

Here is the tree.
tree
Now, let us assign V to the root, clearly we have to visit level by level and distribute the remaining volume uniformly in all children of each node.
In level 2, we have remaining volume V-u . We distribute it equally to both children of root. So each glass in level 2 have (V-u)/2 volume.
In level 3 we have remaining volume V – 2u . We distribute it in 4 equal portion, two for each node in level 2. This will result in (V-2u )/4 in the first glass in level 3, 2(V-2u)/4 in middle glass in level 3 and (V-2u)/4 in last glass in level 3.

So let us write the pseudo code for this approach. The idea is to travel one level at a time, for each node at a level, we store u amount of wine at the node and distribute the remaining equally in the two children.

The maxLevel variable gives the level which has wine.

Source Code – Filling Wine Glasses Interview Question

To download the complete source code, please visit the github link for techieme.

Conclusion

This post presents a different perspective to a tree, a tree here can have multiple parents. If we can visualize a problem using a suitable data structure it will be real easy. For the sake of trying, you can try and find a mathematical solution. It gets too complex and hence, it is good to analyze a problem using Data structures.

Don’t forget to subscribe to TechieMe to get updates on latest posts.