Facebook Interview Question for Software Engineer / Developers


Country: United States




Comment hidden because of low score. Click to expand.
6
of 8 vote

Solved it with O(k).
The idea is simple. Pour L into coup 1. Divide into its children if overflows. Do this for subsequent elements, until find k.
The biggest problem is to find the children. The first child of a coup is the same of last if height does not change. The second one is first + 1.
For the given example, children would found in the the folowing order (se how children repeats when height repeats (kth is one based!):

Height: 1  2  2  3  3  3
Coup  : 1  2  3  4  5  6
Child : 23 45 56 78 89 910

	public static double calculateWaterVol(double c, double l, int kth /* one based */) {
		int [] height = new int[kth];
		double[] water = new double[kth];
		water[0] = l;
		int childIndex = 0;
		for (int i=0; i<(kth-1);++i) {
			double over = 0.0;
			if (water[i] > c) {
				over = (water[i] - c)/2;
				water[i] = c;
			}
			if (i == 0 || height[i-1] < height[i]) {
				++childIndex;
			}
			if (childIndex >= kth) break;
			height[childIndex] = height[i]+1;
			water[childIndex] += over;
			++childIndex;
			if (childIndex >= kth) break;
			height[childIndex] = height[i]+1;
			water[childIndex] += over;
		}
		return water[kth-1] >  c ? c : water[kth-1];
	}

- lucas.eustaquio August 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

quite impressive..

thanks a lot..

- Anonymous August 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice and easy solution!

The only comment I could make is that
childIndex can be calculated in the following way
childIndex = i + height[i] + 1 for the first child,
childIndex += 1 for the next.

- kala kutta August 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It would make the code more understandable. Thanks!

- lucas.eustaquio August 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The solution is also using space O(k) ... correct me if I am wrong, also what do you mean by kth is one based ?

- Anonymous September 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Space O(k) is right. K one based means the first k is 1, instead of 0. The first k will be 1, second 2, and so on.

- lucas.eustaquio September 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

good idea.
One minor issue is that we need init height[0] = 1

- Anonymous November 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

is there any easy way to get the higher of an element just knowing the ith of the element?

- Oscar March 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Idea is good, but code is wrong. Just take a simple example: c=2.0, l=1.0, kth=2. The correct answer is 0.5, but the code returns 0.0.

- Anonymous April 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Must be easy to correct.
As for the easy way to find the height given kth: the total number of cups it is an arithimetical progression of h: (1+2+3+4+5...+n). That creates a relationship between h and n. n = h(h+1)/2 (A.P. formula). n = h²/2 + h/2 or h²/2 + h/2 - n = 0. Solve this equation using bhaskara ((-b + sqrt(b²-4ac))/2a, with a=0.5, b=0.5 and c=n).
That should do it!

- lucas.eustaquio April 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't quite understand your idea, but I think the question is bit more complicated than your thought. The cups are not filled by levels:
1
2 3
4 5 6
7 8 9 (10)
if we pour water:
cup 1 filled first;
then cup 2,3 filled at the same time;
then since 5 have two resources, the time when 5 is filled, 2,3 are only half filled:
1
2 3
4 5 6
8 9
Then cup 8,9 start to get filled but 7,(10) remains empty.
I don't quite understand your algorithm how this could be simply divided into two sub-problem.

- nanny November 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thats exactly what was implemented.
The idea of the algorithm is simple. Put all water on cup 1.
Then for all cups do (1 to n, only once):
1. If there is more water than capacity subtract the exceding water and put half of each on the 2 cups directly below.

The variables height and child index are just to figure that out. Run it debugging and you will see.

- lucas.eustaquio November 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ok. i see what you are saying . "divide the water" i thought you mean dividing the problem.

- nanny November 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks lucas.eustaquio. I built the following solution on top of your solution.

public static double[] calculateWaterVolumeFirstNCups(double capacityPerCup, double totalWaterVolume, int n) {
		double[] waterInCups = new double[n];
		waterInCups[0] = totalWaterVolume;
		int currentLevel = 1;
		int elementsAtLevel = 0;
		
		// Iterate over all cups (until kth cup) 
		for(int i=0; i<n; i++){
			double overflowingVolume = 0.0d;
			
			// Determine level of the ith cup
			elementsAtLevel++;
			if(elementsAtLevel>currentLevel){
				elementsAtLevel = 1;
				currentLevel++;
			}
			
			// check if ith cup is overflowing
			if(waterInCups[i] > capacityPerCup){
				overflowingVolume = waterInCups[i] - capacityPerCup;
				waterInCups[i] = capacityPerCup;
			}
			
			// if the cup is overflowing overflowing, divide the distribute water volume to cups below the ith cup
			if(overflowingVolume>0){
				int firstChild = (i + currentLevel); // First child cup below the ith cup
				if(firstChild<n){
					waterInCups[firstChild]+=(overflowingVolume/2);
				}
				firstChild++; // advance to the second cup below ith cup
				if(firstChild<n){
					waterInCups[firstChild]+=(overflowingVolume/2);
				}
			}
		}
		return waterInCups;
	}
	
	public static void main(String[] args){
		System.out.println(calculateWaterVolumeFirstNCups(1, 4, 8)[5]); // 6th cup
	}

- AbhiM August 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice idea. here is my version:

public double fillWater(int c, int l, int k){		
		double[] water = new double[k+1];
		int level = 1;
		int i = 1;
		water[1]=l;
		for(int j=0; j<level; j++){
			if(water[i]>c){
				double extra = water[i]-c;
				water[i+level]+=extra/2;
				water[i+level+1]+=extra/2;
			}
			// if k has alrady been filled, break because we don't care about cups below.
			if(i+level==k || i+level+1==k) 
				break;
			// increment level if we've reached last item in current level
			if(j==level-1){
				j=-1;
				level++;
			}
			i++;
		}
		// if its above capacity, it would be ful and we remove extra.
		if(water[k]>c) 
			water[k]=c;
			
		return water[k];
	}

- crime7 September 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

What about this?
I am building up the nodes from top-bottom and assigning water to it.
I can know the 2 children of a node based on the level of a node, since at each level there are (level+1) nodes.

struct nodeInfo
{
	int level;
	int water;
}


int fillWater(int L, int C, int i /*0 based*/)
{
	struct nodes[2*i] = {0};
	
	nodes[0].level = 0;
	nodes[0].water = L;
	
	int index = 0;
	while(index <= i)
	{
           int level = nodes[index].level;
	   int child1Index = index + level + 1;
	   int child2Index = index + level + 2;

	   nodes[child1Index].level = level + 1;
	   nodes[child2Index].level = level + 1;

	   if(nodeInfo[index].water > C)
	   {
               nodes[child1Index].water += (nodes[index].water - C)/2;
	       nodes[child2Index].water += (nodes[index].water - C)/2;
	   }
           index++;
	}
	return nodeInfo[i].water;
}

- ksh October 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Yeah, it is good too and easier to understand.

- Anonymous November 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I like it because it's simple but it calculates the water of much more cups than it's necessary to answer the question.

- Safi December 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I write this in Java. I think this is more easy to understand, but maybe not short enough.
{

public double calculateWaterVol(double c, double l, int kth)
{
// the first cup is numbered as 1, not 0.
int height = 1;
int currentTotal = height;
double water[] = new double[kth];
water[0] = l;

for (int i=1; i<kth; i++)
{
if (i > currentTotal)
{
height++;
currentTotal += height;
}
if (water[i-1] > c)
{
double overLoad = (water[i-1] - c)/2;
int leftChild = i + height;
int rightChild = i + height + 1;
if (leftChild > kth)
break;
else
water[leftChild-1] = overLoad;

if (rightChild > kth)
break;
else
water[rightChild-1] = overLoad;

water[i-1] = c;
}
}

return water[kth-1]>c? c: water[kth-1];
}

}

- Jason.WengPengfei January 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think we can do it in O(level of ith cup) also, idea is to calculate the water required to fill ALL the cups till nth level.
Water required to fill 1st level = C
Water required to fill 2nd level = 2C ( because 2 cups are there )
Water required to fill 3rd level = 3C ( 3 cups)
and so on

so water required to fill all the cups till nth level will be:
C + 2C + 3C + 4C + .... + nC = C * n * (n+1) / 2

Ok, now that we are given the cup number i, we can determine its level in O(level) let say L.

Now we need to check how much water is required to fill the cups completely till (L-1)th level.

water_required = C * L * (L-1) / 2; 
if( water_required < M ) return 0; // i.e. upper cups are not filled (no overflow)
else {
      int water_overflowed =  M - water_required;
      return (water_overflowed)/ no_of_cups_in_level_L;
}

- HauntedGhost February 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is how I would do it, but as someone mentioned above, not all cups are filled with the same amount of water.

- Maggie September 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

the pyramid actually looks like
1
2 3
4 5 6

- Anonymous July 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am nt able to make the pyramid properly . Its in acute triangle shape. and wen water flows from 1 it gets transfered to both 2 and 3 equally.

- Anonymous July 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's what you meant:

1
 2 3
4 5 6

- anon July 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what is M here?

- Anonymous July 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ anon yaa this is what i meant :)
and M is the total amount of water poured initially

