Microsoft Interview Question Software Engineer / Developers
Team: QTB
Country: India
Interview Type: In-Person
You can maintain an int[ , ] array and use recursion to simulate the process, the signature of the method can be like this (in c#): void Process(ref int[ , ] matrix, int c, int v, int x, int y). c is the volume of water that would fill in this cup dropping from its parent(s). v is the volume of this cup. The logic is as follows:
1. if x or y is out of bound of matrix, return. (means the water will drop on the floor)
2. get the current empty volume of this cup (int empty=v-matrix[x,y])
3. fill the cup with c: matrix[x,y] += ( c>empty ) ? empty : c;
4. if matrix[x,y]==v do 5 and 6
5. recursive call: Process(ref matrix, (c-empty)/2, v, x+1, y);
6. recursive call: Process(ref matrix, (c-empty)/2, v, x+1, y+1);
Finally we will get a matrix with numbers indicating the volumes of water of all cups. We can easily get the answer for all 3 questions above.
You can maintain an int[ , ] array and use recursion to simulate the process, the signature of the method can be like this (in c#): void Process(ref int[ , ] matrix, int c, int v, int x, int y). c is the volume of water that would fill in this cup dropping from its parent(s). v is the volume of this cup. The logic is as follows:
1. if x or y is out of bound of matrix, return. (means the water will drop on the floor)
2. get the current empty volume of this cup (int empty=v-matrix[x,y])
3. fill the cup with c: matrix[x,y] += ( c>empty ) ? empty : c;
4. if matrix[x,y]==v do 5 and 6
5. recursive call: Process(ref matrix, (c-empty)/2, v, x+1, y);
6. recursive call: Process(ref matrix, (c-empty)/2, v, x+1, y+1);
Finally we will get a matrix with numbers indicating the volumes of water of all cups. We can easily get the answer for all 3 questions above.
You can maintain an int[ , ] array and use recursion to simulate the process, the signature of the method can be like this (in c#): void Process(ref int[ , ] matrix, int c, int v, int x, int y). c is the volume of water that would fill in this cup dropping from its parent(s). v is the volume of this cup. The logic is as follows:
1. if x or y is out of bound of matrix, return. (means the water will drop on the floor)
2. get the current empty volume of this cup (int empty=v-matrix[x,y])
3. fill the cup with c: matrix[x,y] += ( c>empty ) ? empty : c;
4. if matrix[x,y]==v do 5 and 6
5. recursive call: Process(ref matrix, (c-empty)/2, v, x+1, y);
6. recursive call: Process(ref matrix, (c-empty)/2, v, x+1, y+1);
Finally we will get a matrix with numbers indicating the volumes of water of all cups. We can easily get the answer for all 3 questions above.
You can maintain an int[ , ] array and use recursion to simulate the process, the signature of the method can be like this (in c#): void Process(ref int[ , ] matrix, int c, int v, int x, int y). c is the volume of water that would fill in this cup dropping from its parent(s). v is the volume of this cup. The logic is as follows:
1. if x or y is out of bound of matrix, return. (means the water will drop on the floor)
2. get the current empty volume of this cup (int empty=v-matrix[x,y])
3. fill the cup with c: matrix[x,y] += ( c>empty ) ? empty : c;
4. if matrix[x,y]==v do 5 and 6
5. recursive call: Process(ref matrix, (c-empty)/2, v, x+1, y);
6. recursive call: Process(ref matrix, (c-empty)/2, v, x+1, y+1);
Finally we will get a matrix with numbers indicating the volumes of water of all cups. We can easily get the answer for all 3 questions above.
You can maintain an int[ , ] array and use recursion to simulate the process, the signature of the method can be like this (in c#): void Process(ref int[ , ] matrix, int c, int v, int x, int y). c is the volume of water that would fill in this cup dropping from its parent(s). v is the volume of this cup. The logic is as follows:
1. if x or y is out of bound of matrix, return. (means the water will drop on the floor)
2. get the current empty volume of this cup (int empty=v-matrix[x,y])
3. fill the cup with c: matrix[x,y] += ( c>empty ) ? empty : c;
4. if matrix[x,y]==v do 5 and 6
5. recursive call: Process(ref matrix, (c-empty)/2, v, x+1, y);
6. recursive call: Process(ref matrix, (c-empty)/2, v, x+1, y+1);
Finally we will get a matrix with numbers indicating the volumes of water of all cups. We can easily get the answer for all 3 questions above.
You can maintain an int[ , ] array and use recursion to simulate the process, the signature of the method can be like this (in c#): void Process(ref int[ , ] matrix, int c, int v, int x, int y). c is the volume of water that would fill in this cup dropping from its parent(s). v is the volume of this cup. The logic is as follows:
1. if x or y is out of bound of matrix, return. (means the water will drop on the floor)
2. get the current empty volume of this cup (int empty=v-matrix[x,y])
3. fill the cup with c: matrix[x,y] += ( c>empty ) ? empty : c;
4. if matrix[x,y]==v do 5 and 6
5. recursive call: Process(ref matrix, (c-empty)/2, v, x+1, y);
6. recursive call: Process(ref matrix, (c-empty)/2, v, x+1, y+1);
Finally we will get a matrix with numbers indicating the volumes of water of all cups. We can easily get the answer for all 3 questions above.
You can maintain an int[ , ] array and use DP: Process(int[,] matrix, int c, int v)
int[,] s - the volume of water that each cup will get.
int c - the total volume of water
int v - the volume of cup
s[x,y] = ((s[x-1,y]>v) ? (s[x-1,y]-v) : 0) / 2 + ((s[x-1,y-1]>v) ? (s[x-1,y-1]-v) : 0) / 2
Logic:
1. Initial s[0,0] = c;
2.
for each row x in s
for each column y in s
s[x,y] = ((s[x-1,y]>v) ? (s[x-1,y]-v) : 0) / 2 + ((s[x-1,y-1]>v) ? (s[x-1,y-1]-v) : 0) / 2;
Answer of each question above:
1. Count # of int in s that >=v
2. Count # of s[i,j] such that 0<s[i,j]<v
3. Count max i in s such that s[i,j]>0
Time: O(n^2)
Space: O(n^2)
You can maintain an int[ , ] array and use DP: Process(int[,] matrix, int c, int v)
int[,] s - the volume of water that each cup will get.
int c - the total volume of water
int v - the volume of cup
s[x,y] = ((s[x-1,y]>v) ? (s[x-1,y]-v) : 0) / 2 + ((s[x-1,y-1]>v) ? (s[x-1,y-1]-v) : 0) / 2
Logic:
1. Initial s[0,0] = c;
2.
for each row x in s
for each column y in s
s[x,y] = ((s[x-1,y]>v) ? (s[x-1,y]-v) : 0) / 2 + ((s[x-1,y-1]>v) ? (s[x-1,y-1]-v) : 0) / 2;
Answer of each question above:
1. Count # of int in s that >=v
2. Count # of s[i,j] such that 0<s[i,j]<v
3. Count max i in s such that s[i,j]>0
Time: O(n^2)
Space: O(n^2)
You can maintain an int[ , ] array and use DP: Process(int[,] matrix, int c, int v)
int[,] s - the volume of water that each cup will get.
int c - the total volume of water
int v - the volume of cup
s[x,y] = ((s[x-1,y]>v) ? (s[x-1,y]-v) : 0) / 2 + ((s[x-1,y-1]>v) ? (s[x-1,y-1]-v) : 0) / 2
Logic:
1. Initial s[0,0] = c;
2.
for each row x in s
for each column y in s
s[x,y] = ((s[x-1,y]>v) ? (s[x-1,y]-v) : 0) / 2 + ((s[x-1,y-1]>v) ? (s[x-1,y-1]-v) : 0) / 2;
Answer of each question above:
1. Count # of int in s that >=v
2. Count # of s[i,j] such that 0<s[i,j]<v
3. Count max i in s such that s[i,j]>0
Time: O(n^2)
Space: O(n^2)
The filling of the cups with water need to be affected by the water left in the jug for the rest of cups .So after filling the water in cups at each level, we need to recalculate the water left in jug and the %of water to be filled in each cups as we go down
V =capacity of jug
v = capacity of cup
l = level
n = number of cups at that level
final_l = final level to which cups are to be filled for eg 5th level
initially
l = 1, n = 1;
%pernentage = (V - (l*n*v))/(final_l* final_l - l*n)
After filling the water to the cups at each level we can calculate the percentage of water to be filled in the cups at next level so that all the cups are covered, also store the value of % into an array
int V[10][10] = {0};
void fullyfilled(double c, double v, int n)
{
double diff;
int fullyfilledglasses = 0;
for(int x = 0; x < n; x++)
{
if (c <= 0)
{
break;
}
diff = c / (x + 1);
if( diff >= v)
{
diff = v;
}
else
{
diff = c / (x + 1);
}
c -= diff * (x + 1);
for(int y = 0; y <= x; y++)
{
V[x][y] = diff;
}
}
for( x = 0; x < n; x++)
{
for(int y = 0; y <= x; y++)
{
std::cout << V[x][y] << " ";
}
std::cout << endl;
}
}
Please find the below code written in C.
Assuming the volume of jug is 100 and we have stack of 10 level.
I have take the parameters as static. this is only concept,
#include <stdio.h>
int main()
{
int x=10, y=10;
float arr[x][y];
float volume=100; int i,j;
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
arr[i][j]=0.0;
}
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
{
printf("%.1f ",arr[i][j]);
}
printf("\n");
}
printf("\n \n \n");
arr[0][0]=volume;
for(i=0;i<y-1;i++)
{
for(j=0;j<=i;j++)
{
if(i>x-1 || j>y-1)
continue;
if(arr[j][i]>1.0)
{
arr[j][i+1]+=(arr[j][i]-1.0)/2;
arr[j+1][i+1]+=(arr[j][i]-1.0)/2;
arr[j][i]=1;
}
}
}
for(i=0;i<x;i++)
if(arr[i][y-1]>1)
arr[i][y-1]=1;
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
{
printf("%.1f ",arr[j][i]);
}
printf("\n\n");
}
return 0;
}
A simple loop should find out all the answers. Question need to be clearified with interviewer here: How is each level filled? For example:
1. the very middle cup will be filled first and then filling two neighboor cups aftwards, or
2. for even level, filling middle two cup first, but for odd level, filling middle one cup first, or
3. other filling patterns
It will affect how to calculated to last level.
const int V = <value of V>;
const int v = <value of v>;
void code()
{
int level = 0; //level count
int numberOfCupFilled = 0;
int left = V; //leftover int he jar
int tmpSum;
while(true)
{
//the sum of each level
tmpSum = level*v;
if(tmpSum > left) //found the level here
{
numberOfCupFilled += left/v;
float percentage = (float)(left%v)/v;
cout << "the level not fully filled is " << level;
cout << "percentage is " << percentage;
cout << "number of cup filled is " << numberOfCupFilled;
break;
}
numberOfCupFilled += level;
left -= tmpSum;
level++;
}
}
the topdown approach.. recursive with global function and global storage structure..
- dhandeepm March 03, 2012#include<iostream> #include<stdio.h> #include<algorithm> using namespace std; float a[100][100]={0}; int l=0; void fill(float n,int i,int j) { l=max(l,i); if(a[i][j]>=n) {a[i][j]-=n; } else { n-=a[i][j]; a[i][j]=0; if (n>0) { fill(n/2,i+1,j); fill(n/2,i+1,j+1); } } } int main() { for(int i=0;i<100;i++) for(int j=0;j<=i;j++) a[i][j]=1; float n; cin >>n; fill(n,0,0); for(int i=0;i<=l+2;i++) { for(int j=0;j<=i;j++) { cout<<a[i][j]<<"\t"; } cout<<"\n"; } return 0; }