Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
The denominator should be 2*level not level^2, what happens when there's 7 liters and you want glass 8?
@camelcase
While a solution for this problem is explored, there are several ways to look at this problem. My posting describes "the *rate* at which a particular glass(based on its position in the row) gets filled when a liter of water gets overflowed from all of the glasses above."
However, if only a few of the glasses in a row are overflowing at a given time, the above mentioned distribution pattern will not hold for a row beneath it.
Finally, the actual implementation of an algorithm to solve the problem has a different approach altogether than a mathematical way of looking at the problem.
About your argument, on what basis are you saying that denominator should be 2*level.Give reasons.
I believe the problem was not correctly interpreted: a glass can only fill the one below it *if* it is full! Therefore it can never happens some glass 5 is non-empty while glass 2 and 3 are only half filled.
@ Chih.Chiu.19
You are not quite correct. You haven't completely understood my statements.
For the above configuration, work out what happens when the volume of water X = 5 & 6 and look at glass numbers 4, 5, 6 & 7, 8, 9, 10
At 5 liters you will see the following configuration, where the numbers in brackets denote the volume held.
At X= 5
4(1/2) 5(1) 6(1/2)
7(0) 8(0) 9(0) 10(0)
At X=6
4(3/4) 5(1) 6(3/4)
7(0) 8(1/4) 9(1/4) 10(0)
Do you now see that glass numbers 4 & 6 are not completely filled, yet glass numbers 8 & 9 get some volume inflow into them? That is what I mean when I say the all the glasses in the current row might not be completely filled, yet some glasses from lower row starts getting filled up.
@Ayahuasca
Ok I see what you did now. You are right :) I was just confused by your "flow chart" table at the beginning, since for no situations will we have a configurations like that. Anyway, I see now that your solution is correct, thanks.
C# Code
public static void GetVolume(double inputVolume, int row, int position)
{
double[] prev = new double[1];
prev[0] = inputVolume;
for (int i = 0; i < row+1; i++)
{
double[] next = new double[i+1];
for (int j = 0; j < i + 1; j++)
{
if (j == 0 || j == i)
inputVolume = i==0?prev[0]: (double)(prev[0] / 2.0);
else
inputVolume = (double)(prev[j - 1] / 2.0 + prev[j] / 2.0);
if (i == row && j == position)
{
if (inputVolume > 1)
Console.WriteLine(1);
else
Console.WriteLine(inputVolume);
}
if (inputVolume >= 1)
next[j] = inputVolume - 1.0;
else
next[j] = inputVolume;
}
prev = next;
}
}
// Program to find the amount of water in jth glass of ith row
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Returns the amount of water in jth glass of ith row
float findWater(int i, int j, float X)
{
// A row number i has maximum i columns. So input column number must
// be less than i
if (j > i)
{
printf("Incorrect Input\n");
exit(0);
}
// There will be i*(i+1)/2 glasses till ith row (including ith row)
float glass[i * (i + 1) / 2];
// Initialize all glasses as empty
memset(glass, 0, sizeof(glass));
// Put all water in first glass
int index = 0;
glass[index] = X;
// Now let the water flow to the downward glassses till the
// amount of water X is not 0 and row number is less than or
// equal to i (given row)
for (int row = 1; row <= i && X !=0.0; ++row)
{
// Fill glasses in a given row. Number of columns in a row
// is equal to row number
for (int col = 1; col <= row; ++col, ++index)
{
// Get the water from current glass
X = glass[index];
// Keep the amount less than or equal to
// capacity in current glass
glass[index] = (X >= 1.0f) ? 1.0f : X;
// Get the remaining amount
X = (X >= 1.0f) ? (X - 1) : 0.0f;
// Distribute the remaining amount to the down two glasses
glass[index + row] += X / 2;
glass[index + row + 1] += X / 2;
}
}
// The index of jth glass in ith row will be i*(i-1)/2 + j - 1
return glass[i*(i-1)/2 + j - 1];
}
// Driver program to test above function
int main()
{
int i = 2, j = 2;
float X = 2.0; // Total amount of water
printf("Amount of water in jth glass of ith row is: %f",
findWater(i, j, X));
return 0;
}
A little modified version with 2D array
// Returns the amount of water in jth glass of ith row
static float findJthGlassWater(int i, int j, float X)
{
// A row number i has maximum i columns. So input column number must
// be less than i
if (j > i)
{
System.out.println("Incorrect Input");
return -1;
}
int columns = i*2-1;
// Create a 2D aray with i rows and i*2-1 columns
float glass[][] = new float[i][columns];
int index = (int) Math.floor(columns/2);
glass[0][index] = X;
int localIndex;
// Now let the water flow to the downward glassses till the
// amount of water X is not 0 and row number is less than or
// equal to i (given row)
for (int row = 0; row < i && X !=0.0; ++row, index--)
{
localIndex=index;
// Fill glasses in a given row. Number of columns in a row
// is equal to row number
for (int col = 0; col <= row; ++col)
{
// Get the water from current glass
X = glass[row][localIndex];
// Keep the amount less than or equal to
// capacity in current glass
glass[row][localIndex] = (X >= 1.0f) ? 1.0f : X;
// Get the remaining amount
X = (X >= 1.0f) ? (X - 1) : 0.0f;
// Distribute the remaining amount to the down two glasses if x is greater than 1
// And it shouldn't go beyond i-1 rows
if (X > 0.0f && row+1 < i)
{
glass[row+1][localIndex-1] += X / 2;
glass[row+1][localIndex+1] += X / 2;
}
localIndex+=2;
}
}
for(int k=0; k <i ; k++)
{
for ( int r=0 ; r < columns ; r++)
{
System.out.print(" " + glass[k][r]);
}
System.out.println();
}
// The index of jth glass in ith row will be glass[i-1] [glass.length-i + (2*(j-1))]
return glass[i-1] [glass.length-i + (2*(j-1))];
}
#include<stdio.h>
void main(){
int noOfLiters = 0;
int n = 0; //number of rows to print
int j = 0;
int i = 0;
int presentRow = 0;
int nextRow = 0;
float boundary = 0;
float middle = 0;
float temp = 0;
printf("Enter the value of noOfLiters\n");
scanf("%d",&noOfLiters);
printf("how many rows\n");
scanf("%d",&n);
i = 0; //row on which water is poured is taken as i =0 or zeroth row
while(i<n){
presentRow = i*(i+1)/2;
nextRow = (i+1)*(i+2)/2;
if(presentRow < noOfLiters && nextRow <= noOfLiters){
printf("row %d has 1 liter\n",i);
}
else if(presentRow > noOfLiters){
printf("row %d has no water \n",i);
}
else{
temp = noOfLiters;
for(j = 0;j<i;j++){
temp = (temp-1)/2;
}
boundary = temp;
middle = noOfLiters - i*(i+1)/2 - 2*boundary;
middle = middle/(i-1);
printf("row %d has %f liters on boundary columns and %f liters in middle columns\n",i,boundary,middle);
}
i++;
}
}
#include<iostream>
int main()
{
int glass,ltr,rows=1;
std::cout<<"INPUT:\nNo of glasses\namt of water\n";
std::cin>>glass>>ltr;
while(glass>0)
{
glass=glass-rows;
rows++;
}
rows--;
std::cout<<"\n\tRows: "<<rows<<"\t"<<ltr<<"\n";
float arr[rows][rows];
for(int i=0;i<rows;i++)
{ for(int k=4-i;k>0;k--)
{ std::cout<<"\t"; }
for(int j=0;j<=i;j++)
{
arr[i][j]=0;
std::cout<<arr[i][j]<<"\t";
}
std::cout<<"\n";
}
arr[0][0]=ltr;
std::cout<<"1 : "<<arr[0][0];
for(int i=0;i<rows;i++)
{
for(int j=0;j<=i;j++)
{ std::cout<<"."<<i<<j;
if(arr[i][j]>1)
{
arr[i+1][j]=arr[i+1][j]+(arr[i][j]-1)/2;
arr[i+1][j+1]=arr[i+1][j+1]+(arr[i][j]-1)/2;
arr[i][j]=1;
}
}
}
std::cout<<"\n";
for(int i=0;i<rows;i++)
{ for(int k=4-i;k>0;k--)
{ std::cout<<"\t"; }
for(int j=0;j<=i;j++)
{
std::cout<<arr[i][j]<<"\t";
}
std::cout<<"\n";
}
return 0;
}
#include "stdafx.h"
#include "stdlib.h"
void find(int i, int j, int water)
{
int x,y;
float **jug;
float remain;
jug=(float**)calloc(i,sizeof(float *));
for (x=0;x<i;x++)
{
jug[x]=(float*)calloc(i,sizeof(float));
}
jug[0][0]=(float)water;
for (x=0;x<i;x++)
{
for(y=0;y<=x;y++)
{
if (jug[x][y]>1)
{
remain=jug[x][y]-1;
jug[x][y]=1;
remain/=2;
if ((x+1+1)<=i)
{
jug[x+1][y]+=remain;
jug[x+1][y+1]+=remain;
}
}
}
}
for(x=0;x<i;x++)
{
printf("\n");
for(y=0;y<i;y++)
{
printf("\t %f",jug[x][y]);
}
}
printf("ith jth jug value=%f",jug[i-1][y-1]);
}
int main(int argc, _TCHAR* argv[])
{
int i,j;
int water;
printf ("Enter ith ");
scanf("%d",&i);
printf ("Enter jth value");
scanf("%d",&j);
if (j>i)
{
printf ("values are not correctly entered (i>=j)");
return -1;
}
printf ("Enter the amount of water");
scanf("%d",&water);
find(i,j,water);
return 0;
}
This is an interesting problem, but it can be resolved with just math.
The total amount of water to completely fill the glasses up to the nth row is:
f(n) = n * (n + 1) / 2
The number of glasses in the ith row is really simple:
c(i) = i
Assuming the glass isn't completely full, the total water for a glass in the ith row is:
g(i) = (X - f(i - 1)) / c(i)
I'm going to be lazy and not reduce, but the only missing piece is including a stepwise function for X - f(i - 1) as well as g(i) because a glass can't be less than empty or greater than full. In pseudocode:
g(i) = min(1, (max(0, X - f(i - 1)) / c(i))
#include<stdio.h>
#include<stdlib.h>
float min(float a, float b)
{
return a<b?a:b;
}
float winePour(int start, int dest, float qty,int k)
{
float a=0,b=0;
if(start > dest || qty < 0)
return 0;
if(start == dest)
{
printf("Start == destination \n");
return min(1,qty);
}
qty=qty-1;
printf("%d %d %f\n",start+k,dest,qty/2);
a+=winePour(start+k,dest,qty/2,k+1);
printf("%d %d %f\n",start+k+1,dest,qty/2);
b+=winePour(start+k+1,dest,qty/2,k+1);
return min(1,a+b);
}
int main()
{
int glass=5;
float qty=3.5;
float x=0.0;
x=winePour(1,glass,qty,1);
printf("%f \n",x);
return 0;
}
Here is the code in c++
#include<stdio.h>
#include<iostream>
#define ROW 4
#define COL 4
using namespace std;
void printActualCapacity(float actualCapacity[][COL]) {
for(int i=0;i<ROW;i++) {
for(int j=0;j<=i;j++) {
cout<<actualCapacity[i][j]<<" ";
}
cout<<"\n";
}
}
void fillCapacity(int litres) {
float actualCapacity[ROW][COL];
float excessCapacity[ROW][COL];
for(int i=0;i<ROW;i++) {
for(int j=0;j<COL;j++) {
actualCapacity[i][j]=excessCapacity[i][j]=0.0f;
}
}
actualCapacity[0][0]=(litres>=1.0f? 1.0f:litres);
excessCapacity[0][0]=(litres>=1.0f ?litres-1.0f:0.0f);
for(int i=1;i<ROW;i++) {
for(int j=0;j<=i;j++) {
if(excessCapacity[i-1][j]>0) {
actualCapacity[i][j]+=(excessCapacity[i-1][j]/2 >= 1.0f ? 1.0f: excessCapacity[i-1][j]/2 );
excessCapacity[i][j]+=(excessCapacity[i-1][j]/2 >= 1.0f ? excessCapacity[i-1][j]/2 - 1 : 0.0f );
excessCapacity[i-1][j]=excessCapacity[i-1][j]/2;
}
if(j-1>=0 && excessCapacity[i-1][j-1]>0) {
if(actualCapacity[i][j]==1) {
excessCapacity[i][j]+=excessCapacity[i-1][j-1];
excessCapacity[i-1][j-1]=0;
}
else {
excessCapacity[i][j]=excessCapacity[i-1][j-1]+actualCapacity[i][j] > 1 ? excessCapacity[i-1][j-1]+actualCapacity[i][j] -1 : 0;
actualCapacity[i][j]= excessCapacity[i-1][j-1]+actualCapacity[i][j] >=1 ? 1 :excessCapacity[i-1][j-1] + actualCapacity[i][j];
}
}
}
}
printActualCapacity(actualCapacity);
}
int main() {
fillCapacity(6);
}
The problem is similar to pascal triangle. Only a little modification required for boundary conditions.
float distributeWaterUptolevel(int watervol,int row,int column){
int remainingwater,i,j;
float glasses[10][10]= {0};
int uptobeforelebel = ((row-1)*((row-1)+1))/2;
if(uptobeforelebel > watervol)
return 0;
else{
remainingwater = watervol-uptobeforelebel;
glasses[0][0]=remainingwater;
for(i=1;i<row;i++){
for(j=0;j<=i;j++){
if(j==0)
glasses[i][j] = glasses[i-1][j]/2;
else if(j==i)
glasses[i][j] = glasses[i-1][j-1]/2;
else
glasses[i][j] = (glasses[i-1][j] + glasses[i-1][j-1])/2;
}
}
return glasses[row-1][column-1];
}
}
int main()
{
int watervol=7;
float wateratglass = distributeWaterUptolevel(watervol,4,2);
if(wateratglass == 0)
cout<<"Water are consumed at upper level";
else
cout<<"water at specified level is "<<wateratglass<<endl;
getchar();
return 0;
}
public static void main(String[] args) {
int i = 3; // ith row
int j = 1; // jth glass
int x = 5; // water volume
double water;
int totalGlassesUptoPreviousLevel = calculateSum(i - 1);
int totalGlassesUptoCurrentLevel = calculateSum(i);
if (j > i) {
System.out.println("Incorrect Input");
} else {
if (x > totalGlassesUptoPreviousLevel) {
if (x < totalGlassesUptoCurrentLevel) {
System.out.println("caclulating");
if (isCorner(i, j)) {
water = (x - (Math.pow(2, i - 1) - 1)) / Math.pow(2, i - 1);
} else {
water = (x - (Math.pow(2, i - 1) - 1)) / Math.pow(2, i - 2);
}
} else {
water = 1;
}
} else {
water = 0;
}
System.out.println("water in ith row is " + water);
}
}
static boolean isCorner(int i, int j) {
if(j==1 || j==i)
return true;
return false;
}
static int calculateSum(int i) {
return ((i * (i + 1)) / 2);
}
I think it's just a dynamic programming. My code is as follows:
#include <iostream>
#include <string.h>
using namespace std;
#define GLASSES_NUM 100
#define TO_INDEX(i, j) (0.5 * (i) * (i - 1) + (j))
double f[GLASSES_NUM];
int water;
double calculate(int i, int j)
{
int index = TO_INDEX(i, j);
if (f[index] - 0.0 > 1.0e-6)
{
return f[index];
}
else
{
if (i == 1 && j == 1)
{
f[index] = water;
return f[index];
}
else
{
double m1 = 0.0, m2 = 0.0;
if ( j >= 2)
{
double temp = calculate(i-1, j-1);
m1 = temp > 1 ? (temp - 1) : 0;
}
if (j <= 0.5 * i * (i -1))
{
double temp = calculate(i-1, j);
m2 = temp > 1 ? (temp - 1) : 0;
}
f[index] = 0.5 * (m1 + m2);
return f[index];
}
}
}
int main()
{
int i, j;
memset(f, 0.0, sizeof f);
cout << "Input the total water(L):" << endl;
cin >> water;
while(1)
{
cout << "Which glass do you want to know?" << endl;
cout << "i = ";
cin >> i;
cout << "j = ";
cin >> j;
if (j > i)
{
cout << "j must not be bigger than i" << endl;
continue;
}
double result = calculate(i, j);
cout << "answer is " << (result > 1 ? 1 : result) << endl;
}
return 1;
}
#include<stdio.h>
void main()
{
float r,c,n;
printf(" enter row no and col no and total water")
scanf("%f%f%f",&r,&c,&n);
if(((r-1)*(r/2))>=n)
printf("total amt of water is 0");
else if(r*((r+1)/2)==n)
printf("total amt of water is 1");
else
printf("total amt of water is %f",(float)((n-((r-1)*(r)/2))/r));
}
Very similar idea, more OO way of implementation,
each Glass class is responsible for maintaining obtained water and how much overflow/spillover is from this glass.
Parent glass will just pour water to its children.
package careercup;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* There are some glasses with equal volume 1 litre. The glasses kept as follows
* <p/>
* <p/>
* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
* <p/>
* You can put water to only top glass. If you put more than 1 litre water to
* 1st glass, water overflow and fill equally both 2nd and 3rd glass. Glass 5
* will get water from both 2nd glass and 3rd glass and so on.. If you have X
* litre of water and you put that water in top glass, so tell me how much water
* contained by jth glass in ith row. Example. If you will put 2 litre on top.
* 1st glass: 1 litre 2nd glass: 1/2 litre 3rd glass: 1/2 litre
* <p/>
* <p/>
* <p/>
* Created by ifwonderland on 6/10/14.
*/
public class GlassPourer {
private Map<Integer, List<Glass>> levelGlassesMap = new HashMap<Integer, List<Glass>>();
public GlassPourer(int rowNum) {
if (rowNum == 0)
return;
initAllGlasses(rowNum);
}
private void initAllGlasses(int rowNum) {
int globalIndex = 1;
for (int r = 0; r < rowNum; r++) {
// for each row, there are r+1 glasses
List<Glass> glasses = new ArrayList<GlassPourer.Glass>();
for (int c = 0; c < r + 1; c++)
glasses.add(new Glass(globalIndex++));
levelGlassesMap.put(r, glasses);
}
// now connect parent with their children, children of glass is r, r+1
// of next level
for (int r = 0; r < rowNum - 1; r++) {
List<Glass> glasses = levelGlassesMap.get(r);
for (int c = 0; c < glasses.size(); c++) {
Glass glass = glasses.get(c);
List<Glass> nextLevelGlasses = levelGlassesMap.get(r + 1);
Glass left = nextLevelGlasses.get(c);
Glass right = nextLevelGlasses.get(c + 1);
glass.children.add(left);
glass.children.add(right);
}
}
}
public void pourWater(double x) {
levelGlassesMap.get(0).get(0).pour(x);
}
public double getWater(int r, int c) {
return levelGlassesMap.get(r).get(c).contained;
}
public static void main(String[] args) {
GlassPourer gp = new GlassPourer(4);
// for(int x=0;x<10;x++){
int x = 8;
System.out.println("Puring " + x + " liters of water, and we get: ");
gp.pourWater(x);
gp.print();
// }
}
public void print() {
for (int r = 0; r < 4; r++) {
StringBuilder sb = new StringBuilder();
for (int c = 0; c < r + 1; c++)
sb.append(getWater(r, c)).append(" ");
System.out.println(sb);
}
}
public class Glass {
private int id;
public Glass(int id) {
this.id = id;
}
public static final double CAPACITY = 1d;
private double contained = 0; // track how much water is contained in
// this glass
private List<Glass> children = new ArrayList<Glass>();
public double getContained() {
return contained;
}
public String toString() {
return "id: " + id + ",contained: " + contained;
}
public void pour(double water) {
double total = water + contained;
if (total > CAPACITY) {
contained = CAPACITY;
double overflow = total - CAPACITY;
for (Glass child : this.children)
child.pour(overflow / 2);
} else {
contained = total;
}
}
}
}
package careercup;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* There are some glasses with equal volume 1 litre. The glasses kept as follows
* <p/>
* <p/>
* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
* <p/>
* You can put water to only top glass. If you put more than 1 litre water to
* 1st glass, water overflow and fill equally both 2nd and 3rd glass. Glass 5
* will get water from both 2nd glass and 3rd glass and so on.. If you have X
* litre of water and you put that water in top glass, so tell me how much water
* contained by jth glass in ith row. Example. If you will put 2 litre on top.
* 1st glass: 1 litre 2nd glass: 1/2 litre 3rd glass: 1/2 litre
* <p/>
* <p/>
* <p/>
* Created by ifwonderland on 6/10/14.
*/
public class GlassPourer {
private Map<Integer, List<Glass>> levelGlassesMap = new HashMap<Integer, List<Glass>>();
public GlassPourer(int rowNum) {
if (rowNum == 0)
return;
initAllGlasses(rowNum);
}
private void initAllGlasses(int rowNum) {
int globalIndex = 1;
for (int r = 0; r < rowNum; r++) {
// for each row, there are r+1 glasses
List<Glass> glasses = new ArrayList<GlassPourer.Glass>();
for (int c = 0; c < r + 1; c++)
glasses.add(new Glass(globalIndex++));
levelGlassesMap.put(r, glasses);
}
// now connect parent with their children, children of glass is r, r+1
// of next level
for (int r = 0; r < rowNum - 1; r++) {
List<Glass> glasses = levelGlassesMap.get(r);
for (int c = 0; c < glasses.size(); c++) {
Glass glass = glasses.get(c);
List<Glass> nextLevelGlasses = levelGlassesMap.get(r + 1);
Glass left = nextLevelGlasses.get(c);
Glass right = nextLevelGlasses.get(c + 1);
glass.children.add(left);
glass.children.add(right);
}
}
}
public void pourWater(double x) {
levelGlassesMap.get(0).get(0).pour(x);
}
public double getWater(int r, int c) {
return levelGlassesMap.get(r).get(c).contained;
}
public static void main(String[] args) {
GlassPourer gp = new GlassPourer(4);
// for(int x=0;x<10;x++){
int x = 8;
System.out.println("Puring " + x + " liters of water, and we get: ");
gp.pourWater(x);
gp.print();
// }
}
public void print() {
for (int r = 0; r < 4; r++) {
StringBuilder sb = new StringBuilder();
for (int c = 0; c < r + 1; c++)
sb.append(getWater(r, c)).append(" ");
System.out.println(sb);
}
}
public class Glass {
private int id;
public Glass(int id) {
this.id = id;
}
public static final double CAPACITY = 1d;
private double contained = 0; // track how much water is contained in
// this glass
private List<Glass> children = new ArrayList<Glass>();
public double getContained() {
return contained;
}
public String toString() {
return "id: " + id + ",contained: " + contained;
}
public void pour(double water) {
double total = water + contained;
if (total > CAPACITY) {
contained = CAPACITY;
double overflow = total - CAPACITY;
for (Glass child : this.children)
child.pour(overflow / 2);
} else {
contained = total;
}
}
}
}
Brute force. Give to the first node the water, and start overflowing.
#include <iostream>
using namespace std;
class Glass {
public:
Glass *leftChild;
Glass *rightChild;
double maxQuantity;
double currentQuantity = 0;
int index;
Glass(){
}
Glass(int q, int i){
maxQuantity = q;
index = i;
}
double calculateWater(double water);
void setLeftChild(Glass *leftChild);
void setRightChild(Glass *rightChild);
void giveWater(double givenQuantiy);
};
double Glass::calculateWater(double water) {
//cout<<"Glass calculateWater() water " << water << "\n";
}
void Glass::setLeftChild(Glass *leftChild) {
this->leftChild = leftChild;
}
void Glass::setRightChild(Glass *rightChild) {
this->rightChild = rightChild;
}
void Glass::giveWater(double givenQuantiy) {
if(currentQuantity < maxQuantity){
if(givenQuantiy < maxQuantity - currentQuantity){
currentQuantity += givenQuantiy;
givenQuantiy = 0;
}else {
givenQuantiy -= (maxQuantity - currentQuantity);
currentQuantity = maxQuantity;
}
}
if(givenQuantiy <= 0)
return;
if(leftChild != NULL){
cout<<"Giving to " << leftChild->index << " " << givenQuantiy/2 << " liters\n";
leftChild->giveWater(givenQuantiy/2);
}
if(rightChild != NULL){
cout<<"Giving to " << rightChild->index << " " << givenQuantiy/2 << " liters\n";
rightChild->giveWater(givenQuantiy/2);
}
}
int main()
{
cout<<"Hello World \n";
int totalGlasses = 15;
double givenQuantiy = 6;
Glass * glasses [totalGlasses];
for (int i = 0; i < totalGlasses; i++){
Glass *glass = new Glass(i+1, i+1);
glasses[i] = glass;
}
int level = 1;
int currentLevelItems = 0;
for (int i = 0; i < totalGlasses; i++){
if(currentLevelItems >= level){
level++;
currentLevelItems = 0;
}
currentLevelItems ++;
if(i + level < totalGlasses)
glasses[i]->leftChild = glasses[i + level];
if(i + level + 1 < totalGlasses)
glasses[i]->rightChild = glasses[i + level + 1];
}
//Starts problem. We give the total quantity to first node. He will recursively give to childs
glasses[0]->giveWater(givenQuantiy);
for (int i = 0; i < totalGlasses; i++){
cout<<"Index: " << (i+1) << " - " << glasses[i]->currentQuantity << " liters.\n";
}
return 0;
}
Brute force. Give all the water to the first one, and start overflowing
#include <iostream>
using namespace std;
class Glass {
public:
Glass *leftChild;
Glass *rightChild;
double maxQuantity;
double currentQuantity = 0;
int index;
Glass(){
}
Glass(int q, int i){
maxQuantity = q;
index = i;
}
double calculateWater(double water);
void setLeftChild(Glass *leftChild);
void setRightChild(Glass *rightChild);
void giveWater(double givenQuantiy);
};
double Glass::calculateWater(double water) {
//cout<<"Glass calculateWater() water " << water << "\n";
}
void Glass::setLeftChild(Glass *leftChild) {
this->leftChild = leftChild;
}
void Glass::setRightChild(Glass *rightChild) {
this->rightChild = rightChild;
}
void Glass::giveWater(double givenQuantiy) {
if(currentQuantity < maxQuantity){
if(givenQuantiy < maxQuantity - currentQuantity){
currentQuantity += givenQuantiy;
givenQuantiy = 0;
}else {
givenQuantiy -= (maxQuantity - currentQuantity);
currentQuantity = maxQuantity;
}
}
if(givenQuantiy <= 0)
return;
if(leftChild != NULL){
cout<<"Giving to " << leftChild->index << " " << givenQuantiy/2 << " liters\n";
leftChild->giveWater(givenQuantiy/2);
}
if(rightChild != NULL){
cout<<"Giving to " << rightChild->index << " " << givenQuantiy/2 << " liters\n";
rightChild->giveWater(givenQuantiy/2);
}
}
int main()
{
cout<<"Hello World \n";
int totalGlasses = 15;
double givenQuantiy = 6;
Glass * glasses [totalGlasses];
for (int i = 0; i < totalGlasses; i++){
Glass *glass = new Glass(i+1, i+1);
glasses[i] = glass;
}
int level = 1;
int currentLevelItems = 0;
for (int i = 0; i < totalGlasses; i++){
if(currentLevelItems >= level){
level++;
currentLevelItems = 0;
}
currentLevelItems ++;
if(i + level < totalGlasses)
glasses[i]->leftChild = glasses[i + level];
if(i + level + 1 < totalGlasses)
glasses[i]->rightChild = glasses[i + level + 1];
}
//Starts problem. We give the total quantity to first node. He will recursively give to childs
glasses[0]->giveWater(givenQuantiy);
for (int i = 0; i < totalGlasses; i++){
cout<<"Index: " << (i+1) << " - " << glasses[i]->currentQuantity << " liters.\n";
}
return 0;
}
package GlassPyramide;
import java.util.Scanner;
public class GlassPyramide {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print("Input number of litres: ");
double x = input.nextDouble();
System.out.print("Input number of glass: ");
int j = input.nextInt(); //number of glass
int count = 1; //start counting numbers of glasses from 1
int k, m; //k - number of rows; m - helping number
double V; //V - volume of glass with water
for (k = 1; count < j; k++) {
for (m=0; m < k; m++) {
System.out.printf("%4d", new Object[] { Integer.valueOf(count++) });
}
System.out.println();
}
V=(k-1-x)/(k-1);
if (x < k-1)
System.out.println("Glass №"+j+" contains "+V+" liters");
else
System.out.println("Glass №"+j+" contains 1 liter");
}
}
TL;DR;
so lets see how the water flows down
evel 0: 1
level 1: 1/2 1/2
level 2: 1/4 2/4 1/4
level 3: 1/6 2/6 2/6 1/6
level 4: 1/8 2/8 2/8 2/8 1/8
and so on.
So by analysing the above data a simple formula can be designed for the 2 different cases that we will have
Case 1. if the glass is the outer most, either on left or on right.
Case 2. if the glass is as inner glass.
For case 1 the formula will be:
Amount of water in Glass(Y) = (X - (1+2+i-1)) / (2 * (i-1))
where i is the row and X is the total amount of water being poured.
And for case 2 just multiply the value of case 1(Y) by 2.
and we have our desired output.
If x=6, i=4 and j=2, your solution gives 0 as output and correct answer is 0.25 (first litre fills (1,1) glass, next two fills (2,1) and (2,2) glasses, next two liters distributed between (3,1), (3,2) and (3,3) glasses as 0.5, 1.0 and 0.5, so glass (3,2) is filled. Now we put last liter, that distributes as 0.25, 0.25, 0.25, 0.25 between (3,1), (4,2), (4,3) and (3,3))
int X;
int main( )
{
// Get the row number and glass num
// Set the water in global variable
X = 8; /* litres*/
findparentglass(in_row,in_glass_num,out_parent1,out_parent2);
// Amount of water in glass for X Lit of water is
min(1,findoverflow(out_parent_1) + findoverflow(out_parent2));
}
double findoverflow(int i)
{
if(i ==0)
{
return 0;
}
else if(i == 1) // i is glass number
{
return (max(0,(X -1));
}
else if(i == 2 || i == 3)
{
return (max(0,(X - 3)/4));
}
findRowandGlassNum(i,row_out,glass_out);
findparentglass(ow_out,glass_out,out_parent1,out_parent2);
return(findoverflow(out_parent_1) + findoverflow(out_parent2) - 2);
}
int X;
int main( )
{
// Get the row number and glass num
// Set the water in global variable
X = 8; /* litres*/
findparentglass(in_row,in_glass_num,out_parent1,out_parent2);
// Amount of water in glass for X Lit of water is
min(1,findoverflow(out_parent_1) + findoverflow(out_parent2));
}
double findoverflow(int i)
{
if(i ==0)
{
return 0;
}
else if(i == 1) // i is glass number
{
return (max(0,(X -1));
}
else if(i == 2 || i == 3)
{
return (max(0,(X - 3)/4));
}
findRowandGlassNum(i,row_out,glass_out);
findparentglass(ow_out,glass_out,out_parent1,out_parent2);
return(findoverflow(out_parent_1) + findoverflow(out_parent2) - 2);
}
#include<conio.h>
#include<stdio.h>
void main()
{
clrscr();
int i,x;
printf("Enter The Total Water:");
scanf("%d",&x);
for(i=1;i<=x;i++)
{
x=x-i;
printf("\nWater In Row%d=%d lit.",i,i);
}
printf("\nWater In Row%d=%d lit.",i,x);
printf("\nWater In Each Glass Of Row%d=%f lit.",i,(float)x/i);
getch();
}
In this problem the rates at which glasses get filled in are rational numbers, whose numerators form the binomial coefficients and denominators are powers of 2 - specifically 2 raised to the power of level at which glasses are present.
A litre of water (overflowed from previous level) gets distributed among the glasses at each level as follows:
The above distribution pattern provides with a partial progress towards the actual algorithm that finds the amount of water in jth glass of ith row. The algorithm gets tricky because all the glasses at a level might not be completely filled yet, before water starts getting filled up in levels below (albeit, in an inverted triangle fashion).
----------------------------------------------------------------------------
The above observation apart, a DP-like algorithm below(that remembers quantities in glasses of the previous row) to find out the amount of water in jth jug of ith row can solve the problem.
0. For each glass, maintain 2 variables - the amount of water it holds and the amount of water it overflows.
1. For a glass at index i in the given row, look up two glasses in the previous row at index i-1 & i. (Boundary cases of indices need to be checked though)
2. The inflow into the current glass = half of outflow of glass in the previous row at i-1 + half of outflow of glass in the previous row at index i
3. Based on the inflow, volume held in the current glass = min(1, inflow) and the overflow at the current glass = inflow - volume held by the current glass
4. Repeat steps 1 to 3 until we reach the required glass.
An implementation in java goes like the below:
- Murali Mohan July 17, 2013