- Anonymous July 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution : for L leter of water
max full cup level :l=Log(L/C+1) this gives the max level of nodes which are full.
Now if i<=l then cup number i is full otherwise i should be at the next level which should contail (L-lC)/nodes at that level.
nodes at that level=pow(2,l).

problem wud be more tuff if the capacity of each cup wud vary according to their label.
Any suggestions are appriciable.

- mrn July 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i guess you are not taking into account that cup 5 will get water from both 2 and 3 whereas cup 4 will get water only from 2 .
so if we have 25 litres of water then cup 5 will end up with 5 litres and cup 4 and 6 woth 2.5 each
Plz correct me if i am wrng

- kk July 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ohh sorry i solved it for a binary tree. :)
1. i=1 and decrease (i++) from L until we get 0(it is the right corner node) or negative(if differ just by one from last value of i then left corner node).
2.At the same time increase level (l) variable to get level of that node.
3. Now the situation of full+partially full cups is at the last two levels (if at all L can fill up cups upto this level whether partially or fully).
so we decrease from L (if possible) , the number of nodes N upto grandparent level (l-2) of i (N*C) and assign it new value
4. for remaining water if L-(l-1) > 0 then node is definitely partially fulled else subtract from L until we reach i or until L gets exhausted.

- mrn July 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The i th row starts with i*(i-1)/2+1 indexed cup and ends with i*(i+1)/2 indexed cup. We have three cases, two for the cups at ends and one for the cups between them.
The cups at the end are filled by only one cup lying above while the ones in between are filled by two cups. We find the amount of water spilled by the cups responsible for filling a cup recursively. For the cup whose content needs to be determined returns the spilledWater or capacity whichever is less


