Skip to main content

17. LRU Cache

mediumAsked at DigitalOcean

Design an LRU cache with O(1) get and put — a must-know data structure that DigitalOcean uses to probe OS-level caching intuition.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Design a data structure that follows the Least Recently Used cache constraint. Implement get(key) returning the value if it exists and -1 otherwise, and put(key, value) inserting/updating the key, evicting the LRU key when capacity is exceeded. Both operations must run in O(1) average time.

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key <= 10^4
  • 0 <= value <= 10^5
  • At most 2*10^5 calls to get and put

Examples

Example 1

Input
LRUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2)
Output
1, -1 (2 was evicted)

Example 2

Input
LRUCache(1); put(2,1); get(2); put(3,2); get(2); get(3)
Output
1, -1, 2

Approaches

1. Ordered Map / naive array eviction

Track insertion order in an array; on each access shift the element to the front — O(n) per operation.

Time
O(n)
Space
O(capacity)
// naive: find + splice on every access
class LRUCache {
  constructor(cap) { this.cap = cap; this.keys = []; this.map = {}; }
  get(key) {
    if (!(key in this.map)) return -1;
    this.keys = [key, ...this.keys.filter(k => k !== key)];
    return this.map[key];
  }
  put(key, val) {
    this.keys = [key, ...this.keys.filter(k => k !== key)];
    this.map[key] = val;
    if (this.keys.length > this.cap) delete this.map[this.keys.pop()];
  }
}

Tradeoff:

2. HashMap + Doubly Linked List

Map keys to doubly-linked-list nodes; move-to-front and evict-tail are O(1) pointer operations. Sentinel head/tail nodes eliminate edge cases.

Time
O(1)
Space
O(capacity)
class Node { constructor(k,v){this.key=k;this.val=v;this.prev=this.next=null;} }
class LRUCache {
  constructor(cap) {
    this.cap=cap; this.map=new Map();
    this.head=new Node(0,0); this.tail=new Node(0,0);
    this.head.next=this.tail; this.tail.prev=this.head;
  }
  _remove(n){n.prev.next=n.next;n.next.prev=n.prev;}
  _insert(n){n.next=this.head.next;n.prev=this.head;this.head.next.prev=n;this.head.next=n;}
  get(key){
    if(!this.map.has(key))return -1;
    const n=this.map.get(key);this._remove(n);this._insert(n);return n.val;
  }
  put(key,val){
    if(this.map.has(key))this._remove(this.map.get(key));
    const n=new Node(key,val);this._insert(n);this.map.set(key,n);
    if(this.map.size>this.cap){const lru=this.tail.prev;this._remove(lru);this.map.delete(lru.key);}
  }
}

Tradeoff:

DigitalOcean-specific tips

DigitalOcean expects you to discuss how LRU relates to OS page-replacement and block-device caching — referencing that context signals infrastructure depth.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill LRU Cache and other DigitalOcean interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →