## Amazon Interview Question

**Country:**United States

pretty simple:

1) get sum of elements of array,

2) get count of elements of array,

3) {1} / {2}.

O(n).

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

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.

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.

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.

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

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:

- blckembr November 19, 2015