#include<cstdio>
#include<cmath>
#include<iostream>
bool isLeftMost(int index);
bool isRightMost(int index);
#define GETROW(index)((1 + (int)sqrt(-1+4*(index)*2*1.0))/2)
#define GETLEFTMOST(row)((row)*((row)-1)/2+1)
#define GETRIGHTMOST(row)((row)*((row)+1)/2)
double getSpilled(int cap, int vol, int index);
double getRecv(int cap, int vol, int index);
int getLeftParent(int index);
using namespace std;
int main()
{
int temp;
cout<<"Enter the capacity ";
int c;
scanf("%u", &c);
cout<<"Enter the volume of fluid ";
int vol;
scanf("%u", &vol);
while(true)
{
cout<<"Enter the number of cup ";
int num;
scanf("%u", &num);
double content = getRecv(c,vol, num);
cout<<"fluid content = "<<content<<'\n';
}

}
double getRecv(int cap, int vol, int index)
{
double recv;
if(index == 1)
return vol<cap?vol:cap;
else if(isLeftMost(index))
{
int upperIndex = GETLEFTMOST(GETROW(index)-1);
recv = getSpilled(cap, vol, upperIndex)/2;
}
else if(isRightMost(index))
{
int upperIndex = GETRIGHTMOST(GETROW(index)-1);
recv = getSpilled(cap, vol, upperIndex)/2;
}
else
{
recv = getSpilled(cap, vol, getLeftParent(index))/2
+ getSpilled(cap, vol, getLeftParent(index)+1)/2;
}
return recv<cap?recv:cap;
}
double getSpilled(int cap, int vol, int index)
{
double recv = 0;
if(index == 1)
return vol-cap>0?vol-cap:0;
else if(isLeftMost(index))
{
int upperIndex = GETLEFTMOST(GETROW(index)-1);
recv = getSpilled(cap, vol, upperIndex)/2;
}
else if(isRightMost(index))
{
int upperIndex = GETRIGHTMOST(GETROW(index)-1);
recv = getSpilled(cap, vol, upperIndex)/2;
}
else
{
recv = getSpilled(cap, vol, getLeftParent(index))/2
+ getSpilled(cap, vol, getLeftParent(index)+1)/2;
}
return recv-cap>0?recv-cap:0;
}
int getPos(int index)
{
return 1 + index - GETLEFTMOST(GETROW(index));
}
int getLeftParent(int index)
{
int pos = getPos(index);
return GETLEFTMOST(GETROW(index)-1)+pos-2;
}
bool isLeftMost(int index)
{
int num = GETROW(index);
if(GETLEFTMOST(num) == index)
return true;
return false;
}
bool isRightMost(int index)
{
int num = GETROW(index);
if(GETRIGHTMOST(num) == index)
return true;
return false;
}

