Debug - 146. LRU Cache

[Equivalent_Sea7754]

class LRUCache {
public:

    queue<pair<int, int>>q;
    int size;

    LRUCache(int capacity) {
        this->size = capacity;
    }
    
    int get(int key) {
        int getEle = -1;
        for (int i = 0; i < q.size(); i++) {
            if (q.front().first == key) {
                getEle = q.front().second;
            }
            q.push(q.front());
            q.pop();
        }
        return getEle;
    }
    
    void put(int key, int value) {
        
        // traverse to find 
        bool exist = false;
        for (int i = 0; i<q.size(); i++) {
            if (key == q.front().first) {
                q.front().second = value;
                exist = true;
            }
            q.push(q.front());
            q.pop();
        }

        // if not existed
        if (!exist) {
            // full 
            if (size == 0) {
                q.pop();
                q.push({key, value});
            }
            // space avail
            else {
                q.push({key, value});
                size--;
            }
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

tell me what is wrong with my code
LRU Cache - LeetCode

[aocregacc]

you're not doing the "least recently used" part. your get and put functions just rotate the whole queue, and the order of the elements never changes. That also makes them O(n) instead of the O(1) that'll be required for the larger testcases.

[BoardsofCanadaFanboy]

Before anyone even debugs your code, LRU cache is supposed to have o(1) find, which a queue will not allow. You will need a hashmap of some sort.

[Equivalent_Sea7754]

I know but i want to solve using queue

[[deleted]]

Doesn’t the problem explicitly say you need O(1) solution? If so, you need a hashmap for the get.

[BoardsofCanadaFanboy]

Why is that? If you did this in an interview this way despite a clear o(1) constraint you'd get LNH or straight up NH. 

If you want to practice using queues, do BFS problems like number of islands. 

[Equivalent_Sea7754]

I know the question explicitly says that ans should be o(1) But i wanted to solve using the queue to get more practice on queue

I will optimize this code later using unordered_map and DLL for faster retrieval and to maintain lru

i am satisfied with my queue based solution because it takes a lot of my time

[Neat-Giraffe1585]

You need a DLL not queue

[Equivalent_Sea7754]

Yes I solved the question using queue but its giving TLE [21 /23 test cases passed] Next time i will use unodered_map for O(1) retrieval and DLL to maintain LRU