432. All O'one Data Structure
Asked at Atlassian, TikTok
Difficulty
Hard
Time
O(1) average per operation
Space
O(n)
Pattern
Hash Table
Companies
2
Problem
Design a class AllOne that keeps a count for each string key and can quickly tell you which key has the smallest count and which has the largest count.
You must support four operations. inc(key) adds 1 to the count of key, creating it with count 1 if it is new. dec(key) subtracts 1 from the count of key, and if the count becomes 0 the key is deleted. It is guaranteed that key already exists when dec is called. getMaxKey() returns any key with the largest count, and getMinKey() returns any key with the smallest count. When the structure is empty, both getters return the empty string "".
The hard part is speed: every operation must run in O(1) average time. A simple hash map of counts is not enough, because finding the min or max by scanning is O(n). You need a structure that always keeps the smallest and largest counts at hand.
Counts must be readable at both ends
Constraints
- ●
1 <= key.length <= 10 - ●
key consists of lowercase English letters - ●
It is guaranteed that for each call to dec, key is existing in the data structure - ●
At most 5 * 10^4 calls will be made to inc, dec, getMaxKey, and getMinKey
Examples
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
[[], ["hello"], ["hello"], [], [], ["leet"], [], []][null, null, null, "hello", "hello", null, "hello", "leet"]Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Atlassian | Hard | View all Atlassian questions → |
| TikTok | Hard | View all TikTok questions → |
How to Think About It
Brute force: use a hash map for counts and scan for min/max on each query. increment and decrement are O(1), but getMinKey and getMaxKey are O(n). The interviewer wants all operations in O(1).
Key insight: use a doubly linked list of frequency buckets. Each bucket stores a count and all keys with that count. A hash map maps each key to its bucket node. This makes all operations O(1).
Why doubly linked list: when a key's count changes, remove it from its current bucket and move it to the adjacent bucket (increment: next, decrement: prev). With a hash map pointing to the node, removal is O(1). Doubly linked gives O(1) deletion.
Bucket structure: bucket = {count: int, keys: HashSet, prev: Node, next: Node}. Sentinel head (min) and tail (max) buckets simplify edge cases. When a bucket becomes empty, remove it from the list.
Edge cases: increment a non-existent key (create it), decrement a key with count 1 (remove it entirely), getMinKey/getMaxKey when empty.
Optimal Approach
Use a doubly linked list of frequency buckets plus a hash map from key to bucket node.
Each node in the linked list stores: a HashSet of keys at that frequency, the frequency count, prev/next pointers.
Maintain sentinel head (frequency 0) and tail (frequency infinity) nodes.
increment(key):
- If key exists, remove from current bucket. newCount = count + 1.
- If next bucket has this count, add key there. Else create new bucket.
- Clean up empty buckets.
decrement(key):
- Remove from current bucket. newCount = count - 1.
- If newCount == 0, just remove the key entirely.
- If prev bucket has this count, add key there. Else create new bucket.
- Clean up empty buckets.
getMaxKey(): return any key from tail.prev (highest non-empty bucket).
getMinKey(): return any key from head.next (lowest non-empty bucket).
Time: O(1) for all operations. Space: O(n) where n is the number of keys.
Buckets in a doubly linked list
What Trips People Up in Real Interviews
Trying to use a min-heap and max-heap together. Heaps give O(log n) for insert/delete, not O(1). The doubly linked list with hash map is the correct approach for all O(1) operations.
Forgetting to remove empty buckets. When a key moves out of a bucket and the bucket becomes empty, remove it from the linked list. Empty buckets waste space and break getMin/getMax.
Not using sentinel head and tail nodes. Without sentinels, you must handle null checks for every edge case (empty list, only one bucket, inserting at boundaries). Sentinels eliminate all of this.
Using a singly linked list instead of doubly linked. You need O(1) deletion from both ends and from the middle. A singly linked list requires scanning to find the previous node, making deletion O(n).
Losing track of the key-to-node mapping. Every time a key moves between buckets, update the hash map. If the mapping is stale, you will access the wrong bucket and corrupt the data structure.
Solution Code
O(1) average per operation timeclass Node:
def __init__(self, count=0):
self.count = count
self.keys = set()
self.prev = None
self.next = None
class AllOne:
def __init__(self):
self.key_to_node = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_after(self, prev_node, new_node):
new_node.prev = prev_node
new_node.next = prev_node.next
prev_node.next.prev = new_node
prev_node.next = new_node
def inc(self, key):
if key in self.key_to_node:
node = self.key_to_node[key]
node.keys.remove(key)
next_node = node.next
if next_node.count == node.count + 1:
next_node.keys.add(key)
else:
new_node = Node(node.count + 1)
new_node.keys.add(key)
self._add_after(node, new_node)
next_node = new_node
self.key_to_node[key] = next_node
if not node.keys:
self._remove(node)
else:
if self.head.next.count == 1:
self.head.next.keys.add(key)
self.key_to_node[key] = self.head.next
else:
new_node = Node(1)
new_node.keys.add(key)
self._add_after(self.head, new_node)
self.key_to_node[key] = new_node
def dec(self, key):
if key not in self.key_to_node:
return
node = self.key_to_node[key]
node.keys.remove(key)
if node.count == 1:
del self.key_to_node[key]
else:
prev_node = node.prev
if prev_node.count == node.count - 1:
prev_node.keys.add(key)
self.key_to_node[key] = prev_node
else:
new_node = Node(node.count - 1)
new_node.keys.add(key)
self._add_after(prev_node, new_node)
self.key_to_node[key] = new_node
if not node.keys:
self._remove(node)
def getMaxKey(self):
if self.tail.prev == self.head:
return ""
return next(iter(self.tail.prev.keys))
def getMinKey(self):
if self.head.next == self.tail:
return ""
return next(iter(self.head.next.keys))Frequently Asked Questions
What is the All O'one Data Structure problem?
Design a data structure to store the counts of strings and return the keys with maximum and minimum counts. Supports increment, decrement, and getMinKey/getMaxKey all in `O(1)` time. This is a classic design problem testing your ability to combine hash maps with linked lists.
How do you solve All O'one Data Structure?
The optimal approach runs in O(1) average per operation time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask All O'one Data Structure?
All O'one Data Structure is asked at Atlassian, TikTok. It is a hard difficulty problem.
What are common mistakes on All O'one Data Structure?
- Trying to use a min-heap and max-heap together. Heaps give `O(log n)` for insert/delete, not `O(1)`. The doubly linked list with hash map is the correct approach for all `O(1)` operations.
- Forgetting to remove empty buckets. When a key moves out of a bucket and the bucket becomes empty, remove it from the linked list. Empty buckets waste space and break getMin/getMax.
- Not using sentinel head and tail nodes. Without sentinels, you must handle null checks for every edge case (empty list, only one bucket, inserting at boundaries). Sentinels eliminate all of this.
- Using a singly linked list instead of doubly linked. You need `O(1)` deletion from both ends and from the middle. A singly linked list requires scanning to find the previous node, making deletion `O(n)`.
- Losing track of the key-to-node mapping. Every time a key moves between buckets, update the `hash map`. If the mapping is stale, you will access the wrong bucket and corrupt the data structure.