This was an interview question that I was told is supposed to be an open ended discussion of the trade-offs. You have a collection of comparable objects and want to be able to do the following: 1. Lookup, add, delete objects 2. Get and/or extract Min, max objects 3. Objects should be unique (no duplicates)
A max-heap or min-heap almost fits the criteria except you can only have easy access to either min or max but not both. I ended up saying that if we know if one of max or min is more commonly needed, build a max or min heap.
A hash table is out of the question since the elements are un-ordered although it does have O(1) lookup.
What are the most appropriate data structure(s) in this scenario?