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

- Jit March 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- sonesh November 26, 2012 | Flag
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);
		}
		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 )

- Prateek March 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yep. Something like quickselect is required.

- eugene.yarovoi March 06, 2012 | Flag
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

- Patryk Ozga March 05, 2012 | Flag Reply
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]);
	}
}

- CAFEBABE March 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Linear general selection algorithm - Median of Medians algorithm

- Anonymous March 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Sean.B.Wan May 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- grssriram008 September 09, 2012 | Flag
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

- Nit January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Nit January 26, 2014 | Flag
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);


}

- Anonymous June 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What are you trying to do ?

- Raja Sriram June 26, 2014 | Flag
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.

- merlinme December 04, 2014 | Flag Reply
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

- CheckThisResume.com March 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- CheckThisResume.com March 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous March 05, 2012 | Flag
Comment hidden because of low score. Click to expand.


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More