Soyo

Day 24 of 30 days Leetcode challenge - LRU Cache

LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Solution

Use double linked list with general OOP programming


class LRUCache {

    private var data: [Int: Node] = [:]
    private var queue: Queue = Queue()
    private var count: Int = 0
    private let capacity: Int
    
    init(_ capacity: Int) {
        self.capacity = capacity
    }
    
    func get(_ key: Int) -> Int {
        guard let node = data[key] else { return -1 }
        queue.moveToFront(node)
        return node.value
    }
    
    func put(_ key: Int, _ value: Int) {
        if capacity == 0 {
            return
        }
        let newNode = Node(value, key)
        
        if let node = data[key] {
            queue.drop(node)
            data[key] = nil
            count -= 1
        }
        
        if count == capacity {
            let node = queue.pop()
            print(node?.key)
            data[node!.key] = nil
            count -= 1
        }
        
        queue.insert(newNode)
        data[key] = newNode
        count += 1
    }
}

class Node : NSObject {
    var next: Node?
    var prev: Node?
    var value: Int
    var key: Int
    
    init(_ val: Int, _ key: Int) {
        self.value = val
        self.key = key
        self.next = nil
        self.prev = nil
    }
}

class Queue {
    var front: Node?
    var rear: Node?
    
    func insert(_ node: Node?) {
        if front == nil {
            front = node
            rear = node
            return
        }
        node?.next = front
        front?.prev = node
        front = node
    }
    
    func drop(_ node: Node?) {
        if rear == front {
            front = nil
            rear = nil
            return
        }
        if rear == node {
            rear = rear?.prev
            rear?.next = nil
            return
        }
        if front == node {
            front = node?.next
            front?.prev = nil
            return
        }
        
        node?.prev?.next = node?.next
        node?.next?.prev = node?.prev
    }
    
    func pop() -> Node? {
        var temp = rear
        if front == rear {
            front = nil
            rear = nil
        }else {
            rear = rear?.prev
            rear?.next = nil
        }
        return temp
    }
    
    func moveToFront(_ node: Node?) {
        drop(node)
        insert(node)
    }
}

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

Comments