Interview Patterns in C++

Four ways to avoid trying everything

A service stores sorted event times, compares two sorted measurements, analyzes a stretch of requests, and searches a network of connected stations. Each task admits an obvious exhaustive approach. Each also has a structural fact that lets the program discard work safely. The skill is recognizing that fact and preserving it while the state changes.

Binary search discards a region that cannot contain the boundary. Two pointers discard one candidate per comparison. A moving interval repairs a local constraint without restarting from scratch. Breadth-first search processes unweighted distances in order. These are not interchangeable tricks: each needs a different precondition, and each fails quietly when that precondition is missing.

You know containers, iterator ranges and complexity from module 10, including std::unordered_map and std::queue. Here you will practice making the search state explicit. The lesson's examples are event times, latencies, request tags and a station network. The lab's vectors, word and maze are different instances, and its final challenge will not tell you which technique it needs.

First identify what the answer means

Before writing code, specify the answer on an empty input, on duplicates, and when no answer exists. Is a search asking for any equal value, the first equal value, or the first value meeting a threshold? Those are different contracts. A function returning a boundary can use the sequence length for “none,” while a function returning a pair of positions needs a separate absent result.

The exhaustive approach is valuable as a specification oracle on small inputs. It can enumerate all pairs, inspect every interval, or compute distances independently. Keep that reference simple and separate from the optimized implementation. Every Python block in this lesson is such a reference: it replays a trace from a figure and checks it against plain enumeration. None of them is the optimized loop, which the lab asks you to write.

Then name the reason some candidates can be discarded. Sortedness permits order-based elimination. A constraint that only removal can restore permits interval repair. An unweighted graph permits distance layers. Without those conditions, a familiar-looking loop silently solves a different problem.

A boundary in sorted event times

Suppose sorted event times are 2, 5, 5, 11, 14, 19 and 27. We want the first time at least 12. The answer is position 4, which holds 14. Scanning from the start looks at five values here and at every value in the worst case. A boundary search instead keeps an unresolved range [lo, hi), where lo is included and hi is not, and compares the middle of that range with the threshold.

Initially both known regions are empty: lo is zero and hi is the sequence length. If the middle value is too small, sortedness certifies that everything up to and including the middle is too small, so lo moves just past it. Otherwise the middle already qualifies, and so does everything after it, so hi moves onto it. Either way the invariant still holds and the unresolved range is strictly shorter. When lo meets hi nothing is unresolved, and the invariant says that lo is the boundary. That is the whole proof: true at the start, preserved by each step, and decisive at the end.

A closed range [lo, hi] with both ends included also works, but it starts at size() - 1 and stops when hi passes below lo. Both of those want a value below zero, which an unsigned index cannot hold. The half-open form never needs one.

The middle, computed safely

The obvious middle is (lo + hi) / 2. Whether that is wrong depends on the index type. With int indices, which are 32 bits on this course's compiler and on mainstream desktop systems, lo + hi can pass 2,147,483,647 only when the sequence has more than $2^{30}$ elements, about 1.07 billion. Signed overflow is undefined behavior: the program has no guaranteed result at all. With std::size_t indices the sum wraps around instead of being undefined, but it would have to reach the full range of the type first. A std::vector<int> spends four bytes per element, so its indices stay below a quarter of that range and the sum of two of them cannot wrap.

So the classic bug belongs to signed indices on very large sequences. The form lo + (hi - lo) / 2 is correct for both types whenever lo <= hi, because the difference and the result both lie between zero and hi. It costs nothing, so use it always. Unsigned indices have a different trap: size() - 1 on an empty vector wraps to the largest std::size_t.

Count the discarded positions

A step on an unresolved range of length $L$ leaves at most $\lfloor L/2\rfloor$ positions. A range of length $n$ therefore takes at most $\lfloor {\log }_{2}n\rfloor +1$ comparisons in the worst case, for every sorted input of that length, and the extra state is two indices. Seven values need at most three comparisons, a million need at most twenty. This counts element comparisons and assumes random access: stepping to the middle must take constant time.

from bisect import bisect_left

class Probed:
    """A value that records each comparison made against it."""
    log = []
    def __init__(self, value):
        self.value = value
    def __lt__(self, other):
        Probed.log.append(self.value)
        return self.value < other

