Cave of Knowledge — Phase 1: DSA Foundation

Week 1

Array & String

Array — row of stone, side by side, each stone has number-spot (index). Touch any stone fast, but move stone in middle slow, whole line must shift.

Key Idea

Array store item in one long block of memory, back to back. Index give instant jump — this why arr[5] take same time as arr[500000]. String is just array of character — most trick same for both.

Complexity Table

Operation	Time
Access by index	O(1)
Search (unsorted)	O(n)
Insert/Delete at end	O(1)*
Insert/Delete at start/middle	O(n)

// Reverse array in-place — classic first hunt
function reverseArray(arr) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
  return arr;
}
reverseArray([1,2,3,4,5]); // [5,4,3,2,1]

Cave wisdom: Most array problem solve with one of three tool — extra pointer, extra hash-map, or sort first. Ask "which tool fit here" before write code.

Week 1

Hashing

Hash-map — magic memory-stone. Give it name (key), it give back thing instant (value). No need walk whole cave to find — jump straight there.

Key Idea

Hash function turn key into number (hash code), number point to bucket. Good hash spread key even, so lookup stay O(1) average. Bad hash — many key same bucket, become O(n) worst case (collision chain).

Complexity Table

Operation	Average	Worst
Insert	O(1)	O(n)
Lookup	O(1)	O(n)
Delete	O(1)	O(n)

// Two Sum — hash-map trick, one pass only
function twoSum(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
  return [];
}
twoSum([2,7,11,15], 9); // [0,1]

Cave wisdom: Whenever hunter think "must search again and again" — stop, ask "can hash-map remember this instead?" Trade little memory for big speed.

Week 1

Two-Pointer Trick

Two hunter walk from two end of line, meet in middle. Work best on sorted array — no need check every pair, only O(n) walk.

▶ Live Hunt: Find Pair Sum = Target (sorted array)

Press Step to begin hunt. Target sum = 10

Approach	Time	Space
Brute force (check all pair)	O(n²)	O(1)
Two-Pointer (sorted)	O(n)	O(1)

// Pair with target sum — sorted array
function pairSum(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return [left, right];
    else if (sum < target) left++;   // need bigger, move left up
    else right--;                   // need smaller, move right down
  }
  return [-1, -1];
}

Cave wisdom: Two-pointer only work if array sorted (or can sort first). Common hunt: pair-sum, remove duplicate, container-with-most-water, palindrome check.

Week 1

Sliding Window Trick

Imagine window-hole cut in bark, hold over array, slide across. Only add new stone enter window, remove stone leave window — no recount whole window every time.

▶ Live Hunt: Max Sum of Window Size 3

Press Step to slide window across array.

Approach	Time
Brute force (recompute each window)	O(n·k)
Sliding Window	O(n)

// Max sum of window size k
function maxWindowSum(arr, k) {
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += arr[i];
  let maxSum = windowSum;

  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k];   // add new, drop old
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

Cave wisdom: Fixed-size window (like above) and variable-size window (grow/shrink based on condition) are two different hunt style — learn both. Variable window common in "longest substring without repeat" type problem.

Week 2

Linked List

Not row of stone side-by-side. Instead — each stone hold arrow pointing to next stone, scattered anywhere in cave. Slow to jump to middle, but fast to add/remove.

Complexity Table

Operation	Time
Access by index	O(n)
Insert/Delete at head	O(1)
Insert/Delete at tail	O(n)*
Search	O(n)

Array vs Linked List

Array — fast random-access, slow insert/delete middle.
Linked List — slow random-access, fast insert/delete once you at spot.
*tail insert O(1) if you keep tail pointer.

// Reverse a singly linked list — must-know hunt
function reverseList(head) {
  let prev = null, curr = head;
  while (curr !== null) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev; // new head
}

// Detect cycle — Floyd's Tortoise and Hare
function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

Cave wisdom: Slow-fast pointer (tortoise-hare) is signature linked-list trick — find middle, detect cycle, find cycle start, find nth-from-end all use this same idea.

Week 2

Stack

Pile of stone. Last stone you drop on top — first stone you pick back up. LIFO: Last In, First Out.

Complexity

Operation	Time
Push	O(1)
Pop	O(1)
Peek	O(1)

Where Stack Hide

Browser back-button, undo-redo, call-stack of function itself, bracket-matching, DFS traversal, expression evaluation (postfix/infix).

