Mock Set 3 — One Hard, 45 min

Review boundary and corrected contracts

These are practice protocols, not hiring rubrics. Times, score bands and review intervals are adjustable conventions; neither a difficulty label nor a score predicts an interview outcome. Record the input contract, evidence of correctness and what remains uncertain.

Learning objective: Decompose an unfamiliar Hard into testable sub-problems and report useful partial progress during a 45-minute attempt.

Series: LeetCode — From Basics to Production-Ready · Session 61 / 65 · Phase 4 · Design review simulation

Watch first

Optional pre-reading, outside the timed session. These original links are retained as navigation; they were not watched or externally revalidated in this review. Use them to collect observations, not as governing evidence for company frequency, stress effects or hiring outcomes.

• Example Coding / Engineering Interview — Observe how a baseline and optimisation are explained.
• Software Engineering Job Interview — Full Mock Interview — Observe clarification and pauses in the first twenty minutes.
• Mock Google Interview — Coding and Algorithms Tips — Observe the closing status report; do not infer a universal grading rubric.

Why this session exists

Some Hard problems combine familiar mechanisms; others need a new invariant or technique. “Two Mediums stacked” is a search heuristic, not a measured rule about difficulty labels. Trapping Rain Water can combine prefix and suffix maxima. Word Ladder II can combine BFS distance layers with reconstruction along shortest-path parents; reconstruction still has output-dependent cost. Merge k Sorted Lists can repeatedly select the smallest current list head with a heap; it does not require a separate two-list merge.

Practise finding the interface: what does each component consume, produce and guarantee? For rainwater, both scans return a maximum at every index; combining those arrays is then justified by the lower enclosing wall. Naming two patterns without proving that their outputs compose is not enough.

A successful full solve is welcome, not evidence that you selected badly. If unfinished, leave a tested baseline, a specific optimisation hypothesis, one working component and a candid summary. Those are this exercise's artifacts, not a promise of passing a real evaluation.

Blank-file warm-up

No template warm-up: this attempt measures cold recall. Select by number from the bank without reading statements, and replace a problem you recognise. Check required techniques after the attempt, not while selecting for comfort. Keep the single communication habit chosen in L58 visible; observe whether you use it during difficulty rather than assuming it will collapse.

Pattern anatomy

The working discipline is to name the current sub-problem and its output contract. A name gives the next experiment a target; it does not establish correctness.

# HARD DECOMPOSITION PROTOCOL — 45 minutes
# 0–8: clarify, trace a small input, implement a bounded baseline if feasible.
# 8–20: run probes; write the interface and a test for a promising component.
#   A: What repeated computation could I precompute?
#   B: What would sorting buy, and would it destroy needed input order?
#   C: What state captures the future-relevant history?
#   D: Which familiar mechanisms could compose, and what links them?
# 20–40: implement and test the justified approach or one useful component.
# 40–45: state what passes, what fails, the next step and conditional complexity.

For probe C, try DP when equivalent states can share work, or backtracking when enumerating choices is necessary; history dependence alone does not prove either is the best approach. A baseline can expose repeated work, but a proof or hand trace can also reveal an invariant without executable brute force. Never run exponential code on an unbounded input just to meet the clock.

The cue

Treat each cue as a hypothesis to test:

1. Two requirements may suggest separate components: counting frequencies and selecting the largest k is one example. Two nouns do not prove decomposability.
2. A simple slow baseline exposes repeated work. Identify which repeated operation dominates before choosing precomputation.
3. Small bounds permit candidate methods. Values in 0–100 permit 101 buckets; they do not require counting sort. Sorted input may permit a monotone search, but prove the predicate.
4. A familiar sub-structure such as next-greater-element suggests a stack only when its discard rule is valid.
5. Adding reconstruction to a decision problem, as in Word Break II, can require enumerating exponentially many outputs even if the feasibility table is small.

If no probe helps, record the missing invariant rather than declaring the problem unfair or proving that an unfamiliar named algorithm is necessary. During review, distinguish “I did not find a decomposition” from “the editorial uses a technique I have not learned.”

Guided solve

Worked example: Trapping Rain Water. Heights are nonnegative integers and columns have unit width. At index i, a water unit needs a wall at least that high on both sides. Including the current column in both maxima makes their minimum at least its height, so the subtraction is already nonnegative. Empty inputs return zero.

Baseline. Compute the two enclosing maxima afresh:

def trap_brute(h):
    total = 0
    for i in range(len(h)):
        left = max(h[:i + 1])
        right = max(h[i:])
        total += min(left, right) - h[i]
    return total

Each slice and maximum costs O(n), giving O(n²) time and O(n) peak temporary space in this Python implementation, not O(1) extra space. Slices are transient rather than retained for every index.

Probe A. Cache each prefix/suffix maximum once:

def trap(h):
    n = len(h)
    if n < 3:
        return 0
    left = [0] * n
    right = [0] * n
    left[0] = h[0]
    for i in range(1, n):
        left[i] = max(left[i - 1], h[i])
    right[n - 1] = h[n - 1]
    for i in range(n - 2, -1, -1):
        right[i] = max(right[i + 1], h[i])
    return sum(min(left[i], right[i]) - h[i] for i in range(n))

The forward induction is left[i] = max(h[0:i+1]): extending a prefix changes its maximum only if the new height is larger. The reverse induction establishes right[i] = max(h[i:n]). For [3, 0, 2, 0, 4] these are [3,3,3,3,4] and [4,4,4,4,4]; contributions [0,3,1,3,0] sum to 7. Both functions leave the input unchanged. The cached version takes O(n) time and O(n) auxiliary space.

A two-pointer alternative can use constant auxiliary space, but specify its own invariant rather than mixing pointer rules. Update maxima at the two current boundaries, then settle the side with the smaller running maximum: the opposite known wall certifies that side's limiting level. The quiz below explains this version; it is not an additional displayed implementation.

Solo timed

Attempt one unseen Hard for 45 minutes with no editorial; explain decisions aloud when useful. At minute 8, if no baseline is feasible, save a hand trace and a precise baseline description. At minute 20, test the most promising probe on a counterexample instead of committing blindly. At minute 40, stop implementing and summarize even if a function is unfinished. Afterward, read feedback, close it and reimplement the missing mechanism on a small input.

Timing rubric

Use observable checkpoints rather than an inferred grade:

The first two rows partition the eight-minute baseline stage. Stage lengths are 8 + 12 + 20 + 5 = 45 minutes. A further 20-minute review makes 65 minutes, excluding optional pre-reading and a later re-solve.

Self-scoring checklist

Use five dimensions, 0–2 each, total 10. Record the evidence beside each number:

• Baseline: 2 = tested baseline within the chosen budget; 1 = late, traced only or not run; 0 = absent.
• Seam: 2 = independently justified composition; 1 = justified after a hint; 0 = no justified decomposition.
• Build: 2 = complete algorithm passes relevant tests; 1 = a component passes; 0 = baseline only or no working component.
• Narration: 2 = decisions, uncertainty and pivots explained; 1 = explanations missing during difficulty; 0 = no usable reasoning record. Quiet thinking is allowed; no twenty-second speech quota.
• Close: 2 = complete position statement; 1 = partial statement; 0 = absent.

8–10 suggests this protocol was mostly followed; 5–7 identifies several items to revisit; below 5 means inspect the evidence before selecting a repair. These are local labels, not pass/borderline/fail predictions, and an aggregate can hide a serious correctness gap.

Hard bank — pick blind

Pick by number before opening the statement. These are examples of mechanisms, not a company-frequency ranking.

Precomputation or composition — start here:

• Trapping Rain Water (42) — prefix max + suffix max.
• Merge k Sorted Lists (23) — heap selection over current list heads.
• Sliding Window Maximum (239) — window + monotonic deque.
• Word Break II (140) — the Medium DP plus reconstruction.
• Largest Rectangle in Histogram (84) — monotonic stack + span arithmetic.
• Basic Calculator (224) — stack + parsing.

Harder seams — probe C or a specific invariant:

• Median of Two Sorted Arrays (4) — binary search on a partition invariant.
• Serialize and Deserialize Binary Tree (297) — traversal + null encoding.
• Word Ladder II (126) — BFS levels + backtracking over parents.
• Minimum Window Substring (76) — window + satisfied-counter.
• LFU Cache (460) — two hash maps + a frequency bucket list.

Additional mechanisms — choose after checking your prerequisites during review:

• Regular Expression Matching (10), Count of Smaller Numbers After Self (315), Number of Atoms (726). If the probes fail, record the limitation and review the missing mechanism afterward. The labels do not establish what is fair in an interview.

Common failure modes

No baseline or concrete example. A tiny correct reference makes an optimisation falsifiable. If implementing it would consume the session, state it precisely and test a hand-worked instance instead.

Circling without a named sub-problem. Write the next question: “Can I compute each prefix maximum once?” A wrong hypothesis can be useful when you test and reject it.

Continuing after a counterexample. Record why the approach fails; decide whether a repaired invariant fits the remaining budget. Change direction for evidence, not merely discomfort.

Silence or over-narration. Give concise decision updates and label thinking pauses. Neither constant speech nor guessed confidence improves a proof.

Implementing nothing until every piece is known. Build a component with explicit inputs, outputs and tests. Keep the integration gap visible.

No closing statement. Do not call an unverified plan correct. Say what was tested and what remains conjectural.

The misconception “insight either arrives or it does not” misses systematic search. The four probes provide concrete experiments, not coverage of a known fraction of Hard problems. Use the firewood-seam analogy only as a search aid: a mathematical problem need not have a convenient crack. Derive a baseline, inspect its repeated work, propose a component, prove the interface, then test the composition. No prediction such as “two of your next three Hards will yield” follows.

