Data Structure

LRU Cache

A Least Recently Used (LRU) Cache evicts the item accessed least recently when full. Implemented with a doubly linked list + hash map for O(1) GET & PUT.

O(1) GET O(1) PUT Doubly Linked List + Hash Map Used in: CPU Caches, Redis, Browsers

Cache State

MRU ← Most Recent   Least Recent → LRU
🗄️ Cache is empty — use PUT to add items
💡 How LRU Cache Works
MRUA
←→
B
←→
C
←→
LRUD

Items are in a doubly linked list. MRU at left, LRU at right — evicted first when cache is full.

GET
Hit — found → move to MRU, return value.
Miss — not found → return -1.
PUT
New key — full? evict LRU → insert at MRU.
Existing — update value → move to MRU.
📘 Walkthrough — capacity = 3
PUT 1,A→[1]
PUT 2,B→[2→1]
PUT 3,C→[3→2→1]
GET 1→ HIT →[1→3→2]
PUT 4,D→ evict 2 →[4→1→3]
Cache Hit Cache Miss Evicted New / Updated

Activity Log

live
Graph

Graph BFS / DFS

Breadth-First Search (BFS) explores a graph level by level using a queue. Depth-First Search (DFS) explores as far as possible using a stack. Both run in O(V + E) time.

O(V + E) Queue (BFS) / Stack (DFS) Graph Traversal Used in: Shortest Path, Connectivity, AI

Graph

Click any node to set as start
Queue / Stack
empty
Visited Order
none yet

Step Log

live
Algorithm

N-Queens Backtracking

Place N queens on an N×N chessboard so no two queens threaten each other. Uses backtracking — try a position, recurse, undo when a conflict is found.

Backtracking Recursion Constraint Satisfaction O(N!) worst case

Chessboard

Backtracking Log

live