Data structures and algorithms fundamentals

An upper bound on how the cost grows as the input grows, with constant factors and lower-order terms deliberately discarded. So O(n) says the work grows roughly in proportion to the input, not that it takes n operations. Discarding the constants is what makes it useful for comparing algorithms and what makes it misleading in production, where an O(n log n) algorithm with a huge constant can lose to an O(n²) one at the sizes you actually run. State the bound, then say what the constants are doing if it matters.

Worst case is the cost on the least favourable input of that size, which is what Big-O usually reports. Average case assumes a distribution over inputs, which means it depends on an assumption you should state. Amortised is different in kind: it is the average per operation across a worst-case sequence, so it is a guarantee rather than a probabilistic claim. A dynamic array's append is amortised constant because the occasional doubling is paid for by the cheap appends around it.

Each doubling copies everything, which looks expensive until you total the copying across a whole sequence of appends.

appends:   1  2  3  4  5  6  7  8  9 ...
capacity:  1  2  4  4  8  8  8  8 16 ...
copies:    -  1  2  -  4  -  -  -  8 ...

Total copying to reach n elements: 1 + 2 + 4 + ... + n/2  <  n
So n appends cost fewer than 2n operations -> O(1) each, amortised.

The sum of a doubling series is less than its final term, which is the whole argument. Any growth factor greater than one gives the same result; growing by a fixed amount does not.

# Growing by one each time: every append copies everything.
# 1 + 2 + 3 + ... + n = n(n+1)/2 operations -> O(n) per append, O(n^2) total.

Two consequences worth carrying. Amortised constant is not the same as constant: a single append can take O(n), so it is the wrong guarantee for a real-time system where one slow operation matters more than a good average. And if you know the final size, preallocating avoids the copying entirely — the same reasoning that makes sizing a hash map at construction worthwhile.

Four recur. Naming the wrong n, when a problem has two dimensions such as rows and columns, or a list of strings where sorting costs comparisons times string length. Forgetting space the language allocates for you, particularly the recursion stack and the copies made by slicing. Confusing the cost of a call with the cost of what it does, so a membership test that is constant on a set and linear on a list looks identical in code. And stopping at the bound without checking it against the stated input limits.

They are given to you for free and eliminate whole families in a sentence. A limit of about twenty invites an exponential solution over subsets. A few thousand accommodates quadratic, which usually means a two-dimensional dynamic-programming table. A hundred thousand rules out quadratic and points at sorting, a single pass with a structure, or something logarithmic per element. A billion means you are not iterating at all and the answer is mathematical.

A property your code guarantees is true between steps — the window contains at most one of each character, everything left of the pointer is already sorted, the heap's root is the smallest element. It matters because it is the difference between an argument for correctness and a hope. A candidate who names the invariant has designed the solution; one who cannot has recalled it, and the distinction shows immediately when the interviewer changes a constraint.

That the work halves at each step, which is why binary search, balanced trees and heap operations all land there. The practical significance is how flat it is: doubling the input adds one step, so a structure with logarithmic operations scales to enormous sizes without meaningful slowdown. Log base is irrelevant in Big-O because changing base is a constant factor, which is why nobody writes log₂.

Count the work at each level and multiply by the number of levels — that single habit covers most divide-and-conquer analysis.

def merge_sort(items):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])      # T(n/2)
    right = merge_sort(items[mid:])     # T(n/2)
    return merge(left, right)           # O(n) to merge

level 0:  one problem of size n        -> n work
level 1:  two of size n/2              -> n work
level 2:  four of size n/4             -> n work
...
level k:  n problems of size 1         -> n work

Levels: how many halvings reach 1, which is log2(n).
Total:  n work per level x log n levels = O(n log n)

The space is the part people miss. The slicing in the code above copies at every level, so it allocates O(n log n) in total over the run. Peak live space is still O(n), because sibling calls are sequential rather than concurrent - the same order as an in-place merge sort's buffer, with a much worse constant and far more allocator pressure. The recursion stack adds O(log n) on top.

The same counting applies when the branching factor and the shrinkage differ. A recursion making two calls on n−1 has 2ⁿ nodes, which is why naive Fibonacci is exponential — the tree is wide and deep. Recognising that shape in a call tree is what tells you memoisation will collapse it.

