R05 · Week 5 Recall & Drill

Assessment scope

Attempt the recall prompts before reading the worked drill and answer explanations. The worked examples below restore the combined teaching task, with explicit contracts and checks; a local model is distinguished from a reproduced external service. The minute allocations are adjustable practice suggestions, not evidence of learning speed.

Sessions covered

• S021 — Probability — Random Variables, Distributions, Expectation
• S022 — Statistics — CLT, Hypothesis Testing, Confidence Intervals
• S023 — Arrays & Strings — Indexing, Slicing, Two-Pointer
• S024 — Hashmaps & Sets — Hash Functions, Collisions
• S025 — Linked Lists — Singly, Doubly, When They Win

By the end of this revision you can

1. Choose a distribution by stating trial, independence and rate assumptions; compare its expectation and variance formulas with bounded simulation.

2. Apply Bayes' rule with explicit prevalence, sensitivity and specificity: with sensitivity and specificity both 0.99, half of positives are false at prevalence 0.01, while about 90.98% are false at prevalence 0.001.

3. State what a p-value is a probability of, and name the four interpretations that get analysts into trouble.

4. Write the two-pointer and sliding-window templates from memory and say what invariant each pointer maintains.

5. Distinguish expected lookup and amortized resizing from hashing/equality costs and cached string hashes; explain collisions.

6. Perform the three linked-list surgeries — reverse in place, cycle detection, merge two sorted — and argue when an array beats a list anyway.

90-min structure

Treat this as an adjustable practice budget: 5 minutes to recall the five subjects, 30 for the blank-page questions, 30 for the worked drill, 15 to compare answers and test a counterexample, and 10 to record a gap and plan an unseen retest. The solutions and transfer exercises can take longer; the goal is correct reasoning, not racing a timer.

Blank-page reconstruction · 30 min

S021 · Probability

1. Match each situation to a distribution: number of heads in ten flips; time until the next request arrives; count of rare events in a fixed window; a single yes-or-no outcome; measurement error around a true value.
2. Write the definition of expectation for a discrete random variable, then compute the expectation and variance of a single yes-or-no trial with success probability p.
3. State Bayes' rule and label each of the four quantities with its name.

S022 · Statistics

1. State the central limit theorem in one sentence, and say what it lets you do that you could not do without it.
2. Write the null and alternative hypothesis for a conversion-rate A/B test, then say exactly what p = 0.03 means.
3. Name the four p-value interpretations that are outright wrong, and correct each one.

S023 · Arrays & Strings

1. Explain in one breath why an array gives constant-time indexing but linear-time insertion in the middle.
2. Write the sliding-window template in three lines of pseudocode and say what condition shrinks the window.
3. Say what invariant the slow pointer maintains in remove-duplicates-from-sorted-array.

S024 · Hashmaps & Sets

1. Name the two properties a good hash function must have, and say what breaks when each one fails.
2. Explain the difference between chaining and open addressing for collision resolution.
3. Write the complement-lookup template that turns the two-sum problem from quadratic into linear.

S025 · Linked Lists

1. Write the four-line reverse-in-place loop in pseudocode, naming each pointer.
2. Explain why the tortoise-and-hare algorithm detects a cycle in linear time and constant memory.
3. Give one real system where a linked list is genuinely the right structure, and say what property makes it so.

Hands-on drill · 30 min

Task: compare the base-rate calculation with a simulation, then implement the week's three DSA patterns and measure the array-versus-list claim.

Step 1 — simulate Bayes instead of trusting the formula (10 min)

# basrate.py
import numpy as np
 
rng = np.random.default_rng(7)
N = 100_000
PREVALENCE = 0.01      # 1% of the population has the condition
SENSITIVITY = 0.99     # P(positive | has it)
SPECIFICITY = 0.99     # P(negative | does not have it)
 
has_it = rng.random(N) < PREVALENCE
roll = rng.random(N)
positive = np.where(has_it, roll < SENSITIVITY, roll < (1 - SPECIFICITY))
 
tp = int((positive & has_it).sum())
fp = int((positive & ~has_it).sum())
 
