Description
Design a data structure to store the strings’ count with the ability to return the strings with minimum and maximum counts.
Implement the AllOne class:
- AllOne() Initializes the object of the data structure.
- inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.
- dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement.
- getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string “”.
- getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string “”.
Note that each function must run in O(1) average time complexity.
Example 1:
Input
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
[[], ["hello"], ["hello"], [], [], ["leet"], [], []]
Output
[null, null, null, "hello", "hello", null, "hello", "leet"]
Explanation
AllOne allOne = new AllOne();
allOne.inc("hello");
allOne.inc("hello");
allOne.getMaxKey(); // return "hello"
allOne.getMinKey(); // return "hello"
allOne.inc("leet");
allOne.getMaxKey(); // return "hello"
allOne.getMinKey(); // return "leet"
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.
Solution
A very good question, but 35min to solve it might be a little bit tough.
Use a double linked list to store the frequency and the string keys. And a reversed index hashmap to store the string key with the frequency.
Previously I used a set in the node to store the key, but I will need to transform the set to a list for getMaxKey and getMinKey. So I used a list instead and it’s even more complicated. I saw in the solution that we could use next(iter(set)) to get a random one in o ( 1 ) o(1) o(1) time, so I would use that in the set solution. But I think using a list is also a good solution.
Code
With a set
class LinkedNode:
def __init__(self, key: int) -> None:
self.key = key
# {string_key1, string_key2, ...}
self.values = set()
self.prev = None
self.next = None
class AllOne:
def __init__(self):
# {string_key: node}
self.hashmap = {}
self.max_node = LinkedNode(0)
self.min_node = LinkedNode(0)
self.max_node.next = self.min_node
self.min_node.prev = self.max_node
def _insert_before(self, key: str, node: LinkedNode) -> None:
# if the previous node is max_node, create a new node
if node.prev == self.max_node or node.prev.key != node.key + 1:
new_node = LinkedNode(node.key + 1)
prev_node = node.prev
prev_node.next = new_node
new_node.prev = prev_node
node.prev = new_node
new_node.next = node
# else put it in
node.values.remove(key)
node.prev.values.add(key)
# update the self.hashmap
self.hashmap[key] = node.prev
def _insert_after(self, key: str, node: LinkedNode) -> None:
if node.next.key != node.key - 1:
new_node = LinkedNode(node.key - 1)
next_node = node.next
new_node.prev = node
node.next = new_node
next_node.prev = new_node
new_node.next = next_node
node.values.remove(key)
node.next.values.add(key)
self.hashmap[key] = node.next
def _delete_node(self, node: LinkedNode) -> None:
prev_node, next_node = node.prev, node.next
prev_node.next = next_node
next_node.prev = prev_node
node.prev = None
node.next = None
def _print_nodes(self) -> None:
node = self.max_node.next
while node != self.min_node:
print(node.key)
print(node.values)
node = node.next
def inc(self, key: str) -> None:
if key not in self.hashmap:
self.min_node.values.add(key)
self.hashmap[key] = self.min_node
node = self.hashmap[key]
self._insert_before(key, node)
# delete possible empty nodes
if node != self.min_node and len(node.values) == 0:
self._delete_node(node)
# self._print_nodes()
def dec(self, key: str) -> None:
# move the string to the next node
node = self.hashmap[key]
self._insert_after(key, node)
# if next node is min_node, delete it
if node.next == self.min_node:
self.min_node.values.clear()
self.hashmap.pop(key)
# delete possible empty nodes
if node != self.min_node and len(node.values) == 0:
self._delete_node(node)
# self._print_nodes()
def getMaxKey(self) -> str:
if len(self.max_node.next.values) == 0:
return ''
else:
return next(iter(self.max_node.next.values))
def getMinKey(self) -> str:
if len(self.min_node.prev.values) == 0:
return ''
else:
return next(iter(self.min_node.prev.values))
# Your AllOne object will be instantiated and called as such:
# obj = AllOne()
# obj.inc(key)
# obj.dec(key)
# param_3 = obj.getMaxKey()
# param_4 = obj.getMinKey()
With a list
class LinkedNode:
def __init__(self, key: int) -> None:
self.key = key
# [string_key1, string_key2, ...]
self.values = []
self.prev = None
self.next = None
class AllOne:
def __init__(self):
# {string_key: [node, index]}
self.hashmap = {}
self.max_node = LinkedNode(0)
self.min_node = LinkedNode(0)
self.max_node.next = self.min_node
self.min_node.prev = self.max_node
def _insert_before(self, key: str, node: LinkedNode) -> None:
# if the previous node is max_node, create a new node
if node.prev == self.max_node or node.prev.key != node.key + 1:
new_node = LinkedNode(node.key + 1)
prev_node = node.prev
prev_node.next = new_node
new_node.prev = prev_node
node.prev = new_node
new_node.next = node
# else put it in
cur_key_index, last_key = self.hashmap[key][1], node.values[-1]
# swap
node.values[cur_key_index], node.values[-1] = last_key, key
# update the last key's index
self.hashmap[last_key][1] = cur_key_index
node.values.pop()
# add the key to new node
node.prev.values.append(key)
# update the self.hashmap
self.hashmap[key] = [node.prev, len(node.prev.values) - 1]
def _insert_after(self, key: str, node: LinkedNode) -> None:
if node.next.key != node.key - 1:
new_node = LinkedNode(node.key - 1)
next_node = node.next
new_node.prev = node
node.next = new_node
next_node.prev = new_node
new_node.next = next_node
# swap
cur_key_index, last_key = self.hashmap[key][1], node.values[-1]
node.values[cur_key_index], node.values[-1] = last_key, key
node.values.pop()
# update the last_key's index
self.hashmap[last_key][1] = cur_key_index
node.next.values.append(key)
self.hashmap[key] = [node.next, len(node.next.values) - 1]
def _delete_node(self, node: LinkedNode) -> None:
prev_node, next_node = node.prev, node.next
prev_node.next = next_node
next_node.prev = prev_node
node.prev = None
node.next = None
def inc(self, key: str) -> None:
if key not in self.hashmap:
self.min_node.values.append(key)
self.hashmap[key] = [self.min_node, len(self.min_node.values) - 1]
node = self.hashmap[key][0]
self._insert_before(key, node)
# delete possible empty nodes
if node != self.min_node and len(node.values) == 0:
self._delete_node(node)
def dec(self, key: str) -> None:
# move the string to the next node
node = self.hashmap[key][0]
self._insert_after(key, node)
# if next node is min_node, delete it
if node.next == self.min_node:
self.min_node.values.clear()
self.hashmap.pop(key)
# delete possible empty nodes
if node != self.min_node and len(node.values) == 0:
self._delete_node(node)
def getMaxKey(self) -> str:
if len(self.max_node.next.values) == 0:
return ''
else:
return self.max_node.next.values[0]
def getMinKey(self) -> str:
if len(self.min_node.prev.values) == 0:
return ''
else:
return self.min_node.prev.values[0]
# Your AllOne object will be instantiated and called as such:
# obj = AllOne()
# obj.inc(key)
# obj.dec(key)
# param_3 = obj.getMaxKey()
# param_4 = obj.getMinKey()