## Morgan Stanley Interview Question

Associates**Country:**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