Skip to main content

24. All O`one Data Structure

hardAsked at Redis

Design a data structure supporting inc, dec, getMaxKey and getMinKey all in O(1); Redis loves this because it is the exact LFU-counter primitive used internally for eviction sampling.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Implement AllOne with inc(key), dec(key) (deleting if count drops to 0), getMaxKey() returning any key with the max count (or empty string), and getMinKey() returning any key with the min count. All four operations must be average O(1).

Constraints

  • 1 <= key.length <= 10
  • Up to 5 * 10^4 calls per method

Examples

Example 1

Input
inc('hello'); inc('hello'); inc('leet'); getMaxKey()='hello'; getMinKey()='leet'
Output
see explanation

Approaches

1. Hash map + sort on query

Keep Map<key, count>; on getMin/getMax scan all entries.

Time
O(n) per getMin/getMax
Space
O(n)
// Walk Map every read; O(n) per call.

Tradeoff:

2. Doubly linked list of count-buckets

Each bucket node holds a Set of keys at that count. Maintain key->bucketNode and bucketNode->prev/next. On inc/dec move the key to the adjacent (or newly created) bucket. Head/tail give getMax/getMin in O(1). This is exactly Redis's per-bucket LFU sampling design.

Time
O(1) per op
Space
O(distinct keys + distinct counts)
class AllOne {
  constructor() {
    this.head = null; // highest count
    this.tail = null; // lowest count
    this.keyBucket = new Map();
  }
  inc(key) { /* move key from its bucket to bucket with count+1, creating if needed */ }
  dec(key) { /* move key down or remove */ }
  getMaxKey() { return this.head ? this.head.keys.values().next().value : ''; }
  getMinKey() { return this.tail ? this.tail.keys.values().next().value : ''; }
}

Tradeoff:

Redis-specific tips

Redis interviewers grade for the bucket-of-keys design AND for relating it to allkeys-lfu eviction sampling — bonus if you cite OBJECT FREQ for inspecting per-key counters.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill All O`one Data Structure and other Redis interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →