DSA & Algorithms

Naive: nested loop, O(n²). Optimal: process right-to-left maintaining a sorted structure (BIT/Fenwick tree or merge-sort during count) for O(n log n). Explain both; the brute force is usually accepted but mention the optimization.

Two-step: in-order traversal produces a sorted array of node values, then build a balanced BST from that array by recursively picking the middle as the root. O(n) time, O(n) space. Result is a height-balanced BST (not necessarily an AVL/RB) — height ⌈log₂(n+1)⌉.

Catch-all category. Common forms: shortest path (BFS for unweighted, Dijkstra for weighted, Bellman-Ford for negative edges, A* with heuristic), minimum spanning tree (Kruskal/Prim), max-flow/min-cut (Ford-Fulkerson), strongly connected components (Tarjan/Kosaraju), topological sort (DFS or Kahn). Recognize the problem shape, then pick the algorithm.

A general technique question: start with a correct brute force, analyze its complexity to find the bottleneck, then apply a pattern — hashing for lookups, sorting, two pointers, sliding window, precomputation/prefix sums, memoization/DP, or better data structures — to cut redundant work.

Maintain a window [l, r] over an array/string; expand by moving r, shrink by moving l when the window violates a constraint. Turns O(n²) brute force into O(n) for problems like 'longest substring without repeating chars', 'min window substring', and 'max sum of subarray of size k'.

Use the two-pointer technique: one pointer from each end moving inward, comparing characters. O(n) time, O(1) space — no reversal, no extra allocation. Clarify whether to normalize case/whitespace/punctuation first.

Run a single BFS/DFS from any node and check whether every node was visited. O(V+E). For directed graphs, distinguish weak vs strong connectivity (strong needs Kosaraju/Tarjan or a check from one node on both the graph and its transpose).

Walk both lists in lockstep with two pointers; at each step compare values; return false on first mismatch or unequal length. O(min(m,n)) time, O(1) space. Variants: compare for value-equality regardless of node identity; deep-compare lists of lists (recursion); compare cyclic lists (detect cycle with Floyd's, then compare lengths + values).

Count character frequencies in one pass, then scan the string again and return the first character with a count of 1. O(n) time, O(k) space where k is the alphabet size.

Reduce into a Map (or plain object): for each element, increment its count. `new Map` if keys may be objects or non-strings; object literal if all keys are strings/numbers (faster lookup, JSON-friendly). `Object.create(null)` to avoid prototype-chain key collisions like `__proto__`.

Sliding window with a Map<char, lastIndex>. Move right pointer through the string; when the current char's last index is within the window, jump left to one past it; track max window size as you go. O(n) time, O(min(n, alphabet)) space.

Fixed-size sliding window: compute the first window's sum, then slide by adding the incoming element and subtracting the outgoing one. O(n) time, O(1) space — no need to recompute each window.

Three approaches: (a) sort and slice — O(n log n), simplest, fine for small n; (b) min-heap of size k — O(n log k), best when n ≫ k; (c) Quickselect — O(n) average, O(n²) worst, in-place. Pick by data size + whether you need elements in sorted order.

For each node in a binary tree, point its `next` to the node immediately to its right at the same level (or null if last). Two approaches: BFS using a queue (O(n) time, O(n) space); level-by-level traversal using the `next` pointers built in previous levels for O(1) extra space (the canonical perfect-tree solution).

Dedupe with a Set, then sort. One-liner: [...new Set(arr)].sort((a,b)=>a-b). The catch interviewers test: default .sort() is lexicographic, so you MUST pass a numeric comparator for numbers.

Three approaches: (1) sort and index — O(n log n), simple; (2) min-heap of size k — O(n log k); (3) Quickselect — average O(n), worst O(n²). For most interviews say 'min-heap of size k' (clean, predictable) or Quickselect (best average).

Find the max in every window of size k. Use a deque storing indices in decreasing-value order: each element is pushed and popped at most once, giving O(n) time, O(k) space — versus O(n*k) brute force or O(n log n) with a heap.

Classic multi-source BFS on a grid (a.k.a. 'rotting oranges'). Seed a queue with ALL initial zombie cells at once, then BFS level by level — each level is one time unit. Track minutes as you process levels; mark cells visited as you infect them. At the end, if any human remains, return -1. Time O(rows×cols), space O(rows×cols).

Given a string `s` and a dictionary, return all ways to segment `s` into dictionary words. DFS/backtracking with memoization on the suffix: for each position, try every dictionary word that matches the prefix and recurse on the remainder; cache results by start index. Time worst-case exponential; memoization makes practical inputs tractable.

Stacks: LIFO — undo/redo, browser history, balanced parens, expression eval, DFS, monotonic stack (next-greater-element). Queues: FIFO — BFS, task scheduling, event loops, request batching, sliding-window-max via a deque. In JS both are arrays with push/pop or push/shift (or a deque-like structure).

Trees model hierarchy (DOM, file systems, comment threads, nested menus, category trees, virtual DOM). BSTs come up rarely in frontend; you're more often using ordered structures like indexed/keyed maps. Most frontend tree work is traversal (DFS/BFS), recursion, and tree-flatten/find/transform.

Classic: find a target in a sorted array in O(log n). Variants: first/last occurrence, lower/upper bound, search in rotated sorted array, search the answer (binary search on a predicate over a range — capacity, threshold). The pattern is 'monotonic predicate over an index range'.

Use two pointers when scanning a sorted array or linked list and a nested loop would be O(n²). Variants: opposite ends converging (sorted two-sum, palindrome, container with most water), and fast/slow (cycle detection, middle of list). Turns O(n²) into O(n) with O(1) space.

BFS (queue): shortest path in an unweighted graph, level-order, 'closest match'. DFS (stack/recursion): connectivity, cycle detection, topological sort, path enumeration, backtracking. BFS uses more memory (frontier width); DFS uses less but can recurse deep. Both must track visited.