LeetCode - LRU Cache

쿠팡에서 설계 문제로 나온 LRU Cache. 핵심 포인트는 HashMap과 LinkedList를 동시에 유지하는 것.

 

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

Follow up:
Could you do get and put in O(1) time complexity?

 

Example 1:

Input ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output [null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation LRUCache lRUCache = new LRUCache(2);

lRUCache.put(1, 1); // cache is {1=1}

lRUCache.put(2, 2); // cache is {1=1, 2=2}

lRUCache.get(1); // return 1

lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}

lRUCache.get(2); // returns -1 (not found)

lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}

lRUCache.get(1); // return -1 (not found)

lRUCache.get(3); // return 3 lRUCache.get(4); // return 4

 

Constraints:

• 1 <= capacity <= 3000
• 0 <= key <= 3000
• 0 <= value <= 104
• At most 3 * 104 calls will be made to get and put.

class LRUCache(val capacity: Int) {
    val list = LinkedList<Int>()
    val map = mutableMapOf<Int, Int>()

    fun get(key: Int): Int {
        map[key]?.let {
            list.remove(key)
            list.addLast(key)
            return it
        }
        return -1
    }

    fun put(key: Int, value: Int) {
        //있으면 삭제하고 뒤에다 추가
        val index = list.indexOf(key)
        if(index != -1) {
            list.remove(list[index])
        } else {
            //없을 경우 사이즈가 초과하는지 확인후에 삭제 
            if(list.size >= capacity) {
                map.remove(list[0])
                list.removeFirst()
            }
        }
        list.addLast(key)
        map[key] = value
    }

}

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */