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)
*/