Amazon Interview Question
Country: United States
Interview Type: In-Person
1. creating a BST and then printing the N/2 nodes similar to doing sorting (i.e. inorder traversal of the nodes) to figure out the median. But the question requires no sorting.
So to me this looks like a sol but not what the qus demands exactly. Comments?
2. the second approach seems to work but not for both the cases when n is odd/even. Coz according to this we are returning a single median which is the root of min-heap.
The better/complete solution would be to use 2 heap 1 max-heap containing the lowest n/2 elements and the other min-heap containing the rest elements. These lists can differ in size by +-1 factor at the end.
But the approaches are definately in the rite direciton.
create a max heap and min heap.. delete each element from root of each heap one by one...
when both the elements are equal .. it is the median..
Well, somehow I feel this is an (Nlog N) solution.
For building each heap( min and max) u require (Nlog N) time, so 2Nlog N is equivalent to Nlog N.
Now you are deleting an element from each heap, which is a log N operation . This delete operation is performed n/2 times for each heap , so that again sums up to Nlog N.
so what we have is 2(N log N) + (N/2)log N + (N/2)log N ...which is Nlog N.
Doesn't the heap creation take O(n) time? Extracting min from the min-heap roughly n/2 times can give the n/2-th smallest (as root) number which is the median, almost like the heap sort.
one don't need (n log n) time to calculate the complexity, it only require o(n). Here are two ways.
1) use optimize version of partition methods used in quicksort.
2) divide the array into n/5 small arrays each of size at max 5, calculate median of each of them, store it into a another array . this new array size is n/5. now we calculate median of this array too. lets suppose i calculated median of this, then i divide my array based upon this median of median array. in my division the largest array is of size at max 7n/10. and smallest array is of size at least 3n/10.
so the time complexity equations is :
T(n) = T(7n/10) + T(n/5) + 0(n)
this equation give 0(n) solution.
ya but space requirement is 0(n) too.
Hints: Quick Sort Approach, i.e. select pivot num.
Sol:
1. Take a random pivot number from the list.
2. Put the pivot number to it's exact location in the list. T(N) = O(N)
3. If position of the pivot num is the middle of list then retun the pivot as median.
else if position of the pivot num id less than middle num position then select a random pivot number from the right group and goto setp 2(above).
else select a random pivot number from the left group and goto setp 2(above).
The complexity of above approach depends on how pivot choosen. So its comlexity will be less than (N*LogN) or it will above (N*LogN).
no sorting means that no sorting should be done on the input array because then its straight forward.
What the previous approach is depicting is a modifaction of partition to find the ith order statistics by traversing only a part of the array depending on the index of the pivot found. Hence it doesn't sort the array rather just uses it to recurse either to the left or the right of the array.
Find the sum of all elements in one scanning of the array.
Then do sum/no of elements
Then in the second scan, check which element has the least difference with this sum. Then that element is the median.
Solution obtained in 2n
But i am doubtful if this is right. Can some one comment
1. Create a BST from the numbers. Print the N/2 node of the BST.
- Aashish July 27, 20122. Create a min-heap of size N/2. Populate with first N/2 numbers.For each new number, if it is larger than the head value, replace & update the heap. At the end, head will indicate the N/2 node.