times = [2, 5, 5, 11, 14, 19, 27]
boundary = bisect_left([Probed(t) for t in times], 12)
assert boundary == 4 and times[boundary] == 14
assert Probed.log == [11, 19, 14]          # the three probes in the figure
assert bisect_left(times, 28) == len(times) and bisect_left([], 12) == 0

def worst_case(n):
    most = 0
    for target in range(n + 1):
        Probed.log = []
        bisect_left([Probed(i) for i in range(n)], target - 0.5)
        most = max(most, len(Probed.log))
    return most

assert all(worst_case(n) == n.bit_length() for n in range(1, 130))
assert (7).bit_length() == 3 and (10**6).bit_length() == 20

Python's bisect_left is a documented stand-in with the same boundary contract; the wrapper only counts what it compares. For positive $n$, n.bit_length() equals $\lfloor {\log }_{2}n\rfloor +1$, and the loop confirms that bound is reached for every length up to 129. When a check grades your own search, it replays the probes you made. A printed count proves nothing about the work behind it.

Two ends can eliminate a row of candidates

Seven sorted latencies, in milliseconds, are 3, 8, 12, 17, 21, 30 and 34. Do two different measurements add up to 29? Trying every pair costs 21 additions here and $n(n-1)/2$ in general. Sortedness allows better: look at the smallest and the largest remaining values. If their sum is too large, the largest value is too large with every remaining partner, because every other partner is at least as big as the smallest. If the sum is too small, the smallest value is too small with every remaining partner, because none is bigger than the largest. One comparison finishes one value, which rules out a whole row of the table of pairs.

The paragraph above proves each discard obeys this. Now suppose some valid pair exists, and look at the first moment one of its two values is discarded. Its partner is still between the ends at that moment, which contradicts the invariant. So neither value of a valid pair is ever discarded, and since the ends close in by one position per step, they must stop on a valid pair. If the ends meet, no pair exists. The loop takes at most $n-1$ steps for $n$ values, one sum per step, on every input.

from itertools import combinations

latency = [3, 8, 12, 17, 21, 30, 34]
wanted = 29
trace = [(0, 6), (0, 5), (0, 4), (1, 4)]   # the ends shown in the figure
for (left, right), following in zip(trace, trace[1:]):
    too_large = latency[left] + latency[right] > wanted
    dropped = right if too_large else left
    assert following == ((left, right - 1) if too_large else (left + 1, right))
    others = [i for i in range(left, right + 1) if i != dropped]
    assert all(latency[dropped] + latency[i] != wanted for i in others)
left, right = trace[-1]
assert latency[left] + latency[right] == wanted
pairs = [p for p in combinations(range(7), 2) if latency[p[0]] + latency[p[1]] == wanted]
assert pairs == [(1, 4), (2, 3)]
assert len(trace) <= len(latency) - 1 and len(list(combinations(range(7), 2))) == 21

Enumeration finds two valid pairs, 8 + 21 and 12 + 17. The walk reports one of them, so the contract must say “some pair,” or name which one. The proof needs sorted values. On unsorted data the same movement rule still terminates, and it still returns an answer, but nothing justifies the discards.

Two details are C++ rather than algorithm. The ends must stay distinct, or one value is used twice. And the sum needs a type wide enough for the contract: two valid int values can overflow an int sum, so widen one operand before adding. Casting the result is too late.

#include <vector>

long long endpoint_total(const std::vector<int>& values) {
    if (values.empty()) return 0;
    return static_cast<long long>(values.front()) + values.back();
}

int main() {
    const long long big = endpoint_total({2000000000, 2000000000});
    return endpoint_total({}) == 0 && big == 4000000000LL ? 0 : 1;
}

This helper shows the empty-input guard and widening before addition, with a total no int could hold. It is not one of the lab's algorithms.

A moving interval repairs its constraint

A request log carries one tag per request: G, P, G, D, P, P, U. What is the longest run of consecutive requests whose tags are all different? A naive program starts at every position and extends until a tag repeats. On this log it looks at 19 tags, most of them more than once. A better program keeps one interval and its state: extend the right end by one request, then move the left end forward until the new repetition is gone.

Why the longest? Distinctness has a one-way property: removing a request can never create a repetition, and adding one can never cure a repetition. So once a left position is too far left for some right end, it is too far left for every later right end, and the left end never needs to move back. The step at right = 5 in the figure shows why the repair is a loop. One removal drops a G, and the two P tags are both still inside. A single if would leave the interval broken.

