63Extended Coding Round (20+ more problems)

Problem 13 — Kadane (max subarray sum)

Prompt: Given [-2,1,-3,4,-1,2,1,-5,4], return 6 (subarray [4,-1,2,1]).

function maxSubArray(nums: number[]): number {
  let best = nums[0], cur = nums[0];
  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]);   // extend or restart
    best = Math.max(best, cur);
  }
  return best;
}
// O(n) time, O(1) space

Problem 14 — Intersection of two arrays (unique)

function intersection(a: number[], b: number[]): number[] {
  const setA = new Set(a);
  return [...new Set(b.filter(x => setA.has(x)))];
}
// O(n + m) time

Problem 15 — Rotate array by k

Prompt: Rotate [1,2,3,4,5,6,7] by 3 → [5,6,7,1,2,3,4].

function rotate(nums: number[], k: number): void {
  k = k % nums.length;
  reverse(nums, 0, nums.length - 1);
  reverse(nums, 0, k - 1);
  reverse(nums, k, nums.length - 1);
}
function reverse(a: number[], i: number, j: number) {
  while (i < j) { [a[i], a[j]] = [a[j], a[i]]; i++; j--; }
}
// O(n) time, O(1) space

Problem 16 — Missing number (0…n)

Prompt: Array contains 0..n with one missing. Find it.

function missingNumber(nums: number[]): number {
  const n = nums.length;
  const expected = (n * (n + 1)) / 2;
  const actual = nums.reduce((a, b) => a + b, 0);
  return expected - actual;
}
// O(n) time, O(1) space

Problem 17 — Reverse linked list

class ListNode { val: number; next: ListNode | null;
  constructor(v: number, n: ListNode | null = null) { this.val = v; this.next = n; }
}

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null, curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}
// O(n) time, O(1) space

Problem 18 — Linked list has cycle (Floyd's)

function hasCycle(head: ListNode | null): boolean {
  let slow = head, fast = head;
  while (fast?.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}
// O(n) time, O(1) space

Problem 19 — Merge two sorted lists

function mergeTwoLists(a: ListNode | null, b: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else                  { tail.next = b; b = b.next; }
    tail = tail.next!;
  }
  tail.next = a || b;
  return dummy.next;
}

Problem 20 — BFS level order traversal

class TreeNode { val: number; left: TreeNode | null = null; right: TreeNode | null = null;
  constructor(v: number) { this.val = v; }
}
function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const out: number[][] = [];
  let q: TreeNode[] = [root];
  while (q.length) {
    const level: number[] = [];
    const next: TreeNode[] = [];
    for (const n of q) {
      level.push(n.val);
      if (n.left) next.push(n.left);
      if (n.right) next.push(n.right);
    }
    out.push(level);
    q = next;
  }
  return out;
}
// O(n) time, O(n) space

Problem 21 — Lowest Common Ancestor (BST)

function lca(root: TreeNode | null, p: number, q: number): TreeNode | null {
  let n = root;
  while (n) {
    if (p < n.val && q < n.val) n = n.left;
    else if (p > n.val && q > n.val) n = n.right;
    else return n;
  }
  return null;
}
// O(h) time where h = tree height

Problem 22 — Is balanced binary tree?

function isBalanced(root: TreeNode | null): boolean {
  function height(n: TreeNode | null): number {
    if (!n) return 0;
    const l = height(n.left); if (l === -1) return -1;
    const r = height(n.right); if (r === -1) return -1;
    if (Math.abs(l - r) > 1) return -1;
    return 1 + Math.max(l, r);
  }
  return height(root) !== -1;
}
// O(n) time

Problem 23 — All subsets (power set)

function subsets(nums: number[]): number[][] {
  const out: number[][] = [];
  function bt(start: number, path: number[]) {
    out.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      bt(i + 1, path);
      path.pop();
    }
  }
  bt(0, []);
  return out;
}
// O(n · 2^n) time

Problem 24 — All permutations

function permute(nums: number[]): number[][] {
  const out: number[][] = [];
  function bt(path: number[], used: boolean[]) {
    if (path.length === nums.length) { out.push([...path]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true; path.push(nums[i]);
      bt(path, used);
      path.pop(); used[i] = false;
    }
  }
  bt([], Array(nums.length).fill(false));
  return out;
}
// O(n · n!) time

Problem 25 — Climbing stairs (DP)

Prompt: 1 or 2 steps at a time. How many ways to reach step n? (Fibonacci.)

function climbStairs(n: number): number {
  let a = 1, b = 1;
  for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
  return b;
}
// O(n) time, O(1) space

Problem 26 — House robber

Prompt: Can't rob adjacent houses. Max loot from [2,7,9,3,1] = 12.

function rob(nums: number[]): number {
  let prev = 0, curr = 0;
  for (const n of nums) [prev, curr] = [curr, Math.max(curr, prev + n)];
  return curr;
}
// O(n) time, O(1) space

Problem 27 — Coin change (min coins)

function coinChange(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) if (a - c >= 0) dp[a] = Math.min(dp[a], dp[a - c] + 1);
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}
// O(amount · coins.length) time

