Amazon Interview Question for SDE1s


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
7
of 13 vote

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:

level 0: 1
level 1: 1/2  1/2
level 2: 1/4  2/4  1/4
level 3: 1/8  3/8  3/8  1/8
level 4: 1/16  4/16  6/16  4/16  1/16

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:

import java.util.Scanner;
import java.util.regex.Pattern;

class GlassStatus {
	float heldVolume;
	float overflownVolume;
}

public class GlassPyramid {

	static int ipRowNum, ipGlassNum, ipVolume;
	public static float computeWaterAt(float volume, int level, GlassStatus[] previousRows) {

		if (volume <= 0)
			return 0;
		
		GlassStatus[] rows = new GlassStatus[level + 1];
		float overflow1 = 0, overflow2 = 0, inflow = 0, tempVol = 0;
		
		for (int i = 0, prev = i-1, next = i; i <= level; i++, prev++, next++) {
			
			rows[i] = new GlassStatus();
			
			if (prev < 0) {
				overflow1 = 0;
			} else {
				overflow1 = previousRows[prev].overflownVolume/2;
			}
			
			if (next >= level) {
				overflow2 = 0;
			} else {
				overflow2 = previousRows[next].overflownVolume/2;
			}
			if (level == 0) {
				inflow = volume;
			} else {
				inflow = overflow1 + overflow2;
			}
			
			tempVol += rows[i].heldVolume = Math.min(1, inflow);
			rows[i].overflownVolume = inflow - rows[i].heldVolume; 			
		}
		
		if (level == ipRowNum) {
			return rows[ipGlassNum].heldVolume; 
		} else {
			return computeWaterAt(volume - tempVol, level + 1, rows);
		}
	}

	public static void readInput() {
		Scanner scanner = new Scanner(System.in);
		scanner.useDelimiter(System.getProperty("line.separator"));
		Pattern delimiters = Pattern.compile(System.getProperty("line.separator")+"|\\s");
		scanner.useDelimiter(delimiters);
		
		System.out.println("Input row#:");
		ipRowNum = scanner.nextInt();
		
		System.out.println("Input glass#:");
		ipGlassNum = scanner.nextInt();
		
		System.out.println("Input volume:");
		ipVolume = scanner.nextInt();
				
	}
	
	public static void main(String[] args) {
		readInput();
		System.out.println("Volume in the glass=" + computeWaterAt(ipVolume, 0, new GlassStatus[] {}));
	}

}

- Murali Mohan July 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
-2
of 2 votes

The denominator should be 2*level not level^2, what happens when there's 7 liters and you want glass 8?

- camelCase July 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Murali Mohan July 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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 July 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Murali Mohan July 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Chih.Chiu.19 July 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- pretentious.bastard February 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
3
of 9 vote

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

- Nitin Gupta July 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Prashant Kesarwani July 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- praveen July 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Anurag July 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous July 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Isn't it related to Pascal's triangle?

- Amandeep July 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- LoganK July 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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

- Rahul Sharma July 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Sibendu Dey July 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public String findwater(int n ,int i, int j)
{
int temp =i*(i+1)/2;
int left = n -temp;
if(left > 0)
{
if((2(i-1) ) > left)
return ""+1;
else
{
float a=left/2(i-1)
if(j==1 || j ==i)
return ""+float/2;
else
return ""+float;
}
}

}

- anonymous July 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public String findwater(int n ,int i, int j)
{
int temp =i*(i+1)/2;
int left = n -temp;
if(left > 0)
{
if((2(i-1) ) > left)
return ""+1;
else
{
float a=left/2(i-1)
if(j==1 || j ==i)
return ""+float/2;
else
return ""+float;
} } }

- anonymous July 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Rudra July 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Swetha Reddy July 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this check is wrong x > totalGlassesUptoPreviousLevel . May be u have assumed that water reaches the next level only after the current level is full, which is wrong.

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

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

- Lilianzeng July 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
void main()
{
float r,c,n;
scanf("%f%f%f",&r,&c,&n);
if(((r-1)*(r/2))>=n)
printf("0");
else if(r*((r+1)/2)==n)
printf("1");
else
printf("%f",(float)((n-((r-1)*(r)/2))/r));
}

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

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

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

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

		}

	}

}

- ifwonderland June 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

		}

	}

}

- ifwonderland June 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- David Sanchez September 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- david.sanchez.plaza September 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Avenir Fetisov July 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, wrong code.Why? See Ayahuasca answer above. =(

- Avenir Fetisov July 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 vote

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.

- chetan July 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Solar July 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The numerator should be the value in pascal's triangle.

- camelCase July 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, here the rate at which the glasses are filled has also to taken into consideration.
I strongly think this can be taken care by a formula, rather hen some complex code.

- rd22 July 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous July 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous July 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The approach seems right but there are many issues in your code

- Shiva July 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

bu kadar basit gencler dagılın

#include<iostream>
using namespace std;

main(){
       int su,i;
       
       cin>>su;
       for(i=1;i<1000;i++){
             su=su-i;
             if(su<=0)
             break;
             }
       cout<<i<<". sira\n";
       
       
       system("pause");
       }

- hllactivity July 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

#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();
}

- Yeshwant July 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well sorry my bad.Haven't read the question properly.

- Sibendu Dey July 17, 2013 | Flag


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