Because it converts a nested scan into a single pass: instead of comparing every element with every other, you record what you have seen and look up in constant average time. That turns O(n²) into O(n) at the cost of memory, which is the trade almost every "optimise this" prompt is asking for. It is also the most common real fix in application code, where a membership test inside a loop over a list is the usual accidental quadratic.

Two distinct keys producing the same bucket index, which is unavoidable because the key space is larger than the table. Implementations resolve it by chaining entries in the bucket, or by probing for another slot. The consequence is that constant-time lookup is an average rather than a guarantee: with adversarial or pathological keys everything lands in one bucket and lookups degrade to linear, which is a real denial-of-service vector and why some languages randomise their hash seed.

Two-sum is the canonical example because both versions are short and the difference is the whole point.

# O(n^2): for each element, scan the rest.
def two_sum_slow(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

# O(n): remember what you have seen, and look up the complement.
def two_sum(nums, target):
    seen = {}                              # value -> index
    for i, n in enumerate(nums):
        if target - n in seen:             # constant average lookup
            return [seen[target - n], i]
        seen[n] = i                        # record AFTER checking
    return []

The ordering in the loop is the detail that gets missed. Recording before checking would let an element pair with itself when target is twice its value, so a single 4 in the list would be returned as a valid pair for a target of 8.

The general shape transfers well beyond this problem: whenever the brute force is "for each element, look for a matching element", the question to ask is what you would need to have remembered to answer in one pass. For anagram grouping it is a sorted-letters key; for a subarray summing to k it is the running prefix sum; for first-duplicate it is simply the set of things seen.

The cost is memory — O(n) rather than O(1) — and that is worth saying aloud rather than presenting the improvement as free.

Precomputing cumulative totals so any range sum can be answered in constant time by subtracting two entries. It converts a problem where you would otherwise sum a subarray per query, which is O(n) each, into O(n) preprocessing plus O(1) per query. The same idea extends to two dimensions for rectangle sums, and the running-prefix variant with a hash map solves "count subarrays summing to k" in one pass.

Because strings are immutable in most languages, so each concatenation allocates a new string and copies both operands. Doing that n times copies a growing prefix each time, which totals quadratic work. The fix is to collect the pieces in a list and join once at the end, or to use a builder. It is one of the few performance rules worth applying without measuring, because the alternative is no harder to write.

A subarray is contiguous, a subsequence preserves order but may skip elements, and a subset ignores order entirely. The distinction decides the technique: a contiguous constraint invites a sliding window, a subsequence usually needs dynamic programming because you are choosing at each position, and subsets over a small n invite bitmask enumeration. Misreading which one the problem wants is one of the more expensive misunderstandings, because it sends you to the wrong family entirely.

A set gives O(n) time and O(n) space, which is the default answer. Sorting first gives O(n log n) time and O(1) extra space if sorting in place is allowed, which is the answer when memory is the constraint. If the values are known to be in a fixed range, marking presence by negating or offsetting values in place gives O(n) time and no extra space. Which is right depends on the constraint the interviewer stated, so ask before choosing.

A sorted input where you are looking for a pair or a partition, or a problem where moving an index one way can never require moving it back. The underlying property is monotonicity: if the sum is too large, advancing the left pointer can only make it larger, so the right must move. That argument is the reason the technique is correct, and being able to state it is what distinguishes applying it from having memorised it.

A contiguous run — the words "subarray" or "substring" — combined with a constraint that behaves monotonically as the window grows. Longest substring without repeats, smallest subarray with a sum at least k, at most k distinct characters. The window expands from the right while the constraint holds and shrinks from the left when it breaks, and each index enters and leaves once, which is why the whole thing is linear despite the nested loop.

Nearly every window problem is this shape, and knowing it means the work is deciding what goes in the state rather than how to structure the loop.

def longest_without_repeats(s):
    last_seen = {}          # the window state
    left = 0
    best = 0

    for right, ch in enumerate(s):
        # Shrink until the invariant holds again.
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1

        last_seen[ch] = right
        best = max(best, right - left + 1)   # window is [left, right]

    return best

The invariant is the sentence to say out loud: the window contains no repeated character. Everything else follows — the right pointer always advances, the left only moves forward, and each index is visited at most twice, so it is O(n) despite looking nested.

The >= left check is the part that catches people. A character seen before but already outside the window must not move left backwards, and omitting the comparison produces a subtly wrong answer only on inputs where a repeat falls behind the window.

The variable-versus-fixed distinction is worth holding too. A fixed-size window is simpler — add the entering element, remove the leaving one — while a variable window needs the shrink loop above. If the problem states the size, you are in the easier case and should say so.

Because although there is a loop inside a loop, each pointer only ever moves forward and each index is entered and left exactly once. So the total number of pointer movements is bounded by 2n regardless of how the inner loop is written. This is an amortised argument, and stating it is what proves the solution is linear — an interviewer asking "isn't that O(n²)?" is checking whether you know why it is not.

When the constraint is not monotonic, so shrinking the window can make it valid again in a way that requires reconsidering earlier positions. Negative numbers in a sum problem are the classic breaker: adding an element can decrease the total, so growing the window no longer moves the constraint in one direction, and the window logic silently returns wrong answers. That case usually wants a prefix sum with a hash map instead.

Anything where the most recent unmatched thing is what you need next: bracket matching, expression evaluation, undo history, and depth-first traversal written iteratively rather than recursively. The tell in a problem statement is a nesting or pairing structure, or a phrase like "the most recent" or "the previous smaller element". If you find yourself wanting to look backwards for the nearest something, a stack is almost always the structure, and the recursion you were about to write is a stack the language is managing for you.

A monotonic stack keeps its contents ordered by discarding elements that can never be the answer again, which turns a quadratic scan into a linear one.

def next_greater(nums):
    """For each element, the next element to its right that is larger."""
    result = [-1] * len(nums)
    stack = []                       # holds indices, values decreasing

    for i, n in enumerate(nums):
        # Anything smaller than n has found its answer: it is n.
        while stack and nums[stack[-1]] < n:
            result[stack.pop()] = n
        stack.append(i)

    return result

nums    [2, 1, 5, 3]
i=0     stack [0]                       waiting: 2
i=1     stack [0,1]                     waiting: 2, 1
i=2     5 > 1 -> pop, result[1] = 5
        5 > 2 -> pop, result[0] = 5
        stack [2]                       waiting: 5
i=3     stack [2,3]
result  [5, 5, -1, -1]

The efficiency argument is the same amortised one as the sliding window: each index is pushed once and popped at most once, so the inner while cannot make the whole thing quadratic even though it looks like it might.

What the stack is really holding is unanswered questions. An element stays until something resolves it, and the monotonic property means once an element is popped it can never be needed again — the value that popped it is closer and larger, so it would have answered anything the popped element could. That observation is the invariant, and it generalises to largest rectangle in a histogram, daily temperatures and trapping rain water.

A heap is a partially ordered tree stored in an array, where each parent compares favourably with its children, so the extreme element is at the root and retrievable in constant time. Insertion and removal are logarithmic. What it is not is sorted: the second-smallest element could be either child of the root, and iterating a heap gives no useful order. That distinction is the answer to most heap questions — it gives you the extreme cheaply and tells you nothing else.

When you need the top k rather than the whole order. Sorting is O(n log n); maintaining a heap of size k while scanning is O(n log k), which is substantially better when k is small relative to n and is the difference between feasible and not on a stream you cannot hold in memory. It also works when the input arrives incrementally, where sorting requires having everything first.

Two heaps facing each other keep the middle of a stream available in constant time, which no single ordered structure does as cheaply.

import heapq

class RunningMedian:
    def __init__(self):
        self.low = []    # max-heap, negated because Python's heap is a min-heap
        self.high = []   # min-heap

    def add(self, n):
        heapq.heappush(self.low, -n)                     # always add to low
        heapq.heappush(self.high, -heapq.heappop(self.low))  # move its max over

        # Rebalance so low is never smaller than high.
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def median(self):
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2

The invariant is that every element in low is at most every element in high, and the sizes differ by at most one. Given both, the median is either the top of the larger heap or the average of the two tops.

The push-then-move step is the part worth understanding rather than memorising. Adding straight to whichever heap looks right can violate the ordering, because the new value might belong on the other side. Pushing to low and immediately moving its maximum to high guarantees the ordering holds, and the rebalance then fixes only the sizes. It costs one extra heap operation and removes every edge case.

A double-ended queue supporting constant-time insertion and removal at both ends. You need it for a queue, since removing from the front of an array is linear, and for sliding-window maximum, where you keep indices in decreasing order and pop from both ends. It is also the right structure for a bounded history buffer. The mistake it prevents is using a list as a queue, which turns an O(1) operation into O(n) and a loop into a quadratic.

Only where the node is visited relative to its children. Pre-order visits the node first, which suits copying a tree or serialising it. In-order visits left, node, right, which on a binary search tree yields sorted order — that is the single most useful fact about in-order. Post-order visits children first, which is what you need when a node's result depends on its subtrees, such as computing heights or deleting a tree safely.

The position of the work decides what information is available, and most tree problems are really a question about which one you need.

# Work BEFORE the calls: the node knows about its ancestors.
def depths(node, depth=0):
    if not node:
        return
    print(node.value, "is at depth", depth)   # uses information passed down
    depths(node.left, depth + 1)
    depths(node.right, depth + 1)

# Work AFTER the calls: the node knows about its subtrees.
def height(node):
    if not node:
        return 0
    left = height(node.left)                  # results come back up
    right = height(node.right)
    return 1 + max(left, right)

Information flows down through parameters and up through return values, and choosing the direction is the design decision. Depth is inherited from a parent so it is a parameter; height is derived from children so it is a return value.

Some problems need both, which is where candidates get stuck:

def is_valid_bst(node, low=None, high=None):
    if not node:
        return True
    # Bounds come DOWN from ancestors...
    if (low is not None and node.value <= low) or (high is not None and node.value >= high):
        return False
    # ...and validity comes UP from children.
    return (is_valid_bst(node.left, low, node.value)
            and is_valid_bst(node.right, node.value, high))

Validating a BST by comparing each node only with its two children is the classic wrong answer, because the constraint is over whole subtrees rather than parent and child pairs — a node deep in the left subtree can still be larger than the root.

Inserting sorted or nearly sorted data, which produces a chain rather than a tree and turns every operation from O(log n) into O(n). This is why self- balancing variants exist — red-black trees, AVL trees — which perform rotations on insertion to keep the height logarithmic. The practical takeaway is that a plain BST has good average behaviour and a bad worst case, and library tree maps are balanced for exactly this reason.

Depth is measured from the root down to the node; height is measured from the node down to its deepest leaf. So the root has depth zero and height equal to the tree's height, and a leaf has height zero. They are computed in opposite directions, which is why depth is passed down as a parameter and height comes back as a return value. Mixing them up is a common source of off-by-one answers.

In a binary search tree, walk down from the root: if both targets are smaller go left, if both are larger go right, and the first node where they diverge is the answer. In a general binary tree, recurse and return the node if it matches either target, otherwise return whichever side produced a non-null result — if both sides do, this node is the ancestor. The second version is a good example of a post-order algorithm where the return value carries the meaning.

Storing strings by shared prefix, so lookup costs the length of the key rather than depending on how many keys exist, and prefix queries become natural. Autocomplete is the standard use, because a hash map can tell you whether a string is present and cannot tell you which keys start with something. The cost is memory: a node per character per branch, which is why tries suit dense key sets and waste space on sparse ones.

Whenever entities have relationships and the question is about reachability, ordering or connection. Build dependencies, mutual follows, a maze, currency conversions, state machines, prerequisites — all graphs. This recognition is where most candidates fail rather than in the traversal itself, because the problem statement rarely uses the word. If you can phrase the question as "can I get from here to there" or "what must happen first", it is a graph.

BFS explores by distance, so it finds the shortest path in an unweighted graph and needs a queue plus memory proportional to the width of the frontier. DFS explores one branch fully before backtracking, so it uses memory proportional to depth and suits cycle detection, topological ordering and exhaustive search. If the question asks for the fewest steps, it is BFS; if it asks whether something is reachable or asks for an ordering, DFS is usually simpler.

The traversal is short; the placement of the visited check is what separates a correct implementation from one that degrades badly.

from collections import deque

def shortest_path_length(graph, start, goal):
    queue = deque([(start, 0)])
    visited = {start}                  # marked when ENQUEUED, not when dequeued

    while queue:
        node, dist = queue.popleft()
        if node == goal:
            return dist
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)     # before pushing
                queue.append((neighbour, dist + 1))
    return -1

