Structure Design

Least Recently Used (LRU) Cache

hashmap + queue

  • hashmap: O(1) time find value and pointer
  • queue: maintain the relative order
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class LRUCache {
public:
LRUCache(int capacity) {
capacity_ = capacity;
}

int get(int key) {
if (M.find(key) == M.end()) return -1;

auto p = M[key];
Q.push_back(key);
Q.erase(p.second);
M[key].second = --Q.end();

return p.first;
}

void put(int key, int value) {
if (M.find(key) != M.end()) {
auto p = M[key];
Q.push_back(key);
Q.erase(p.second);
} else {
if (Q.size() == capacity_) {
M.erase(Q.front());
Q.pop_front();
}
Q.push_back(key);
}
M[key] = {value, --Q.end()};
}

private:
list<int> Q;
unordered_map<int, pair<int, list<int>::iterator>> M;
int capacity_;
};

Two Sum

unordered_multiset

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class TwoSum {
unordered_multiset<int> nums;
public:
void add(int number) {
nums.insert(number);
}
bool find(int value) {
for (int i : nums) {
int count = (value == 2 * i ? 1 : 0);
if (nums.count(value - i) > count) {
return true;
}
}
return false;
}
};