# The output for this input?

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

• It is a right output.

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

• 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) ...

• 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];
}
// ...
}``````

• This post is deleted!

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