Problem Explanation

Given four different functions with various tasks to perform:

1. Inc(Key): This function will insert a new key with value 1. If the key already exists, it increments the current key value by 1. The key is guaranteed to be a non-empty string.

2. Dec(Key): This function checks if the key's value is 1, then removes it from the data structure. If key value is greater than 1, then it decrements the key value by 1. If the specified key does not exist in the data structure, nothing would be done. The key is also a non-empty string.

3. GetMaxKey(): This function retrieves one of the keys which has the maximum value. If there is no key available in the data structure, then it returns an empty string "".

4. GetMinKey(): Similar to GetMaxKey(), but it returns one of the keys with the minimum value. If there are no keys in the data structure, it returns an empty string "".

The challenge here is to implement these functions in a way they execute in O(1) time complexity, which means regardless of the number of elements in the data structure, all operations should be done in constant time.

Approach Explanation

The solution uses a combination of a doubly linked list and a hashmap. The list node keeps the count of the keys and each node is linked with the next higher and lower count. Each node also holds a hashmap of keys which have the same count, for constant time access.

1
2
3Doubly LinkedList Node:
4    - count
5    - keys with count = count
6        * insert key in constant time
7        * delete key in constant time
8        * get any key in constant time
9    - prev node : previous count
10    - next node : next count

The hashmap keyToIterator stores the keys and a pointer to its associated Node in the linked list.

On inc(key) operation, the solution does the following:

• if the key doesn't exist, a new Node is created and appended at the front or inserted after the node with count 1.
• if the key does exist, the key is moved to the next Node. If the next Node has a different count, a new Node is created. Once the key is moved, if the present Node doesn't have any keys, the Node is removed.

On dec(key) operation:

• if the key doesn't exist, the function does nothing.
• if the key exists and the count is more than 1, the key is moved to the previous Node. If the previous Node has different count, again a new Node is created. Once the key is moved, if the present Node doesn't contain any keys, the Node is removed.
• if the key exists and the count is 1, the key is simply removed. If after removal, the Node doesn't contain any keys, the Node is removed from the linked list.

getMaxKey() and getMinKey() operations just return the any key from the respective Node in constant time.

Example Walk-through

Let's consider we have following keys and associated counts:

1
2
3keys = ["A", "B", "C", "D", "E"]
4counts = [3, 2, 4, 1, 3]

Which means "A" is present 3 times, "B" is present 2 times and so on.

Our linked list would look like this:

1
2
31 - ["D"]
42 - ["B"]
53 - ["A", "E"]
64 - ["C"]

When we call inc("A"), the count of "A" becomes 4 and our linked list becomes:

1
2
31 - ["D"]
42 - ["B"]
53 - ["E"]
64 - ["A", "C"]

When we call dec("C"), the count of "C" becomes 3 and our linked list becomes:

1
2
31 - ["D"]
42 - ["B"]
53 - ["E", "C"]
64 - ["A"]

When we call getMaxKey(), it returns "A", and when we call getMinKey(), it returns "D".# Solutions

Solution in Python

1
2python
3from collections import defaultdict
4from collections import OrderedDict
5
6class Node:
7    def __init__(self, count=0):
8        self.keys = OrderedDict()
9        self.count = count
10
11class AllOne:
12    def __init__(self):
13        self.d = {}
14        self.dll = Node(0)
15        self.dll.next = self.dll.prev = self.dll
16
17    def inc(self, key: str) -> None:
18        if key in self.d:
19            self.removeKey(self.d[key], key)
20        else:
21            self.d[key] = self.dll.next
22        self.addNode(self.d[key].prev, Node(self.d[key].count+1), key)
23
24    def dec(self, key: str) -> None:
25        if key in self.d:
26            if self.d[key].count > 1:
27                if self.d[key].next.count == self.d[key].count-1:
28                    nxt = self.d[key].next
29                else:
30                    nxt = self.addNode(self.d[key], Node(self.d[key].count-1))
31                self.removeKey(self.d[key], key)
32                nxt.keys[key] = None
33                self.d[key] = nxt
34            else:
35                self.removeKey(self.d[key], key)
36
37    def getMaxKey(self) -> str:
38        if self.dll.prev.count > 0:
39            return next(iter(self.dll.prev.keys))
40        return ''
41
42    def getMinKey(self) -> str:
43        if self.dll.next.count > 0:
44            return next(iter(self.dll.next.keys))
45        return ''
46
47    def addNode(self, prevNode, node: Node, key: str=None) -> Node:
48        nxt = prevNode.next
49        prevNode.next = nxt.prev = node
50        node.next = nxt
51        node.prev = prevNode
52        if key:
53            node.keys[key] = None
54            self.d[key] = node
55        return node
56
57    def removeKey(self, node: Node, key: str) -> None:
58        del node.keys[key]
59        if len(node.keys) == 0:
60            node.prev.next = node.next
61            node.next.prev = node.prev

Solution in Java

1
2java
3import java.util.HashMap;
4
5class Node {
6    int count;
7    HashMap<String, Node> keys = new HashMap<>();
8    Node prev, next;
9
10    Node(int count) {
11        this.count = count;
12    }
13}
14
15public class AllOne {
16    Node head, tail;
17    HashMap<String, Node> keyMap = new HashMap<>();
18
19    public AllOne() {
20        head = new Node(0);
21        tail = new Node(0);
22        head.next = tail;
23        tail.prev = head;
24    }
25
26    public void inc(String key) {
27        if (!keyMap.containsKey(key))
28            insertAfter(head, key);
29        else
30            insertAfter(keyMap.get(key), key);
31    }
32
33    public void dec(String key) {
34        if (keyMap.containsKey(key)) {
35            Node node = keyMap.get(key);
36            if (node.count > 1) {
37                if (node.prev.count != node.count - 1)
38                    addNode(node.prev, node.count - 1);
39                node.prev.keys.put(key, node.prev);
40            }
41            node.keys.remove(key);
42            if (node.keys.isEmpty())
43                remove(node);
44        }
45    }
46
47    public String getMaxKey() {
48        return tail.prev == head ? "" : tail.prev.keys.keySet().iterator().next();
49    }
50
51    public String getMinKey() {
52        return head.next == tail ? "" : head.next.keys.keySet().iterator().next();
53    }
54
55    private void insertAfter(Node node, String key) {
56        if (node.next.count != node.count + 1)
57            addNode(node, node.count + 1);
58        node.next.keys.put(key, node.next);
59        if (!node.keys.isEmpty())
60            node.keys.remove(key);
61        if (node.keys.isEmpty() && node.count > 0)
62            remove(node);
63    }
64
65    private void addNode(Node prevNode, int count) {
66        Node node = new Node(count);
67        node.prev = prevNode;
68        node.next = prevNode.next;
69        node.prev.next = node;
70        node.next.prev = node;
71    }
72
73    private void remove(Node node) {
74        node.prev.next = node.next;
75        node.next.prev = node.prev;
76    }
77}

These solutions utilize a frequently used Data Structure concept - using an Hash Map combined with a Doubly Linked List. This concept can be used to solve similar problems as well. This allows us to perform each operation like searching, getting maximum and minimum value in O(1) time.