Getting output limit exceeded


  • 1
    V

    I am getting output limit exceeded error and i have no idea whats wrong with the code. Can any one throw some light on this???

    class LRUCache{
    public:
        int bound,count;
        int capacity;
        map <int,vector<int>> cache;
        LRUCache(int capacity) {
            capacity=capacity;
            bound=0;
            count=0;
        }
        
        int get(int key) {
               if(cache.find(key)==cache.end())
                    return -1;
                vector<int> a {cache[key][0],count++};
                cache[key]= a;
            
        }
        int get_least_count_key()
        {
            int min_key=-1,min=9999;
            for(map<int,vector<int>>::iterator iter = cache.begin(); iter != cache.end(); iter++) {
    
            if(min>iter->second[1])
            {
                min=iter->second[1];
                min_key=iter->first;
            }
            return min_key;
            }
        }
        void set(int key, int value) {
            vector<int> a {value,count++};
            if(bound>capacity)
            {
                //dkey=get_least_count_key();
                int dkey=1;
                cache.erase(dkey);
            }
            cache[key]= a;
            
        }
    };

  • 0
    W

    The get_least_count_key() method requires iterating over the entire map, leading to O(N) time compexity, where N is the capacity.


  • 2

    As mentioned by @wolf, your method get_least_count_key is not efficient enough and will result in Time Limit Exceeded, but that is another problem.

    You are returning min_key inside the for loop. What if you are not in the for loop? Then you are not returning anything, and this is bad because this results in undefined behavior.

    In your specific case, when you are not returning anything C++ just happen to return a random integer value for you, which is some arbitrary large number. This ends up outputting more characters than it should be, resulting in Output Limit Exceeded.


Log in to reply
 

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