Morgan Stanley Interview Question
AssociatesCountry: United States
Interview Type: Written Test
// from an array build max Heap
// here array is A, mSize is size of array
// and finally return the top element of the heap by taking out k-1 max elements out of heap
// Main Program
MyHeap maxHeap = new MyHeap(A);
maxHeap.buildHeap();
for(int i=0;i<k-1;i++)
maxHeap.removeTop();
maxHeap.getPriorityElement(); // required result
public MyHeap(ArrayList<Integer> arr){
mArrList = arr;
mSize = arr.size();
}
public void buildHeap(){ O(n)
for( int i=mSize/2-1; i>=0; i-- ){
max_heapify(i);
}
}
private boolean max_heapify(int pos){
int sPos = getMaxOfTwoChild(pos);
if( pos > mSize || sPos == -1 )
return true;
if( mArrList.get(pos-1) < mArrList.get(sPos-1) ){
swap(pos-1,sPos-1);
return max_heapify(sPos);
}
else
return true;
}
private int getMaxOfTwoChild(int pos) {
int left = leftOf(pos);
int right = rightOf(pos);
if( left <= mSize && right <= mSize && left > 0 ){
return mArrList.get(left-1) > mArrList.get(right-1) ? left : right;
}
else if( left <= mSize && right > mSize )
return left;
else if ( right <= mSize && left > mSize )
return right;
return -1;
}
public int removeTop(){ // O(k * logn)
int top = getPriorityElement();
if( top != -1 ){
swap(0,mSize-1);
mArrList.remove(--mSize);
max_heapify(1);
}
return top;
}
public int getPriorityElement(){
if( mSize > 0 )
return mArrList.get(0);
else return -1;
}
private int leftOf(int pos){
return 2*pos;
}
private int rightOf(int pos){
return 2*pos+1;
}
// total complexity of program = O(n) + O(k * logn )
public static int[] getlargest(int [] a, int k){
int max = Integer.MIN_VALUE;
int maxpos = 0;
int [] arr = new int [k];
for(int i=0; i<k; i++){
for(int j=0; j<a.length; j++){
if(a[j] > max){
max = a[j];
maxpos = j;
}
}
arr[i] = max;
a[maxpos] = Integer.MIN_VALUE;
max = Integer.MIN_VALUE;
}
return arr;
}
public static void main(String [] args){
int [] a = {3,5,6,41,4,7,1,2,8,19,65,21};
int [] res = getlargest(a,4);
for(int i=0; i<res.length; i++){
System.out.println((i+1)+"th largest element is : "+res[i]);
}
}
agree. Median of Medians algorithm is what interviewer want. But my question is how many people can implement Median of Medians algorithm in half an hour?
This question is ridicule.
function select(list, left, right, n)
if left = right
return list[left]
loop
pivotIndex := ... // select pivotIndex between left and right
pivotIndex := partition(list, left, right, pivotIndex)
if n = pivotIndex
return list[n]
else if n < pivotIndex
right := pivotIndex - 1
else
left := pivotIndex + 1
///For calculating pivot use median of median algo
// returns the index of the median of medians.
// requires a variant of select, "selectIdx"
// which returns the index of the selected item rather than the value
function medianOfMedians(list, left, right)
numMedians = ceil((right - left) / 5)
for i from 0 to numMedians
// get the median of the five-element subgroup
subLeft := left + i*5
subRight := subLeft + 4
if (subRight > right) subRight := right
// alternatively, use a faster method that works on lists of size 5
medianIdx := selectIdx(list, subLeft, subRight, (subRight - subLeft) / 2)
// move the median to a contiguous block at the beginning of the list
swap list[left+i] and list[medianIdx]
// select the median from the contiguous block
return selectIdx(list, left, left + numMedians - 1, numMedians / 2)
public static void main(String[] args) throws NoSuchMethodException, SecurityException, ClassNotFoundException, IllegalAccessException, IllegalArgumentException, InvocationTargetException {
// TODO Auto-generated method stub
int[] array = { 9, 1, 7, 2, 4, 5, 6, 3 };
int one = 0;
int two = 0;
int three = 0;
int fourth = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] > one) {
fourth=three;
three=two;
two = one;
one = array[i];
}
else if (array[i] > two) {
fourth=three;
three = two;
two = array[i];
}
else if (array[i] > three) {
fourth = three;
three = array[i];
}
else if(array[i] > fourth){
fourth=array[i];
}
}
System.out.println(one+ " "+two+ " "+three+" "+fourth);
}
#define SIZE 3
int tab[SIZE];
int max, i, j, sovj;
for(i=0; i<4 ; i++)
{
max=-MAXINT;
for(j=0; j<SIZE ; j++)
{
if(tab[j]>max)
{
max=tab[j];
sovj=j;
}
}
if(j<3)
tab[sovj]=-MAXINT;
}
CheckThisResume.com
This returns the 4th largest number. replace 4 by k and 3 with k-1 to answer the question.
QuickSelect
- Jit March 03, 2012