CareerCup

Implement an ADT that encapsulates a BALANCED BST and two variables min and max.

insertion,deletion,extractMin,extractMax would then take O(logn) time

On every insertion update the min and max variables.So max() and min() would take O(1) time.

what is adt

@cunomad:
ADT = Abstract Data Type
http://en.wikipedia.org/wiki/Abstract_data_type

@random: i think you're right

use a heap!!

@coder : Heap is not right because it lacks order throughout the tree (Think about insert and than lookup or more deeply about getting the next min/max number after extractmin/max). BST is the right implementation with a min and max variable so that the lookup is O(1) while update takes lg(n). Update(insert, extract) shall also change the min/max variable

This solution (proposed by random) will fail with extractMin() or extractMax(). Because after that the values in the Min and Max variables will be invalid and you don't know the next Min and next Max.

Having a balanced BST, is good. But while we are trying perform extractMin() delete the leftmost leaf of the BST, we need to maintain another variable tempMin. Which will be updated as we travel from head to the leftmost node and will hold the prev-min value (at the end the parent of the left-most node). This is what the next min is after removing the Min from the BST in extractMin() operation and stored in Min variable.
Similarly, have tempMax variable to store the previous-max during extractMax() operation.
In fact, the same Min and Max variables can be reused for the tempMin and tempMax purpose.

I guess Interval Heaps suits best.. root stores (MIN,MAX) and every other operation is of lg(n)..

I guess Interval Heaps suits best.. root stores (MIN,MAX) and every other operation is of lg(n)..

what are these interval heaps ? plz explaining your approach with some examples

Implement Stack as a link-list.
1) Each node of link-list contains two additional parameters "current_min", current_max"
2) As the name indicates "current_min" -> points current minimum during its insertion. Same for current_max.

now every-opr can be done in O(1)

For every solution, think of a scenario when the currentMin is removed. i.e. extractMin. Now, whatever data structure you propose should provide a way to find out next min/max. The solution provided by Shwetank does not handle this case. Also it is more space complex. And off-source time complex as well.
If the new element that you insert into a linked list is smaller than the current Min? You need to update each node in the list to point to this new Min. How do you say each operation is O(1)?

Use two heaps - minheap and maxheap. Each entry contains integer, and a pointer to the same value on the other heap.
Min and max are constant time as they only require a look up to the appropriate heap's root node.
Extractmin will remove root on minheap, replace the last element of maxheap with node pointed by just removed min node and finally 'heapify' both structures.
Extractmax works symmetrically.
Insert puts value in both heaps and updates the pointers.
All of O(logN) operations will take O(2logN) => still O(logN) bound. May not be space efficient, but solves for the time constraint.

Question is insert in O(1) and Extract in O(logN).
If i use any heap or linked list, it will take O(n) or O(logN) time to insert but we need O(1) time complexity to insert and O(logN) to extract.

I think BST with min and max as variables works well because while using extractMax and extractMin you can use predecessor and successor methods which run in (lg N) time to update the min and max

BST with Min and Max.

1) each node while insertion will update the min and max.
2) extractMin is performed then left end child will be updated as Min in root
3) extractMax is performed then right end child will be updated as Max in root
4) for deletion, if min or max node is deleted then do the same thing which is done by extractMin and extracMax.

so Min and Max will be done in O(1) and rest of the operation will be done in O(log2n)

Use Min-Max Heap

a min-max heap will do the job...except min,max all the operation takes O(log n)...min,max takes O(1)...

why dont we use a threaded binary tree, where binary tree holds the property of a bst.

why dont we use a threaded binary tree, where binary tree holds the property of a bst.

the correct ans is min-max heap...