The DSA round

The shape generalises: expand end every iteration, shrink start while the window is invalid, record the answer. The only thing that changes between problems is what "invalid" means and what state you keep — a count map, a sum, a set.

function longest(s) {
  const last = new Map()      // char → last index seen
  let start = 0, best = 0
  for (let end = 0; end < s.length; end++) {
    const c = s[end]
    // only move start forward, never back
    if (last.has(c) && last.get(c) >= start) start = last.get(c) + 1
    last.set(c, end)
    best = Math.max(best, end - start + 1)
  }
  return best
}
// O(n) time, O(min(n, alphabet)) space

The tie-break in that sort is the whole problem: at the same timestamp, an ending meeting must be processed before a starting one, or a room that just freed up gets double-counted. That is the same half-open [start, end) reasoning from the machine coding round — say so, and connect it to the booking system you built.

function merge(intervals) {
  if (!intervals.length) return []
  intervals.sort((a, b) => a[0] - b[0])        // sort by start — always step one
  const out = [intervals[0]]
  for (const [s, e] of intervals.slice(1)) {
    const last = out[out.length - 1]
    if (s <= last[1]) last[1] = Math.max(last[1], e)   // overlap → extend
    else out.push([s, e])
  }
  return out
}
// O(n log n) — the sort dominates

// sweep line: +1 at every start, -1 at every end, take the running max
function minRooms(meetings) {
  const events = []
  for (const [s, e] of meetings) { events.push([s, 1]); events.push([e, -1]) }
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1])   // end before start at equal time
  let cur = 0, best = 0
  for (const [, d] of events) { cur += d; best = Math.max(best, cur) }
  return best
}

Say out loud why this is O(1): a JavaScript Map guarantees insertion order, and delete plus set is the cheapest way to move a key to the most-recent end. That is language fluency, not a shortcut — but be ready to give the canonical version too, because some interviewers want it.

The canonical answer: a hash map from key to node, plus a doubly linked list with sentinel head and tail. The map gives O(1) lookup; the list gives O(1) move-to-front and O(1) eviction from the tail. The sentinels exist so you never write a null check for the empty case.

class LRU {
  constructor(cap) { this.cap = cap; this.m = new Map() }

  get(k) {
    if (!this.m.has(k)) return -1
    const v = this.m.get(k)
    this.m.delete(k); this.m.set(k, v)     // re-insert → moves to the end
    return v
  }

  put(k, v) {
    if (this.m.has(k)) this.m.delete(k)
    this.m.set(k, v)
    if (this.m.size > this.cap) {
      this.m.delete(this.m.keys().next().value)   // first key = least recent
    }
  }
}

• Deep flatten to a given depth, without Array.prototype.flat. Recursive, plus the iterative stack version for when they say "no recursion".
• Deep clone with circular references — the WeakMap of seen objects from R3.
• Promise.all from scratch — asked constantly. Index order and the empty array.
• A promise pool with concurrency N — the highest-value one to have ready.
• Retry with exponential backoff and jitter.
• An event emitter with on, off, once, emit. Watch the bug: removing a listener during emit while iterating the live array skips the next one — iterate a copy.
• memoize with a configurable key resolver and a Map cache.
• pipe / compose — const pipe = (...fns) => x => fns.reduce((v, f) => f(v), x).
• Debounce and throttle, with cancel and trailing edge.
• A deep equality function — handle arrays, dates, NaN, and different key counts.
• Chunk an array and group by — trivial, but asked as warm-ups.
• Curry a function of arbitrary arity — fn.length is how you know when it is saturated.

