## Morgan Stanley Interview Question for Associates

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
7
of 9 vote

QuickSelect

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

in worst case it can require O(n*n) complexity...!!!
But think little more, this can be done in O(n) worst case also, Hint : using median of median(int this, we get T(n) = T(7n/10) + T(n/5) + n as complexity)

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

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

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 )

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

Yep. Something like quickselect is required.

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

Use the median of medians algorithm and you get O(n) worst case

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

``````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]);
}
}``````

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

Linear general selection algorithm - Median of Medians algorithm

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

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.

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

It is the order statistics algorithm given in cormen ! It is not that much tough to implement. If u know how quick sort works then it is easy to implement..

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

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

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

///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)``````

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

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

}

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

What are you trying to do ?

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

1. Add elements from array to ordered set, sorting by greater than.
2. Use an iterator to return value at position k.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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

This returns the 4th largest number. replace 4 by k and 3 with k-1 to answer the question.

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

This is O(k*n) so not acceptable according to the question statement.

Comment hidden because of low score. Click to expand.

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.