HàPhan 河

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.

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.put(4, 4);    // evicts key 1
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)
*/
``````