## Google Interview Question

Software Developers**Country:**India

**Interview Type:**In-Person

Fairly straight forward, just a pascal's triangle.

1=1

1 1=1+2=2^2-1

1 2 1=1+2+4=2^3-1

1 3 3 1 =1+2+4+8=2^4-1

....

Find log of X to find the levels fully filled, create pascal's triangle for missing level, and distribute accordingly. For example, 9 liters would means 2 liters in the last row and distributed as 1/4,3/4,3/4,1/4 liters in the last row.

```
import sys
def sum_till(num):
sum = 0
while num > 0:
sum += num
num -= 1
return sum
water = int(raw_input())
row, glass = [int(x) for x in raw_input().strip().split()]
# check if row is beyond the water limit
if sum_till(row - 1) >= water:
print 0
sys.exit(1)
# check if there is still water left after filling row completely
if sum_till(row) <= water:
print 1
sys.exit(1)
# calculate water in the row
# calculate water remaining after filling row - 1
water -= sum_till(row - 1)
# calculate pascals coefficients for the row
line = [1]
for k in range(row - 1):
line.append(line[k] * (row - 1 - k) / (k + 1))
water_ratio = float(water)/sum(line)
print line[glass - 1] * water_ratio
```

```
import sys
def sum_till(num):
sum = 0
while num > 0:
sum += num
num -= 1
return sum
water = int(raw_input())
row, glass = [int(x) for x in raw_input().strip().split()]
# check if row is beyond the water limit
if sum_till(row - 1) >= water:
print 0
sys.exit(1)
# check if there is still water left after filling row completely
if sum_till(row) <= water:
print 1
sys.exit(1)
# calculate water in the row
# calculate water remaining after filling row - 1
water -= sum_till(row - 1)
# calculate pascals coefficients for the row
line = [1]
for k in range(row - 1):
line.append(line[k] * (row - 1 - k) / (k + 1))
water_ratio = float(water)/sum(line)
print line[glass - 1] * water_ratio
```

#include<iostream>

using namespace std;

int main()

{

int t;

cin>>t;

while(t--)

{

int n,i,j,k,l;

cin>>n>>k>>l;

float ar1[n+1][n+1];

for( i=0;i<=n;i++)

for(j=0;j<=n;j++)

{

ar1[i][j]=0;

}

ar1[1][1]=n;

for(i=2;i<=n;i++)

{

for(j=1;j<=i-1;j++)

{

ar1[i][j]=(ar1[i-1][j]-1)*1.0/2;

ar1[i][j+1]=(ar1[i-1][j]-1)*1.0/2;

}

}

if(ar1[k][l]>0 && ar1[k][l]<=1)

cout<<ar1[k][l];

if(ar1[k][l]>1)

cout<<"1";

else

cout<<"0";

}

}

I believe this could be solved in O(1) Time, O(1) Space, using discharge rate.

Please correct if it is wrong.

1) Every row can be considered a a power of 11, meaning each digit in the power of 11, is the fill rate of the glass. Ex: row 5 is: 1 4 6 4 1 => end glasses in this row fill at (1/pow(2,4)) rate and glass 2 fills at 2*(1/pow(2,4)) and glass 3 fills at 6*(1/pow(2,4)) rate.

2) For a given amountX, and row i and glass j, we subtract the amount of water already consumed till the previous row and use the remaining water for current row by multiplying with the initialized discharge rate.

```
public class AmountInGlass {
public double amountOfWater(int rowI, int glassJ, double amountX){
if(rowI < 0 && glassJ < 0){
return -1;
}
double dischargeRate = 1/(Math.pow(2, rowI-1));
int elevenExp = (int)Math.pow(11, rowI-1);
if(glassJ > rowI){
return -1;
}
double remainingWater = amountX - (rowI * (rowI-1)/2);
// Get the actual digit in this row.
elevenExp = elevenExp/(int)Math.pow(10,rowI-glassJ);
elevenExp = elevenExp % 10;
double result = elevenExp * dischargeRate * remainingWater;
return result > 1.0 ? 1.0 : result;
}
public static void main(String[] args) {
AmountInGlass amountInGlass = new AmountInGlass();
int rowI =4;
int glassJ = 2;
double result = amountInGlass.amountOfWater(rowI, glassJ, 8);
System.out.println("amount of water in row "+rowI+ " glass "+glassJ +" is: "+result);
}
```

That's an interesting solution, but how can you know how much water we consumed on the previous rows? It also depends on total amount of liters we trying to put, right?

For instance, when we calculate non-zero value for a glass in the 4th row, the third row might contain either 3 liters (1/2 + 1 + 1/2) or 3 liters (1 + 1 + 1).

- Python Implementation September 22, 2016