// Valid Parentheses — classic stack hunt
function isValid(s) {
  const stack = [];
  const pairs = { ')': '(', ']': '[', '}': '{' };
  for (const ch of s) {
    if ('([{'.includes(ch)) stack.push(ch);
    else {
      if (stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0;
}
isValid("({[]})"); // true

Cave wisdom: If problem talk about "matching," "nested," "undo," or "most-recent-first" — stack probably right tool.

Week 2

Queue

Line of hunter waiting outside cave. First hunter join line — first hunter get food. FIFO: First In, First Out.

Complexity

Operation	Time
Enqueue	O(1)
Dequeue	O(1)*
Peek	O(1)

Where Queue Hide

BFS traversal, task scheduling, print queue, message queue (Kafka/RabbitMQ concept), rate-limiter buffer. *Array-based dequeue is O(n) unless use pointer or actual linked structure.

// Queue via two stacks — clever interview hunt
class MyQueue {
  constructor() { this.inS = []; this.outS = []; }
  enqueue(x) { this.inS.push(x); }
  dequeue() {
    if (this.outS.length === 0) {
      while (this.inS.length) this.outS.push(this.inS.pop());
    }
    return this.outS.pop();
  }
}

Cave wisdom: "Level by level" or "shortest path unweighted" — smell of BFS, means Queue is weapon of choice.

Week 3

Recursion

Hunter tell smaller version of self to solve smaller problem, that hunter tell even smaller self, until problem tiny enough (base case) to solve direct.

Three Law of Recursion

1. Must have base case — stop condition.
2. Must change state toward base case each call.
3. Must call self (directly or indirectly).

Cost Warning

Each call use call-stack frame — deep recursion can overflow stack. Naive recursion can duplicate work (see Fibonacci) — fix with memoization (cache).

// Factorial — simplest recursion
function factorial(n) {
  if (n <= 1) return 1;      // base case
  return n * factorial(n - 1); // smaller problem
}

// Fibonacci with memoization — avoid duplicate hunt
function fib(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

Cave wisdom: Every recursion can rewrite as loop with explicit stack — recursion just borrow call-stack to do it for you. Use recursion when problem naturally "tree-shape" (tree, backtrack, divide-conquer).

Week 3

Binary Search

Sorted line of stone. Don't check one-by-one — jump to middle stone, throw away half you don't need, repeat. Cut problem in half every step.

▶ Live Hunt: Find 23 in Sorted Array

Press Step to begin binary hunt for target = 23

Approach	Time
Linear search	O(n)
Binary search	O(log n)

// Iterative binary search
function binarySearch(arr, target) {
  let low = 0, high = arr.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

Cave wisdom: Binary search need sorted data. Beyond plain search, it also solve "find first/last occurrence," "search in rotated array," "find peak," and any "minimize/maximize answer" problem where answer-space itself monotonic.

Week 3

Sorting — Why Merge Sort Fast

Bubble sort — hunter compare neighbor stone again and again, slow O(n²). Merge sort — split cave in half, sort each half, then weave together smart. This why merge sort beat bubble sort on big pile.

Complexity Table

Algorithm	Best	Average	Worst	Space
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)

Why Merge Sort Win

Bubble sort compare pair again and again — n stone need n pass, each pass n compare → n×n = n².

Merge sort split problem in half each time (log n level of split), and merge two sorted half in n work per level. Total = n × log n — much smaller than n² when n big.

// Merge Sort — divide and conquer
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(a, b) {
  const result = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    result.push(a[i] <= b[j] ? a[i++] : b[j++]);
  }
  return [...result, ...a.slice(i), ...b.slice(j)];
}

Cave wisdom: In real interview, no need write sort from scratch usually — but MUST explain "why" one sort faster, and know when to pick which (stable? in-place? nearly-sorted data?).

Week 4

Tree (Binary Tree, BST) & Traversal

Tree — like family of cave, one elder (root) has two child, each child has own two child. Binary Search Tree (BST) special: left child always smaller, right child always bigger.

▶ Live Hunt: Watch Traversal Order

Pick a traversal to watch cave-elders visited in order.

Complexity (Balanced Tree)

Operation	Time
Search (BST)	O(log n)
Insert (BST)	O(log n)
Traverse (any)	O(n)

Three Traversal Order

In-order (Left → Root → Right): give sorted order for BST.
Pre-order (Root → Left → Right): good for copy tree.
Post-order (Left → Right → Root): good for delete tree, or compute size.

class TreeNode {
  constructor(val) { this.val = val; this.left = this.right = null; }
}

function inorder(node, out = []) {
  if (!node) return out;
  inorder(node.left, out);
  out.push(node.val);
  inorder(node.right, out);
  return out;
}

function preorder(node, out = []) {
  if (!node) return out;
  out.push(node.val);
  preorder(node.left, out);
  preorder(node.right, out);
  return out;
}

function postorder(node, out = []) {
  if (!node) return out;
  postorder(node.left, out);
  postorder(node.right, out);
  out.push(node.val);
  return out;
}

Cave wisdom: BST search feel like binary search on array — throw away half tree each step. But if tree not balanced (all node lean one side), it degrade to O(n) — like linked list in disguise!

Learn Shape of Data First

Array & String

Key Idea

Complexity Table

Hashing

Key Idea

Complexity Table

Two-Pointer Trick

▶ Live Hunt: Find Pair Sum = Target (sorted array)

Sliding Window Trick

▶ Live Hunt: Max Sum of Window Size 3

Linked List

Complexity Table

Array vs Linked List

Stack

Complexity

Where Stack Hide

Queue

Complexity

Where Queue Hide

Recursion

Three Law of Recursion

Cost Warning

Binary Search

▶ Live Hunt: Find 23 in Sorted Array

Sorting — Why Merge Sort Fast

Complexity Table

Why Merge Sort Win

Tree (Binary Tree, BST) & Traversal

▶ Live Hunt: Watch Traversal Order

Complexity (Balanced Tree)

Three Traversal Order