Both ends move forward only. Each position enters the interval once and leaves at most once, so $n$ requests cost at most $2n$ end movements in total. That is an amortized bound: one step may make many removals, but the whole call cannot. On the seven tags it is twelve movements against the naive nineteen, and on a thousand distinct tags it is 1,000 against 500,500.

tags = list("GPGDPPU")
lefts = [0, 0, 1, 1, 2, 5, 5]              # the left end after each right end
def distinct(a, b):
    return len(set(tags[a:b + 1])) == b - a + 1
for right, left in enumerate(lefts):
    assert distinct(left, right)
    assert left == 0 or not distinct(left - 1, right)
assert lefts == sorted(lefts)
every = [(a, b) for a in range(7) for b in range(a, 7) if distinct(a, b)]
best = max(right - left + 1 for right, left in enumerate(lefts))
assert best == 3 == max(b - a + 1 for a, b in every)
assert len(tags) + lefts[-1] == 12 <= 2 * len(tags)

def naive_looks(sequence):
    looks = 0
    for start in range(len(sequence)):
        seen = set()
        for tag in sequence[start:]:
            looks += 1
            if tag in seen:
                break
            seen.add(tag)
    return looks
assert naive_looks(tags) == 19 and naive_looks(list(range(1000))) == 500500

In C++ the record is a std::unordered_map<char, int> from tag to count. The program below performs only the bookkeeping of that step, to show that one removal is not enough:

#include <string>
#include <unordered_map>

int main() {
    const std::string tags = "GPGDPPU";
    std::unordered_map<char, int> counts;
    for (int i = 2; i <= 4; i++) counts[tags[i]]++;   // the interval G D P
    counts[tags[5]]++;                                // a second P arrives
    const bool broken = counts['P'] == 2;
    counts[tags[2]]--;                                // G leaves on the left
    const bool still_broken = counts['P'] == 2 && counts['G'] == 0;
    return broken && still_broken ? 0 : 1;
}

The movement bound counts map operations, not time. A std::unordered_map operation takes constant time on average and time linear in the number of stored keys in the worst case, when many keys share a bucket. So $2n$ movements cost linear time on average and can cost on the order of $n·k$ in the worst case, for $k$ different keys. A std::map guarantees logarithmic operations. With char keys a plain array of 256 counts guarantees constant ones.

The technique requires a repairable constraint: one that extending can only break and removing can only restore. Distinctness is one. Before moving the rule to another constraint, prove both directions for that constraint, and ask what would have to be true of the data for them to hold.

Breadth-first search pays once per discovery

A graph is a set of vertices, here stations, joined by edges, here direct connections. An adjacency list stores, for each vertex, the list of its neighbours. Seven stations A to G have eight connections: A–B, A–C, B–D, C–D, C–E, D–F, E–F and F–G. Each connection counts as one step. How many steps from A is every station?

A std::queue explores by distance. Begin with the start at distance zero. Take the oldest station from the front and inspect its neighbours. A neighbour not yet discovered receives a distance one larger and joins the back.

Mark discovery when adding the neighbour, not later when removing it. D is a neighbour of both B and C. If D were marked only when taken out, B and C would each add it, the queue would hold it twice, and its predecessor would depend on which copy came out first.

The second sentence is what makes a first discovery final. A station taken from the front at distance $d$ only appends stations at distance $d+1$, which keeps the queue in order and within one of its front. Suppose a station could be reached in fewer steps than the distance it was given. The station just before it on that shorter route is nearer the start, so it left the queue earlier, and it would have discovered the station then, with the smaller distance. So every assigned distance is the least number of edges.

#include <queue>
#include <vector>

int main() {
    // Stations A to G are 0 to 6. links[s] lists the neighbours of s.
    const std::vector<std::vector<int>> links = {
        {1, 2}, {0, 3}, {0, 3, 4}, {1, 2, 5}, {2, 5}, {3, 4, 6}, {5}};
    std::vector<int> distance(links.size(), -1);    // -1: not discovered
    std::queue<int> waiting;
    distance[0] = 0;
    waiting.push(0);
    int pushes = 1;
    while (!waiting.empty()) {
        const int station = waiting.front();
        waiting.pop();
        for (int next : links[station]) {
            if (distance[next] != -1) continue;     // discovered earlier
            distance[next] = distance[station] + 1; // marked on the push
            waiting.push(next);
            pushes++;
        }
    }
    const std::vector<int> expected = {0, 1, 1, 2, 2, 3, 4};
    return distance == expected && pushes == 7 ? 0 : 1;
}