- K Kishore July 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your solution is top down...
can we do it using DP bottom up..
what is time complexity of your algorithm?

- kk July 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Thanks for pointing out. I think, complexity is O(n) where n is the index of the cup, for the above solution. We can modify each recursive call to store the values of spilled water.

- K Kishore July 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Pseudo code:

float findAmount(int L, int C, int i)
{
int j=0;
float jc=0.0f;
while(L && i>0)
{
j++;
if(L>=(C*j))
{
jc=C;
L=L-(C*j);
}
else
{
jc= L/j;
}
i-=j;
}
return jc;
}


Plz correct me if it is wrong...

- Sonal July 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry for this post...please see the next one...n correct me if m wrong!!

- Sonal July 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

float findAmount(int L, int C, int i)
{
    int j=0;
    float jc=0.0f;
    while(L && i>0)
    {
        j++;
        if(L>=(C*j))
        {
            jc=C;
            L=L-(C*j);
        }
        else
        {
            jc= (float)L/j;
            L=L-(jc*j);
        }
        i-=j;
    }
    if(L<=0 && i>0)
        return 0.0f;
    return jc;
}

- Sonal July 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i= numbers= of cups

- Anonymous July 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I use recursive method to solve the problem.ps: php language.

<?php
$cupWater = array(); // water in each cup
function findAmount($l, $c, $i) { // find water amount in ith cup
    global $cupWater;
    flow($l, $c, 1); // recurve from cup 1
//    echo 'result:';
    echo $cupWater[$i] ? $cupWater[$i]:0;
//    print_r($cupWater);// show water in each cup
}

function flow($l, $c, $mid) { // pour water    
    global $cupWater;
    $rest = $c - $cupWater[$mid]; // how much water left unfilled in current cup
//    echo 'rest:'.$rest . '<br />';
    if ($l <= $rest) {
        $cupWater[$mid] += $l;
        return;
    } else {
        $cupWater[$mid] = $c;
        list($left, $right) = getLeftRightNode($mid);
//        echo $left . ' '.$right .'<br />';
        flow(($l - $rest) / 2, $c, $left);
        flow(($l - $rest) / 2, $c, $right);
    }
}

function getLeftRightNode($mid) {
// get the indexes of the two cups which get water equally from cup $mid
    $n = getLayerNum($mid);
//    echo 'layer for point '. $mid. ' is:'.$n.'<br />';
    $l = $mid + $n;
    $r = $l + 1;
    return array($l, $r);
}

function getLayerNum($mid) {
    // get the layer of cup $mid
    $n = 1;
    while (1) {
        $bottom = ($n * $n - $n + 2) / 2;
        $top = ($n * $n + $n) / 2;
//        echo 'n is: '.$n.' mid is: '.$mid. ' bot: '.$bottom. ' top: '.$top. '<br />';
        if ($mid >= $bottom && $mid <= $top) {
            break;
        } else {
            $n++;
        }
    }
    return $n;
}

findAmount(17, 3, 5);
?>

- Elle July 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Given r the row of cup there are r/2 * (r+1) cups. So we need to find the first r such that r/2 * (r+1) * C > L. for the i < r/2 * (r-1) they are filled. for i > r/2 * (r-1) they are (L - r/2 * (r-1) * C) / r filled.
So the trick is to find r. There are two way either solve the in eq. r^2 + r - 2L/C >= 0 or doing the following:

r <-- 2^0
    while(r/2*(r+1) < L/C) do
        r = 2*r;

    r <-- modified_binary_search(r, r/2, L, C);

