Coding interview patterns

Sorted order gives each comparison a direction: a sum below the target is only fixable by advancing the low end, one above only by retreating the high end. With unsorted input no move is provably safe, so the scan could skip the answer.

Both cursors only move forward and neither restarts, so each takes at most n steps in total — roughly 2n operations. Nested loops cost O(n^2) because the inner one restarts from scratch; two monotone cursors inside one loop never do.

A partition pass guarantees only a two-region split: everything left of the boundary is at most the pivot value, everything right is at least it. Neither region is sorted, and the two sides need not be the same size.

The invariant: if any qualifying pair exists, at least one still lies inside the window between the pointers. Each move discards only pairs proven impossible — a too-small sum condemns every pair through the low element — so no answer is ever skipped.

Slow marks the last slot already written — the end of the kept prefix, not the next free one. Positions 0 through slow hold distinct timestamps, so the surviving length is slow + 1, and an empty log needs its own guard.

Adjacent windows differ by exactly two elements, so a rolling sum adds the entering value and subtracts the leaving one in constant time instead of re-adding all k. Across n slides that is O(n) total work rather than O(n·k).

A running sum suffices when the answer is a single reversible total, like hours worked. A per-key frequency map is needed when the answer depends on which distinct keys are present, not just on a total.

The right edge grows every iteration to admit the next element; the left edge shrinks only when the window's constraint is violated, advancing until the window is valid again. Growth explores; shrinking repairs.

Because both pointers only move forward. The right pointer takes at most n steps and the left pointer at most n steps across the entire scan, so total work is bounded by about 2n pointer moves — O(n).

Only two symbols change per slide, so rather than comparing whole count tables you keep a tally of how many symbols disagree with the target counts and adjust it for those two. The window matches when the tally is zero.

A singly linked chain has no backward pointers, so nothing can walk from the tail inward. The standard fix splits the chain at the middle, reverses the back half in place, then compares the two halves node by node.

The step must be deterministic and side-effect-free, must give every reachable state exactly one successor over a finite set, and must be cheap to re-evaluate. Branching states, or a walk that can simply end, invalidate the two-pointer loop.

Use a visited set when the state count is small, when the step is expensive enough to want each transition computed once, or when the report must name the looping states. Use two pointers when memory is the binding constraint.

With finitely many values, among the first N+1 terms two must be equal — pigeonhole. Because the step depends only on the current value, that repeat locks the sequence into a loop forever: tail, then cycle.

Every slot holds exactly one valid index, so each position has exactly one successor over finitely many positions. That deterministic walk can never end and can never avoid revisiting a position, so it must fall into a loop.

Sorting by start guarantees any interval that could overlap the one being built arrives before the pass moves past it. In arrival order, an overlapping slot can appear after you already emitted an interval, so a single pass misses merges.

Two half-open intervals overlap exactly when a.start < b.end and b.start < a.end. That pair of strict comparisons is the negation of the only two ways intervals can miss each other: one finishing at or before the other begins.

A sweep line throws away the intervals and keeps only their boundaries: +1 at each login coordinate, -1 at each logout. Sort those events by coordinate, scan once with a running sum, and remember the largest sum seen.

Sorting by start does not order the ends, so the next interval can be fully contained in the open one. Assigning next.end there truncates coverage that the input actually had; max keeps the furthest end seen and handles containment with no special case.

Sort the flights by start time, then walk them keeping every currently-running end time in a min-heap. Before each flight, pop all end times at or before its start; push its own end. The largest heap size seen is the answer.

A difference array stores the gap between neighbouring entries. Adding v at index l and subtracting v at index r+1 raises the running total by v for exactly positions l through r, and one prefix pass turns those two marks back into real values.

Keep a running total of the signed deltas and a map counting how often each running total has already appeared. Two positions with the same running total bracket a stretch that nets to zero, so each earlier match adds one more qualifying stretch.

A prefix array stores running cumulative totals, so any range sum becomes one subtraction: the total over positions l..r equals P[r+1] - P[l]. The extra leading slot holds 0, so ranges that begin at index 0 need no special case.

Without a seeded entry for total 0, every qualifying stretch that begins at the first element is lost. Those stretches need the running total from before any element was read, and the only way the map can offer it is to record total 0 once up front.

Taking running sums and taking successive differences undo each other, so either transform recovers the original array. That duality splits the work: prefix arrays make reads cheap and writes useless, difference arrays make range writes cheap and defer all reading to one pass.

A reading older and smaller than the newest one can never win again: every remaining window that contains it also contains that newer, larger reading. Being dominated, it is evicted from the back and never revisited.

The stack holds indices of items still waiting for a greater value to their right, kept in decreasing order of value. Each new item answers every stacked index it beats, then is pushed itself.

Each position is appended to the candidate list exactly once and removed at most once, so the inner eviction loop performs at most n removals across the entire scan. Total work is linear even though a single step can evict many candidates.

A rectangle needs both edges. The right edge stays unknown until a shorter bar arrives, and that arrival is exactly what triggers the pop; the left edge is the bar left underneath on the stack. Only at pop time are both known.

Every index is pushed exactly once and popped at most once, so the inner while loop runs at most n times in total across the scan. Total work is linear even though one step may pop many indices.

Choose by what you must read back later. A set answers only "have I seen this?". A counter map answers "how many times?". A key-to-index map answers "where did it first appear?". Store the least that answers your question.

A cue narrows the pattern family: sorted input points to converging pointers or binary search, a longest contiguous stretch points to a sliding window or prefix sums, and 'next stronger later value' points to a monotonic stack.

Hashing scatters keys, so a hash map holds no ordering. It answers exact-key lookups in expected O(1) but cannot find the nearest smaller key without inspecting every entry — an O(n) scan. Predecessor and range queries need an order-preserving structure.

The interleaving decides, not the graph. If edges arrive between queries, union-find answers each merge and check in amortized near-constant time. If the edge set is known up front, one traversal labels every component and each check is a label comparison.

The shrinking window assumes the total only rises when you extend right and only falls when you advance the left edge. Negative values break that monotonicity, so a discarded left endpoint can still belong to the answer.

Cyclic sort moves every value v to index v-1, so once placement finishes index i must hold i+1. The first index that breaks that rule names the absent value outright, with no extra lookup structure.

Every swap parks one value permanently on its home index, and a settled index is never disturbed again. So total swaps are capped by the slot count, and the cursor advances at most that many times — linear overall.

An index-based guard spins forever on duplicates: two slots holding the same value swap identical contents while the cursor never advances. Comparing the current value against what already sits at its home fires the skip branch and guarantees progress.

Reject it when the values are not a dense bounded range, or when the buffer is read-only, shared, or must keep its arrival order. Recognising the missing license is the actual skill the question tests.

The naive loop has n^n equally likely execution paths but only n! orderings, and n! does not divide n^n. Some orderings therefore come out more often than others, however good the random source is.

Keeping the i-th item with probability k/i, and evicting a uniformly chosen resident, holds the invariant that after i items each is held with probability k/i. That holds at every prefix, so the length is never needed.

Randomizing moves the bad case from the input to the coin. The worst-case bound is unchanged, but no fixed input triggers it reliably any more: expected cost becomes good for every input, not only for inputs assumed to be unordered.

A Las Vegas algorithm is always correct with variable runtime; a Monte Carlo one has bounded cost and a chance of being wrong. Figures that must reconcile exactly can absorb a late finish, never a wrong number.