• Three similar O(1) design questions on Leetcode:
Leetcode432. All O(1) Data Structure

Leetcode146. LRU

Leetcode460. LFU

``````class Node{
public:
unordered_set<string> st;
int val;
Node* pre;
Node* next;
Node(int val, Node* pre, Node* next){
this->val = val;
this->pre = pre;
this->next = next;
}
};
``````

``````class AllOne {
unordered_map<string, int> keyMap;
unordered_map<int, Node*> valueMap;
Node* head = new Node(0, nullptr, nullptr);
public:
/** Initialize your data structure here. */
AllOne() {
}
void deleteNode(Node* node){
if(node == nullptr) return;
if(node->pre == nullptr){
node = node->next;
}else{
node->pre->next = node->next;
}
if(node->next != nullptr){
node->next->pre = node->pre;
}
}
``````

``````/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
void inc(string key) {
if(keyMap.find(key) == keyMap.end()){
keyMap.insert({key,0});
}
//increase
int freq = keyMap[key];
Node* node = valueMap[freq];
keyMap[key]++;
freq++;
if(node->next == nullptr){
Node* tmp = new Node(freq, node, nullptr);
tmp->st.insert(key);
node->next = tmp;
valueMap[freq] = tmp;
}else if(node->next->val > freq){
Node* tmp = new Node(freq, node, node->next);
tmp->st.insert(key);
node->next->pre = tmp;
node->next = tmp;
valueMap[freq] = tmp;
}else{
node->next->st.insert(key);
}
if(tail->val < freq) tail = node->next;
node->st.erase(key);
if(node->val != 0 && node->st.empty()){
valueMap.erase(node->val);
deleteNode(node);
}
``````

``````/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
void dec(string key) {
if(keyMap.find(key) == keyMap.end()) return;
//decrease:
int freq = keyMap[key];
Node* node = valueMap[freq];
if(freq == 1){
keyMap.erase(key);
}else{
keyMap[key]--;
freq--;
if(node->pre->val < freq){
Node* tmp = new Node(freq, node->pre, node);
tmp->st.insert(key);
node->pre->next = tmp;
node->pre = tmp;
valueMap[freq] = tmp;
}else{
node->pre->st.insert(key);
}
}
node->st.erase(key);
if(node->val != 0 && node->st.empty()){
if(node == tail){tail = node->pre;}
valueMap.erase(node->val);
deleteNode(node);
}
}
``````

``````/** Returns one of the keys with maximal value. */
string getMaxKey() {
if(tail->val > 0){return *(tail->st.begin());}
return "";
}

/** Returns one of the keys with Minimal value. */
string getMinKey() {
return "";
}
};
``````

/**

• Your AllOne object will be instantiated and called as such:
• AllOne obj = new AllOne();
• obj.inc(key);
• obj.dec(key);
• string param_3 = obj.getMaxKey();
• string param_4 = obj.getMinKey();
*/

• Two functions: Increase and Decrease:

``````    void increase(string key){
int freq = keyMap[key];
Node* node = valueMap[freq];
keyMap[key]++;
freq++;
if(node->next == nullptr){
Node* tmp = new Node(freq, node, nullptr);
tmp->st.insert(key);
node->next = tmp;
valueMap[freq] = tmp;
}else if(node->next->val > freq){
Node* tmp = new Node(freq, node, node->next);
tmp->st.insert(key);
node->next->pre = tmp;
node->next = tmp;
valueMap[freq] = tmp;
}else{
node->next->st.insert(key);
}
if(tail->val < freq) tail = node->next;
node->st.erase(key);
if(node->val != 0 && node->st.empty()){
valueMap.erase(node->val);
deleteNode(node);
}
``````

``````void decrease(string key){
int freq = keyMap[key];
Node* node = valueMap[freq];
if(freq == 1){
keyMap.erase(key);
}else{
keyMap[key]--;
freq--;
if(node->pre->val < freq){
Node* tmp = new Node(freq, node->pre, node);
tmp->st.insert(key);
node->pre->next = tmp;
node->pre = tmp;
valueMap[freq] = tmp;
}else{
node->pre->st.insert(key);
}
}
node->st.erase(key);
if(node->val != 0 && node->st.empty()){
if(node == tail){tail = node->pre;}
valueMap.erase(node->val);
deleteNode(node);
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.