- saimok July 29, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I do not think that this solution is right... The rate of inflow will vary for the cups in same row.. cups at the ends will have slower inflow..

- Ashish Kumar Singh July 29, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree with Asish

- Anonymous July 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This will calculate the overflows, from which it is easy to calculate what each cup holds:

public class FlowingCups {
	private static final float c = 6.0f;

	public static void main(String[] args) {
		System.out.println(overflow(3,2));

	}
	
	public static float overflow(int level, int pos) {
		if(level == 1) {
			if(c  > 1.0f) {
				return c-1.0f;
			} else {
				return 0.0f;
			}
		}
		if(pos == 1) {
			return (overflow(level-1, 1) / 2.0f)-1.0f;
		} else if(pos == level) {
			return (overflow(level-1, level-1) / 2.0f)-1.0f;
		}
		else {
			return (overflow(level-1, pos-1) / 2.0f + overflow(level-1, pos) / 2.0f) -1.0f;
		}
	}

}

- memo July 30, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I should add, that the i,j th result should be cached in an optimal answer.

- memo July 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I should also add that, the code is buggy in the sense you can get negative overflow. You need to make a check like in level==1 for the other levels also.

- memo July 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

if L<=C then L goes to cup #1

if C<L<=3C then #1 is filled, cups #2 and #3 gets (L-C)/2

if 3C<L<=5C then cups #1,#2,and #3 are filles, cup #4 and #6 gets (L-3C)/4 and cup #5 gets 2(L-3C)/4

if 5C<L<=7C then cups #1,#2,#3,#4, #5, #6 are filled, cups #8 and #9 are half, and rest are empty

if 7C<L<7.5 then cups #1 to #6 and #8, and #9 are filled, cups #7 and #10 are 1/4 filled

so, the next step is to generalized this formula

- Anonymous July 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Same logic as above, but building the pyramid instead of calculating its children.

public static double calculateWaterVol2(double c, double l, int kth) {
		double[][] pyramid = buildCupPyramid(kth);
		pyramid[0][0] = l;
		for (int k=1, h = 0; h < pyramid.length; ++h) {
			for (int i=0; i<pyramid[h].length;++i, ++k) {
				if (pyramid[h][i] > c) {
					if (h < pyramid.length - 1) {
						double over = (pyramid[h][i]-c)/2;
						pyramid[h+1][i] += over;
						pyramid[h+1][i+1] += over;
					}
					pyramid[h][i] = c;
				}
				if (k == kth)
					return pyramid[h][i];
			}
		}
		return 0.0;
	}
	
	private static double[][] buildCupPyramid(int kth) {
		int n = 0;
		int h = 0; // 1, 2, 3, 4 ...
		while (n < kth) {
			++h;
			n += h;
		}
		double[][] pyramid = new double[h][];
		for (int i=0; i<pyramid.length;++i) {
			pyramid[i] = new double[i+1];
		}
		return pyramid;
	}

- lucas.eustaquio August 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The cups are arranged in form of pascal's triangle, the amount will be equal to (L-C) times the corresponding Pascal's coefficient.

- Vinay August 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Great solution.

- PlayerOne September 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is just wrong

- Anonymous September 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1
2 3

- Anonymous August 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

since we are only interested in the water at cup i, you can just go back up by tracing the parents instead of tracing the kids. algorithmically it should be < O(n) but i dont know how to prove that. ie

