Skip to content

Problem

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.

Constraints:

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

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|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

Solve

Using build-in

Using built-in class OrderedDict of python

from collections import OrderedDict

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        if key in self.cache:
            self.cache.move_to_end(key)
            return self.cache[key]
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        else:
            if len(self.cache) >= self.capacity:
                self.cache.popitem(last=False)
        self.cache[key] = value

Reimplementation - Double Linked list

This is a hard task, and require a lot of knowledge from a person. Here is a double linked list version where

  • Adding a node is pushing it in to end of the linked list, which cost O(1).
  • Popping a node will need 
    class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.count = 0
        self.head = None
        self.tail = None
        self.hashmap = {}

    def delete_node(self, node):
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next

        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev

    def add_to_front(self, node):
        node.next = self.head
        node.prev = None

        if self.head:
            self.head.prev = node

        self.head = node

        if not self.tail:
            self.tail = node

    def update_lru_cache(self, key, value):
        node = self.hashmap[key]

        if node:
            node.value = value
            self.delete_node(node)
            self.add_to_front(node)

    def get(self, key: int) -> int:
        node = self.hashmap.get(key)

        if node:
            self.delete_node(node)
            self.add_to_front(node)
            return node.value
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.hashmap:
            self.update_lru_cache(key, value)
        else:
            if self.count == self.capacity:
                self.hashmap.pop(self.tail.key)
                self.delete_node(self.tail)
                self.count -= 1

            new_node = Node(key, value)
            self.hashmap[key] = new_node
            self.add_to_front(new_node)
            self.count += 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LOOKUP_SIZE (unsigned long)1e4

typedef struct cache_node {
    int key;
    int val;
    struct cache_node* next;
    struct cache_node* prev;
} cache_node;

typedef struct {
    cache_node* cache;
    cache_node head;

    int capacity;
    int size;
    cache_node* lookup[MAX_LOOKUP_SIZE];
} LRUCache;

// Function to create a new cache node
cache_node* createNode(int key, int value) {
    cache_node* newNode = (cache_node*)malloc(sizeof(cache_node));
    newNode->key = key;
    newNode->val = value;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

// Function to insert a node at the tail of the doubly linked list
void insertAtTail(cache_node* head, cache_node* node) {
    cache_node* tail = head->prev;
    node->next = tail->next;
    node->prev = tail;
    tail->next = node;
    node->next->prev = node;
}

// Function to remove a node from the doubly linked list
void removeNode(cache_node* node) {
    node->next->prev = node->prev;
    node->prev->next = node->next;
}

// Function to move a node to the tail of the doubly linked list (mark as least recently used)
void makeLRU(cache_node* head, cache_node* node) {
    removeNode(node);
    insertAtTail(head, node);
}

LRUCache* lRUCacheCreate(int capacity) {
    LRUCache* lru = (LRUCache*)malloc(sizeof(LRUCache));
    memset(lru->lookup, 0, sizeof(lru->lookup));
    lru->cache = (cache_node*)malloc(sizeof(cache_node) * capacity);
    lru->size = 0;
    lru->capacity = capacity;
    lru->head.next = lru->head.prev = &lru->head;
    return lru;
}

int lRUCacheGet(LRUCache* obj, int key) {
    cache_node* found = obj->lookup[key];
    if (!found) {
        return -1;
    }
    makeLRU(&obj->head, found);
    return found->val;
}

void lRUCachePut(LRUCache* obj, int key, int value) {
    cache_node* found = obj->lookup[key];
    if (found) {
        found->val = value;
        makeLRU(&obj->head, found);
        return;
    }

    cache_node* head = obj->head.next;
    cache_node* tmp;
    /* Evict case */
    if (obj->capacity == obj->size) {
        obj->lookup[head->key] = NULL;
        removeNode(head);
        tmp = head;
    } else {
        tmp = &obj->cache[obj->size++];
    }
    tmp->key = key;
    tmp->val = value;
    obj->lookup[key] = tmp;
    insertAtTail(&obj->head, tmp);
}

void lRUCacheFree(LRUCache* obj) {
    free(obj->cache);
    free(obj);
}

For compiler file and testing, you want to add main function

int main() {
    LRUCache* cache = lRUCacheCreate(2);

    lRUCachePut(cache, 1, 1);
    lRUCachePut(cache, 2, 2);

    printf("%d\n", lRUCacheGet(cache, 1)); // Output: 1

    lRUCachePut(cache, 3, 3);

    printf("%d\n", lRUCacheGet(cache, 2)); // Output: -1

    lRUCachePut(cache, 4, 4);

    printf("%d\n", lRUCacheGet(cache, 1)); // Output: -1
    printf("%d\n", lRUCacheGet(cache, 3)); // Output: 3
    printf("%d\n", lRUCacheGet(cache, 4)); // Output: 4

    lRUCacheFree(cache);

    return 0;
}

Last update : October 13, 2023
Created : August 16, 2023