Contents
LRU Cache
Least Recently Used cache using hash map + doubly linked list.
class LRUCache {
private:
int capacity_;
list<int> keyList_;
unordered_map<int, pair<int, list<int>::iterator>> hashMap_;
void insert(int key, int value) {
keyList_.push_back(key);
hashMap_[key] = make_pair(value, --keyList_.end());
}
public:
LRUCache(int capacity) : capacity_(capacity) {
}
int get(int key) {
auto it = hashMap_.find(key);
if(it != hashMap_.end()) {
keyList_.splice(keyList_.end(), keyList_, it->second.second);
return it->second.first;
}
return -1;
}
void put(int key, int value) {
if(get(key) != -1) {
hashMap_[key].first = value;
return;
}
if(hashMap_.size() < capacity_) {
insert(key, value);
} else {
int removeKey = keyList_.front();
keyList_.pop_front();
hashMap_.erase(removeKey);
insert(key, value);
}
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
Thread-Safe LRU Cache
Thread-safe version using mutex for concurrent access.
#include <mutex>
#include <shared_mutex>
class ThreadSafeLRUCache {
private:
int capacity_;
list<int> keyList_;
unordered_map<int, pair<int, list<int>::iterator>> hashMap_;
mutable shared_mutex mtx_; // Use shared_mutex for read-write lock
void insert(int key, int value) {
keyList_.push_back(key);
hashMap_[key] = make_pair(value, --keyList_.end());
}
bool exists(int key) const {
return hashMap_.find(key) != hashMap_.end();
}
public:
ThreadSafeLRUCache(int capacity) : capacity_(capacity) {
}
int get(int key) {
unique_lock<shared_mutex> lock(mtx_); // Exclusive lock for read+modify
auto it = hashMap_.find(key);
if(it != hashMap_.end()) {
keyList_.splice(keyList_.end(), keyList_, it->second.second);
return it->second.first;
}
return -1;
}
void put(int key, int value) {
unique_lock<shared_mutex> lock(mtx_); // Exclusive lock for write
if(exists(key)) {
hashMap_[key].first = value;
keyList_.splice(keyList_.end(), keyList_, hashMap_[key].second);
return;
}
if(hashMap_.size() < capacity_) {
insert(key, value);
} else {
int removeKey = keyList_.front();
keyList_.pop_front();
hashMap_.erase(removeKey);
insert(key, value);
}
}
size_t size() const {
shared_lock<shared_mutex> lock(mtx_);
return hashMap_.size();
}
};
// Example usage:
// ThreadSafeLRUCache cache(2);
// cache.put(1, 1);
// cache.put(2, 2);
// int val = cache.get(1); // returns 1
// cache.put(3, 3); // evicts key 2
LFU Cache
Least Frequently Used cache.
class LFUCache {
int capacity, minFreq;
unordered_map<int, pair<int, int>> keyValFreq; // key -> {value, frequency}
unordered_map<int, list<int>> freqKeys; // frequency -> list of keys
unordered_map<int, list<int>::iterator> keyIter; // key -> iterator in freqKeys list
void updateFreq(int key) {
int freq = keyValFreq[key].second;
freqKeys[freq].erase(keyIter[key]);
if (freqKeys[freq].empty() && freq == minFreq) {
minFreq++;
}
freq++;
keyValFreq[key].second = freq;
freqKeys[freq].push_back(key);
keyIter[key] = --freqKeys[freq].end();
}
public:
LFUCache(int capacity) : capacity(capacity), minFreq(0) {}
int get(int key) {
if (keyValFreq.find(key) == keyValFreq.end()) return -1;
updateFreq(key);
return keyValFreq[key].first;
}
void put(int key, int value) {
if (capacity == 0) return;
if (keyValFreq.find(key) != keyValFreq.end()) {
keyValFreq[key].first = value;
updateFreq(key);
} else {
if (keyValFreq.size() >= capacity) {
int evictKey = freqKeys[minFreq].front();
freqKeys[minFreq].pop_front();
keyValFreq.erase(evictKey);
keyIter.erase(evictKey);
}
keyValFreq[key] = {value, 1};
freqKeys[1].push_back(key);
keyIter[key] = --freqKeys[1].end();
minFreq = 1;
}
}
};
Trie
Prefix tree for efficient string operations.
class Trie {
struct TrieNode {
vector<TrieNode*> children;
bool isEnd;
TrieNode() : children(26, nullptr), isEnd(false) {}
};
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* node = root;
for (char c : word) {
int idx = c - 'a';
if (!node->children[idx]) {
node->children[idx] = new TrieNode();
}
node = node->children[idx];
}
node->isEnd = true;
}
bool search(string word) {
TrieNode* node = root;
for (char c : word) {
int idx = c - 'a';
if (!node->children[idx]) return false;
node = node->children[idx];
}
return node->isEnd;
}
bool startsWith(string prefix) {
TrieNode* node = root;
for (char c : prefix) {
int idx = c - 'a';
if (!node->children[idx]) return false;
node = node->children[idx];
}
return true;
}
};
| ID |
Title |
Link |
Solution |
| 208 |
Implement Trie (Prefix Tree) |
Link |
- |
| 211 |
Design Add and Search Words Data Structure |
Link |
- |
Time-based Key-Value Store
class TimeMap {
unordered_map<string, vector<pair<int, string>>> store;
public:
TimeMap() {}
void set(string key, string value, int timestamp) {
store[key].push_back({timestamp, value});
}
string get(string key, int timestamp) {
if (store.find(key) == store.end()) return "";
auto& pairs = store[key];
int left = 0, right = pairs.size() - 1;
string result = "";
while (left <= right) {
int mid = left + (right - left) / 2;
if (pairs[mid].first <= timestamp) {
result = pairs[mid].second;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
};
| ID |
Title |
Link |
Solution |
| 981 |
Time Based Key-Value Store |
Link |
- |
Design Patterns
Random Pick with Weight
class Solution {
vector<int> prefixSum;
public:
Solution(vector<int>& w) {
prefixSum.push_back(0);
for (int weight : w) {
prefixSum.push_back(prefixSum.back() + weight);
}
}
int pickIndex() {
int target = rand() % prefixSum.back();
return upper_bound(prefixSum.begin(), prefixSum.end(), target) - prefixSum.begin() - 1;
}
};
Design Tic-Tac-Toe
class TicTacToe {
vector<int> rows, cols;
int diagonal, antiDiagonal;
int n;
public:
TicTacToe(int n) : n(n), rows(n, 0), cols(n, 0), diagonal(0), antiDiagonal(0) {}
int move(int row, int col, int player) {
int add = (player == 1) ? 1 : -1;
rows[row] += add;
cols[col] += add;
if (row == col) diagonal += add;
if (row + col == n - 1) antiDiagonal += add;
if (abs(rows[row]) == n || abs(cols[col]) == n ||
abs(diagonal) == n || abs(antiDiagonal) == n) {
return player;
}
return 0;
}
};