Facebook Interview Question
Software Engineer / DevelopersCountry: United States
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.
The solution is also using space O(k) ... correct me if I am wrong, also what do you mean by kth is one based ?
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.
is there any easy way to get the higher of an element just knowing the ith of the element?
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.
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!
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.
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.
ok. i see what you are saying . "divide the water" i thought you mean dividing the problem.
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
}
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];
}
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;
}
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];
}
}
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;
}
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.
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
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.
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;
}
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...
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;
}
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);
?>
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);
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..
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;
}
}
}
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
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;
}
The cups are arranged in form of pascal's triangle, the amount will be equal to (L-C) times the corresponding Pascal's coefficient.
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.
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).
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)
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];
}
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
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];
}
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];
}
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;
}
}
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!):
- lucas.eustaquio August 01, 2011