DSA at the ₹50L bar

Almost every graph question is one of four things wearing a costume. Learn to see the costume.

• BFS — shortest path in an unweighted graph, level-by-level processing, "minimum number of steps".
• DFS — connectivity, cycle detection, flood fill, "can I reach", path enumeration.
• Topological sort — anything with dependencies or ordering. Course Schedule, build systems, task ordering. If the words "prerequisite", "depends on" or "order" appear, this is it.
• Union-Find — connected components under incremental merging. Number of Provinces, Redundant Connection, Kruskal's MST, and the "are these two in the same group" family.

function topo(n, edges) {
  const adj = Array.from({length:n}, () => [])
  const indeg = new Array(n).fill(0)
  for (const [a, b] of edges) { adj[a].push(b); indeg[b]++ }   // a → b

  const q = []
  for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i)

  const out = []
  while (q.length) {
    const v = q.shift()
    out.push(v)
    for (const nx of adj[v]) if (--indeg[nx] === 0) q.push(nx)
  }
  return out.length === n ? out : null   // short → a cycle exists
}
// O(V + E). Use a pointer instead of shift() for real performance.

class DSU {
  constructor(n) { this.p = [...Array(n).keys()]; this.r = new Array(n).fill(0) }
  find(x) {
    while (this.p[x] !== x) { this.p[x] = this.p[this.p[x]]; x = this.p[x] }  // path halving
    return x
  }
  union(a, b) {
    let ra = this.find(a), rb = this.find(b)
    if (ra === rb) return false                       // already connected → a cycle
    if (this.r[ra] < this.r[rb]) [ra, rb] = [rb, ra]  // union by rank
    this.p[rb] = ra
    if (this.r[ra] === this.r[rb]) this.r[ra]++
    return true
  }
}
// near O(1) amortised per operation

Practise: Number of Islands · Course Schedule I & II · Clone Graph · Rotting Oranges · Word Ladder · Pacific Atlantic Water Flow · Number of Provinces · Redundant Connection · Accounts Merge · Alien Dictionary.

The two things interviewers watch for: do you build the adjacency list cleanly, and do you handle the disconnected graph — a single BFS from node 0 misses everything else, so the outer loop over all nodes is not optional.

The if (d > dist[u]) continue line is the whole trick: JavaScript has no decrease-key, so you push duplicates and skip the stale ones when they surface. Candidates who omit it get a correct but slow solution and usually cannot explain why.

When Dijkstra is wrong: negative edge weights — it will silently return the wrong answer, not fail. That is Bellman-Ford's territory (and it detects negative cycles). For unweighted graphs BFS is simpler and faster. For a grid with 0/1 weights, 0-1 BFS with a deque beats a heap.

function dijkstra(n, adj, src) {          // adj[u] = [[v, w], ...]
  const dist = new Array(n).fill(Infinity)
  dist[src] = 0
  const pq = new MinHeap([[0, src]])       // [distance, node]

  while (pq.size) {
    const [d, u] = pq.pop()
    if (d > dist[u]) continue              // stale entry — the lazy-deletion trick
    for (const [v, w] of adj[u]) {
      if (d + w < dist[v]) { dist[v] = d + w; pq.push([d + w, v]) }
    }
  }
  return dist
}
// O((V + E) log V)

• Top K largest. Keep a min-heap of size K. Counter-intuitive and always asked: you pop the smallest, so what remains is the K largest. O(n log k), which beats sorting when k is small.
• Merge K sorted lists. A heap holding the current head of each list. O(N log k).
• Median from a data stream. Two heaps — a max-heap of the lower half, a min-heap of the upper half, kept balanced within one element. The median is a heap top or the average of two. This is the classic hard-flavoured question and it is entirely learnable.

class MedianFinder {
  lo = new MaxHeap()   // lower half
  hi = new MinHeap()   // upper half

  add(x) {
    this.lo.push(x)
    this.hi.push(this.lo.pop())              // funnel through, keeps order correct
    if (this.hi.size > this.lo.size) this.lo.push(this.hi.pop())
  }
  median() {
    return this.lo.size > this.hi.size
      ? this.lo.peek()
      : (this.lo.peek() + this.hi.peek()) / 2
  }
}

JavaScript has no built-in heap, so write one before the interview and know it cold — sift-up, sift-down, and the array-as-tree indexing (parent = (i-1) >> 1, children 2i+1, 2i+2). Spending fifteen of your forty minutes writing a heap from scratch is how this round is lost.

Practise: Kth Largest Element · Top K Frequent · Merge K Sorted Lists · Find Median from Data Stream · Task Scheduler · Reorganize String.

Every DP question is three decisions: what is the state, what is the transition, what is the base case. Get the state right and the rest usually falls out. The recognisable families:

