p105 — All O(1) Data Structure — Hints

  1. The bucket-DLL is the only path to O(1) extremes. Group keys by count: each bucket = (count, set_of_keys). Keep buckets in a doubly-linked list sorted ascending by count. getMinKey = any key in head bucket. getMaxKey = any key in tail bucket. Both O(1).

  2. count_to_bucket: dict[int, BucketNode] is mandatory. Without it, inc(key) would need to scan the DLL to find the bucket at the new count.

  3. inc(key) is a 3-case move-or-create:

    • key absent → insert into bucket(1); create bucket(1) at the head of the DLL if missing.
    • key at count c → move from bucket(c) to bucket(c+1); create bucket(c+1) immediately AFTER bucket(c) if missing.
    • If the old bucket becomes empty after the move, unlink it from the DLL and delete it from the map.

  4. dec(key) mirrors inc with two extra cases:

    • key was at count 1 → delete the key entirely.
    • else → move from bucket(c) to bucket(c-1); create bucket(c-1) immediately BEFORE bucket(c) if missing.

  5. getMinKey() / getMaxKey() on empty must return "". Use a sentinel head and tail; head.next is tail means empty.

If stuck: see solution.py.