Problem 28 — Parse a CSV-like log line and count errors

SDET-flavoured. Given a list of log strings "2024-01-15T12:00:00Z LEVEL=ERROR msg=...", return count of ERROR per minute.

function errorsPerMinute(lines: string[]): Map<string, number> {
  const out = new Map<string, number>();
  for (const line of lines) {
    const m = line.match(/^(\S+) LEVEL=(\w+)/);
    if (!m || m[2] !== 'ERROR') continue;
    const minute = m[1].slice(0, 16);    // "2024-01-15T12:00"
    out.set(minute, (out.get(minute) ?? 0) + 1);
  }
  return out;
}

Problem 29 — Debounce

function debounce<T extends (...args: any[]) => void>(fn: T, wait: number): T {
  let t: ReturnType<typeof setTimeout>;
  return ((...args: any[]) => {
    clearTimeout(t);
    t = setTimeout(() => fn(...args), wait);
  }) as T;
}

// Usage
const onSearch = debounce((q: string) => console.log('search:', q), 300);
onSearch('h'); onSearch('he'); onSearch('hel'); onSearch('hello');
// Only "hello" runs, 300ms after the last call.

Problem 30 — Throttle

function throttle<T extends (...args: any[]) => void>(fn: T, wait: number): T {
  let last = 0;
  return ((...args: any[]) => {
    const now = Date.now();
    if (now - last >= wait) { last = now; fn(...args); }
  }) as T;
}

Problem 31 — Deep equal

function deepEqual(a: any, b: any): boolean {
  if (a === b) return true;
  if (a == null || b == null) return false;
  if (typeof a !== typeof b) return false;
  if (typeof a !== 'object') return false;
  if (Array.isArray(a) !== Array.isArray(b)) return false;
  const ka = Object.keys(a), kb = Object.keys(b);
  if (ka.length !== kb.length) return false;
  return ka.every(k => deepEqual(a[k], b[k]));
}

Problem 32 — Retry wrapper (with exponential backoff)

SDET-flavoured. Wrap an async function so it retries on failure.

async function retry<T>(
  fn: () => Promise<T>,
  opts: { attempts: number; baseMs: number } = { attempts: 3, baseMs: 100 }
): Promise<T> {
  let last: unknown;
  for (let i = 0; i < opts.attempts; i++) {
    try { return await fn(); }
    catch (e) {
      last = e;
      await new Promise(r => setTimeout(r, opts.baseMs * 2 ** i));
    }
  }
  throw last;
}

// Use it
await retry(() => fetch('/api/flaky').then(r => r.json()), { attempts: 5, baseMs: 200 });

Problem 33 — Flatten nested array

function flatten(arr: any[]): any[] {
  return arr.reduce((acc, v) => acc.concat(Array.isArray(v) ? flatten(v) : v), []);
}
// or: arr.flat(Infinity)

Problem 34 — Polyfill Array.prototype.map

function myMap<T, R>(arr: T[], fn: (v: T, i: number, arr: T[]) => R): R[] {
  const out: R[] = [];
  for (let i = 0; i < arr.length; i++) out.push(fn(arr[i], i, arr));
  return out;
}

Problem 35 — Implement a simple Promise.all

function pAll<T>(promises: Promise<T>[]): Promise<T[]> {
  return new Promise((resolve, reject) => {
    const out: T[] = new Array(promises.length);
    let done = 0;
    if (!promises.length) return resolve([]);
    promises.forEach((p, i) => {
      Promise.resolve(p).then(
        v => { out[i] = v; if (++done === promises.length) resolve(out); },
        reject
      );
    });
  });
}

Problem 36 — Validate parentheses with brackets and types

Variant: support (), [], {} with content rules (e.g. matching tags).

function isMatched(s: string, openers = '([{', closers = ')]}'): boolean {
  const pair = new Map([...closers].map((c, i) => [c, openers[i]]));
  const stack: string[] = [];
  for (const ch of s) {
    if (openers.includes(ch)) stack.push(ch);
    else if (pair.has(ch)) { if (stack.pop() !== pair.get(ch)) return false; }
  }
  return !stack.length;
}

63.X SDET interview wisdom (the soft skill)

• Explain before you code. 30 seconds of clarification > 5 min of wrong code.
• Pseudo-code first if stuck. Get the shape right, fill in syntax.
• State complexity unprompted. Always say time + space at the end.
• Test by hand on the given example AND a tricky one. Empty, single, all-same, negatives.
• If you don't know an API, say so and write a stub. They want to see thinking, not memorisation.
• For SDET-specific rounds: if asked "how would you test this function" — list cases (happy, edge, negative), then write 2-3 test cases using Jest/Vitest syntax. Show test mindset, not just algorithmic mindset.