Data Structures & Algorithms Quiz

The sequential loops contribute O(n) + O(n) and the nested loop contributes O(n²); the total is O(2n + n²), which simplifies to O(n²) because Big-O keeps only the dominant term and drops constant factors. Writing O(2n + n²) as a final answer is a classic sign of not simplifying.

Brute force asks, for each element, 'is its complement anywhere else?' — an O(n) scan inside an O(n) loop, so O(n²). A hash map answers that membership question in O(1) average time, collapsing the search to a single pass. Trading O(n) extra memory for a per-step O(n)→O(1) lookup improvement is the most reusable trick in coding interviews.

Keep a min-heap holding the k largest seen so far; its root is the smallest of them — the threshold. Each new element is compared against the root, and if larger, replaces it in O(log k). Memory stays O(k) regardless of stream size. The counterintuitive part interviewers watch for: you track the k LARGEST with a MIN-heap, because you need cheap access to the weakest member.

BFS explores level by level — all nodes at distance 1, then 2, and so on — so a node's first discovery is guaranteed to be along a minimum-edge path. DFS plunges down one branch arbitrarily deep and may first reach a node by a long detour. For weighted graphs this level argument breaks, which is where Dijkstra's algorithm comes in.

Halving the search space only works if ordering tells you which half to discard — that requires sorted data (or more generally, a monotonic predicate). Each comparison halves the candidates, so n elements need at most ~log₂(n) steps. Many hard interview problems are binary search in disguise: 'binary search on the answer' applies whenever a yes/no condition is monotonic.

Two pointers only ever move forward: the right pointer advances n times, and the left pointer advances at most n times in total across the whole run. Amortized, that's O(n) even though the window shrinks and grows. Recognizing 'contiguous substring/subarray with a constraint' as a sliding-window signal is the pattern-matching skill being tested.

Optimal substructure means an optimal solution is built from optimal solutions to subproblems; overlapping subproblems means the naive recursion solves the same subproblems repeatedly, so caching them (memoization or tabulation) pays off. Without the overlap, plain divide-and-conquer suffices; without optimal substructure, cached sub-answers can't be combined correctly.

Bracket matching is last-opened-first-closed — exactly LIFO: push each opener, and each closer must match the most recent unmatched opener at the top of the stack. Maze shortest paths want BFS (a queue), FCFS scheduling is literally a queue, and streaming medians use two heaps. Mapping problem structure to data-structure discipline (LIFO vs FIFO) is the skill here.

Model courses as nodes and prerequisites as directed edges: a valid study order is a topological ordering, which exists if and only if the directed graph has no cycle. Kahn's algorithm (repeatedly removing zero-in-degree nodes) or DFS coloring both detect the cycle. 'Dependencies + is an ordering possible' should instantly read as topological sort.

Quicksort partitions in place (O(log n) auxiliary space vs mergesort's O(n) buffer) and scans memory sequentially, which caches love; with random pivot selection, hitting the O(n²) case is statistically negligible. Mergesort's wins are guaranteed O(n log n) and stability — it's the sort of choice for external sorting and linked structures. Note it's mergesort that's stable, not quicksort.

A trie stores strings character by character along paths from the root, so every word sharing a prefix shares that path. Walking the prefix takes O(prefix length) regardless of dictionary size, and the subtree below holds exactly the completions. Hash maps can't do prefix queries at all, and sorted arrays need O(log n) plus contiguous scans — the trie makes prefix lookup structural.

Once both pointers are in the cycle, the fast one gains one position per step on the slow one; a gap that shrinks by exactly 1 each step cannot skip over zero, so they must collide within one cycle length — regardless of parity. The follow-up interviewers love: after meeting, resetting one pointer to the head and advancing both one step at a time finds the cycle's entrance.

Sortedness makes each comparison informative: when arr[lo]+arr[hi] < target, no pair using arr[lo] can work (arr[hi] is already the largest partner), so lo can be discarded — and symmetrically for hi when the sum is too large. Each step eliminates one element with certainty, giving O(n) without checking all O(n²) pairs. Recognizing 'sorted input → two pointers / binary search' is one of the highest-value pattern matches in coding interviews.

Union-Find maintains a partition of elements into disjoint groups under two operations: union (merge two groups) and find (which group is this element in?). With path compression and union by rank, both are effectively O(1) amortized. It powers connected components in graphs, cycle detection in Kruskal's MST, and 'number of islands II'-style problems where connectivity changes dynamically — BFS/DFS would have to re-traverse after every change.

With capacity doubling, a copy of size n happens only after n cheap appends, so total work for n appends is n + (1+2+4+...+n) < 3n — constant per operation on average, even though a single append can be O(n). That is amortized analysis: bounding the average cost over a sequence, not the worst single operation. The same argument explains hash map resizing and why interviewers accept O(1) for both.

Every nested recursive call pushes a stack frame that lives until that call returns, so the peak is the deepest active chain — the tree height. A balanced tree costs O(log n) but a degenerate (linked-list-shaped) tree costs O(n), and a deep enough input overflows the stack — which is why 'convert it to an iterative version with an explicit stack' is a standard follow-up. Counting recursion's hidden space is a detail interviewers use to separate levels.

Greedy commits to the locally best move and never reconsiders — valid only when the problem has the greedy-choice property (as US coin denominations happen to). Arbitrary coin systems don't, so coin change needs DP, which considers all options per subproblem. In interviews, if you propose greedy, immediately probe for a counterexample; showing you know when greedy is safe matters more than knowing the greedy itself.

Backtracking is DFS over a decision tree: choose, recurse, un-choose. The un-choose step (restoring state after the recursive call) is what lets one shared path buffer explore an exponential space correctly — and forgetting it is the classic bug. Pruning invalid branches early (as in N-Queens or combination-sum with sorted candidates) is what separates workable backtracking from brute force.

One O(n) pass builds prefix[k] = sum of the first k elements; any range sum is then a single subtraction. This precompute-once, query-cheap pattern extends widely: 2D prefix sums for submatrix queries, prefix XOR, and the prefix-sum + hash-map trick behind 'count subarrays summing to k'. When a problem says 'many range queries', prefix sums (or Fenwick trees, if updates are needed) should come to mind immediately.

The stack holds elements still waiting for their answer, kept monotonic: when a new element arrives, it pops every smaller (or larger, depending on variant) element — for each popped element, the new one IS its next greater element. Every element is pushed and popped at most once, hence O(n) despite the nested-looking loop. Spotting 'nearest larger/smaller to the left/right' as a monotonic-stack signal turns several hard-rated problems into templates.