Mock Interview Day

Every palindrome has a center — either a single character (odd length) or a gap between two characters (even length). Try every possible center and expand outward while both sides match. O(n) centers, O(n) expansion each, O(n²) total — no DP table needed.

function longestPalindrome(s) {
  if (s.length < 2) return s;
  let start = 0, maxLen = 1;

  function expand(l, r) {
    while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
    return [l + 1, r - 1];             // the last valid palindrome bounds
  }

  for (let i = 0; i < s.length; i++) {
    const [l1, r1] = expand(i, i);     // odd-length center at i
    if (r1 - l1 + 1 > maxLen) { start = l1; maxLen = r1 - l1 + 1; }
    const [l2, r2] = expand(i, i + 1); // even-length center between i and i+1
    if (r2 - l2 + 1 > maxLen) { start = l2; maxLen = r2 - l2 + 1; }
  }
  return s.substring(start, start + maxLen);
}

Walkthrough: every index is tried as both an odd-length center (single character) and an even-length center (gap between two characters) — that covers every possible palindrome shape. expand grows outward while the characters on both sides keep matching, and returns the bounds of the last valid match. Whichever expansion produces a longer palindrome than anything seen so far updates start/maxLen. Time O(n²) (n centers, up to O(n) expansion each), space O(1) beyond the output.

Sort by start time first — same opening move as Day 27's interval greedy, just sorted by the other endpoint. Then walk left to right: if the current interval's start is within the last merged interval's end, extend that interval's end instead of starting a new one.

function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];
  const sorted = intervals.slice().sort((a, b) => a[0] - b[0]);
  const result = [sorted[0].slice()];

  for (let i = 1; i < sorted.length; i++) {
    const last = result[result.length - 1];
    const [start, end] = sorted[i];
    if (start <= last[1]) {
      last[1] = Math.max(last[1], end);  // overlaps — extend the last merged interval
    } else {
      result.push([start, end]);         // no overlap — starts a new merged interval
    }
  }
  return result;
}

Walkthrough: sorting by start time means every interval that could possibly overlap the one currently being built is guaranteed to be checked before we move past it. start <= last[1] is the overlap test — note it's <=, not <, since touching intervals like [1,4] and [4,5] should still merge into [1,5]. Time O(n log n), dominated by the sort; space O(n) for the output.

Every rotten orange rots its neighbors simultaneously, every minute — that's multi-source BFS, exactly like Day 24's 01 Matrix, except the queue seeds with every ALREADY-rotten cell instead of every 0-cell. Track elapsed minutes per queue entry, and count remaining fresh oranges to know if any are unreachable.

function orangesRotting(grid) {
  const rows = grid.length, cols = grid[0].length;
  const queue = [];
  let fresh = 0;

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r, c, 0]);  // seed with EVERY already-rotten cell
      else if (grid[r][c] === 1) fresh++;
    }
  }

  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let minutes = 0;
  let qi = 0;
  while (qi < queue.length) {
    const [r, c, t] = queue[qi++];
    minutes = Math.max(minutes, t);
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
        grid[nr][nc] = 2;
        fresh--;
        queue.push([nr, nc, t + 1]);
      }
    }
  }
  return fresh === 0 ? minutes : -1;
}

Walkthrough: seeding the queue with every rotten cell at once (not just one) is what makes this multi-source BFS — the same trick Day 24's 01 Matrix used for "distance to nearest 0-cell." Every cell's t is exactly how many minutes it took to rot, so the answer is the largest t reached. Any fresh orange never visited means it was unreachable — the fresh counter catches that and returns -1 instead of a wrong number. Time O(rows × cols), space O(rows × cols) for the queue in the worst case.

Build a 2D table where dp[i][j] is the LCS length using the first i characters of text1 and the first j characters of text2. If those two characters match, extend the diagonal (dp[i-1][j-1] + 1); if they don't, take the best of dropping one character from either string (max(dp[i-1][j], dp[i][j-1])).

function longestCommonSubsequence(text1, text2) {
  const m = text1.length, n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;              // characters match — extend the diagonal
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // no match — best of dropping either side
      }
    }
  }
  return dp[m][n];
}

Walkthrough: row 0 and column 0 are implicit base cases — an empty string has an LCS of length 0 with anything, which is exactly what .fill(0) already gives every cell before the loop runs. dp[i][j] only ever depends on the cell diagonally above-left, directly above, or directly left — every one of those is guaranteed already filled by the time row-major order reaches (i, j). This is the same "cache overlapping subproblems" idea as Days 25-26, just stretched across 2 dimensions instead of 1. Time O(m × n), space O(m × n) for the table.