The output for this input?


  • 0
    T

    The input is 3, [set(1,1),set(2,2),set(3,3),set(4,4),get(4),get(3),get(2),get(1),set(5,5),get(1),get(2),get(3),get(4),get(5)].

    The size of lru is 3.

    For the first 4 input (set(1,1),set(2,2),set(3,3),set(4,4)),
    the lru is [4,4], [3,3], [2,2], [4,4] is the most recently used, [2,2] is the least recently used.

    For the next 4 input (get(4),get(3),get(2),get(1)),
    the output is 4, 3, 2, -1. And the lru is [2,2], [3,3], [4,4]. [2,2] is the most recently used, [4,4] is the least recently used.

    After we set(5,5), the lru become [5,5], [2,2], [3,3].

    For the last 5 input (get(1),get(2),get(3),get(4),get(5)), we can get -1, 2, 3, -1, 5.

    In all, the output is 4, 3, 2, -1, -1, 2, 3, -1, 5.

    Do I make mistake?

    I also attach my simple LRU code here.
    It always get run time error for this input, I donot know why... Wrong test case ?

    class LRUCache{
    
    public:
    
        LRUCache(int capacity) {
            csz = capacity;
            keyvec.reserve(capacity);
            valvec.reserve(capacity);   
            for(int id=0; id<capacity; id++) {
                keyvec[id] =-1;
                valvec[id] =-1;
            }
        }
        
        int get(int key) {
            int rval = -1;
            int rpos = -1;
            for(int id=0; id<csz; id++) {
                if (key == keyvec[id]) {
                    rval = valvec[id];
                    rpos = id;
                }
            }
            if (rpos>0) {
                int tmpkey = keyvec[rpos];
                int tmpval = valvec[rpos];
                for(int id=rpos; id>0; id--) {
                    keyvec[id] = keyvec[id-1];
                    valvec[id] = valvec[id-1];
                }
                keyvec[0] = tmpkey;
                valvec[0] = tmpval;
            }
            return rval;
        }
        
        void set(int key, int value) {
            int pos = -1;
            for(int id=0; id<csz; id++) {
                if (key == keyvec[id]) {
                    pos = id; break;
                }
            }
            if (pos>0) {
                int tmpkey = key;
                int tmpval = valvec[pos];
                for(int id=pos; id>0; id--) {
                    keyvec[id] = keyvec[id-1];
                    valvec[id] = valvec[id-1];
                }
                keyvec[0] = tmpkey;
                valvec[0] = tmpval;
                return;
            }
            if (pos<0) {
                int ipos = -1;
                for(int id=0; id<csz; id++) {
                    if (-1 == keyvec[id]) {
                        ipos = id; break;
                    }
                }
                if (ipos == -1) {
                    for(int id=csz; id>0; id--) {
                        keyvec[id] = keyvec[id-1];
                        valvec[id] = valvec[id-1];
                    }
                    keyvec[0] = key;
                    valvec[0] = value;
                    return;
                }
                else {
                    for(int id=ipos; id>0; id--) {
                        keyvec[id] = keyvec[id-1];
                        valvec[id] = valvec[id-1];
                    }
                    keyvec[0] = key;
                    valvec[0] = value;
                    return;
                }
            }
            
        }
    
        int csz;
        vector <int> keyvec;
        vector <int> valvec;
    };

  • 1
    S

    It is a right output.

    Both set and get will trigger the element to be the most recently used.


  • 0
    T

    Thanks for your answer.
    I tested my code for LRU problem.
    The system told me that my code generates run time error for this input.
    But I test the code on my machine, its output is right (4, 3, 2, -1, -1, 2, 3, -1, 5) ...


  • 0
    A

    Your output of this test case is right

    but, your code has at least one bug: vector out of range

        void set(int key, int value) {
           // ...
           if (ipos == -1) {
                for(int id=csz; id>0; id--) {  // here, keyvec[csz] may be out of range
                    keyvec[id] = keyvec[id-1];
                    valvec[id] = valvec[id-1];
                }
            // ...
           }

  • 0
    T
    This post is deleted!

Log in to reply
 

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