Amazon Interview Question
The solution to this problem is Treap, a BST as well as a heap,
TreapNode {
left, right, parent
value
priority
}
In the node keep an extra field named Priority (OR insertion Order) increment it everytime a new node comes...
So keep creating the BST based on the value and .... rotate it (kind of heapify) whenever a high priority item is inserted on a lower levels in BST untill it becomes a root
Please see Treap for better understanding:
Order of insertion and deletion would be O(logN) as we need to rotate (heapify)
My humble opinion:
Use an integer index to track the order of the comming nodes. For each new node, increase this index by 1 and use this integer as the identifier of the node.
Use this identifier to decide the position of the BST. When poping a node, extract the biggest one in the BST.
The problem of this strategy is to BST may be unbalanced. So, BST balancing operation should be done from time to time.
Building a treap would be a better idea...Have the nodes hold an index. Start with index 0. As you insert elements, increment the index. Build a treap with that.. This would ensure O(log n) height for the tree
Yes..a max tree-heap with nodes containing a field for storing index to track the order of incoming nodes in increasing order sounds like an idea. Since it is a max-heap, popping from the stack would essentially mean deleting the root node of the heap {this is the max-heap,the node with the highest index, is of interest as this is a simulation of a LIFO }and then the re-heaping may happen that shall bring the node with the next highest index-value {order of insertion} to the root.
Have extra field in node as "node *previouslyAdded". Always have the TOP pointer pointing to last added. While poping return the node and point the TOP to previously added.
Augment the BST with the actual data being kept in augmented field and the order of insertion number kept as the key. Then find max in each search to get the most recently added element i.e. top of the stack.
The insertion number will always increase and I am asuuming you are creating the BST on the basis of the insertion number. So you will end up with a Linked List and not a BST..
heap would be the most suitable implementation for this problem,
- monj021 November 02, 2009but using a BST,i think traversing in reverse inorder might solve the problem
the steps would be
1.construct the BST as when the values arrive with arrival time as the key value along with necessary balancing at each step(otherwise no point in using bst and it will end up to be a linked list).
2.do reverse inorder traversal(this will print the values in decreasing order equivalent to a stack pop operation)
order would be O(nlogn)
please correct me if i am wrong!!