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

Hash Map (Key -> Node Address)

Empty
🗄️ 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

Pseudo-code & Log

live 
procedure BFS(G, root) is
  let Q be a queue
  Q.enqueue(root)
  while Q is not empty do
    v := Q.dequeue()
    if v is not labeled as discovered then
      label v as discovered
      for all edges from v to w in G.adjacentEdges(v) do
        Q.enqueue(w)
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

Pseudo-code & Log

live 
function solve(row) {
  if (row == N) return true;
  for (col = 0; col < N; col++) {
    if (isSafe(row, col)) {
      board[row] = col;
      if (solve(row + 1))
        return true;
      board[row] = UNASSIGNED; // backtrack
    }
  }
  return false;
}
Graph

Dijkstra's Shortest Path

Finds the shortest path from a source node to all others in a weighted graph. Uses a min-priority queue and edge relaxation — greedily expanding the nearest unvisited node.

O((V + E) log V) Min-Priority Queue Edge Relaxation Used in: GPS, Network Routing, Games

Weighted Graph

Click any node to set as source
Priority Queue (dist → node)
empty
Visited Order
none yet

Pseudo-code & Log

live 
func dijkstra(graph, src):
  dist[all] = ∞;  dist[src] = 0
  prev[all] = null
  pq.push(src, 0)        // (node, dist)
  while pq not empty:
    (u, d) = pq.pop_min() // lowest dist
    if u already visited: skip
    mark u as visited
    for each neighbor v of u:
      if d + w(u,v) < dist[v]:
        dist[v] = d + w(u,v)
        pq.push(v, dist[v])