62Coding Round (JS/TS DSA for SDET)

62.1 Patterns to recognise

Problem 1 — Two Sum

Prompt: Given an array nums and target t, return indices of the two numbers that add up to t.

Approach

Brute force is O(n²). The trick: as you iterate, remember every value you've seen and its index in a map. For each new value x, check if t - x is already in the map. If yes, return.

function twoSum(nums: number[], t: number): [number, number] {
  const seen = new Map<number, number>();   // value → index
  for (let i = 0; i < nums.length; i++) {
    const need = t - nums[i];
    if (seen.has(need)) return [seen.get(need)!, i];
    seen.set(nums[i], i);
  }
  throw new Error('no solution');
}
// Time O(n), space O(n)

Problem 2 — First non-repeating character

Prompt: Return the first character in a string that appears only once. Return '' if none.

Approach

Two passes. Pass 1: count every char into a map. Pass 2: walk the string left-to-right, return the first char whose count is 1.

function firstUnique(s: string): string {
  const count = new Map<string, number>();
  for (const c of s) count.set(c, (count.get(c) ?? 0) + 1);
  for (const c of s) if (count.get(c) === 1) return c;
  return '';
}
// Time O(n), space O(k) where k = alphabet size

Problem 3 — Valid palindrome (case/alphanumeric ignored)

Prompt: Given "A man, a plan, a canal: Panama", return true.

Approach

Two pointers — one from each end. Skip non-alphanumeric. Compare lowercased.

function isPalindrome(s: string): boolean {
  const isAlnum = (c: string) => /[a-z0-9]/i.test(c);
  let i = 0, j = s.length - 1;
  while (i < j) {
    while (i < j && !isAlnum(s[i])) i++;
    while (i < j && !isAlnum(s[j])) j--;
    if (s[i].toLowerCase() !== s[j].toLowerCase()) return false;
    i++; j--;
  }
  return true;
}
// Time O(n), space O(1)

Problem 4 — Longest substring without repeating characters

Prompt: "abcabcbb" → 3 ("abc").

Approach

Sliding window. Expand the right pointer; if you see a char already in the window, shrink from the left until it's gone. Track max length.

function lengthOfLongestSubstring(s: string): number {
  const lastSeen = new Map<string, number>();
  let start = 0, best = 0;
  for (let i = 0; i < s.length; i++) {
    const c = s[i];
    if (lastSeen.has(c) && lastSeen.get(c)! >= start) {
      start = lastSeen.get(c)! + 1;       // jump past the duplicate
    }
    lastSeen.set(c, i);
    best = Math.max(best, i - start + 1);
  }
  return best;
}
// Time O(n), space O(k)

Problem 5 — Valid parentheses

Prompt: "({[]})" → true, "(]" → false.

Approach

Stack. Push openers. For every closer, pop and compare. Empty stack at end = valid.

function isValid(s: string): boolean {
  const pair: Record<string, string> = { ')': '(', ']': '[', '}': '{' };
  const stack: string[] = [];
  for (const c of s) {
    if (c === '(' || c === '[' || c === '{') stack.push(c);
    else if (stack.pop() !== pair[c]) return false;
  }
  return stack.length === 0;
}
// Time O(n), space O(n)

Problem 6 — Group anagrams

Prompt: Group strings that are anagrams: ["eat","tea","tan","ate","nat","bat"] → [["eat","tea","ate"],["tan","nat"],["bat"]].

Approach

Anagrams share the same sorted-letter key. Group by that key in a map.

function groupAnagrams(strs: string[]): string[][] {
  const groups = new Map<string, string[]>();
  for (const s of strs) {
    const key = s.split('').sort().join('');
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key)!.push(s);
  }
  return [...groups.values()];
}
// Time O(n · k log k), space O(n · k) where k = max string length

Problem 7 — Merge intervals

Prompt: [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]].

Approach

Sort by start. Walk through; if next.start ≤ current.end, extend current.end; else push current and move on.

function merge(intervals: number[][]): number[][] {
  if (!intervals.length) return [];
  intervals.sort((a, b) => a[0] - b[0]);
  const out: number[][] = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const top = out[out.length - 1];
    const [s, e] = intervals[i];
    if (s <= top[1]) top[1] = Math.max(top[1], e);
    else out.push([s, e]);
  }
  return out;
}
// Time O(n log n), space O(n)

Problem 8 — Evaluate basic infix expression (+, -, *, /, integers)

Prompt: Evaluate "3+2*2" → 7, " 3/2 " → 1, "3+5 / 2" → 5.

Approach

State machine with a stack. Track the previous operator; when a new operator (or end) appears, apply the previous one to the running number. * and / apply to the top of the stack, +/- push the sign-applied number.