print(f"population           : {N}")
print(f"actually have it     : {int(has_it.sum())}")
print(f"tested positive      : {tp + fp}")
print(f"  true positives     : {tp}")
print(f"  false positives    : {fp}")
print(f"P(has it | positive) : {tp / (tp + fp):.3f}")

Expected outcome: roughly half of the positives are false, so the final probability lands near 0.5 despite sensitivity and specificity both being 99%. The reason is visible directly in the counts: the true positives come from the 1% who have the condition, while the false positives come from the 99% who do not, and 1% of that much larger group is comparable in size. Change PREVALENCE to 0.5 and rerun — the same detector now gives a posterior near 0.99. The detector did not change; the base rate did.

Step 2 — the three patterns, from memory (12 min)

The simulation checked a probability claim against counts. Now switch to the week's data-structure problems, where the evidence is an invariant rather than a population: the window must contain no repeated character, the lookup must contain only previously visited values, and pointer updates must preserve the remaining chain. These are separate problems, not extensions of the detector. Write these without looking at S023 to S025. Then run the assertions.

# patterns.py
from typing import Optional
 
 
# --- S023: sliding window -------------------------------------------------
def longest_unique(s: str) -> int:
    seen: dict[str, int] = {}
    best = start = 0
    for i, ch in enumerate(s):
        if ch in seen and seen[ch] >= start:
            start = seen[ch] + 1        # shrink: jump past the previous copy
        seen[ch] = i
        best = max(best, i - start + 1)
    return best
 
 
# --- S024: complement lookup ---------------------------------------------
def two_sum(nums: list[int], target: int) -> tuple[int, int] | None:
    seen: dict[int, int] = {}
    for i, n in enumerate(nums):
        if target - n in seen:
            return (seen[target - n], i)
        seen[n] = i
    return None
 
 
# --- S025: reverse in place + cycle detection ----------------------------
class Node:
    __slots__ = ("val", "next")
 
    def __init__(self, val: int, nxt: "Optional[Node]" = None) -> None:
        self.val = val
        self.next = nxt
 
 
def reverse(head: Optional[Node]) -> Optional[Node]:
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev
 
 
def has_cycle(head: Optional[Node]) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
 
 
def build(vals: list[int]) -> Optional[Node]:
    head = None
    for v in reversed(vals):
        head = Node(v, head)
    return head
 
 
def to_list(head: Optional[Node]) -> list[int]:
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out
 
 
if __name__ == "__main__":
    assert longest_unique("abcabcbb") == 3
    assert longest_unique("bbbbb") == 1
    assert longest_unique("") == 0
    assert two_sum([2, 7, 11, 15], 9) == (0, 1)
    assert two_sum([1, 2, 3], 100) is None
    assert to_list(reverse(build([1, 2, 3, 4]))) == [4, 3, 2, 1]
 
    h = build([1, 2, 3])
    assert has_cycle(h) is False
    h.next.next.next = h.next          # make a cycle
    assert has_cycle(h) is True
    print("all patterns pass")

Expected outcome: all patterns pass. One cause of a wrong result on a repeat behind the window start is a missing seen[ch] >= start guard. The guard stops a stale index from dragging the window backwards, as the discriminating input "abba" demonstrates: removing the guard gives 3 instead of 2.

Step 3 — measure the pointer-chasing claim (8 min)

The assertions check the named cases; the invariants justify the algorithms under their contracts. The timing rows ask what the chosen operations cost. Read the operation names as carefully as the container names: the list is drained from the end in one row and from the front in another. This is not a direct timing of the Node chain above or an isolated pointer-chasing benchmark; a deque uses linked blocks, and the front-pop row also uses fewer items. The useful comparison is the work each removal requires, not a blanket ranking of arrays and linked lists.

# chase.py
import time
from collections import deque
 
N = 2_000
 
# Array: append and pop from the end — contiguous, predictable.
t0 = time.perf_counter()
arr = []
for i in range(N):
    arr.append(i)
while arr:
    arr.pop()
array_time = time.perf_counter() - t0
 
