[JAVA] Time Limit Exceeded

Question

Got time limit exceeded and did not know why. As shown in the code, I want to use Hashmap to store the key-value pairs and use Arraylist to store the keys in the LRU order.

import java.util.*;

public class LRUCache {

    HashMap<Integer, Integer> cacheMap; // key, value

    ArrayList<Integer> cacheList; // key

    int capacity;

public LRUCache(int capacity) {
    this.cacheMap = new HashMap<Integer, Integer>();
    this.cacheList = new ArrayList<Integer>();
    this.capacity = capacity;
}

public int get(int key) {
    if (this.cacheMap.containsKey(key)) {
        this.cacheList.remove(new Integer(key));
        this.cacheList.add(key);
        return this.cacheMap.get(key);
    }
    return -1;
}

public void set(int key, int value) {
    if (!this.cacheMap.containsKey(key)) {
        if (this.capacity == this.cacheList.size()) {
            this.cacheMap.remove(this.cacheList.get(0));
            this.cacheList.remove(0);
        }
        this.cacheList.add(key);
        this.cacheMap.put(key, value);
    } else {
        this.cacheMap.remove(key);
        this.cacheMap.put(key, value);
        this.cacheList.remove(new Integer(key));
        this.cacheList.add(key);
    }
}

}

Answer 1

The remove() method on an ArrayList takes O(n) time. You can solve LRU cache in a way such that every operation takes O(1) time.

Answer 2

Do not meet 'least' condition. Assume the capacity is 3. Like keys input: set(2,1), set(2,1), set(1,1), set(3,1), then the cache is full. When set(5,1), your code replace the 2 with the 5. Obviously the key 1 should be replaced by 5, instead of 2.