Morgan Stanley Interview Question
Sales Development RepresentativesCountry: India
package interview_questions;
/**
*
* @author just_do_it
*
*/
public class CountBinaryHeaps {
/*
* f(38) = 37C22 * f(15) * f(22)
*/
static long numBinaryHeaps(int n){
if(n == 1 || n == 2) {
return 1;
} else if (n == 3){
return 2;
}
int numElementsChild1, numElementsChild2;
int n1 = largestPowerOf2LessOrEqual(n);
if(n1 - 1 + n1/2 >= n){
numElementsChild1 = n1/2 - 1;
numElementsChild2 = n - n1/2;
} else {
numElementsChild1 = n1 -1;
numElementsChild2 = n - n1;
}
long res = choose(n-1,numElementsChild1) * numBinaryHeaps(numElementsChild1) * numBinaryHeaps(numElementsChild2);
return res;
}
public static int choose(int n, int m){
if(n < m)
return 0;
if(m == 0 || n == m)
return 1;
return choose(n-1,m-1)+choose(n-1,m);
}
static int largestPowerOf2LessOrEqual(int n){
int pow2 = 1;
while(pow2*2 < n){
pow2 *= 2;
}
return pow2;
}
public static void main(String[] args){
int[] testcases = {1 , 2 , 3 , 4 , 5 , 6};
long[] results = {1 , 1 , 2 , 3 , 4*2, 10*2 };
for(int i = 0; i < testcases.length; i++){
int n = testcases[i];
long res = numBinaryHeaps(n);
System.out.println(n + "\t" + res + "\t" + results[i]);
}
}
}
package interview_questions;
- just_do_it July 18, 2014/**
*
* @author just_do_it
*
*/
public class CountBinaryHeaps {
/*
* f(38) = 37C22 * f(15) * f(22)
*/
static long numBinaryHeaps(int n){
if(n == 1 || n == 2) {
return 1;
} else if (n == 3){
return 2;
}
int numElementsChild1, numElementsChild2;
int n1 = largestPowerOf2LessOrEqual(n);
if(n1 - 1 + n1/2 >= n){
numElementsChild1 = n1/2 - 1;
numElementsChild2 = n - n1/2;
} else {
numElementsChild1 = n1 -1;
numElementsChild2 = n - n1;
}
long res = choose(n-1,numElementsChild1) * numBinaryHeaps(numElementsChild1) * numBinaryHeaps(numElementsChild2);
return res;
}
public static int choose(int n, int m){
if(n < m)
return 0;
if(m == 0 || n == m)
return 1;
return choose(n-1,m-1)+choose(n-1,m);
}
static int largestPowerOf2LessOrEqual(int n){
int pow2 = 1;
while(pow2*2 < n){
pow2 *= 2;
}
return pow2;
}
public static void main(String[] args){
int[] testcases = {1 , 2 , 3 , 4 , 5 , 6};
long[] results = {1 , 1 , 2 , 3 , 4*2, 10*2 };
for(int i = 0; i < testcases.length; i++){
int n = testcases[i];
long res = numBinaryHeaps(n);
System.out.println(n + "\t" + res + "\t" + results[i]);
}
}
}