Problem Statement
The task involves designing an efficient data structure named AllOne that manages a collection of strings and efficiently tracks their occurrence counts. This data structure should offer the ability to increment or decrement the count of any given string and must also provide quick access to the string with the highest and lowest counts respectively. Specifically, the functions required in this data structure include:
AllOne(): A constructor to initiate the data structure.inc(String key): Increases the count of a specified stringkeyby 1. Ifkeyis not present, it is added to the data structure with an initial count of 1.dec(String key): Decreases the count of a specified stringkeyby 1 and removes the string entirely if its count reaches 0. It is ensured that thekeyexists in the data structure before its count is decremented.getMaxKey(): Retrieves a string that has the maximum count so far. Returns an empty string if the data structure is empty.getMinKey(): Retrieves a string that has the minimum count so far. Returns an empty string if the data structure is empty.
In addition, every operation in the data structure (inc, dec, getMaxKey, getMinKey) should operate in average O(1) time complexity, pointing towards the requirement for optimized data management and access strategies.
Examples
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 <= 10keyconsists of lowercase English letters.- It is guaranteed that for each call to
dec,keyis existing in the data structure. - At most
5 * 104calls will be made toinc,dec,getMaxKey, andgetMinKey.
Approach and Intuition
Given the requirements of the AllOne data structure, a combination of multiple data organization strategies can be employed to ensure optimal performance as described in the constraints. Here is an intuitive approach based on the operations described:
Handling the Counts: A hash map (
countMap) can be employed where keys are the strings and values are their respective counts. This allowsO(1)time complexity for increment (inc) and decrement (dec) operations simply by checking and updating the count directly via the hash key.Tracking Minimum and Maximum: To retrieve the minimum and maximum count strings efficiently:
- Maintain two additional hash maps: one (
maxFreqMap) to store strings with the maximum count and another (minFreqMap) for those with the minimum count. Updating these maps on everyincanddecoperation ensures constant time access to minimum and maximum count strings. - Alternatively, a more evolved approach involves using a doubly linked list (
DLL) alongside the primary hash map (countMap). This list maintains nodes in sorted order of counts, where each node contains strings with the same count. This allows efficient movement of strings between different count nodes and quick updates to min and max references.
- Maintain two additional hash maps: one (
Ensuring O(1) Operations: Using the hash maps for direct access to counts and doubly linked lists to maintain order without needing to rebuild or rescan array-like structures ensures all operations meet the required
O(1)time complexity on average.Example Execution:
- Initializing the
AllOne: Start with an emptycountMap,maxFreqMap, andminFreqMap. - On calling
inc("hello")twice, the count for "hello" becomes 2. "hello" updates both the maximum and minimum as it is the only string. - When
inc("leet")is called, it is added with a count of 1. Now, "leet" becomes the new minimum, while "hello" remains the maximum.
- Initializing the
Solutions
- C++
- Java
- Python
class FrequencyNode {
public:
int frequency;
FrequencyNode* previous;
FrequencyNode* next;
unordered_set<string> itemKeys;
FrequencyNode(int frequency) : frequency(frequency), previous(nullptr), next(nullptr) {}
};
class MaxMinCounter {
private:
FrequencyNode* dummyHead;
FrequencyNode* dummyTail;
unordered_map<string, FrequencyNode*> keyToNodeMap;
public:
MaxMinCounter() {
dummyHead = new FrequencyNode(0);
dummyTail = new FrequencyNode(0);
dummyHead->next = dummyTail;
dummyTail->previous = dummyHead;
}
void increase(string key) {
if (keyToNodeMap.count(key)) {
FrequencyNode* currentNode = keyToNodeMap[key];
int currentFreq = currentNode->frequency;
currentNode->itemKeys.erase(key);
FrequencyNode* nextNode = currentNode->next;
if (nextNode == dummyTail || nextNode->frequency != currentFreq + 1) {
FrequencyNode* newNode = new FrequencyNode(currentFreq + 1);
newNode->itemKeys.insert(key);
newNode->previous = currentNode;
newNode->next = nextNode;
currentNode->next = newNode;
nextNode->previous = newNode;
keyToNodeMap[key] = newNode;
} else {
nextNode->itemKeys.insert(key);
keyToNodeMap[key] = nextNode;
}
if (currentNode->itemKeys.empty()) {
deleteNode(currentNode);
}
} else {
FrequencyNode* firstNode = dummyHead->next;
if (firstNode == dummyTail || firstNode->frequency > 1) {
FrequencyNode* newNode = new FrequencyNode(1);
newNode->itemKeys.insert(key);
newNode->previous = dummyHead;
newNode->next = firstNode;
dummyHead->next = newNode;
firstNode->previous = newNode;
keyToNodeMap[key] = newNode;
} else {
firstNode->itemKeys.insert(key);
keyToNodeMap[key] = firstNode;
}
}
}
void decrease(string key) {
if (!keyToNodeMap.count(key)) {
return;
}
FrequencyNode* currentNode = keyToNodeMap[key];
currentNode->itemKeys.erase(key);
int currentFreq = currentNode->frequency;
if (currentFreq == 1) {
keyToNodeMap.erase(key);
} else {
FrequencyNode* prevNode = currentNode->previous;
if (prevNode == dummyHead || prevNode->frequency != currentFreq - 1) {
FrequencyNode* newNode = new FrequencyNode(currentFreq - 1);
newNode->itemKeys.insert(key);
newNode->previous = prevNode;
newNode->next = currentNode;
prevNode->next = newNode;
currentNode->previous = newNode;
keyToNodeMap[key] = newNode;
} else {
prevNode->itemKeys.insert(key);
keyToNodeMap[key] = prevNode;
}
}
if (currentNode->itemKeys.empty()) {
deleteNode(currentNode);
}
}
string getMaximumKey() {
if (dummyTail->previous == dummyHead) {
return "";
}
return *dummyTail->previous->itemKeys.begin();
}
string getMinimumKey() {
if (dummyHead->next == dummyTail) {
return "";
}
return *dummyHead->next->itemKeys.begin();
}
private:
void deleteNode(FrequencyNode* node) {
FrequencyNode* prevNode = node->previous;
FrequencyNode* nextNode = node->next;
prevNode->next = nextNode;
nextNode->previous = prevNode;
delete node;
}
};
This summary explains the implementation of a custom data structure using C++ designed to efficiently track the maximum and minimum frequency of keys or items. This data structure is often referred to as "All O`one Data Structure". Here's a breakdown of the code and how the structure operates:
Class Structure and Nodes:
FrequencyNode: Represents each node in the doubly linked list, containing:frequency: the frequency of keys in this node.itemKeys: a set of keys with the same frequency.previousandnext: pointers to the previous and next nodes in the list.
MaxMinCounter: Maintains a list ofFrequencyNode, providing insertion and deletion operations, and functions to fetch keys with maximum and minimum frequencies.
Initialization:
- Create
dummyHeadanddummyTailnodes to simplify edge cases handling, making insertion and removal operations more consistent by eliminating the need to check for NULL pointers.
- Create
Key Operations:
- Increase Frequency (
increase):- If the key exists, move the key to the next frequency node or create a new one if necessary.
- Adjust pointers and, if needed, remove old nodes that become empty.
- Decrease Frequency (
decrease):- Similar to increase but in reverse; decrease the frequency and potentially move the key to a lower frequency node, handling edge cases like the lowest frequency specially.
- Fetch Maximum and Minimum (
getMaximumKeyandgetMinimumKey):- Retrieve keys from the nodes near the tail and head of the list respectively, these nodes represent the highest and lowest frequency nodes that currently possess keys.
- Increase Frequency (
Auxiliary Functionality:
- Node Deletion (
deleteNode):- Properly handles the removal of a node by adjusting adjacent nodes' pointers and safely deleting the node to free memory, maintaining the integrity of the doubly linked list.
- Node Deletion (
This implementation ensures operations are optimized for frequency updates, important for scenarios where the frequency of access is crucial, such as caching systems or tracking real-time usage statistics. By linking nodes, updates occur in constant time, leveraging the advantages of the linked list structure for fast insertions and deletions combined with direct access using a hash map for the keys. This provides a robust and efficient method to track and retrieve items based on their frequencies in real-time.
public class ListNode {
int frequency;
ListNode previous;
ListNode following;
Set<String> entries = new HashSet<>();
ListNode(int frequency) {
this.frequency = frequency;
}
}
class DataStructure {
ListNode start;
ListNode end;
Map<String, ListNode> index = new HashMap<>();
DataStructure() {
start = new ListNode(0);
end = new ListNode(0);
start.following = end;
end.previous = start;
}
public void increase(String key) {
if (index.containsKey(key)) {
ListNode curNode = index.get(key);
int currentFreq = curNode.frequency;
curNode.entries.remove(key);
ListNode next = curNode.following;
if (next == end || next.frequency != currentFreq + 1) {
ListNode newNode = new ListNode(currentFreq + 1);
newNode.entries.add(key);
newNode.previous = curNode;
newNode.following = next;
curNode.following = newNode;
next.previous = newNode;
index.put(key, newNode);
} else {
next.entries.add(key);
index.put(key, next);
}
if (curNode.entries.isEmpty()) {
detachNode(curNode);
}
} else {
ListNode first = start.following;
if (first == end || first.frequency > 1) {
ListNode newNode = new ListNode(1);
newNode.entries.add(key);
newNode.previous = start;
newNode.following = first;
start.following = newNode;
first.previous = newNode;
index.put(key, newNode);
} else {
first.entries.add(key);
index.put(key, first);
}
}
}
public void decrease(String key) {
if (!index.containsKey(key)) {
return;
}
ListNode curNode = index.get(key);
curNode.entries.remove(key);
int currentFreq = curNode.frequency;
if (currentFreq == 1) {
index.remove(key);
} else {
ListNode prev = curNode.previous;
if (prev == start || prev.frequency != currentFreq - 1) {
ListNode newNode = new ListNode(currentFreq - 1);
newNode.entries.add(key);
newNode.previous = prev;
newNode.following = curNode;
prev.following = newNode;
curNode.previous = newNode;
index.put(key, newNode);
} else {
prev.entries.add(key);
index.put(key, prev);
}
}
if (curNode.entries.isEmpty()) {
detachNode(curNode);
}
}
public String getMaxKey() {
if (end.previous == start) {
return "";
}
return end.previous.entries.iterator().next();
}
public String getMinKey() {
if (start.following == end) {
return "";
}
return start.following.entries.iterator().next();
}
private void detachNode(ListNode node) {
ListNode before = node.previous;
ListNode after = node.following;
before.following = after;
after.previous = before;
}
}
The provided solution implements an advanced data structure in Java to manage string keys based on their frequencies. This structure allows for efficient retrieval of the key with the maximum and minimum frequencies, as well as increasing or decreasing the frequencies of the keys.
The
ListNodeclass:- Holds the frequency and a set of entries (keys) with this frequency.
- Links to the previous and the next node to form a doubly linked list.
The
DataStructureclass:- Initializes a doubly linked list with start and end sentinel nodes.
- Manages the relationship between keys and their corresponding nodes using a hash map.
Key methods:
increase(String key): Increases the frequency of a key.- If the key exists, it moves the key to the next node or creates a new node if the next node has a different frequency.
- If the key does not exist, it adds it to the first node or creates a new node with frequency 1.
decrease(String key): Decreases the frequency of a key.- Removes the key from its current node.
- Moves the key to the previous node or creates a new previous node if needed.
getMaxKey(): Returns a key with the maximum frequency.getMinKey(): Returns a key with the minimum frequency.detachNode(ListNode node): Removes an empty node from the linked list.
This structure is particularly useful for scenarios where it’s necessary to keep track of items' frequencies and access those with the highest or lowest frequencies quickly and efficiently. The use of a doubly linked list along with a hash map ensures that all operations, such as insertions, deletions, and frequency adjustments, are handled in an optimal manner.
class ListNode:
def __init__(self, frequency):
self.freq = frequency
self.previous = None
self.next = None
self.items = set()
class AllOneDS:
def __init__(self):
self.start = ListNode(0) # Starting dummy node
self.end = ListNode(0) # Ending dummy node
self.start.next = self.end # Connect start to end
self.end.previous = self.start # Connect end to start
self.lookup = {} # Store item-node association
def increment(self, item: str) -> None:
if item in self.lookup:
current = self.lookup[item]
current_freq = current.freq
current.items.remove(item)
next_node = current.next
if next_node == self.end or next_node.freq != current_freq + 1:
new_node = ListNode(current_freq + 1)
new_node.items.add(item)
new_node.previous = current
new_node.next = next_node
current.next = new_node
next_node.previous = new_node
self.lookup[item] = new_node
else:
next_node.items.add(item)
self.lookup[item] = next_node
if not current.items:
self.deleteNode(current)
else:
first_node = self.start.next
if first_node == self.end or first_node.freq > 1:
new_node = ListNode(1)
new_node.items.add(item)
new_node.previous = self.start
new_node.next = first_node
self.start.next = new_node
first_node.previous = new_node
self.lookup[item] = new_node
else:
first_node.items.add(item)
self.lookup[item] = first_node
def decrement(self, item: str) -> None:
if item not in self.lookup:
return
current = self.lookup[item]
current.items.remove(item)
current_freq = current.freq
if current_freq == 1:
del self.lookup[item]
else:
previous_node = current.previous
if previous_node == self.start or previous_node.freq != current_freq - 1:
new_node = ListNode(current_freq - 1)
new_node.items.add(item)
new_node.previous = previous_node
new_node.next = current
previous_node.next = new_node
current.previous = new_node
self.lookup[item] = new_node
else:
previous_node.items.add(item)
self.lookup[item] = previous_node
if not current.items:
self.deleteNode(current)
def maximumKey(self) -> str:
if self.end.previous == self.start:
return ""
return next(iter(self.end.previous.items))
def minimumKey(self) -> str:
if self.start.next == self.end:
return ""
return next(iter(self.start.next.items))
def deleteNode(self, node):
prev_node = node.previous
next_node = node.next
prev_node.next = next_node
next_node.previous = prev_node
The code provided describes the implementation of a complex data structure designed to efficiently track a set of strings by their frequency of occurrences and allow dynamic changes to each string's frequency. This custom data structure is called AllOneDS which is implemented using a doubly linked list in conjunction with hash maps in Python.
The class ListNode represents a node in the doubly linked list where each node holds:
- a frequency.
- pointers to the previous and next nodes in the list.
- a set of items (strings) having that frequency.
The AllOneDS class is the main class that manages the nodes. It has methods for incrementing or decrementing the frequency of items, as well as retrieving the item with maximum and minimum frequencies. Here's an overview of each component and the method functionalities:
Initialization (
__init__): Initializes the doubly linked list with dummy start and end nodes, which are connected to each other, and an empty dictionary (lookup) mapping items to their respective nodes.Incrementing Frequency (
increment):- Checks if an item exists in
lookup. If it does, it adjusts the node accordingly by creating a new node with an incremented frequency or moves the item to an existing node with the next higher frequency. If the current node becomes empty, it's removed. - If the item does not exist, it either adds it to the node with frequency 1 or creates a new node if it doesn't exist.
- Checks if an item exists in
Decrementing Frequency (
decrement):- If the item exists in the
lookup, it is removed from its current node. - If the current frequency is 1, it removes the item from
lookup. Otherwise, it either moves the item to the previous node with a decremented frequency or creates a new node if no such node exists. - If the current node is left empty after decrementing, it removes the node.
- If the item exists in the
Retrieve Maximum Frequency Key (
maximumKey):- Returns the item with the highest frequency. If the list is nearly empty, it returns an empty string.
Retrieve Minimum Frequency Key (
minimumKey):- Returns the item with the lowest frequency. Similar to
maximumKey, returns an empty string if the list contains no useful data.
- Returns the item with the lowest frequency. Similar to
Delete Node (
deleteNode):- Removes a specified node from the linked list carefully updating previous and next pointers.
This implementation allows for very efficient operations concerning frequency management of the items, suitable for scenarios where frequent updates related to item counts are required, avoiding the pitfalls of straightforward counting algorithms which may perform poorly with frequent updates.
No comments yet.