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 <= 10key consists of lowercase English letters.dec, key is existing in the data structure.5 * 104 calls will be made to inc, dec, getMaxKey, and getMinKey.The key challenge in #432 All O`one Data Structure is supporting inc, dec, getMaxKey, and getMinKey operations in O(1) time. A common approach combines a hash table with a doubly-linked list. The hash map stores the mapping from each key to its corresponding node or bucket, enabling constant-time access when updating counts.
The doubly-linked list organizes buckets by frequency, where each node represents a specific count and holds all keys with that count. When a key is incremented or decremented, it moves to the adjacent bucket representing the updated frequency. If the required bucket does not exist, a new one is created and inserted in the correct position. This structure ensures that the head and tail of the list always represent the minimum and maximum frequencies.
By maintaining this ordered bucket structure and direct key references through hashing, all required operations can be executed efficiently with O(1) time and controlled space usage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map + Doubly Linked List Buckets | O(1) for inc, dec, getMaxKey, getMinKey | O(N) |
Ashish Pratap Singh
This approach involves using a hash map to store the frequency of each key and a doubly linked list (DLL) to keep track of the keys at each frequency level. Each node in the DLL represents a unique frequency and holds a set of keys that have the same frequency. This data structure allows us to efficiently update, delete, and access keys while keeping track of the frequencies.
Time Complexity: Each of the operations—inc, dec, getMaxKey, and getMinKey—takes O(1) on average.
Space Complexity: O(K) for storing the keys and their corresponding nodes, where K is the number of unique keys.
1```c
2#include <stdio.h>
3#include <stdlib.h>
4#include <string.h>
5#include <limits.h>
6
7#define MAX_KEY_LENGTH 11
8
9// Node in doubly linked list
10typedef struct Node {
11 int count;
12 struct Node *prev, *next;
13 struct KeySet *keys;
14} Node;
15
16// Keys in the count node
17typedef struct KeySet {
18 char key[MAX_KEY_LENGTH];
19 struct KeySet *next;
20} KeySet;
21
22// Hash map entry
23typedef struct MapEntry {
24 char key[MAX_KEY_LENGTH];
25 Node *node;
26} MapEntry;
27
28// Hash map to store key and its count node
29#define MAP_SIZE 1009
30MapEntry *map[MAP_SIZE];
31
32Node *head, *tail; // Head and tail of the doubly linked list
33
34// Function definitions
35Node *createNode(int count);
36void removeKeyFromNode(Node *node, const char *key);
37void addKeyToNode(Node *node, const char *key);
38unsigned int hash(const char *key);
39MapEntry* getMapEntry(const char *key);
40
41Node *head, *tail; // Head and tail of the doubly linked list
42
43unsigned int hash(const char *key) {
44 unsigned int hash = 0;
45 const char *ptr;
46 for (ptr = key; *ptr != '\0'; ptr++) {
47 hash = (hash * 31 + *ptr) % MAP_SIZE;
48 }
49 return hash;
50}
51
52MapEntry* getMapEntry(const char *key) {
53 unsigned int h = hash(key);
54 while (map[h] != NULL) {
55 if (strcmp(map[h]->key, key) == 0) {
56 return map[h];
57 }
58 h = (h + 1) % MAP_SIZE;
59 }
60 return NULL;
61}
62
63void inc(const char *key) {
64 MapEntry *entry = getMapEntry(key);
65
66 if (entry == NULL) {
67 entry = (MapEntry *)malloc(sizeof(MapEntry));
68 strcpy(entry->key, key);
69 entry->node = head;
70 addKeyToNode(head, key);
71
72 unsigned int h = hash(key);
73 while (map[h] != NULL) {
74 h = (h + 1) % MAP_SIZE;
75 }
76 map[h] = entry;
77 } else {
78 Node *node = entry->node;
79 removeKeyFromNode(node, key);
80 Node *nextNode = node->next;
81
82 if (nextNode == NULL || nextNode->count != node->count + 1) {
83 Node *newNode = createNode(node->count + 1);
84 newNode->prev = node;
85 newNode->next = node->next;
86 if (node->next != NULL) {
87 node->next->prev = newNode;
88 }
89 node->next = newNode;
90 nextNode = newNode;
91 }
92
93 addKeyToNode(nextNode, key);
94 entry->node = nextNode;
95 }
96}
97
98void dec(const char *key) {
99 MapEntry *entry = getMapEntry(key);
100 if (entry == NULL) {
101 return;
102 }
103
104 Node *node = entry->node;
105 removeKeyFromNode(node, key);
106
107 if (node->count == 1) {
108 free(entry);
109 unsigned int h = hash(key);
110 while (strcmp(map[h]->key, key) != 0) {
111 h = (h + 1) % MAP_SIZE;
112 }
113 map[h] = NULL;
114 return;
115 }
116
117 Node *prevNode = node->prev;
118
119 if (prevNode == head || prevNode->count != node->count - 1) {
120 Node *newNode = createNode(node->count - 1);
121 newNode->prev = node->prev;
122 newNode->next = node;
123 node->prev->next = newNode;
124 node->prev = newNode;
125 prevNode = newNode;
126 }
127
128 addKeyToNode(prevNode, key);
129 entry->node = prevNode;
130}
131
132Node *createNode(int count) {
133 Node *node = (Node *)malloc(sizeof(Node));
134 node->count = count;
135 node->prev = node->next = NULL;
136 node->keys = NULL;
137 return node;
138}
139
140void removeKeyFromNode(Node *node, const char *key) {
141 KeySet *ks = node->keys, *prev = NULL;
142 while (ks != NULL) {
143 if (strcmp(ks->key, key) == 0) {
144 if (prev == NULL) {
145 node->keys = ks->next;
146 } else {
147 prev->next = ks->next;
148 }
149 free(ks);
150 break;
151 }
152 prev = ks;
153 ks = ks->next;
154 }
155
156 if (node->keys == NULL && (node->prev != NULL || node->next != NULL)) {
157 node->prev->next = node->next;
158 if (node->next != NULL) {
159 node->next->prev = node->prev;
160 }
161 free(node);
162 }
163}
164
165void addKeyToNode(Node *node, const char *key) {
166 KeySet *ks = (KeySet *)malloc(sizeof(KeySet));
167 strcpy(ks->key, key);
168 ks->next = node->keys;
169 node->keys = ks;
170}
171
172char* getMaxKey() {
173 if (tail->prev == head) return "";
174
175 return tail->prev->keys == NULL ? "" : tail->prev->keys->key;
176}
177
178char* getMinKey() {
179 if (head->next == tail) return "";
180
181 return head->next->keys == NULL ? "" : head->next->keys->key;
182}
183
184int main() {
185 // Your code for testing the above logic (initializing head, tail, and running test cases)
186 return 0;
187}
188```The solution uses a doubly linked list to store nodes that keep track of key counts, while a hash map points to these nodes for quick updates. Each node's key set is a linked list storing the keys currently having a particular count. When counts are incremented or decremented, keys are moved to adjacent count nodes, ensuring efficient access for getMaxKey and getMinKey.
This approach utilizes a linked hash map where the keys are linked, ensuring a constant-time access. Frequencies are stored in hash maps that maintain the order of the elements. Keys are moved forward and backward among buckets when incrementing and decrementing, respectively. This combination allows the solution to be optimal with respect to speed and space.
Time Complexity: Each operation incurs only O(1) time on average due to the hash map use.
Space Complexity: O(K) in terms of storage for keys and nodes, where K is the number of unique keys.
1```java
2import java.util.
```Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is commonly asked in top tech company interviews because it tests system design thinking, data structure composition, and the ability to achieve strict O(1) operations using multiple structures together.
The optimal approach combines a hash table with a doubly-linked list of frequency buckets. The hash map gives constant-time access to each key, while the linked list maintains keys grouped by count, allowing O(1) updates and retrieval of minimum and maximum keys.
A doubly linked list allows efficient insertion and removal of frequency buckets while maintaining order. Since each bucket represents a count, keys can move to neighboring buckets during increment or decrement operations in constant time.
A combination of a hash map and a doubly-linked list is the most effective structure. The map tracks each key's location, while the linked list maintains ordered frequency buckets so keys can move between counts efficiently.
This Java implementation leverages a doubly linked list of buckets, where each bucket holds keys with the same frequency. The frequency is managed by the bucket list, enabling constant-time updates. Each operation (inc, dec, getMaxKey, and getMinKey) requires only local adjustments within a bucket, which makes this structure efficient and fast.