## Google Interview Question for Software Developers

Country: India
Interview Type: In-Person

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

``````def get_water_level(water, glassrow):
for i in range(1, glassrow+1):
if water < i:
if i < glassrow:
return 0
else:
return float(water) / i
break
else:
water -= i``````

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

``````def get_water_level(water, glassrow):
for i in range(1, glassrow+1):
if water < i:
if i < glassrow:
return 0
else:
return float(water) / i
break
else:
water -= i``````

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

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.

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

Pascals triangle, and some basic math.
To fill till level i, total 2^i-1 litres of water is needed. So just a modulo and using pascals triangle for the least filled row, find spill into each glass of that level.

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

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

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

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

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

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

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

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

}``````

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

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

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

``````def calculate_glass_fill(litre, row):
litre_used = ((row)*(row - 1))/2
litre_left = float(max(0, (litre - litre_used)))
return min(1.0, litre_left/row)

print calculate_glass_fill(524, 32)``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.