## Amazon Interview Question

• 0

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

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.

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

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

median is not the same as average

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

sorry, now I get it.

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

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.

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

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.

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.

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

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

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

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

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

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

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

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

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.