Amazon Interview Question Interns
Country: United States
Interview Type: Phone Interview
As a practical matter, this solution involves writing your own heap implementation so that you can implement custom operations like removing an arbitrary element through a pointer.
We can make the code easier to implement by using two balanced BSTs from a library instead, and not maintaining a hash table. When popping the stack, the trees will be searched to remove the element.
two heaps: one mean heap and one max heap. The median will be the top element from either the mean or the max heap. Then every node should have a link to the next node added after it and we should also have a pointer to the latest node added.
insertion/push: log N
1)insert a node in the proper heap so that half (or half + 1) nodes are in one heap and rest half is in the other.
2)add a link to this new node from the last added node and preserve a pointer to the new node.
deletion/pop: log N
1)Delete the last node added
2) Adjust the Heap and pointers
Make the stack entries doubly linked list elements, with each element containing Value, Prev, and Next. Prev and Next refer to memory locations within the stack. Maintain reference to current median element.
On Push:
Find and insert new element into list, starting from median
If (stack size was odd) and (new element < median)
median = median.previous;
else if (stack size was even) and (new element > median)
median = median.next;
On pop:
Remove element from list
If (stack size was odd) and (popped element > median)
median = median.previous;
else if (stack size was even) and (popped element < median)
median = median.next;
Push is O(n/2). Pop and Median are O(1)
The main data structure will actually be a pair of heaps, like Skor described. To mimic a stack's functionality, just maintain an actual stack of references to nodes in the heaps. When you pop an element off the stack, you get a reference to the node that you also need to remove from the heap. If we use Fibonacci heaps, then insert and find-median are both constant time, but deletion is logarithmic time.
For the median, you keep a max heap for numbers less than the current median and a min heap for numbers higher than the current median. From here, you will base the new median based on the max and min.
- Skor April 02, 2015Push and pop, you just keep a regular array