All O'one Data Structure
Asked at Atlassian
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | Hard | View all Atlassian 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.
Visual walkthrough for operations: inc("a"), inc("a"), inc("b"), getMaxKey(), dec("a"), getMinKey():
inc("a"): bucket 1 = {a}. List: head <-> count1{a} <-> tail.
inc("a"): move a to bucket 2. List: head <-> count1{} <-> count2{a} <-> tail.
Remove empty bucket 1. List: head <-> count2{a} <-> tail.
inc("b"): bucket 1 for b. List: head <-> count1{b} <-> count2{a} <-> tail.
getMaxKey(): tail.prev = count2, return "a".
dec("a"): move a to bucket 1. List: head <-> count1{b,a} <-> tail.
Remove empty count2. List: head <-> count1{b,a} <-> tail.
getMinKey(): head.next = count1, return "b" or "a".
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.
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
class 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask All O'one Data Structure?
All O'one Data Structure is asked at Atlassian. 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.