R05 · Week 5 Recall & Drill

Weekly revision · Week 5 · Covers 5 sessions from Mon–Fri.

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

90-min structure

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.

Gotcha you probably forgot: "the test is 99% accurate" and "a positive result is 99% likely to be right" are different conditional probabilities. The first is a property of the detector; the second also depends on how rare the condition is. When the condition is rare, the false positives drawn from the huge negative population outnumber the true positives, and the probability that a positive is genuine can be far below the accuracy number.

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.

Gotcha you probably forgot: peeking inflates the false-positive rate. Every time you check an in-flight test and reserve the right to stop when it looks significant, you give the noise another chance to cross the threshold. Fix the sample size in advance, or use a method designed for continuous monitoring — do not stop the moment the dashboard turns green.

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.

Gotcha you probably forgot: building a string with s += part inside a loop is quadratic, not linear. Strings are immutable, so each concatenation allocates a new string and copies everything accumulated so far. Collect the pieces in a list and join once. Slicing has the same hidden cost — a slice copies the elements it selects, so slicing inside a loop is quadratic too.

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.

Gotcha you probably forgot: constant-time lookup is an average-case, amortised claim that assumes hashes spread keys evenly. The worst case, with every key landing in one bucket, is linear. And the constant factor is dominated by computing the hash itself, which for a string or tuple is proportional to its length — so hashing a long key is emphatically not free.

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.

Gotcha you probably forgot: the famous constant-time insert only holds if you already have a pointer to the node. Getting there is a linear traversal, and that traversal is a chain of dependent pointer loads that the CPU cannot prefetch — each load must complete before the next address is even known. An array's linear-time block move is a single predictable sweep through contiguous memory, and it wins up to surprisingly large sizes.

Hands-on drill · 30 min

Task: prove the base-rate result by 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)

mkdir -p ~/projects/w5-drill && cd ~/projects/w5-drill
uv venv .venv --python 3.12 && source .venv/bin/activate
uv pip install numpy

# basrate.py
import numpy as np
 
rng = np.random.default_rng(7)
N = 1_000_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 both accuracy figures 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)

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. If longest_unique fails on a string with a repeat far behind the window start, you dropped the seen[ch] >= start guard — that guard is what stops a stale index from dragging the window backwards, and it is the single most commonly missed line in this template.

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

# chase.py
import time
from collections import deque
 
N = 200_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)")

Expected outcome: the first two rows are broadly comparable, both handling the full item count quickly. The third row processes only a twentieth as many items yet takes disproportionately longer, because every pop(0) shifts the entire remaining array down one slot. That is the quadratic behaviour behind "use a deque when you need to remove from the front" — and the point of the drill is that you have now seen it rather than been told it.

Gap analysis + next week preview · 10 min

• Did the base-rate simulation land where you predicted before you ran it? If you expected a number near 0.99, that intuition will misfire on every rare-event classifier you ever evaluate — write the corrected version down.
• Which of the three patterns did you have to look up? That is the one to rewrite from scratch tomorrow morning, not at the end of the week.
• Can you state what a p-value is a probability of, in one sentence, without hedging? If not, that sentence is the highest-value thing to memorise from this week.

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.

Part of the 6-month evergreen learning plan.