class Emitter {
  #m = new Map()
  on(e, fn) { (this.#m.get(e) ?? this.#m.set(e, new Set()).get(e)).add(fn); return () => this.off(e, fn) }
  off(e, fn) { this.#m.get(e)?.delete(fn) }
  once(e, fn) { const w = (...a) => { this.off(e, w); fn(...a) }; this.on(e, w) }
  emit(e, ...a) { for (const fn of [...(this.#m.get(e) ?? [])]) fn(...a) }
  //                              ^ copy, so off() during emit is safe
}

1. Restate the problem and confirm one edge case. Buys thirty seconds and stops you solving the wrong thing.
2. Give the brute force out loud with its complexity. Never sit in silence — an interviewer cannot score thinking they cannot hear.
3. Name what makes it slow. "The inner loop re-scans what I have already seen — that is usually a hash map." "The input is sorted and I am scanning linearly — that is usually two pointers or binary search."
4. State the approach and the complexity before you type, and get agreement. If they say "can you do better than O(n log n)", you have just saved fifteen minutes.
5. Write it, then dry-run it out loud on a small input — including an empty input and a single element. Finding your own off-by-one is worth more than not having one.

Following that script with a working brute force scores better than a silent optimal solution. And if you are genuinely stuck, say so and ask for a hint — it costs a little, and burning ten minutes in silence costs the round.

Most complexity mistakes in this round are not in your loops. They are in a built-in method you called inside a loop and assumed was free. Know these without pausing:

Space is the half people forget. Recursion uses a stack frame per level, so a recursive DFS down a path-shaped tree is O(n) space even though you allocated nothing. And if they ask about auxiliary space, the output array does not count — say which one you mean.

// 1. looks O(n). Is O(n²) — includes is a scan.
const unique = []
for (const x of arr) if (!unique.includes(x)) unique.push(x)

// 2. looks O(n). Is O(n²) — the spread copies acc every time.
const doubled = arr.reduce((acc, x) => [...acc, x * 2], [])

// 3. looks O(n²). Is O(n) — start only ever moves forward.
let start = 0, sum = 0
for (let end = 0; end < arr.length; end++) {
  sum += arr[end]
  while (sum > k) sum -= arr[start++]   // non-negative input
}

The third one is worth being able to argue: the inner while looks like a nested loop, but start only moves forward, so across the whole run it moves at most n times. Counting how many times each element is touched in total, rather than per iteration, is amortised analysis — and it is exactly the sentence they want to hear.

The instinct is a sliding window, and here it is wrong. A window only works when growing it moves the sum in one direction; with negative numbers, adding an element can make the sum smaller, so you never know whether to shrink. Say that out loud — spotting why the obvious pattern fails is most of the marks.

The move is prefix sums. If the running sum up to index j is P[j], the subarray from i + 1 to j sums to P[j] − P[i]. So a subarray ending at j sums to k exactly when some earlier prefix equals P[j] − k. Count every prefix you have seen, and each step is one lookup.

function countBrute(nums, k) {
  let count = 0
  for (let i = 0; i < nums.length; i++) {
    let sum = 0
    for (let j = i; j < nums.length; j++) {
      sum += nums[j]
      if (sum === k) count++
    }
  }
  return count
}

function subarraySum(nums, k) {
  const seen = new Map([[0, 1]])      // the empty prefix: subarrays that start at index 0
  let sum = 0, count = 0
  for (const x of nums) {
    sum += x
    count += seen.get(sum - k) ?? 0   // earlier prefixes that make this one work
    seen.set(sum, (seen.get(sum) ?? 0) + 1)
  }
  return count
}
// [1, -1, 1], k = 1  →  3

Two details to volunteer. The [0, 1] seed is the one everybody forgets, and without it you miss every subarray that starts at index 0. And the order of the two lines inside the loop matters: look up first, then record the current prefix — the other way round, with k = 0, you count an empty subarray at every step.

The same idea solves a family: the longest subarray with sum k (store the first index of each prefix instead of a count), subarrays divisible by k (store sum % k, normalised because % can be negative in JavaScript), and the longest run with equal zeros and ones (count 0 as −1). Naming the family shows recognition rather than memory.

Do not memorise five variants. Memorise one — lower bound, the first index where arr[i] >= target — and derive the rest from it. Exact match, last occurrence, insert position and count of a value are each a line on top of it.

Use a half-open range [lo, hi) and a single rule: if mid could be the answer, keep it (hi = mid); if it cannot, discard it (lo = mid + 1). The loop ends when lo === hi, and that is the answer, with nothing to patch afterwards.

function lowerBound(arr, target) {
  let lo = 0, hi = arr.length              // half-open: hi is one past the end
  while (lo < hi) {
    const mid = (lo + hi) >>> 1            // integer midpoint — / 2 gives a float in JS
    if (arr[mid] < target) lo = mid + 1    // too small, cannot be the answer
    else hi = mid                          // might be the answer — keep it
  }
  return lo                                // arr.length if everything is smaller
}

// everything else is lowerBound plus one line
const indexOf = (a, t) => { const i = lowerBound(a, t); return a[i] === t ? i : -1 }
const upperBound = (a, t) => lowerBound(a, t + 1)     // integers only
const countOf = (a, t) => upperBound(a, t) - lowerBound(a, t)

Say why each boundary is what it is, because that is what they are checking. hi starts at arr.length, not length − 1, so "insert at the end" is a possible answer. lo = mid + 1 always moves, and hi = mid always shrinks the range because mid < hi, so the loop cannot stall. Then dry-run it on an empty array and on a target larger than everything.

Rotated sorted arrays, peak finding and binary search on the answer (in the ₹50L section) are the same loop with a different test inside the if. The test changes; the boundaries do not.

Walk the grid. Every time you meet land you have not visited, that is a new island: count it, then flood-fill everything connected so it is never counted again. O(rows × cols) time, because each cell is touched a constant number of times.

Recursive DFS is the shortest to write and the first thing to break. A grid that is one long snake of land recurses once per cell, and Node's stack gives out somewhere around ten thousand frames — a 200 × 200 grid can do it. Say that before they ask, then write the iterative version:

function numIslands(grid) {
  const R = grid.length, C = grid[0]?.length ?? 0
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
  let islands = 0

  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (grid[r][c] !== '1') continue
      islands++
      grid[r][c] = '0'                          // mark when you enqueue, not when you dequeue
      const queue = [[r, c]]
      for (let head = 0; head < queue.length; head++) {   // a pointer, not queue.shift()
        const [cr, cc] = queue[head]
        for (const [dr, dc] of dirs) {
          const nr = cr + dr, nc = cc + dc
          if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] === '1') {
            grid[nr][nc] = '0'
            queue.push([nr, nc])
          }
        }
      }
    }
  }
  return islands
}

Three details that score. Mark on enqueue: marking on dequeue lets the same cell enter the queue several times from different neighbours. A head pointer instead of shift(), because shift is O(n) and makes the BFS quadratic on a big grid. And ask before mutating the input — overwriting the grid is the no-extra-space answer, but if the caller needs it back, keep a separate visited array and say what it costs.

The same skeleton does Rotting Oranges (start the queue with every rotten cell at once — multi-source BFS), the shortest path through a binary maze (BFS finds shortest paths in unweighted grids; DFS does not), and Surrounded Regions (flood from the border first).