1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ A balanced binary tree achieves $log(n)$ time for all operations, and tries (e.g. a crit-bit tree) give you constant time for integer or floating-point keys. You could also use a max-heap and a min-heap with a hash-table indexing the positions of each element in the heaps, but this would have large constant factors and substantial implementation complexity. $\endgroup$ – user1502040 Mar 25 '18 at 20:03
  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Mar 25 '18 at 20:24
  • 1
    $\begingroup$ Since there are no performance criteria given, there are many options. $\endgroup$ – Raphael Mar 25 '18 at 20:24
  • 1
    $\begingroup$ BSTs can be augmented to support selection of any order-statistic in time proportional to the height of the tree without impacting the other operations unduly. That's a popular exercise problem. $\endgroup$ – Raphael Mar 25 '18 at 20:25
  • $\begingroup$ What about min-max heap? $\endgroup$ – Evil Mar 25 '18 at 21:10
1
$\begingroup$
  • If there is no restriction on execution time or $n$ stays small then a simple unsorted array is always an option. It gives $O(n)$ execution time for all operations except adding an object and removing by swap-with-back-and-pop. As a less obvious bonus iteration over an array is very cache friendly so it will likely outperform nearly everything for small $n$.

  • When you value lookup more than modification you can sort the array, lookups are now $O(\log n)$ and min and max are $O(1)$. But modifications are now $O(n)$ in all cases however they can be amortized a bit by using a small scratch array on the side that gets merged in periodically for additions and tombstone sentinels for removed elements.

  • Using a min or max heap will reduce modification time to $O(\log n)$ at the cost of all other operations becoming $O(n)$ except the query for min or max depending on which it is. You can split the data into 2 using a selected pivot element where if smaller then elements get pushed into a min heap and if larger they get pushed into a max heap. Depending on the order of operation you may need to reselect the pivot element is the sizes of the heaps become too unbalanced.

Then there are the node-based solutions:

  • Linked list (sorted or not) is not useful at all here, you still have $O(n)$ execution time for nearly everything like with unsorted array with additional cache miss and dependent-load costs during iteration and the only bonus you have is that insert and remove can happen in-place. I'm mentioning it here because:

  • You can use a look-ahead list, essentially a sorted linked list with the addition that each node has a finger table of nodes that lets you skip ahead in the list. modifications and lookups are now $O(\log n)$. However it has an element of randomness (how large each finger table is) that can potentially screw you over and regress performance to $O(n)$ for lookups.

  • A balanced search tree isn't random in that way and every operation becomes $O(\log n)$ and correct implementation of the balancing routing can be tricky.

  • you already mentioned why you don't like the hashtable though the $O(1)$ modification and lookup can outweigh the $O(n)$ cost for min/max. Though keep in mind that there are various ways of implementing one each with various benefits and drawbacks.

Those are the basic data structures I'd select between for holding a set of values. If there are other requirements and performance is a big enough issue then I'll go research more exotic options.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.