Marking on enqueue rather than on dequeue is the detail. If you mark only when you pop, a node reachable from several frontier nodes gets pushed several times, so the queue grows with duplicates and the work becomes exponential in a dense graph. Nothing is incorrect about the answer — it is just far slower, which makes it the kind of bug that passes a small test.

flowchart TD
    A[Start node in queue and visited] --> B[Pop the front]
    B --> C{Is it the goal}
    C -- Yes --> D[Return the distance]
    C -- No --> E[For each unvisited neighbour]
    E --> F[Mark visited and enqueue with distance plus one]
    F --> B

The correctness argument for shortest path is that BFS visits nodes in non-decreasing distance order, so the first time you reach the goal you have reached it by a shortest route. That holds only on an unweighted graph — with weights, a longer-hop path can be cheaper, which is what Dijkstra's algorithm exists to handle by using a priority queue instead of a plain one.

An ordering of a directed graph's nodes such that every edge points forwards, which is what you want for build steps, task dependencies or course prerequisites. It exists only if the graph is acyclic: a cycle means each node in it must come before the others, which no ordering satisfies. That makes topological sort a cycle detector as a side effect, which is often the more useful half — the answer to "why can't this build" is the cycle it found.

The three-colour method is the one to know, because the two-state version does not work on a directed graph.

