Daily bit(e) of C++ | O(1) ranking data structure

Daily bit(e) of C++ #35, Common C++ interview problem: all-O(1) ranking data structure

Implement an O(1) data structure, that is, a data structure where all operations run in O(1) (amortized) time.

The data structure should store keys and their integer values and offer the following interface.

• increment(key)
  increment a value for the key if it exists, or insert the key with value 1 if it doesn't

• decrement(key)
  decrement a value for the key if it exists, or if the value is already 1, remove it

• min()
  return one of the minimum keys or an empty string if there are no keys stored

• max()
  return one of the maximum keys or an empty string if there are no keys stored

Before you continue reading the solution, try to solve it yourself. Here is a compiler explorer link with a short test case: https://compiler-explorer.com/z/vaPsGsxze.

Solution

When designing a data structure with specific complexity requirements, it’s worth considering the micro-operations we will need a what tools we can use to achieve those.

For the min() and max() operations, we will need to keep our data structure in some sorted order. This is because we do not have the leeway to recalculate the minimum after removing the min or max element.

With this in mind, we have an additional requirement. Incrementing (or decrementing) a key might require moving the key in front of many other keys with the same value. Only one data structure supports such an operation, the std::list.

To keep the keys sorted, we can group keys by value into buckets. Each increment or decrement can lead to a new bucket being created or, if the destination bucket already exists, a simple move.

Finally, we need a way to jump to a specific key. The std::list provides stable iterators, so we only need a mapping from the key to the specific iterator. We can use a std::unordered_map for that.

Click to open in Compiler Explorer.

---