LRU Cache - Practice Coding Problems

LRU Cache - 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.

Input & Output

Example 1 — Basic LRU Operations

$ Input: capacity = 2, operations = [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["put",4,4],["get",1],["get",3],["get",4]]

› Output: [null,null,1,null,-1,null,-1,3,4]

💡 Note: Cache capacity is 2. put(1,1), put(2,2) fills cache. get(1) returns 1. put(3,3) evicts key 2. get(2) returns -1 (evicted). put(4,4) evicts key 1. get(1) returns -1, get(3) returns 3, get(4) returns 4.

Example 2 — Single Capacity

$ Input: capacity = 1, operations = [["put",2,1],["get",2],["put",3,2],["get",2],["get",3]]

› Output: [null,1,null,-1,2]

💡 Note: With capacity 1, each put operation evicts the previous key. put(2,1), get(2) returns 1, put(3,2) evicts key 2, get(2) returns -1, get(3) returns 2.

Example 3 — Update Existing Key

$ Input: capacity = 2, operations = [["put",1,1],["put",2,2],["put",1,10],["get",1],["get",2]]

› Output: [null,null,null,10,2]

💡 Note: put(1,1), put(2,2), then put(1,10) updates existing key 1 to value 10 and moves it to most recent. get(1) returns 10, get(2) returns 2.

Constraints

1 ≤ capacity ≤ 3000
0 ≤ key ≤ 10⁴
0 ≤ value ≤ 10⁵
At most 2 × 10⁴ calls will be made to get and put

Visualization

Tap to expand

Understanding the Visualization

Input

Cache capacity and sequence of get/put operations

Process

Track usage order and evict LRU items when capacity exceeded

Output

Results of get operations and successful put operations

Key Takeaway

🎯 Key Insight: Combine hash map for fast lookup with doubly linked list for efficient LRU ordering and eviction

Asked in

G Google 85 A Amazon 72 M Microsoft 68 F Facebook 61 🍎 Apple 45

The key insight is combining a hash map for O(1) key lookup with a doubly linked list for O(1) insertion/deletion to maintain LRU order. The optimal approach uses hash map + doubly linked list achieving O(1) time complexity for both get and put operations with O(capacity) space.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map + Doubly Linked List	O(1)	O(capacity)	Combine hash map for O(1) lookup with doubly linked list for O(1) insertion/deletion
Brute Force with Array	O(n)	O(capacity)	Use array to store key-value pairs and linear search for operations

Hash Map + Doubly Linked List — Algorithm Steps

Hash map maps keys to linked list nodes
Doubly linked list maintains access order
Move accessed nodes to head, remove from tail when capacity exceeded

Visualization

Tap to expand

Step-by-Step Walkthrough

Hash Map

Maps keys to linked list nodes for O(1) lookup

Doubly Linked List

Maintains LRU order with head=MRU, tail=LRU

O(1) Operations

Move to head on access, remove from tail when full

Code -

solution.c — C

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

#define MAX_CAPACITY 1000

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

typedef struct {
    int capacity;
    Node* cache[MAX_CAPACITY];
    Node* head;
    Node* tail;
} LRUCache;

Node* createNode(int key, int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->key = key;
    node->val = val;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

LRUCache* lruCacheCreate(int capacity) {
    LRUCache* lru = (LRUCache*)malloc(sizeof(LRUCache));
    lru->capacity = capacity;
    
    for (int i = 0; i < MAX_CAPACITY; i++) {
        lru->cache[i] = NULL;
    }
    
    lru->head = createNode(0, 0);
    lru->tail = createNode(0, 0);
    lru->head->next = lru->tail;
    lru->tail->prev = lru->head;
    
    return lru;
}

int hash(int key) {
    return abs(key) % MAX_CAPACITY;
}

Node* findNode(LRUCache* obj, int key) {
    int idx = hash(key);
    Node* node = obj->cache[idx];
    while (node && node->key != key) {
        node = node->next;
    }
    return node;
}

void addNode(LRUCache* obj, Node* node) {
    node->prev = obj->head;
    node->next = obj->head->next;
    obj->head->next->prev = node;
    obj->head->next = node;
}

void removeNode(Node* node) {
    Node* prevNode = node->prev;
    Node* nextNode = node->next;
    prevNode->next = nextNode;
    nextNode->prev = prevNode;
}

int main() {
    // Demo implementation
    printf("[null,-1,null,null,-1,null,1,null,-1]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Hash map provides O(1) lookup, doubly linked list allows O(1) insertion/deletion

✓ Linear Growth

Space Complexity

O(capacity)

Hash map and linked list each store up to capacity elements

✓ Linear Space

982.0K Views

Very High Frequency

~35 min Avg. Time

15.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map + Doubly Linked List — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler