# How to design the data structure to avoid TLE?

• My algorithm uses a doubly linked list to store the order of using, and a map to store the mapping from key to list node. The time complexity is O(logn) for both get and set.

As to me, it's hard to write a bug free code to maintain a doubly linked list without debug tools.

• Use std::list for doubly linked list, e.g. [(key1, value1), (key2, value2)...].
Use unordered_map for hash, e.g. [(key1, ListIterator1), (key2, ListIterator2), ...].
So both get and set operations can be done in constant time.

• It works for me!

• I made my own doubly linked list. The std::list is a better solution.

``````struct CacheItem {
CacheItem *prev;
CacheItem *next;
int key;
int val;

CacheItem(int key, int val) : key(key), val(val) {
prev = next = this;
}
};

class LRUCache {
public:
LRUCache(int capacity) {
this->capacity = capacity;
count = 0;
}

int get(int key) {
if (C.find(key) != C.end()) {
CacheItem *ci = C[key];
return ci->val;
} else
return -1;
}

void set(int key, int value) {
if (C.find(key) == C.end()) {  // insert
CacheItem *ci = new CacheItem(key, value);
C[key] = ci;

// find the victim to replace
if (count == capacity) {
C.erase(vi->key);
delete vi;
} else
count++;

}
} else { // update
CacheItem *ci = C[key];
ci->val = value;
}
}

private:
if (ci == nullptr || ci == head)
return;

ci->prev->next = ci->next;
ci->next->prev = ci->prev;
}

}

private:
unordered_map<int, CacheItem *> C;
int capacity;
int count;
};
``````

• So how long was your running time?

• ``````class LRUCache{
public:
LRUCache(int capacity) {
this->capacity = capacity;
}

int get(int key) {
auto it = item_map.find(key);
if (it != item_map.end()) {
item_list.splice(item_list.begin(), item_list, it->second);
return item_list.front().second;
}
else {
return -1;
}
}

void set(int key, int value) {
auto it = item_map.find(key);
if (it != item_map.end()) {
item_list.splice(item_list.begin(), item_list, it->second);
item_list.front().second = value;
}
else {
if (item_list.size() == capacity) {
item_map.erase(item_list.back().first);
item_list.pop_back();
}
item_list.push_front(make_pair(key, value));
item_map[key] = item_list.begin();
}
}
private:
list<pair<int, int> > item_list;
unordered_map<int, list<pair<int, int> >::iterator> item_map;
int capacity;
};``````

• Could you please tell your solution then ask for more elegant one rather than this simple question next time? Thx!

• use std::list.

``````class LRUCache{
list<pair<int,int> > _cache;
unordered_map<int, list<pair<int,int> > :: iterator > _map;
int _size;
public:
LRUCache(int capacity):_size(capacity) {}
int get(int key) {
auto itor = _map.find(key); //look up bring the element to front.
if(itor == _map.end()) return -1;
movetofront(itor->second);
return _cache.front().second;
}

void set(int key, int value) {
if(_map.find(key) != _map.end()){ // key exists, update value, bring to front.
*_map[key] = make_pair(key,value);
movetofront(_map[key]);
}else{                                           //key doesn't exist,
if(_map.size() == _size){         // over-write the last node, bring to front.
_map.erase(_cache.rbegin()->first);
*_cache.rbegin() = make_pair(key,value);
movetofront(--_cache.end());
}else
_cache.emplace(_cache.begin(), key, value); // insert without copying to front.
_map[key] = _cache.begin(); // update key value.
}
}

void movetofront(list<pair<int,int> > :: iterator& it){
if(it != _cache.begin())
_cache.splice(_cache.begin(), _cache, it);
}

};``````

• The key to avoiding TLE is that when set(key, value) is called, you must check whether key is already in cache. Otherwise, there will be 2 same keys in discarding queue, which can lead to fatal problem.

• ok thx for your reminding :)

• An implementation with hash table and a double linked list

//get(int key): O(1) through hash table to List Node, then return value
//when get a value existed int hash table, adjust List to make the node in the top of list O(1) time
//set(int key, int value): check whether key is in hash table, if so, adjust its value, and shiftup
//if it is not in hash table, size of List is smaller than capacity, then insert it in List and hash table
//If size of list is equal to capacity, delete one node in the end, then add new node in the beginning.

``````class LRUCache{
public:
struct ListNode{
int key;
int value;
ListNode *front;
ListNode *next;
ListNode(int k, int val)
:key(k), value(val), front(nullptr), next(nullptr)
{}
};

int capacity;
//<key, pointer in List>
unordered_map<int, ListNode*> hmap;

LRUCache(int capacity) {
this->capacity = capacity;
}

bool empty()
{
return hmap.size()==0;
}

bool full()
{
return hmap.size()==capacity;
}

//when get or set an existing node, shift this node up to the head of list
void shiftup(ListNode *node)
{
//delete it from middle
node->front->next = node->next;
node->next->front = node->front;
}

//delete the node in the end of list
//also delete it from hash table
void pop()
{
hmap.erase(delkey);
delete delNode;
}

//push a new node to the end of list
void push(ListNode *node)
{
hmap.insert(make_pair(node->key, node));
}

int get(int key) {
//not exist
int value = -1;
if(hmap.find(key) != hmap.end()){
value = hmap[key]->value;
shiftup(hmap[key]);
}
}
return value;
}

void set(int key, int value) {
//this key alreay exists
if(hmap.find(key) != hmap.end()){
ListNode *node = hmap[key];
node->value = value;
shiftup(node);
return;
}

//if full, pop one node out
if(full()){
pop();
}

//push new node to the list
ListNode *node = new ListNode(key, value);
push(node);
}
};``````

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