function editDistance(a, b) {
  const m = a.length, n = b.length
  const dp = Array.from({length:m+1}, () => new Array(n+1).fill(0))

  for (let i = 0; i <= m; i++) dp[i][0] = i     // delete everything
  for (let j = 0; j <= n; j++) dp[0][j] = j     // insert everything

  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] = a[i-1] === b[j-1]
        ? dp[i-1][j-1]
        : 1 + Math.min(dp[i-1][j-1],   // replace
                       dp[i-1][j],     // delete
                       dp[i][j-1])     // insert
  return dp[m][n]
}
// O(mn) time, O(mn) space — then say: "this rolls to O(n) space,
// because row i only depends on row i-1"

The method that works in the room, and say it out loud in this order: write the brute-force recursion first → identify the repeated subproblem → memoise it (top-down) → only then convert to a table (bottom-up) if they ask. Jumping straight to a table is how people freeze. Memoised recursion is a complete, acceptable answer.

Trie — prefix problems. Autocomplete, word search in a grid, "does any word start with", longest common prefix, and the surprisingly common XOR-maximum trick with a binary trie. Node is { children: Map, isWord: boolean }; insert and search are both O(word length).

Backtracking — build a candidate, recurse, undo. One template covers permutations, combinations, subsets, N-Queens, Sudoku and Word Search. The two scoring details are pruning early and handling duplicates (sort first, then skip i > start && nums[i] === nums[i-1]).

function subsets(nums) {
  const out = [], cur = []
  ;(function go(start) {
    out.push([...cur])                // copy — pushing cur pushes a reference
    for (let i = start; i < nums.length; i++) {
      cur.push(nums[i])
      go(i + 1)
      cur.pop()                       // undo — this is the "backtrack"
    }
  })(0)
  return out
}

function nextGreater(nums) {
  const res = new Array(nums.length).fill(-1)
  const st = []                       // holds INDICES, decreasing values
  for (let i = 0; i < nums.length; i++) {
    while (st.length && nums[st[st.length-1]] < nums[i]) res[st.pop()] = nums[i]
    st.push(i)
  }
  return res
}
// O(n) — each index is pushed once and popped once

Monotonic stack is the one people never recognise. The signal is "next/previous greater or smaller element", and it unlocks Daily Temperatures, Largest Rectangle in Histogram, Trapping Rain Water and Sum of Subarray Minimums — all of which look hard and are the same six lines. Its sibling, the monotonic deque, does Sliding Window Maximum in O(n).

When the answer is a number in a range, and you can check a candidate answer in linear time, and the check is monotonic (if X works then X+1 works), you can binary search the answer space instead of the array.

function minSpeed(piles, hours) {
  const can = (k) => piles.reduce((h, p) => h + Math.ceil(p / k), 0) <= hours

  let lo = 1, hi = Math.max(...piles)
  while (lo < hi) {
    const mid = (lo + hi) >> 1
    if (can(mid)) hi = mid       // mid works — it might be the answer, keep it
    else lo = mid + 1
  }
  return lo
}
// O(n log(max)) — the log is over the ANSWER range, not the input

The template detail worth drilling: while (lo < hi) with hi = mid and lo = mid + 1 converges without an off-by-one and needs no post-loop adjustment. Practise it until you never have to think about the boundary again — boundary bugs under time pressure are how this round is actually lost.

Practise: Koko Eating Bananas · Capacity to Ship Packages · Split Array Largest Sum · Minimise Max Distance · Median of Two Sorted Arrays (the genuinely hard one).

Around 150 problems, done properly. Properly means: attempt for 25 minutes, then read the solution rather than grinding for two hours; write it yourself from scratch afterwards; and redo it a week later from memory. That last step is the one everybody skips and it is where the retention actually comes from.

Four focused hours a week beats twenty unfocused ones. And do the last three weeks with a timer and a whiteboard, out loud, because solving in an IDE in silence trains a different skill than the one being tested.

They chose a problem you have not seen on purpose. The score is not "solved / did not solve"; it is how far you got and how you moved.

1. Restate it and give one concrete example with real numbers. Confirm the example's expected output with them. Roughly a third of failures are solving a slightly different problem.
2. Say the brute force and its complexity within three minutes. You now have a working answer on the board and the pressure drops.
3. Name what is redundant. "I am recomputing the same range" → prefix sums or DP. "I am re-scanning for something I already saw" → hash map. "The input is sorted and I am not using it" → two pointers or binary search. Say these out loud; interviewers give hints to people who are visibly close.
4. Ask for a hint at the twenty-minute mark if you are stuck. It costs a little. Twenty-five minutes of silence costs the round.
5. Code the best idea you have, even if suboptimal, then dry-run it on your example. Working and O(n²) beats elegant and unfinished — every time.

The trap to avoid: recognising the problem, half-remembering the clever solution, and trying to reproduce it from memory. That fails badly and visibly. Derive it, out loud, from the brute force — even if you know the trick, walking there is what gets scored.