WHITE, GREY, BLACK = 0, 1, 2   # unvisited, on the current path, finished

def has_cycle(graph):
    state = {node: WHITE for node in graph}

    def visit(node):
        state[node] = GREY                    # entering: on the current path
        for neighbour in graph[node]:
            if state[neighbour] == GREY:      # back edge: a cycle
                return True
            if state[neighbour] == WHITE and visit(neighbour):
                return True
        state[node] = BLACK                   # leaving: fully explored
        return False

    return any(visit(n) for n in graph if state[n] == WHITE)

The reason a simple visited set fails is that reaching an already-visited node is not itself a cycle — it may just be a node you reached earlier by another route, which is perfectly normal in a directed acyclic graph. A cycle requires reaching a node that is currently on the path you are exploring, which is what GREY records.

    A ──▶ B ──▶ D          Visiting A: grey
    │           ▲          B: grey, then D: grey, then black, B black
    └────▶ C ───┘          C: grey, sees D which is BLACK -> not a cycle
                           Correct: this graph is acyclic

An undirected graph is different again: there, every edge you came in on looks like a back edge, so you have to skip the immediate parent rather than track three states.

Answering connectivity questions — are these two nodes in the same component — in near-constant time per operation, with two optimisations: union by rank and path compression. It suits problems where connections arrive incrementally and you never remove them, such as detecting a cycle while building a graph, or Kruskal's minimum spanning tree. It cannot answer path questions, only membership, which is the trade for how fast it is.