Every station is pushed once and every adjacency-list entry is examined once. The traversal therefore does $O(V+E)$ work and keeps $O(V)$ extra state in the worst case, where $V$ counts vertices and $E$ counts edges. An undirected edge is stored twice, once at each end, so sixteen entries are examined here. A rectangular grid is a graph whose cells have at most four neighbours, so the work is linear in its number of cells. The lab's maze is such a grid, and it asks for a route as well as a distance. Weighted edges change the problem: breadth-first search minimizes the number of edges, not their total weight.

links = {"A": "BC", "B": "AD", "C": "ADE", "D": "BCF", "E": "CF", "F": "DEG", "G": "F"}
steps = {station: (0 if station == "A" else len(links)) for station in links}
changed = True
while changed:                  # a stand-in: relax every edge until nothing improves
    changed = False
    for station in links:
        for neighbour in links[station]:
            if steps[station] + 1 < steps[neighbour]:
                steps[neighbour] = steps[station] + 1
                changed = True
assert steps == {"A": 0, "B": 1, "C": 1, "D": 2, "E": 2, "F": 3, "G": 4}
assert sum(len(neighbours) for neighbours in links.values()) == 2 * 8

The stand-in reaches the same distances without a queue, by repeating until nothing changes. It is simpler to trust and slower, which is what an oracle should be.

Remember a route as well as a distance

Store a predecessor when discovering a station: the station it was discovered from. Once the destination is found, follow predecessors back to the start, then reverse that collected sequence. Every predecessor is one distance level earlier, so the chain terminates. Its reversal is a shortest route in the unweighted model. In the program above the chain from G is F, D, B, A. The route A, C, E, F, G is equally short; the program did not choose it.

Several shortest routes may exist, as they do here. Unless the interface specifies a tie policy, tests should validate the route's ends, adjacency and length rather than require one particular route. A traversal order determined by neighbour order is an implementation choice.

If the goal is unreachable, return the promised absent result. If start equals goal, the route contains one station and zero edges. These cases force the specification to distinguish the number of vertices in a route from its number of steps.

C++ state should belong to one call

Trace counters, visited records and predecessor storage should be initialized for each search. A guard that accumulates across calls may reject a correct second search. The lab's supplied helpers begin each graded call with a fresh record for that reason. The pictures are evidence of one call's execution, not a history mixed with earlier runs.

Use const references for large read-only inputs. Passing a vector or string by value copies it before the algorithm begins, which makes a logarithmic search linear. A small coordinate may be an inexpensive value parameter; a whole maze is not.

A problem that looks different

A sorted sequence of software versions passes a compatibility test up to some boundary and fails afterward. The test is expensive, and no version before a passing one can fail. How many tests are necessary to locate the transition? State what happens if all versions pass or all fail before proposing a search.

Practise

The lab traces a boundary search, a walk from two ends, an interval repair and a maze search, each on a new instance and each replayed step by step from your own code. The final challenge changes the context and asks for a plan, an invariant and a cost argument before code. Work is counted in probes, end movements, discovered cells or reads, never in elapsed time.

Recap

You can now: select a search pattern from its structural precondition and explain why each state change discards work safely.

Invariant: candidates are eliminated only by a proved order or one-way constraint; discovered graph vertices are recorded once and processed in distance order.

Complexity achieved: at most $\lfloor {\log }_{2}n\rfloor +1$ comparisons for a boundary among $n$ sorted random-access values; at most $n-1$ steps for two ends; at most $2n$ end movements for a repaired interval; and $O(V+E)$ work for an unweighted traversal, all worst case in the counted operation.

Failure mode: unsigned subtraction wraps, int sums overflow before widening, state leaks between calls, or a technique is applied without its sortedness, one-way constraint or unit-edge precondition.

In real software: std::lower_bound has this lesson's boundary contract. It returns the first position whose element is not less than the value, or the end of the range, in at most ${\log }_{2}n+O(1)$ comparisons.

Retrieval: from module 9, why can a reference to a vector element stop being valid after push_back?

Check yourself

1. Which invariant justifies discarding the middle element in one boundary-search branch but retaining it in the other?
2. Why can a nested loop with a forward-only left end still have linear total movements?
3. Which fact about edge costs makes the queue's first discovered distance final?

Original SciMigo course material. C++ examples target C++17.