0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 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
    Commented Sep 10, 2018 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
    Commented Sep 12, 2018 at 8:16

1 Answer 1

Reset to default
-1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ We can't assume key is constant size. How will you get min/max in constant time? $\endgroup$
    – rgaut
    Commented Sep 10, 2018 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
    Commented Oct 11, 2018 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
    Commented Aug 8, 2019 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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