When edges have different weights, so the fewest hops is no longer the cheapest route and BFS returns a path that is short but expensive. Dijkstra replaces the plain queue with a priority queue ordered by distance so far, and settles nodes in increasing cost order, which is the same correctness argument as BFS with cost substituted for hops. The constraint worth knowing is that it requires non-negative weights: a negative edge can make an already-settled node cheaper later, which breaks the argument entirely, and that case needs Bellman-Ford instead.

A base case that returns without recursing, and a recursive step that makes progress towards it. Missing the base case gives infinite recursion; a step that does not shrink the problem gives the same. Beyond correctness, the useful framing is that recursion is a way to express "solve a smaller version and combine", so the design question is always what the smaller version is and how the results combine.

Backtracking is recursion that explores choices and undoes them, so the same state structure is reused rather than copied at every level. The undo step is the distinguishing feature: make a choice, recurse, then unmake it. That is what lets you enumerate permutations or solve a constraint problem without allocating a new candidate at every node, and forgetting the undo is the most common bug in the family.

Exhaustive search is easy to write and usually too slow; the pruning is what makes it finish.

def combination_sum(candidates, target):
    candidates.sort()                 # sorting enables the prune below
    results, current = [], []

    def backtrack(start, remaining):
        if remaining == 0:
            results.append(current[:])    # copy: current keeps mutating
            return
        for i in range(start, len(candidates)):
            n = candidates[i]
            if n > remaining:             # THE prune: sorted, so all later are too
                break
            current.append(n)             # choose
            backtrack(i, remaining - n)   # explore, i not i+1 to allow reuse
            current.pop()                 # un-choose
    backtrack(0, target)
    return results

