Why am i getting Time Limit Exceeded error


  • 0
    N

    Why am I getting a time limit exceeded error? Should I implement my own Doubly Linked List?

    struct Node {
        int key_;
        int value_;
        
        inline Node(int key, int val) 
           : key_(key)
           , value_(val) {}
    };
     
    class LRUCache{
    public:
        LRUCache(int capacity) 
                : capacity_(capacity) {  }
        
        int get(int key) {
            unordered_map<int,Node*>::iterator it = cache_.find(key);
            if(it == cache_.end()) {
                return -1;
            } else {
                if(it->second != list_.front()) {
                    list_.remove(it->second);
                    list_.push_front(it->second);
                }
                return it->second->value_;
            }       
        }
        
        void set(int key, int value) {
            unordered_map<int,Node*>::iterator it = cache_.find(key);
            if(it == cache_.end()) {
                Node *tmp =  new Node(key,value);
                list_.push_front(tmp);
                cache_[key] = tmp;
            } else {
                //update node and move to front
                it->second->value_ = value;
                if(it->second != list_.front()) {
                    list_.remove(it->second);
                    list_.push_front(it->second);
                }
            }
            
            if(list_.size() > capacity_) {
                Node* last = list_.back();
                list_.pop_back();
                unordered_map<int,Node*>::iterator it = cache_.find(last->key_);
                if(it != cache_.end()) {
                    cache_.erase(it);
                }
            }        
        }
    private:
        int capacity_;
        unordered_map<int, Node*> cache_;
        std::list<Node*> list_;
        
    };

  • 0
    S

    std::list + std::unordered_map is fast enough for this problem, but you need to be careful about what methods you use. Note that list::remove(const value_type&) is an O(n) operation, therefore, both your get and set functions are running in O(n) time in the worst case. The whole point to use a map is two fold: 1. check if a key already exists in the cache in O(1), and 2. find its corresponding node in the list in O(1). You only did (1), but not (2). In order to find the node in O(1), the value of the map must be some kind of reference/pointer to "the node in the list".

    "This is what I have already done". You may argue. Since the list is defined as list<Node* >, and the value of the map is of type Node*, so how come the value of the map is not referring to the node in the list? Well, the fact is that you only make it APPEAR so. Because, regardless of what the value type of the list is, it is going to be stored as a member in a wrapper class in the internal representation of std::list. The value of the map should be a reference to that wrapper class (for instance, a std::list<Node* >::iterator), not the Node* you created by yourself.


  • 0
    Y

    Your code have some problems.Your logic is wrong. In the function of void set(int key, int value). If you do not find the key, you should consider two situation: 1) list_.size()<capacity_;2)list_.size()>=capacity_.(Not list_.size() > capacity_). In 1), you only need to add the <key,value> to the cache and list. As for 2), you should delete a <key,value> first, then add new <key,value> to the cache and list.


  • 0
    S

    Well, his logic is not really wrong, but could use some improvements. What we do in set() are basically two things: (1) add A, (2) delete B(if applicable). In theory, (1) and (2) can be performed in either order. However, doing it in OP's way (1 first, then 2) would result in a maximum of (capacity + 1) nodes existing at the same time. Although this may be okay for this problem, it may cause trouble for a system where 'capacity' is a strict upper bound.


  • 0
    Y

    Oh!Yes, you are right. His logic is okay in this problem. Thank you for telling me!


Log in to reply
 

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