We are planning to design a system where following operations are supported.

Increment("foo"): Increase the count of key 'foo'

Decrement("bar"): Decrease the count of key 'bar'

getMin():  Return the key which has minimum count

getMax():  Return the key which has maximum count

The catch is all operations should be in $O(1)$ time.

  • 4
    $\begingroup$ Fibonacci heaps support all your operations in $O(1)$ amortized running time (you need to maintain two heaps, one for getMin and one for getMax). The Wikipedia page describes several other heaps which have $O(1)$ worst case running time for all these operations. $\endgroup$ – Yuval Filmus Sep 10 '18 at 6:49
  • 1
    $\begingroup$ Without something not bounded by a constant, there is no point in asymptotic analysis. Be explicit, don't make your readers guess there can be $n$ keys. $\endgroup$ – greybeard Sep 12 '18 at 8:16

If your keys are strings, you can use a prefix tree mapping keys to values. In this way each operation can be implemented in $O(h)$ time, where $h$ is the length of the key, which means it is $O(1)$ to the size of the collection.
To get the minimum key(or maximum) you can traverse the tree, by going through the edge from the lexicographically smallest (or largest if you need max) node on each level.
I don't think you can get better complexity than $O(h)$ for arbitrary sized keys as you need $O(h)$ time to output the key anyway.

  • $\begingroup$ We can't assume key is constant size. How will you get min/max in constant time? $\endgroup$ – rgaut Sep 10 '18 at 21:34
  • $\begingroup$ @rgaut If the key isn't constant size, can't possibly return the min or max key in constant time, so you're sunk. $\endgroup$ – David Richerby Oct 11 '18 at 18:31
  • $\begingroup$ @rgaut You could hash each key to obtain a fixed length value to use as the input to all the operations. $\endgroup$ – RandomPerfectHashFunction Aug 8 '19 at 18:02

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.