Three lines carry the algorithm. The break is the prune, and it works only because the input is sorted — without it the search explores branches that cannot possibly succeed, which is the difference between finishing and not. The current[:] copy is required because current is mutated throughout; appending it directly stores a reference that will be empty by the end. And the pop is the backtrack itself.

The general recipe is choose, explore, un-choose, with a prune as early as possible. The prune is where nearly all the performance is: pushing a check from the base case up into the loop can turn an intractable search into an instant one, because it eliminates an entire subtree rather than one leaf.

Two properties together: overlapping subproblems, meaning the same smaller problem is solved repeatedly, and optimal substructure, meaning the best answer to the whole is built from best answers to its parts. The practical signal is a recursion whose call tree repeats itself — draw two levels by hand and see whether the same arguments appear more than once. If every subproblem is distinct, memoising buys nothing and what you have is divide-and-conquer, where the win comes from the splitting rather than from caching.

The change is small and the change in complexity class is total, which is why this pair is the canonical demonstration.

# Exponential: fib(n-2) is computed along two separate branches, so the
# call tree has roughly 2**n nodes.
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

# Linear: each subproblem is solved once and cached.
def fib_memo(n, seen=None):
    seen = {} if seen is None else seen
    if n < 2:
        return n
    if n not in seen:                       # the line that removes the branching
        seen[n] = fib_memo(n - 1, seen) + fib_memo(n - 2, seen)
    return seen[n]

# Bottom-up: same complexity, no recursion stack, and space can drop to O(1)
# because only the last two values are ever needed.
def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Nothing in the first function looks expensive line by line; the cost is entirely in the shape of the recursion, which is invisible until you draw the call tree. "Overlapping subproblems" is the phrase for what you are looking for.

Drawing the call tree is what makes the repetition visible, and it is worth doing by hand once rather than taking it on trust:

flowchart TD
    A[fib 5] --> B[fib 4]
    A --> C[fib 3]
    B --> D[fib 3]
    B --> E[fib 2]
    C --> F[fib 2]
    C --> G[fib 1]
    D --> H[fib 2]

fib 3 appears twice and fib 2 three times, at depth four of a tiny example. At fib 40 the same duplication compounds into some 331 million nodes, and the cache collapses the whole tree into one node per distinct argument.

The choice between top-down and bottom-up is mostly ergonomic. Memoisation follows the recursive definition directly, so it is easier to derive and only computes states you actually reach. Tabulation avoids the recursion stack, which matters when the depth could overflow it, and it makes space optimisation obvious — the third version keeps two variables because that is all the recurrence looks back at.

Defining the state. Once you can say what dp[i] or dp[i][j] means in one sentence, the transition usually follows and the implementation is mechanical. Get the state wrong and no amount of correct coding recovers it, which is why experienced candidates spend most of their time on that sentence and why "what does this cell represent" is the question an interviewer asks when you are stuck.

When you can argue that a locally best choice never rules out a globally best solution, usually via an exchange argument: take any optimal solution, show it can be transformed into your greedy one without getting worse. Interval scheduling by earliest finishing time has such an argument; the coin change problem does not for arbitrary denominations, which is why the greedy answer is wrong there. The interview question is almost never whether you can code it but why it is safe.

That elements comparing equal keep their original relative order. That matters whenever you sort by one key and then another to get a compound ordering — sort by name, then stably by department, and within each department the names remain sorted. Merge sort is stable and quicksort is not, which is one of the few practical reasons to care which a library uses. Python's and Java's object sorts are stable; several primitive sorts are not.

