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.The functions get
and put
must each run in O(1)
average 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 <= 104
0 <= value <= 105
2 * 105
calls will be made to get
and put
.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.The functions get
and put
must each run in O(1) average time complexity.
This solution uses a hash table and a doubly linked list to achieve O(1) time complexity for both get
and put
operations.
Operations:
get(key)
:
put(key, value)
:
Time Complexity: O(1) for both get
and put
on average. Hash table lookups and doubly linked list operations are O(1) on average.
Space Complexity: O(capacity) to store the cache entries.
class Node:
def __init__(self, key: int = 0, val: int = 0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.size = 0
self.capacity = capacity
self.cache = {} # Hash table
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self.remove_node(node)
self.add_to_head(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.cache:
node = self.cache[key]
self.remove_node(node)
node.val = value
self.add_to_head(node)
else:
node = Node(key, value)
self.cache[key] = node
self.add_to_head(node)
self.size += 1
if self.size > self.capacity:
node = self.tail.prev
self.cache.pop(node.key)
self.remove_node(node)
self.size -= 1
def remove_node(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def add_to_head(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next = node
node.next.prev = node
class Node {
int key, val;
Node prev, next;
Node() {}
Node(int key, int val) {
this.key = key;
this.val = val;
}
}
class LRUCache {
private int size;
private int capacity;
private Node head = new Node();
private Node tail = new Node();
private Map<Integer, Node> cache = new HashMap<>();
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!cache.containsKey(key)) {
return -1;
}
Node node = cache.get(key);
removeNode(node);
addToHead(node);
return node.val;
}
public void put(int key, int value) {
if (cache.containsKey(key)) {
Node node = cache.get(key);
removeNode(node);
node.val = value;
addToHead(node);
} else {
Node node = new Node(key, value);
cache.put(key, node);
addToHead(node);
if (++size > capacity) {
node = tail.prev;
cache.remove(node.key);
removeNode(node);
size--;
}
}
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addToHead(Node node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
}
class LRUCache {
private:
struct Node {
int key, val;
Node* prev;
Node* next;
Node(int key, int val) : key(key), val(val), prev(nullptr), next(nullptr) {}
};
int size;
int capacity;
Node* head;
Node* tail;
unordered_map<int, Node*> cache;
void removeNode(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void addToHead(Node* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}
public:
LRUCache(int capacity) : size(0), capacity(capacity) {
head = new Node(0, 0);
tail = new Node(0, 0);
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (!cache.count(key)) {
return -1;
}
Node* node = cache[key];
removeNode(node);
addToHead(node);
return node->val;
}
void put(int key, int value) {
if (cache.count(key)) {
Node* node = cache[key];
removeNode(node);
node->val = value;
addToHead(node);
} else {
Node* node = new Node(key, value);
cache[key] = node;
addToHead(node);
if (++size > capacity) {
Node* nodeToRemove = tail->prev;
cache.erase(nodeToRemove->key);
removeNode(nodeToRemove);
size--;
}
}
}
};
type Node struct {
key, val int
prev, next *Node
}
type LRUCache struct {
size, capacity int
head, tail *Node
cache map[int]*Node
}
func Constructor(capacity int) LRUCache {
head := &Node{}
tail := &Node{}
head.next = tail
tail.prev = head
return LRUCache{
capacity: capacity,
head: head,
tail: tail,
cache: make(map[int]*Node),
}
}
func (this *LRUCache) Get(key int) int {
if node, ok := this.cache[key]; ok {
this.removeNode(node)
this.addToHead(node)
return node.val
}
return -1
}
func (this *LRUCache) Put(key int, value int) {
if node, ok := this.cache[key]; ok {
this.removeNode(node)
node.val = value
this.addToHead(node)
} else {
node := &Node{key: key, val: value}
this.cache[key] = node
this.addToHead(node)
if this.size++; this.size > this.capacity {
node = this.tail.prev
delete(this.cache, node.key)
this.removeNode(node)
this.size--
}
}
}
func (this *LRUCache) removeNode(node *Node) {
node.prev.next = node.next
node.next.prev = node.prev
}
func (this *LRUCache) addToHead(node *Node) {
node.next = this.head.next
node.prev = this.head
this.head.next = node
node.next.prev = node
}
class Node {
key: number;
val: number;
prev: Node | null;
next: Node | null;
constructor(key: number, val: number) {
this.key = key;
this.val = val;
this.prev = null;
this.next = null;
}
}
class LRUCache {
size: number;
capacity: number;
head: Node;
tail: Node;
cache: Map<number, Node>;
constructor(capacity: number) {
this.size = 0;
this.capacity = capacity;
this.head = new Node(0, 0);
this.tail = new Node(0, 0);
this.head.next = this.tail;
this.tail.prev = this.head;
this.cache = new Map();
}
get(key: number): number {
if (!this.cache.has(key)) {
return -1;
}
const node = this.cache.get(key)!;
this.removeNode(node);
this.addToHead(node);
return node.val;
}
put(key: number, value: number): void {
if (this.cache.has(key)) {
const node = this.cache.get(key)!;
this.removeNode(node);
node.val = value;
this.addToHead(node);
} else {
const node = new Node(key, value);
this.cache.set(key, node);
this.addToHead(node);
if (++this.size > this.capacity) {
const last = this.tail.prev!;
this.cache.delete(last.key);
this.removeNode(last);
this.size--;
}
}
}
removeNode(node: Node): void {
node.prev!.next = node.next;
node.next!.prev = node.prev;
}
addToHead(node: Node): void {
node.next = this.head.next;
node.prev = this.head;
this.head.next!.prev = node;
this.head.next = node;
}
}
use std::collections::HashMap;
use std::rc::Rc;
use std::cell::RefCell;
struct Node {
key: i32,
val: i32,
prev: Option<Rc<RefCell<Node>>>,
next: Option<Rc<RefCell<Node>>>,
}
impl Node {
fn new(key: i32, val: i32) -> Self {
Self { key, val, prev: None, next: None }
}
}
struct LRUCache {
capacity: i32,
map: HashMap<i32, Rc<RefCell<Node>>>,
head: Option<Rc<RefCell<Node>>>,
tail: Option<Rc<RefCell<Node>>>,
}
impl LRUCache {
fn new(capacity: i32) -> Self {
Self { capacity, map: HashMap::new(), head: None, tail: None }
}
fn get(&mut self, key: i32) -> i32 {
if let Some(node) = self.map.get(&key) {
let node = Rc::clone(node);
self.remove(&node);
self.add_to_head(&node);
node.borrow().val
} else {
-1
}
}
fn put(&mut self, key: i32, value: i32) {
if let Some(node) = self.map.get(&key) {
let node = Rc::clone(node);
node.borrow_mut().val = value;
self.remove(&node);
self.add_to_head(&node);
} else {
let node = Rc::new(RefCell::new(Node::new(key, value)));
self.map.insert(key, Rc::clone(&node));
self.add_to_head(&node);
if self.map.len() as i32 > self.capacity {
let last = self.remove_last();
self.map.remove(&last.borrow().key);
}
}
}
fn add_to_head(&mut self, node: &Rc<RefCell<Node>>) {
let mut new_head = Rc::clone(node);
new_head.borrow_mut().next = self.head.clone();
if let Some(head) = self.head.clone() {
head.borrow_mut().prev = Some(Rc::clone(&new_head));
}
self.head = Some(new_head);
if self.tail.is_none() {
self.tail = self.head.clone();
}
}
fn remove(&mut self, node: &Rc<RefCell<Node>>) {
if let Some(prev) = &node.borrow().prev {
prev.borrow_mut().next = node.borrow().next.clone();
} else {
self.head = node.borrow().next.clone();
}
if let Some(next) = &node.borrow().next {
next.borrow_mut().prev = node.borrow().prev.clone();
} else {
self.tail = node.borrow().prev.clone();
}
}
fn remove_last(&mut self) -> Rc<RefCell<Node>> {
let last = self.tail.clone().unwrap();
self.remove(&last);
last
}
}
class Node {
key;
val;
prev;
next;
constructor(key, val) {
this.key = key;
this.val = val;
this.prev = null;
this.next = null;
}
}
class LRUCache {
size;
capacity;
head;
tail;
cache;
constructor(capacity) {
this.size = 0;
this.capacity = capacity;
this.cache = new Map();
this.head = new Node(0, 0);
this.tail = new Node(0, 0);
this.head.next = this.tail;
this.tail.prev = this.head;
}
get(key) {
if (!this.cache.has(key)) return -1;
const node = this.cache.get(key);
this.remove(node);
this.add(node);
return node.val;
}
put(key, value) {
if (this.cache.has(key)) {
const node = this.cache.get(key);
node.val = value;
this.remove(node);
this.add(node);
} else {
const node = new Node(key, value);
this.cache.set(key, node);
this.add(node);
if (this.size === this.capacity) {
this.remove(this.tail.prev);
this.size--;
}
this.size++;
}
}
remove(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
add(node) {
node.next = this.head.next;
node.prev = this.head;
this.head.next.prev = node;
this.head.next = node;
}
}
public class LRUCache {
private int capacity;
private Dictionary<int, Node> cache = new Dictionary<int, Node>();
private Node head = new Node(0, 0);
private Node tail = new Node(0, 0);
private int count = 0;
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int Get(int key) {
if (!cache.ContainsKey(key)) return -1;
var node = cache[key];
remove(node);
add(node);
return node.val;
}
public void Put(int key, int value) {
if (cache.ContainsKey(key)) {
var node = cache[key];
node.val = value;
remove(node);
add(node);
}
else {
var node = new Node(key, value);
cache.Add(key, node);
add(node);
if (count == capacity) {
remove(tail.prev);
count--;
}
count++;
}
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
cache.Remove(node.key);
}
private void add(Node node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
cache.Add(node.key, node);
}
private class Node {
public int key;
public int val;
public Node prev;
public Node next;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
}