water(cup i ) = water (cup (1stparent(i)) + water (cup(2ndparent(i))

That way you only calculate water for the tree that is responsible for pouring water into cup i.

- sharathgeorge September 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class FillCups {
     public static float _calc(int capacity, float water, int level, int cur, int i) {
         if (water <= 0) {
             return 0;
         }

         if (cur == i) {
             return water > capacity ? capacity : water;
         } else {
             if (water <= 0) {
                 return 0;
             }

             float per_child = (water - capacity) / 2;

             float res = _calc(capacity, per_child, level+1, level+cur, i) +
                         _calc(capacity, per_child, level+1, level+cur+1, i);

             return res > capacity ? capacity : res;
         }
     }

     public static float calc(int capacity, float water, int nth) {
         return FillCups._calc(capacity, water, 1, 1, nth);
     }

     public static void main(String args[]) {
         int capacity = 3;
         float water = 10f;

         System.out.format("water: %.2f\n", FillCups.calc(capacity, water, 5));
     }
}

Explore the cups pyramid recursively. On each call check if there is still enough water in a cup to share with its children. If there is, then alter the index of each child and share the remaining water amongst them.

This should run in O(K).

- Anonymous September 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution using array array strats from 1...n
//
as difference of elements in each level is in AP so we can easily tell the 1st element in level as a quadractic equation
let equation be ax^2+bx+c

gives 1 = a+b+c; 2=4a+2b+c; 4=9a+3b+c

solving which we get equation as (x^2-x+2)/2

f(y) gives the level in which cup y belongs to

f(y) = floor(1/2+sqrt(2y-2+1/4))

also a element y children are y + f(y) and y + f(y) +1

so start form index 1 fill overflow to children, then goto 2nd element fill its children and so oncomplexity
O(n)

- Anand October 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

so if 1 Cup can hold 1 L, if I want to know amount of water I need to fill cup in cup 6, then it will be 6L.

Am I wrong?

- Mas Anon November 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C: capacity of each cup
M: total flow of water
n: the cup for which amount of water is required.

float cupfill(int C,int M,int n){

	int i,level=1,count=1;
	float *cups=malloc(n*sizeof(float));
	for(i=0;i<n;i++)cups[i]=0;

	cups[0]=M;	//first put all water in first cup, which may cause overflow
	for(i=0;i<n-1;i++){
		if(cups[i]>C){	//if cup overflows
			float flow=(cups[i]-C)/2.0;
			cups[i]=C;
			//distribute overflow among children
			cups[i+level]+=flow;
			cups[i+level+1]+=flow;
		}
		if(level==count){	//keeping track of the level
			count=1;
			level++;
			if(i+level>n)break;	//if we have calculated everything upto the parents of n, we know how much n holds
		}
		else count++;
	}
			
	if(cups[n-1]>C) return C;
	else return cups[n-1];
}

- a.khan November 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

wouldn't finding the height in pyramid and then if it is edge node or not, sufficient to determine?

- Anonymous February 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

An easy approach:
1. Name the levels as 1,2,3.... A cup numbered i will pour extra water into cups with number i+level and i+level+1.

I am using an integer array cup[] to store the amount of water in each cup. The same logic applies to the float also.

Here is the pseudo code:

void fillWater(int C,int L,int n,int* cup)
{
        int i,level=1,j,diff;
 
        cup[1]=L;
 
        for(i=1;i<=n;)
        {
                for(j=i;j<i+level;++j)
                {
                        L=cup[j];
                        diff=(L-C)<=0?-1:L-C;
                        if(diff>0)
                        {
                                cup[j]-=diff;
                                cup[j+level]+=diff/2;
                                cup[j+level+1]=diff/2;
                        }
                }
                level++;
                i=j;
        }
        for(i=1;i<=n;++i)
                printf("cup number %d has %d water\n",i,cup[i]);
}

C: Capacity of each cup
L: Water poured in the first cup.
n: Number of cups

Complete working code here: ideone.com/7u7yU

- Aashish August 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the ith number in level x 's index is :
(x-1)*x/2 + i, and it's child is (x+1)*x/2 +i, (x+1)*x/2 + i +1;
use the same method just like lucas.eustaquio .

int cup_pyramid(int c, int l, int kth)
{
    double a[kth*2+3];
    for(int i=0; i<sizeof(a)/sizeof(double); i++)
        a[i] = 0.0;
    
    a[1] = l;
    for(int level=1; 1; level++)
    {   
        int pos = level*(level-1)/2;
        int nextpos = level*(level+1)/2;
        int haveover = 0;
        for(int index=1;index <=level;index++)
        {   
            if(a[pos+index] - c > 0.00001) {
                double over = (a[pos+index] -c )/2;
                a[pos+index] = c;
                a[nextpos+index] += over;
                a[nextpos+index+1] += over;
                haveover = 1;
            }   
        }   
        if(pos > kth) break;
        if(!haveover) break;
    }   
    return a[kth];
}

- cy January 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static double calculateWaterVol(double water, double capacity, int kth)
    {
	double[] curLevel = new double[1];
	curLevel[0] = water;
	
	boolean overflow = true;
	
	while(overflow)
	{
	    double[] nextLevel = new double[curLevel.length+1];

	    overflow = false;
	    
	    for (int i=0; i<curLevel.length;i++)
	    {
		if (curLevel[i] > capacity)
		{
		    overflow = true;
		    double over = (curLevel[i] - capacity)/2;
		    curLevel[i] = capacity;

		    nextLevel[i] += over;
		    nextLevel[i+1] += over;
		}
	    }

	    if (kth > curLevel.length)
	    {
		kth -=curLevel.length;
	    }
	    else
	    {
		return curLevel[kth-1];
	    }
	    
	    curLevel = nextLevel;
	}
	
	if (kth > curLevel.length)
	{
	    return 0;
	}
	
	return curLevel[kth-1];
    }

- Anonymous June 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solved with recursion:

import java.util.ArrayList;
import java.util.List;


public class CupProblem {
	
	static List<Cup> cupList = new ArrayList<Cup>();
	static int noOfCup = 7;
	static int cupLevel = (noOfCup * (noOfCup+1))/2;
	
	static void distribute(List<Cup> cupList,int currentIndex)
	{
		if(currentIndex >= cupLevel )
		{
			return;
		}	
		
		float value = cupList.get(currentIndex).getVlaue();
		if(value <= 1)
		{
			currentIndex++;
			distribute(cupList,currentIndex);
			
		}
		else
		{
		cupList.get(currentIndex).setVlaue(1);
		value = value -1;
		value = value/2;
		int lcp = cupList.get(currentIndex).getLeftChildIndex();
		int rcp = cupList.get(currentIndex).getRightChildIndex();
		cupList.get(lcp).setVlaue(cupList.get(lcp).getVlaue() + value);
		cupList.get(rcp).setVlaue(cupList.get(rcp).getVlaue() + value);
		currentIndex++;
		distribute(cupList,currentIndex);
		}

	}
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int level = 1;
		int currentElementInLevel = 1;
		int temp = (noOfCup * (noOfCup+1))/2;
		for(int i=0;i< temp;i++)
		{
			Cup cup = new Cup();
			if( i==0)
			{
				cup.setVlaue(noOfCup);
				
			}
			else{
				cup.setVlaue(0);
			}
			cup.setLevel(level);
			cup.setLeftChildIndex(i + cup.getLevel());
			cup.setRightChildIndex(i+ cup.getLevel() + 1);
			currentElementInLevel++;
			if(currentElementInLevel > level)
			{
				currentElementInLevel = 1;
				level++;
			}
			cupList.add(cup);
		}
		
		for(int i=0;i <noOfCup;i++)
		{
			System.out.println("Level:" + cupList.get(i).getLevel() + " Value: " + cupList.get(i).vlaue + " LCP: " + cupList.get(i).getLeftChildIndex() + " RCP: " + cupList.get(i).getRightChildIndex());
		}
		
		distribute(cupList,0);
		
		System.out.println("*****************88 After Disbursement ****************");
		
		for(int i=0;i <cupLevel;i++)
		{
			System.out.println("Level:" + cupList.get(i).getLevel() + " Value: " + cupList.get(i).vlaue + " LCP: " + cupList.get(i).getLeftChildIndex() + " RCP: " + cupList.get(i).getRightChildIndex());
		}
	}

}
class Cup
{
	float vlaue;
	public int getLeftChildIndex() {
		return leftChildIndex;
	}

	public void setLeftChildIndex(int leftChildIndex) {
		this.leftChildIndex = leftChildIndex;
	}

	public int getRightChildIndex() {
		return rightChildIndex;
	}

	public void setRightChildIndex(int rightChildIndex) {
		this.rightChildIndex = rightChildIndex;
	}

	public int getLevel() {
		return level;
	}

	public void setLevel(int level) {
		this.level = level;
	}

	int leftChildIndex;
	int rightChildIndex;
	int level;
	
	public float getVlaue() {
		return vlaue;
	}

	public void setVlaue(float f) {
		this.vlaue = f;
	}
}

- Rakesh Jha October 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

At leve n, element k, 0-based:

C(n,k) = n choose k / 2^n

n choose k is O(n) worst case, 2^n is O(logn). So O(n) in total.

- Pascal Triangle September 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Calculate leiters to cups. Make that equal to number of cupsLeft.
Create a counter = 1:
while(cupsLeft > counter)
cupsLeft -= counter;
counter++:
return cupsLeft/counter

- desirocker125 August 04, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More