How to design the data structure to avoid TLE?


  • 0
    F

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


  • 0
    D

    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.


  • 8
    Y

    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.


  • 0
    J

    It works for me!


  • 0
    L

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

  • 0
    D

    So how long was your running time?


  • 2
    J
    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;
    };

  • 0
    S

    Please add comments in your code and tell your algorithm.


  • 0
    S

    Please add comments in your code and tell your algorithm.


  • 0
    S

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


  • 4
    K

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

  • 0
    S

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


  • 0
    U

    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.


  • 0
    F

    ok thx for your reminding :)


  • 0
    C

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

Log in to reply
 

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