function calculate(s: string): number {
  const stack: number[] = [];
  let num = 0, prevOp = '+';
  for (let i = 0; i < s.length; i++) {
    const c = s[i];
    if (/\d/.test(c)) num = num * 10 + Number(c);
    if ((!/\d/.test(c) && c !== ' ') || i === s.length - 1) {
      if      (prevOp === '+') stack.push(num);
      else if (prevOp === '-') stack.push(-num);
      else if (prevOp === '*') stack.push(stack.pop()! * num);
      else if (prevOp === '/') stack.push(Math.trunc(stack.pop()! / num));
      prevOp = c;
      num = 0;
    }
  }
  return stack.reduce((a, b) => a + b, 0);
}
// Time O(n), space O(n)

Problem 9 — Top K frequent elements

Prompt: nums = [1,1,1,2,2,3], k = 2 → [1,2].

Approach

Bucket sort by frequency. The frequency is at most n, so make an array of buckets[freq] = list of numbers. Walk from highest freq down, take first k.

function topKFrequent(nums: number[], k: number): number[] {
  const freq = new Map<number, number>();
  for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);
  const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
  for (const [n, f] of freq) buckets[f].push(n);
  const result: number[] = [];
  for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
    result.push(...buckets[i]);
  }
  return result.slice(0, k);
}
// Time O(n), space O(n)

Problem 10 — Find duplicate in an array of n+1 ints in 1..n

Prompt: Exactly one duplicate exists. Find it in O(1) extra space.

Approach

Floyd's tortoise & hare on the value-as-pointer graph. Same algorithm as cycle detection in a linked list.

function findDuplicate(nums: number[]): number {
  let slow = nums[0], fast = nums[0];
  do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow !== fast);
  slow = nums[0];
  while (slow !== fast) { slow = nums[slow]; fast = nums[fast]; }
  return slow;
}
// Time O(n), space O(1)

Problem 11 — String compress (run-length)

Prompt: "aaabbc" → "a3b2c1". If compressed isn't shorter, return original.

function compress(s: string): string {
  if (!s) return s;
  let out = '', count = 1;
  for (let i = 1; i <= s.length; i++) {
    if (i < s.length && s[i] === s[i - 1]) count++;
    else { out += s[i - 1] + count; count = 1; }
  }
  return out.length < s.length ? out : s;
}

Problem 12 — Validate Sudoku row/col/box (state-style)

function isValidSudoku(board: string[][]): boolean {
  const rows: Set<string>[] = Array.from({ length: 9 }, () => new Set());
  const cols: Set<string>[] = Array.from({ length: 9 }, () => new Set());
  const boxes: Set<string>[] = Array.from({ length: 9 }, () => new Set());
  for (let r = 0; r < 9; r++) for (let c = 0; c < 9; c++) {
    const v = board[r][c];
    if (v === '.') continue;
    const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
    if (rows[r].has(v) || cols[c].has(v) || boxes[b].has(v)) return false;
    rows[r].add(v); cols[c].add(v); boxes[b].add(v);
  }
  return true;
}
// Time O(81), space O(81)

62.2 The "talk through it" interview script

1. Restate the problem. "So I'm given… and I need to return…"
2. Walk through an example by hand. Shows your thought process. Confirms you understand.
3. Brute force. State it explicitly: "I could nested-loop in O(n²)…". Doesn't matter if it's bad; shows the floor.
4. Optimise. Pick a pattern from the table. Say: "I notice X, so a hashmap/two-pointer/sliding window will get me to O(n)."
5. Code it. Talk while writing — about variables, edge cases, loop invariants.
6. Dry run. Walk through your code on the example again. Catch off-by-ones.
7. Edge cases. Empty input, single element, all duplicates, max size.
8. Complexity. Always state time and space at the end.

62.3 More high-frequency interview problems (with solutions)

Problem A — Best time to buy/sell stock (max profit)

function maxProfit(prices: number[]): number {
  let min = Infinity, profit = 0;
  for (const p of prices) {
    if (p < min) min = p;
    else if (p - min > profit) profit = p - min;
  }
  return profit;
}
// O(n) time, O(1) space

Problem B — Merge K sorted arrays (heap)

function mergeKSortedArrays(arrs: number[][]): number[] {
  /* Use a min-heap of (value, arrayIdx, valueIdx) tuples.
     Pop smallest, push next from same array. O(n log k). */
  const out: number[] = [];
  const heap = new MinHeap<[number, number, number]>((a, b) => a[0] - b[0]);
  arrs.forEach((arr, i) => { if (arr.length) heap.push([arr[0], i, 0]); });
  while (heap.size()) {
    const [val, i, j] = heap.pop()!;
    out.push(val);
    if (j + 1 < arrs[i].length) heap.push([arrs[i][j+1], i, j+1]);
  }
  return out;
}

