beingsde
Sign In
Back to all DSA patterns
HashMap / Doubly Linked List•Pattern: HashMap + Doubly Linked List•Medium

Design an LRU Cache

Problem Intuition & Objective

Implement a Least Recently Used cache with O(1) get and put.

Time ComplexityO(1) get & put
Optimal
Space ComplexityO(capacity)
Memory Bounds
Optimal Algorithmic Approach

HashMap of key → DLL node + sentinel head/tail nodes.

Core Invariants & Edge Cases

  • HashMap for O(1) key lookup, doubly linked list for O(1) eviction order
  • On get: move node to head (most recent)
  • On put: add to head; if over capacity, remove tail (least recent)
Previous ProblemLongest substring without repeating charactersNext Problem Longest palindromic substring

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.