Amazon Interview Question


Country: United States




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

Can use quickselect to quickly find median (in O(n)).
So if length is odd, one run of quickselect (with k = middle) is enough.
Now, if the problem requires average of two middle elements in case length is even , can run quick select once and then find max on the left half of the array, which is now pivoted around the right number of the two in the middle.
If it is ok to output left of the two middle numbers, than this is again just a single quickselect.

Also, there are multiple variations of quick select that suffers from worst case O(n^2) same as quicksort, which are probably worth discussing, some variants use random to select pivot, median-of-medians is commonly known good choice, or even Introselect variant that falls back to Heapsort in case partitioning is not effective. All these help to reduce worst case of O(n^2).
So assuming some variation of quickselect is used that has worst case O(N), total complexity is O(N) for quickselect + O(N) for finding left of the two middle elements.

Using the simplest implementation of quickselect:

public static double findMedian(int[] input) {
	Random rand = new Random(System.currentTimeMillis());
	if (input==null || input.length<=0) throw new IllegalArgumentException();
	
	if (input.length%2==0) {
		int left = qselect(input, 0, input.length-1, input.length/2, rand);
		int right = getMax(input, 0, input.length/2-1);
		return (left + right)/2.0;
		
	} else {
		return qselect(input, 0, input.length-1, input.length/2, rand);
	}		
}

private static int getMax(int[] input, int i, int j) {
	int max = input[i++];
	while (i <= j) {
		if (input[i]>max) {
			max = input[i];
			i++;
		}
	}		
	return max;
}

private static int qselect(int[] input, int i, int j, int k,  Random rand) { 
	if (j<=i) {
		return input[j];
	}
	int p =  rand.nextInt(j-i+1) + i;
	
	int pIdx = partition(input, i, j, p);
	if (pIdx == k) {
		return input[pIdx];
	} else if (pIdx < k) {
		return qselect(input, pIdx+1, j, k, rand);
	} else {
		return qselect(input, i, pIdx-1, k, rand);
	}
}

private static int partition(int[] input, int start, int end, int pIdx) {
	int pivot = input[pIdx];
	int pivIdx = start;
	
	swap(input, pIdx, end);
	
	for (int  i=start; i <= end-1; i++) {
		if (input[i] < pivot) {
			swap(input, i, pivIdx);
			pivIdx++;
		} 
	}
	
	swap(input, pivIdx, end);
	return pivIdx;
}

- blckembr November 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Apply the sorting algorithm you like and then get the median. If the max and the min of the values are relatively close, countingsort could fit. Otherwise I would apply Quicksort.

- Edu November 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

pretty simple:
1) get sum of elements of array,
2) get count of elements of array,
3) {1} / {2}.
O(n).

- zr.roman November 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

median is not the same as average

- blckembr November 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry, now I get it.

- zr.roman November 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

N order statistic with modified version of Quick sort. Run time O(n).
algorithms:
pivot=partition array()
if pivot index is medium
return
else if pivot index is less then medium
recursively call the first half of array before the pivot
else
recursively call the second half of array after the pivot

- hiuhchan November 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using hint from the interviewer about a binary tree.
If the number of items in array is odd, then the median will be the root node of the binary search tree.
If the problem requires average of two middle elements in case length is even, then the first element is again the root node of the BST, and the second element will occur on the bigger side of the tree.
In balanced BST with odd number of elements the both sides of the tree contain equal number of elements (obviously). But in balanced BST with even number of elements one side will be bigger by 1 element (obviously as well). (This is in case we don't have duplicates among keys, let's assume this).
So, to obtain the second element in case length is even, we should do the following:
If the left side is bigger, we should take the element from it which is nearest smaller than the root element.
And if the right side is bigger, we should take the element from it which is nearest greater than or equal to the root element.

- zr.roman November 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Number of nodes on left and right sides of root are not always equal even in a Balanced BST, such as Red-Black Tree. The only thing that is promised is that height of left and right do not differ by more than some small number. The best in this is an AVL tree where height do not differ by more than 1.

I think the interviewer had this in mind:
- Build a self balancing BST
- when inserting a new node, increment left and right count on each parent (depending on where the new node goes)

Now we have count of left side and right side on the root. if they are equal, root is median, if they are not, can go either back or forth in inorder traversal starting from root the required number of steps which can be calculated from how many nodes are on left and right sides of root.

- blckembr November 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why would you do it with a binary tree? Quick select is O(n) complexity vs nlogn of binary tree. Seems like a weird hint to give. You could even sort the array which would be nlogn but much faster constant factor.

- Anonymous November 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Quick select is O(n^2) in worst case.

- Pratap Das November 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Quickselect's worst case is O(n^2)

- ranapratapchandra November 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Pratap Das, you are correct, but... There are variations on quickselect that avoid O(N^2) worst case, simplest is randomization, which still suffers from worst N^2 for specially crafted input, using median-of-medians for pivot selection, which also still vulnerable to certain inputs, and finaly Introselect, which has the same basic idea as Introsort and switches to known O(n) worst case (such as median-of-medians) in case partitioning is not effective for some input. All of that is worth at least discussing during interview, because coding might be too much in the time given.

- blckembr November 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

it is very simple with out using any of the bst or heap

public static double getMedian(int []arr){

Arrays.sort(arr); //quick sort O(nlongN)
int size=arr.length;
if(size%2!=0){
return arr[size/2];
}else{
int mid1= size/2;

return (arr[mid1-1]+arr[mid1])/2.0;
}

- krishna May 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static double getMedian(int []arr){
		
		Arrays.sort(arr); //quick sort O(nlongN)
		int size=arr.length;
	   if(size%2!=0){
		   return arr[size/2];
	   }else{
		   int mid1= size/2;
		   
		   return (arr[mid1-1]+arr[mid1])/2.0;
	   }

- krishna May 29, 2016 | Flag Reply


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