## 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];
}``````

Comment hidden because of low score. Click to expand.
0

quite impressive..

thanks a lot..

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

It would make the code more understandable. Thanks!

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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.

Comment hidden because of low score. Click to expand.
0

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!

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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
}``````

Comment hidden because of low score. Click to expand.
0

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];
}``````

Comment hidden because of low score. Click to expand.
4
of 4 vote

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;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

Yeah, it is good too and easier to understand.

Comment hidden because of low score. Click to expand.
0

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

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

if (rightChild > kth)
break;
else

water[i-1] = c;
}
}

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

}

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;
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

the pyramid actually looks like
1
2 3
4 5 6

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's what you meant:

``````1
2 3
4 5 6``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

what is M here?

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

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

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;
}

Comment hidden because of low score. Click to expand.
0

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

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.

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...

Comment hidden because of low score. Click to expand.
0

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

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;
}``````

Comment hidden because of low score. Click to expand.
0

i= numbers= of cups

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);
?>``````

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);``````

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..

Comment hidden because of low score. Click to expand.
0

I agree with Asish

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;
}
}

}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

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

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;
}``````

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.

Comment hidden because of low score. Click to expand.
0

Great solution.

Comment hidden because of low score. Click to expand.
0

this is just wrong

Comment hidden because of low score. Click to expand.
0
of 0 vote

1
2 3

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.

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).

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)

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?

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];
}``````

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?

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

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];
}``````

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];
}``````

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++;
}
}

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;
}
}``````

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.

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

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.

### 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.