Amazon Interview Question
Software Engineer in Testsheap1 = max-heap of all +ve numbers
heap2 = min-heap of all -ve numbers
find two products p1, p2
p1 = product of top three of heap1
p2 = product of top two of heap2 and top of heap1
take max(p1, p2)
run selection ( median of median) algorithm 3 times with n, n-1, n-2 and find the product of the 3. O(3n) = O(n).
OMG!!! thats best the solution.. sorry for the solution i gave.. but thats typisch dynamic solution
What if we build a min heap of 3 elements.. Once the first three elements are inserted, we should check if the next number is greater than the root of the heap in which case replace the root with the next number and perform downheap to restructure the heap. In the end we will have the greatest 3 elements in the heap. This should take n*O(logk) where k (in this case 3) is the number of elements whose product is the maximum.
Using selection algo is also a good approach, but may be degenerative if the list is sorted.
am giving the worst case solution of O(n)..( its really worse :( but it works )
Dynamic programming..
1. find the max product with 1 element involving each element.. (the elements themselves)
2. max product with two elements for each element..
3. max product with three elemnts (use the results of previous step - memoization)
the max val of last step gives the max product..
find max element - o(n)
- mudit... June 16, 2010find 2nd max -o(n)
find 3rd max -o(n)
//only when array contains negative elements ...
find 1st min -o(n)
find 2nd min -o(n)
if 1stMin*2ndMin < 2ndMax*3rdNax
answer = 1stMax*2ndMax*3rdMax
else
answer = 1stMax*1stMin*2ndMin