How to design the data structure to avoid TLE?

Question

Which algorithm can get the best time complexcity? And how much?

Comments

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

---

ok thx for your reminding :)

Answer 1

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.

Comments

It works for me!

Answer 2

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);
    }

};

Comments

Please add comments in your code and tell your thought in some words. Thx!

Answer 3

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;
};

Comments

Please add comments in your code and tell your algorithm.

Answer 4

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.

Answer 5

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) {
        head = nullptr;
        this->capacity = capacity;
        count = 0;
    }

    int get(int key) {
        if (C.find(key) != C.end()) {
            CacheItem *ci = C[key];
            moveToHead(ci);
            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) {
                CacheItem *vi = head->prev;
                vi->prev->next = head;
                head->prev = vi->prev;
                C.erase(vi->key);
                if (vi == head)
                    head = nullptr;
                delete vi;
            } else
                count++;

            if (head) {
                ci->next = head;
                ci->prev = head->prev;
                head->prev->next = ci;
                head->prev = ci;
            }
            head = ci;
        } else { // update
            CacheItem *ci = C[key];
            moveToHead(ci);
            ci->val = value;
        }
    }

private:
    void moveToHead(CacheItem *ci) {
        if (ci == nullptr || ci == head)
            return;

        ci->prev->next = ci->next;
        ci->next->prev = ci->prev;
        if (head) {
            ci->prev = head->prev;
            ci->next = head;
            head->prev->next = ci;
            head->prev = ci;
        }

        head = ci;
    }

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

Comments

So how long was your running time?

---

Please add comments in your code and tell your algorithm.

Answer 6

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.

Answer 7

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;
ListNode *head;

LRUCache(int capacity) {
    this->capacity = capacity;
    //maintain a double linked list
    head = new ListNode(0,0);
    head->front = head;
    head->next = head;
}

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;
    //shift up to the head
    node->next = head->next;
    node->front = head;
    head->next->front = node;
    head->next = node;
}

//delete the node in the end of list
//also delete it from hash table
void pop()
{
    int delkey = head->front->key;
    ListNode *delNode = head->front;
    head->front->front->next = head;
    head->front = head->front->front;
    hmap.erase(delkey);
    delete delNode;
}

//push a new node to the end of list
void push(ListNode *node)
{
    node->next = head->next;
    node->front = head;
    head->next->front = node;
    head->next = 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;
        //if the node is not in head, shift it to head
        if(head->next != hmap[key]){
            shiftup(hmap[key]);
        }
    }
    return value;
}

void set(int key, int value) {
    //this key alreay exists
    if(hmap.find(key) != hmap.end()){
        //adjust its value and position
        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);
}
};