Problem C — Longest substring with at most K distinct chars

function longestSubstrKDistinct(s: string, k: number): number {
  const count = new Map<string, number>();
  let start = 0, best = 0;
  for (let i = 0; i < s.length; i++) {
    count.set(s[i], (count.get(s[i]) ?? 0) + 1);
    while (count.size > k) {
      const c = s[start++];
      const n = count.get(c)! - 1;
      if (n === 0) count.delete(c); else count.set(c, n);
    }
    best = Math.max(best, i - start + 1);
  }
  return best;
}

Problem D — Word ladder (BFS)

function ladderLength(begin: string, end: string, wordList: string[]): number {
  const dict = new Set(wordList);
  if (!dict.has(end)) return 0;
  const queue: [string, number][] = [[begin, 1]];
  const visited = new Set([begin]);
  while (queue.length) {
    const [word, steps] = queue.shift()!;
    if (word === end) return steps;
    for (let i = 0; i < word.length; i++) {
      for (let c = 97; c <= 122; c++) {
        const next = word.slice(0, i) + String.fromCharCode(c) + word.slice(i+1);
        if (dict.has(next) && !visited.has(next)) {
          visited.add(next);
          queue.push([next, steps + 1]);
        }
      }
    }
  }
  return 0;
}

Problem E — Trapping rain water

function trap(h: number[]): number {
  let l = 0, r = h.length - 1, leftMax = 0, rightMax = 0, water = 0;
  while (l < r) {
    if (h[l] < h[r]) {
      h[l] >= leftMax ? leftMax = h[l] : water += leftMax - h[l];
      l++;
    } else {
      h[r] >= rightMax ? rightMax = h[r] : water += rightMax - h[r];
      r--;
    }
  }
  return water;
}
// O(n) time, O(1) space (two pointer)

Problem F — Spiral matrix

function spiralOrder(m: number[][]): number[] {
  const out: number[] = [];
  let top = 0, bot = m.length - 1, left = 0, right = m[0].length - 1;
  while (top <= bot && left <= right) {
    for (let j = left; j <= right; j++) out.push(m[top][j]);  top++;
    for (let i = top;  i <= bot;   i++) out.push(m[i][right]); right--;
    if (top <= bot)   { for (let j = right; j >= left; j--) out.push(m[bot][j]); bot--; }
    if (left <= right){ for (let i = bot;   i >= top;  i--) out.push(m[i][left]); left++; }
  }
  return out;
}

Problem G — Longest common prefix

function longestCommonPrefix(strs: string[]): string {
  if (!strs.length) return '';
  let prefix = strs[0];
  for (let i = 1; i < strs.length; i++) {
    while (!strs[i].startsWith(prefix)) prefix = prefix.slice(0, -1);
    if (!prefix) return '';
  }
  return prefix;
}

Problem H — Set matrix zeroes (in-place)

function setZeroes(m: number[][]): void {
  const R = m.length, C = m[0].length;
  let firstRowZero = m[0].some(v => v === 0);
  let firstColZero = m.some(r => r[0] === 0);
  /* use first row + first col as markers */
  for (let i = 1; i < R; i++) for (let j = 1; j < C; j++) {
    if (m[i][j] === 0) { m[i][0] = 0; m[0][j] = 0; }
  }
  for (let i = 1; i < R; i++) for (let j = 1; j < C; j++) {
    if (m[i][0] === 0 || m[0][j] === 0) m[i][j] = 0;
  }
  if (firstRowZero) for (let j = 0; j < C; j++) m[0][j] = 0;
  if (firstColZero) for (let i = 0; i < R; i++) m[i][0] = 0;
}
// O(R*C) time, O(1) extra space

Problem I — Max area of island (DFS)

function maxAreaIsland(grid: number[][]): number {
  const R = grid.length, C = grid[0].length;
  let best = 0;
  function dfs(i: number, j: number): number {
    if (i < 0 || j < 0 || i >= R || j >= C || grid[i][j] !== 1) return 0;
    grid[i][j] = 0;
    return 1 + dfs(i+1,j) + dfs(i-1,j) + dfs(i,j+1) + dfs(i,j-1);
  }
  for (let i = 0; i < R; i++) for (let j = 0; j < C; j++) {
    if (grid[i][j] === 1) best = Math.max(best, dfs(i, j));
  }
  return best;
}

Problem J — Implement strStr (KMP idea acceptable)

function strStr(haystack: string, needle: string): number {
  if (!needle) return 0;
  for (let i = 0; i <= haystack.length - needle.length; i++) {
    if (haystack.slice(i, i + needle.length) === needle) return i;
  }
  return -1;
}
// O(n*m) naive; KMP gives O(n+m)