Baseline-first trades implementation time for a reference result. Direct optimisation is reasonable when you can already justify the invariant and complexity. At roughly minute two, decide which path gives you the best checkable artifact rather than treating the baseline as a universal prerequisite.

Complexity

This is a session budget, not a single algorithm bound. The 45-minute stages and 20-minute review are separate from later retrieval. The rainwater baseline is O(n²) time/O(n) temporary space; cached maxima are O(n) time/O(n) space under constant-cost integer operations. Python integer bit costs can grow with height magnitude.

Self-check (answer follows each question).

Q: What are the four probes for finding the seam in a Hard?

A: Precompute repeated work; ask what sorting would buy; define future-relevant state; test whether known mechanisms compose through a justified interface.

Q: Why write a brute force rather than treating it only as a fallback?

A: It makes the contract concrete, supplies small expected outputs and exposes repeated work. It is useful, not logically required: a valid proof and hand trace may justify a direct approach.

Q: What is the target outcome, and must it exclude a full solve?

A: Aim for a justified decomposition, tested baseline or component, optimisation plan and honest summary. A full correct solve is a good result too; it does not by itself show the exercise was too familiar.

Q: How do you recognise circling rather than progress?

A: You cannot name the current sub-problem, proposed invariant or next test. Write one down, test it and either advance or reject it.

Q: Why does an oddly specific constraint such as values in 0–100 matter?

A: It makes a 101-entry bucket representation feasible. That is a candidate to cost and validate, not proof that the intended algorithm must use buckets.

Q: What invariant permits a constant-space two-pointer rainwater method?

A: Maintain maxima seen from each end, including current endpoints. If left_max is no greater than right_max, some known right wall reaches left_max, so the left index's water is left_max minus its height; settle it and advance left. Otherwise settle right symmetrically. Do not interchange this running-maximum comparison with another pointer rule without its proof.

Recovery scripts

Blank at the start: “Let me trace the smallest nontrivial input and specify what counts as a valid output.” A tiny instance can expose the contract without promising it reveals the algorithm.

Baseline works, no probe fires: ask the probes aloud and name exactly what is recomputed. If nothing useful emerges, document that and seek feedback after the timed attempt.

Approach fails: “This state loses ordering information. I will test adding one dimension for five minutes, then stop if I cannot justify it.” Name the fallback before spending the five minutes.

Broken code at the buzzer: “It passes these two examples but fails duplicates here. My hypothesis concerns pointer advancement; I have not established the fix.” Never call the approach proven solely because the suspected bug sounds local.

A hint arrives in a mock: restate it, test what it implies, and record the attempt as assisted. Taking feedback is compatible with a rigorous self-assessment.

Checkpoint

You can assess this session when you can:

• Produce a tested bounded baseline or explain why the chosen baseline cannot fit the eight-minute target.
• Run precompute, sort, state and composition probes explicitly.
• Break circling with a named question and test.
• Implement a component and specify the missing interface.
• Deliver the minute-40 position statement.
• Score all five dimensions with evidence, not a hiring prediction.
• Use each recovery script without pretending an unverified fix is correct.
• Distinguish a found decomposition from a technique you still need to learn; unsuccessful probing alone cannot decide which case applies.

Spaced queue

Record both assistance and correctness. The proposed ladder is cold +60d, warm +21d, hint +7d, failed +2d then +7d; adjust from delayed performance. For consistency with the other practice lessons, an editorial-assisted completion is hint; no working implementation is failed. Neither is independent mastery.

Schedule a from-scratch attempt tomorrow to rehearse the mechanism, even after a full solve if useful. Keep that near-term practice separate from evidence of delayed retention; a later unseen variant checks transfer. There is no supported claim that Hards decay faster or that the second attempt contains most learning.

Carry forward: test the seam, keep a baseline when useful, run all four probes, name the current question, preserve partial code with its limits, and reserve the closing summary. Also record whether the L58 communication habit held under this attempt's difficulty.

Executable practice boundary

Both displayed functions assume nonnegative integer heights and unit-width columns, accept empty/short arrays as zero and do not mutate the input. Bounded exhaustive tests use an independent water-level enumeration, not the displayed baseline as its own correctness oracle. Negative heights and non-unit widths are outside this contract. Finite tests are not a proof for every input; the prefix/suffix induction supplies the general argument.

Corrective source notes

• Dunlosky and colleagues: Improving Students’ Learning With Effective Learning Techniques — publisher-hosted 2013 review summary, saved 2026-10-07 and re-read 2026-10-09. Supports the limited rationale for practice testing and distributed practice; not exact intervals, decay rates, coding-specific causal effects or hiring scores.

Algorithmic arguments and arithmetic above are derived for the stated contracts. Finite executable checks, saved source passages and their limits are recorded in the review artifacts; they do not certify unexecuted service behavior or interview outcomes.