# Deque: doubly-linked blocks — O(1) at both ends by design.
t0 = time.perf_counter()
dq = deque()
for i in range(N):
    dq.append(i)
while dq:
    dq.popleft()
deque_time = time.perf_counter() - t0
 
# Array used badly: pop from the front, which shifts every element.
t0 = time.perf_counter()
arr = list(range(N // 20))
while arr:
    arr.pop(0)
front_pop_time = time.perf_counter() - t0
 
print(f"list append/pop-end   : {array_time:.4f}s  ({N} items)")
print(f"deque append/popleft  : {deque_time:.4f}s  ({N} items)")
print(f"list pop(0)           : {front_pop_time:.4f}s  ({N // 20} items)")

The exact timings are machine-dependent and may be dominated by noise on this bounded fixture. Draining N front elements shifts N(N−1)/2 references; end-pop and deque popleft avoid those shifts. This operation-count derivation, not a required timing ratio, explains the asymptotic distinction.

Probability and statistics answer key

For disease D and positive test +, Bayes gives P(D|+) = sensitivity × prevalence / (sensitivity × prevalence + (1-specificity) × (1-prevalence)). At prevalence .01 the numerator and false-positive term are both .0099, yielding .5. At .001 the terms are .00099 and .00999, yielding about .09016. At prevalence .5 the answer is .99. Derive these before examining random output; simulation approximates the model, not the model's applicability to a real detector.

A Bernoulli variable has mean p and variance p(1−p) because X²=X. A binomial model for ten flips requires independent trials with a common p; a Poisson count requires assumptions such as a homogeneous Poisson process, whose interarrival time is exponential. Normal measurement error is a modeling assumption, not a consequence of the word “error.” For iid observations with finite positive variance, the normalized sample mean approaches a normal distribution under the classical CLT; heavy tails and dependence require additional conditions.

For a two-sided conversion test, the null is equal population rates and the alternative is unequal rates. A p-value .03 means a probability of .03 for a test statistic at least as extreme under the specified null model and its assumptions. It is not P(null is true), P(effect is real), an effect-size measure, or the probability this specific dataset was caused by chance. A 95% frequentist interval has 95% long-run coverage under its procedure's assumptions; it is not a posterior probability for the fixed realized interval. A large p-value does not establish equivalence. Repeated unadjusted looks or selected comparisons alter the error rate; prespecify a valid fixed or sequential analysis.

Twenty valid null tests at .05 have expected false-rejection count 1 by linearity of expectation, even without independence. Under independence only, the chance of at least one is 1−.95**20. Neither calculation guarantees one rejection in a realized experiment.

Missing variants and structural checks

The window start must never move backward. Complement lookup checks before insertion so a value cannot pair with itself, but two distinct copies can pair. Reversal requires an acyclic singly linked chain; do not call to_list on a cyclic fixture. Merge below assumes sorted disjoint acyclic input chains and reuses their nodes; overlapping input chains violate the contract.

# Continue after patterns.py in the same module.
def merge(a, b):
    dummy = Node(0); tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next
 
def sorted_pair(nums, target):
    left, right = 0, len(nums)-1
    while left < right:
        total = nums[left]+nums[right]
        if total == target:
            return left, right
        if total < target:
            left += 1
        else:
            right -= 1
    return None
 
assert longest_unique("abba") == 2
assert two_sum([3, 3], 6) == (0, 1)
assert reverse(None) is None and not has_cycle(None)
a, b, c = Node(1), Node(2), Node(3)
a.next=b; b.next=c
assert reverse(a) is c and c.next is b and b.next is a and a.next is None
assert to_list(merge(build([1, 3]), build([2, 4]))) == [1, 2, 3, 4]
assert sorted_pair([1, 2, 4, 8], 6) == (1, 2)
assert sorted_pair([], 6) is None

For sorted pair sum, a too-small sum eliminates the left value: pairing it with any smaller right value cannot improve the sum. The slow pointer in sorted deduplication instead marks the length of a unique output prefix, with the read pointer scanning untouched input. Floyd's pointers differ by one step per iteration inside a finite cycle, so their relative offset eventually reaches zero. Without a cycle the fast pointer reaches the end.

Hash equality requires equal keys to hash equally; collisions are possible for unequal keys and require equality checks. Chaining stores colliding entries separately, while open addressing probes other slots and needs an appropriate deletion policy. Python may cache string hashes, so repeatedly looking up the same string does not necessarily rehash every character. Worst-case comparisons and first hashing of long keys still cost work. Repeated immutable concatenation can copy growing prefixes quadratically, though CPython optimizes some += cases; list accumulation plus join gives a clearer portable cost model. Slicing copies its selected extent, not automatically a quadratic algorithm in every context.

A doubly linked list plus a key-to-node map supports LRU splices after a node is found. Arbitrary indexed access remains linear. Pointer chasing tends to harm locality, but “the CPU cannot prefetch” and a universal crossover size are unjustified hardware claims. These benchmarks do not establish either.

A sorted-prefix invariant you can execute

For sorted deduplication, maintain nums[:write] as the distinct values seen so far, in order. Read each original position once; write at or behind the read cursor so unread input is not overwritten. Return the prefix length, not a claim that the unused suffix has been erased. The sorted precondition is essential: adjacent comparisons do not find separated duplicates in an unsorted sequence.

def deduplicate_sorted(nums):
    write = 0
    for read in range(len(nums)):
        if write == 0 or nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1
    return write
 
values = [1, 1, 2, 2, 3]
length = deduplicate_sorted(values)
assert length == 3 and values[:length] == [1, 2, 3]
assert deduplicate_sorted([]) == 0

Under bounded-cost integer/character operations and ordinary hashing, longest_unique and two_sum take expected O(n) time and O(n) auxiliary space; the last-seen map may retain characters outside the active window. Sorted-pair search and sorted deduplication take O(n) time and O(1) auxiliary space. Reversing n acyclic nodes takes O(n) time and O(1) auxiliary space. Floyd detection takes O(n) time for n reachable distinct nodes and O(1) space. Merging chains of lengths m and n takes O(m+n) time and O(1) auxiliary space, excluding the input nodes it reuses. build and to_list allocate O(n) output; they are not constant-space representations of the entire exercise.

For a singly linked list, deleting an arbitrary node in constant time generally needs its predecessor (or the head when deleting the first node). A doubly linked list can unlink a known node through both links. Neither gives constant-time lookup of an arbitrary numeric position. Use these operation-specific contracts rather than assuming that merely holding any node pointer makes every insertion/deletion constant time.

Distribution moments: formula, assumptions and simulation

For a discrete variable, expectation is the sum of x P(X=x) over its support and variance is E[X²]−E[X]². A Bernoulli(p) trial has mean p and variance p(1−p). A binomial(n,p) is a sum of n independent Bernoulli trials: means and variances add, giving np and np(1−p). A Poisson(λ) count has mean and variance λ. An exponential waiting time with rate λ has mean 1/λ and variance 1/λ²; NumPy takes the reciprocal rate as its scale parameter. Normal(μ,σ²) has mean μ and variance σ². A count of rare events is not automatically Poisson: clustering or a changing rate can violate the homogeneous-process model.

Predict the following population moments before running the finite simulation. Here var() uses denominator N (ddof=0) to describe the generated sample, rather than the N−1 unbiased variance estimator. Sample estimates need not equal population moments; do not turn one random tolerance into a universal test.

# Continue with the preinstalled NumPy dependency used by the Bayes drill.
rng_moments = np.random.default_rng(19)
models = [
    ('Bernoulli(.3)', rng_moments.binomial(1, .3, 20000), .3, .21),
    ('Binomial(10,.3)', rng_moments.binomial(10, .3, 20000), 3., 2.1),
    ('Poisson(2)', rng_moments.poisson(2., 20000), 2., 2.),
    ('Exponential(rate=2)', rng_moments.exponential(.5, 20000), .5, .25),
    ('Normal(3,variance=4)', rng_moments.normal(3., 2., 20000), 3., 4.),
]
for label, sample, mean, variance in models:
    print(label, 'sample:', float(sample.mean()), float(sample.var()),
          'population:', mean, variance)
    assert np.isfinite(sample).all()  # sanity, not a statistical guarantee

In Bayes' rule, P(D) is the prior/base rate, P(+|D) the likelihood/sensitivity, P(+) the evidence probability, and P(D|+) the posterior. Specificity is P(negative|not D), not the same as overall accuracy, which also depends on prevalence. Under the elementary CLT assumptions, the sample mean's standard error is σ/√n; this motivates approximate intervals/tests with justified variance estimation, not a claim that the original observations become normal.

For the array prompt, element address arithmetic gives constant-time positional access under fixed-size reference storage; insertion into the middle shifts the suffix, taking linear time. The unique-window template expands right, shrinks left until valid, then records the best length. Here the last-seen map jumps directly to the needed left boundary. Hash-table performance additionally wants well-spread hashes; this is distinct from the correctness rule that equal keys hash equally.

Structural exercise and solution: merge two sorted disjoint chains with repeated equal values. The <= rule takes the left node first on a tie, preserves all input nodes exactly once, and requires no new data nodes beyond the discarded dummy. A self-loop must make has_cycle return True; an empty chain returns False. The slow pointer for array deduplication instead stores the next free slot of the unique output prefix. These are different pointer invariants, not interchangeable templates.

Answer constraints and corrections

For the rare-fraud variant with prevalence .001, the positive predictive value is 0.00099/(0.00099+0.00999), about 9.02%, not 99%; the .01-prevalence simulation instead targets .5. Twenty null tests at α=.05 have expected one false rejection; under independence the probability of at least one is 1−.95²⁰, about 64.15%. Correct the common confusion between expected count and probability.

Gap analysis + next week preview · 10 min

Score each original recall question separately: explain unaided; explain with a hint; or not yet. A fluent verbal answer is not a successful implementation. Choose one failed concept, write a counterexample that distinguishes the mistaken rule from the correct one, and schedule an unseen retest. Keep successes as well as failures in the log so the plan does not become a list of increasingly familiar problems.

For the drill, require an explicit input contract, a correctness argument or domain assumption, one ordinary case, one boundary case and an independent expected result. A chart, compile success or passing sample alone does not meet that rubric. Use the stated input contracts and named runtime when interpreting a result; finite tests and timing samples are not universal correctness or performance guarantees.

Next week (S026–S030) continues the data structures track: stacks and queues and where LIFO and FIFO show up in real systems; recursion, the call stack, and base cases; trees and binary search trees with breadth-first and depth-first traversal; heaps and priority queues; and graphs with representation choices, BFS, DFS, and shortest path. The pointer discipline you drilled in the linked-list surgeries is the direct prerequisite for tree traversal.

Corrective source notes

• 3.3 Two Basic Rules of Probability - Introductory Statistics 2e | OpenStax — Conditional probability divides joint probability by the conditioning probability; the lesson derives the three Bayes posteriors. Source retrieved 2026-10-07; passage and applicability reviewed 2026-10-07.
• ASA press release on statistical significance and p-values (7 March 2016) — P-values do not give probability of the null, chance-caused data, or effect size. Source retrieved 2026-10-07; passage and applicability reviewed 2026-10-07.
• 7.1 The Central Limit Theorem for Sample Means (Averages) - Introductory Statistics 2e | OpenStax — The sample mean has variance sigma squared over n in the elementary CLT setting. Source retrieved 2026-10-07; passage and applicability reviewed 2026-10-07.
• numpy.random.Generator.exponential — NumPy v2.5 Manual — NumPy exponential scale is the reciprocal of rate; the rate-two example passes scale .5. Source retrieved 2026-10-07; passage and applicability reviewed 2026-10-07.
• 3. Data model — Python 3.14.8 documentation — Hash-based container correctness requires stable key hashes; collision costs are a separate performance issue. Source retrieved 2026-10-07; passage and applicability reviewed 2026-10-07.

The cited passages support these named claims. The algebra, counterexamples and executable fixtures supply the lesson-specific reasoning; finite checks are not universal benchmarks.