Because the worst case requires consistently bad pivots, which randomised or median-of-three pivot selection makes vanishingly unlikely, and because its constant factors and cache behaviour are excellent — it sorts in place with good locality. Merge sort guarantees O(n log n) but needs O(n) extra space. Real library sorts are usually hybrids that switch to insertion sort on small partitions and fall back to a guaranteed algorithm if recursion goes too deep.

The form that appears in interviews is usually not searching a sorted array — it is searching the space of possible answers, where nothing is sorted because there is no array.

def min_capacity(weights, days):
    """Smallest ship capacity that ships all weights within `days`."""

    def feasible(capacity):
        needed, load = 1, 0
        for w in weights:
            if load + w > capacity:
                needed += 1
                load = 0
            load += w
        return needed <= days

    lo, hi = max(weights), sum(weights)   # bounds that must contain the answer
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid                      # mid might be the answer, keep it
        else:
            lo = mid + 1                  # mid is too small, discard it
    return lo

The property that makes it valid is monotonic feasibility: if a capacity works, every larger one works too. That turns the answer space into a sorted sequence of false values followed by true values, and binary search finds the boundary.

Two implementation details cause most of the bugs. The bounds must be chosen so the answer is definitely inside them — here the lower bound is the heaviest single item, since no smaller ship can carry it. And the update must not exclude a candidate answer: hi = mid rather than mid - 1, because mid itself may be the smallest feasible value, while lo = mid + 1 is safe because mid is known to fail.

The signal in a problem statement is a question asking for a minimum or maximum value subject to a condition you can check more easily than you can compute the answer.

Because in languages with fixed-width integers the sum can overflow before the division, producing a negative index. Writing lo + (hi - lo) // 2 avoids it. It is a genuine historical bug found in widely used library implementations years after publication, which makes it a good illustration that correct-looking code can hide a defect for a long time. In Python integers are arbitrary precision, so it does not apply, but interviewers still ask.

Not just whether the code runs. The rubric usually has axes for communication, approach, correctness and complexity, so a partially complete solution narrated clearly outscores a complete one produced in silence. The moment that decides most rounds is the added constraint near the end, because it cannot be prepared for — it tests whether you understood your own solution well enough to modify it, or merely reproduced one.

The skill a coding round measures is not writing the solution, it is the ninety seconds between reading the statement and committing to an approach. That period has a structure you can rehearse: look for a small number of signals, each of which rules a family in or out.

flowchart TD
    A[Read the statement and the input limits] --> B{Contiguous run over an array or string}
    B -- Yes --> C[Sliding window or two pointers]
    B -- No --> D{Answer is a number with a monotonic feasibility test}
    D -- Yes --> E[Binary search on the answer]
    D -- No --> F{Same subproblem recurs across choices}
    F -- Yes --> G[Dynamic programming or memoisation]
    F -- No --> H{Entities with relationships}
    H -- Yes --> I[Model as a graph and traverse]
    H -- No --> J[Sort first and see what falls out]

The branch most often missed is the second. Binary search is taught as a way to find a value in a sorted array, and the version that appears in interviews is usually the other one — you are searching the space of possible answers, and there is no array at all.

The last branch is worth keeping as a fallback rather than a guess. A surprising number of problems become obvious once sorted: intervals collapse to a sweep, duplicates become adjacent, and a two-pointer scan becomes available. If nothing else fits, asking "what does sorting make true?" is a productive thirty seconds.

Say the signal out loud when you spot it. "This asks for the longest contiguous run satisfying a condition, and the condition is monotonic in the window width, so this is a sliding window" is a sentence that earns marks on its own — it shows the choice was derived rather than pattern-matched, which is exactly what the interviewer cannot tell from the code alone.

Restate the problem in your own words and ask about input size, edge inputs and whether the input is sorted or contains duplicates or negatives. Then name a brute force and its cost out loud before optimising, because it establishes a baseline, proves you understood the problem, and gives you something to submit if time runs out. Starting to type immediately is the most common way to solve the wrong problem elegantly.

State your variables first — "n is the number of orders and m is the average number of lines" — then account for each part of the algorithm, then give the total. Mention space separately, including the recursion stack. And check the result against the stated limits: noticing yourself that a quadratic solution will not finish at the given input size is worth real credit, because it shows the analysis is a tool you use rather than a label you attach at the end.