Exercises

// ===== Exercise 1: reverse a linked list =====
class ListNode {
  constructor(val, next = null) { this.val = val; this.next = next; }
}

function reverse(head) {
  let prev = null;
  let cur = head;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
}

// ===== Exercise 2: longest palindromic substring =====
function longestPalindrome(s) {
  let start = 0, maxLen = 1;
  function expand(l, r) {
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      if (r - l + 1 > maxLen) { maxLen = r - l + 1; start = l; }
      l--; r++;
    }
  }
  for (let i = 0; i < s.length; i++) {
    expand(i, i);       // odd length
    expand(i, i + 1);   // even length
  }
  return s.slice(start, start + maxLen);
}

// ===== Exercise 3: BFS shortest path in grid =====
function shortestPath(grid, start, end) {
  const [R, C] = [grid.length, grid[0].length];
  const visited = new Set([start.join(',')]);
  const queue = [[start, 0]];
  while (queue.length) {
    const [[r, c], d] = queue.shift();
    if (r === end[0] && c === end[1]) return d;
    for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
      const nr = r + dr, nc = c + dc;
      const key = nr + ',' + nc;
      if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] !== 1 && !visited.has(key)) {
        visited.add(key);
        queue.push([[nr, nc], d + 1]);
      }
    }
  }
  return -1;
}

// ===== Exercise 4: top-k frequent elements =====
function topK(nums, k) {
  const counts = new Map();
  for (const n of nums) counts.set(n, (counts.get(n) ?? 0) + 1);
  return [...counts.entries()]
    .sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map(([n, _]) => n);
}

// O(n log n). For O(n log k), use a min-heap of size k.

// ===== Exercise 5: max subarray sum (Kadane) =====
function maxSubarray(nums) {
  let best = nums[0], current = nums[0];
  for (let i = 1; i < nums.length; i++) {
    current = Math.max(nums[i], current + nums[i]);
    best = Math.max(best, current);
  }
  return best;
}

// O(n)

// ===== Exercise 6: detect cycle in linked list (Floyd) =====
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;
}

// O(n) time, O(1) space — two pointers

// ===== Patterns =====
// - Two pointers (slow + fast)
// - Sliding window
// - BFS for shortest unweighted path
// - DP with rolling variable (Kadane)
// - Frequency hash + sort or heap
// - Expand-around-center for palindromes

// ===== Pitfalls =====
// - Off-by-one on expand-around-center boundaries
// - BFS queue.shift() is O(n) in JS; use deque on large inputs
// - Floyd's cycle returns presence; for cycle START use Brent's algorithm
// - Top-k with full sort is O(n log n); heap version is O(n log k)

// Fill in: while (lo ____ hi) { … }   // classic binary search