🏗️ Design Data Structures

One-line summary: Build custom data structures combining existing primitives (hash maps, heaps, linked lists) to meet specific time/space requirements.

---

Diagram

Concept

Design problems ask you to implement a class with specific operations at defined complexities.

Key building blocks:

• Hash Map + Doubly Linked List → LRU Cache (O(1) get/put)
• Hash Map + Min/Max Heap → LFU Cache
• Two Stacks → Queue; Two Queues → Stack
• Trie + Hash Map → prefix-based lookups
• Hash Map + Array → O(1) insert/delete/getRandom

---

Common Patterns

LRU Cache Skeleton

class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const val = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, val);
    return val;
  }
  put(key, value) {
    this.map.delete(key);
    if (this.map.size === this.cap) this.map.delete(this.map.keys().next().value);
    this.map.set(key, value);
  }
}

O(1) Insert/Delete/GetRandom

class RandomizedSet {
  constructor() {
    this.map = new Map();
    this.arr = [];
  }
  insert(val) {
    if (this.map.has(val)) return false;
    this.map.set(val, this.arr.length);
    this.arr.push(val);
    return true;
  }
  remove(val) {
    if (!this.map.has(val)) return false;
    const i = this.map.get(val),
      last = this.arr[this.arr.length - 1];
    this.arr[i] = last;
    this.map.set(last, i);
    this.arr.pop();
    this.map.delete(val);
    return true;
  }
  getRandom() {
    return this.arr[Math.floor(Math.random() * this.arr.length)];
  }
}

---

Pitfalls

• LRU with JS Map: insertion order is preserved — use map.keys().next() to get LRU
• Thread safety not relevant in JS (single-threaded), but clarify in interviews
• Always clarify expected time complexity before designing

---

Practice Problems

Problem	Difficulty	Solution
LC 146 — LRU Cache	Medium
LC 460 — LFU Cache	Hard
LC 380 — Insert Delete GetRandom O(1)	Medium
LC 705 — Design HashSet	Easy
LC 706 — Design HashMap	Easy
LC 641 — Design Circular Deque	Medium
LC 208 — Implement Trie	Medium
LC 355 — Design Twitter	Medium
LC 1206 — Design Skiplist	Hard
CC — Cache Hits (CACHEHIT)	Easy
LC 1146 — Snapshot Array	Medium
LC 155 — Min Stack	Medium
LC 232 — Implement Queue using Stacks	Easy
LC 295 — Find Median from Data Stream	Hard
LC 346 — Moving Average from Data Stream	Easy
LC 348 — Design Tic-Tac-Toe	Medium
LC 362 — Design Hit Counter	Medium
LC 381 — Insert Delete GetRandom O(1) - Duplicates	Hard
LC 432 — All O`one Data Structure	Hard
LC 588 — Design In-Memory File System	Hard
LC 622 — Design Circular Queue	Medium
LC 631 — Design Excel Sum Formula	Hard
LC 716 — Max Stack	Hard
LC 895 — Maximum Frequency Stack	Hard
LC 1244 — Design A Leaderboard	Medium
LC 1352 — Product of the Last K Numbers	Medium
LC 1472 — Design Browser History	Medium
CC — Data Structure Design (DSDESIGN)	Medium
CC — Custom Stack (CUSTSTACK)	Easy

---

Related Topics

• Heap — LFU, median stream
• Linked List — LRU doubly linked list
• Hashing — O(1) lookups

← Back to Home · © sparshjaswal