L61 · Mock Set 3 — One Hard, 45 min

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

Watch first

Watch these before you pick your Hard — not after. The point is to load the shape of a real 45-minute session into your head so today's clock feels familiar rather than novel.

Why this session exists

Hards are usually two Mediums stacked. That is the claim this session is built on, and it holds far more often than the difficulty label suggests.

Trapping Rain Water is prefix maxima plus suffix maxima — two array scans you already own. Median of Two Sorted Arrays is binary search plus a partition invariant. Word Ladder II is BFS plus backtracking on the parent graph. Merge K Sorted Lists is a heap plus the two-list merge from an Easy. In each case the difficulty is not in either component. It is in seeing that there are two components and finding where they join.

So the skill being trained today is decomposition — specifically, locating the seam. And the secondary skill, which matters at least as much in a real loop, is being visibly productive for forty-five minutes on a problem you do not fully solve. Failing a Hard is normal and frequently survivable. Failing it silently, with nothing on the screen and no stated approach, is not.

A note on expectations. Do not expect to solve it. Roughly speaking, if you solve the Hard outright you picked one that was too close to something you knew, and the session taught you less than a genuine struggle would have. The target outcome is: correct decomposition, a working brute force, a stated plan for the optimisation, and a partial implementation. That set is a pass in most real interviews.

Blank-file warm-up

None. Cold, same as the other mocks.

One setup step: pick a Hard without reading its statement. Filter by difficulty, skip anything whose title you recognise, and take one. Do not browse until something looks tractable — that selection bias is how people accidentally pick a Hard they have already half-solved.

If you did L58's recording, keep your one chosen communication habit in mind. This session is also a check on whether that fix survived contact with a harder problem, which is where such fixes usually collapse.

Pattern anatomy

The pattern is seam-finding, and the invariant is: at every moment you are working on a named sub-problem, not on "the problem". The failure state on a Hard is a kind of undirected circling where you are thinking hard about everything at once and making no reducible progress. Naming a sub-problem — even the wrong one — restores structure.

# HARD DECOMPOSITION PROTOCOL — 45 minutes, one problem.
#
# STAGE 1 — BRUTE FORCE, ALWAYS (0-8 min)
#   Write the exponential or quadratic solution. Actually write it, do not just describe it.
#   Two reasons: it proves you understood the problem, and the optimisation is almost always
#   found by staring at the brute force and asking which step repeats work.
#   In a real interview a working brute force is a partial pass. Silence is not.
#
# STAGE 2 — FIND THE SEAM (8-20 min)
#   Run these four probes in order. One of them usually opens the problem.
#
#   PROBE A — "what would I precompute?"
#     If the brute force recomputes something per index, precompute it.
#     Prefix sums, prefix maxima, suffix maxima, counts. This alone solves many Hards.
#
#   PROBE B — "what if the input were sorted?"
#     If sorting makes it easy, the real question is whether you can afford the sort
#     or need an order-maintaining structure (heap, BST, Fenwick).
#
#   PROBE C — "what is the state?"
#     If the answer depends on choices made so far, it is DP or backtracking.
#     Write dp[i] = ... in ENGLISH before any code. Wrong state definition is the
#     single most common way a DP Hard is lost.
#
#   PROBE D — "which two patterns do I know that each solve HALF of this?"
#     This is the seam probe proper. Say two pattern names out loud and check whether
#     their composition covers the problem. Most Hards answer to this.
#
# STAGE 3 — IMPLEMENT THE HALF YOU CAN (20-40 min)
#   Even if the other half is unsolved. Working code for one component plus a clear
#   statement of the missing piece is a far stronger position than nothing.
#
# STAGE 4 — STATE WHERE YOU ARE (40-45 min)
#   Out loud: what works, what does not, what you would do with more time,
#   and what the complexity would be if the plan completed.

Probe D is the one worth internalising. "Which two things I already know solve half of this each" is a question you can ask about any Hard, and it converts an intimidating monolith into a search over a small set of known pieces.

The cue

You are looking at a decomposable Hard — as opposed to one that genuinely needs an unfamiliar algorithm — when:

1. The problem asks for two things at once. "Find the k most frequent" is counting plus selection. "Longest valid substring" is often validity-checking plus a window. Two nouns in the objective usually means two components.
2. A brute force is easy to write but obviously too slow. That is the good case: the gap between brute force and optimal is where a known pattern lives, and you can search for it systematically with the four probes.
3. One of the constraints is oddly specific. "The array is sorted", "values are at most 100", "k is at most 10". Specific constraints are load-bearing — they are there because the intended solution uses them.
4. You recognise a familiar sub-structure in an unfamiliar frame. "This inner part is just next-greater-element" is the seam appearing.
5. The Hard is a known Medium with one extra dimension. "Word Break" is a Medium; "Word Break II" adds reconstruction, which is the standard DP-plus-backtracking composition. Many Hards are literally a Medium with output reconstruction bolted on.

The case where decomposition does not apply is when the problem needs a specific named algorithm you have never met — max-flow, suffix automaton, heavy-light decomposition. You will recognise this by the four probes all returning nothing. That is a legitimate outcome and the correct response is to say so, implement the brute force, and move on. Not every Hard is fair.

Guided solve

No fixed problem, since yours is unseen. What follows is the protocol worked through with a concrete example, so you can see what the probes look like when they fire.

Worked example: Trapping Rain Water. Given heights, compute the water trapped.

Stage 1, brute force. For each index, water above it is min(max height to the left, max height to the right) - height[i], floored at zero. Computing those two maxima per index by scanning gives O(n²).

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

That is correct and too slow, which is exactly the position you want to be in at minute eight.

Stage 2, probes. Probe A fires immediately: the brute force recomputes the same prefix maximum and suffix maximum over and over. Precompute both in two passes. That is the seam — the problem is prefix maxima plus suffix maxima, two array scans you have owned since the early sessions.

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))

O(n) time, O(n) space. There is a two-pointer version that gets space to O(1), and mentioning it is worth a point even if you do not write it — but the O(n)-space version is a complete, correct answer to a Hard, reached by a single probe.

Notice the shape of what happened. Nothing clever was invented. The brute force was written, one probe was applied, and a known pattern appeared. That is the entire method, and it works on more Hards than intuition suggests.

Solo timed

One unseen Hard, 45 minutes, no editorial, narrated out loud if you can.

Hints, kept generic:

• At minute 8, if you have no brute force on screen, stop trying to be clever and write the exponential one. You cannot search for the seam without something to look at.
• At minute 20, if no probe has fired, pick the most promising one and commit anyway. Circling is worse than committing to a wrong path — the wrong path fails informatively and quickly.
• At minute 40, stop implementing and state your position out loud regardless of where you are. Practising the summary is part of the session.

Timing rubric

The stage boundaries are hard checkpoints. Set an actual timer with marks at 8, 20, and 40 minutes — not a mental estimate, because time perception under difficulty is unreliable in exactly one direction.

The 40-minute mark is the one people skip and the one that most changes an interviewer's write-up. Stop implementing even mid-function.

Self-scoring checklist

Score each dimension 0–2 immediately after the buzzer, before any autopsy. Total out of 10.

• Baseline (0–2). 2 = brute force running before minute 8. 1 = written but late or not run. 0 = never wrote one.
• Seam (0–2). 2 = named the correct decomposition unprompted. 1 = found it after the editorial hinted. 0 = never decomposed.
• Build (0–2). 2 = optimal implemented and passing. 1 = one component working. 0 = nothing beyond the brute force.
• Narration (0–2). 2 = no silence longer than ~20 seconds throughout. 1 = narrated while comfortable, went silent while stuck. 0 = mostly silent.
• Close (0–2). 2 = full position statement including target complexity. 1 = partial. 0 = coded to the buzzer.

8–10 — that is a pass in most real loops even without a full solve. 5–7 — borderline; look at which dimension cost you, it is usually narration or close, both of which are cheap to fix. Below 5 — the problem was likely genuinely out of range, or you skipped the brute force. Check which before concluding anything about your level.

Narration and close are worth 4 of the 10 points on purpose. They are the two dimensions that are entirely under your control regardless of whether the problem was fair.

Hard bank — pick blind

Pick by number without reading the statement. Company tags reflect these problems' long-standing reputation as commonly-asked questions at those companies, not any claim about a specific interview loop.

Decomposable — probe A or D fires (start here):

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

Harder seams — probe C or a specific invariant:

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

Probably unfair for 45 minutes — use only to practise the honest bail-out:

• Regular Expression Matching (10), Count of Smaller Numbers After Self (315), Number of Atoms (726). If all four probes return nothing on one of these, saying so clearly and shipping the brute force is the correct performance.

Common failure modes

Refusing to write the brute force. The most common and the most costly. It feels like wasted time on a Hard, and it is the thing that most reliably reveals the optimisation. It is also the difference between a partial pass and a zero in a real interview.

Circling without a named sub-problem. Thinking hard about the whole problem simultaneously produces no reducible progress. If you cannot name what you are currently working on, you are circling — run the probes.

Pursuing an approach past the point it stopped working. Sunk cost applies to interview minutes. If your chosen probe has produced nothing in ten minutes, say so out loud and switch. Announcing the switch is a strength signal.

Silence during the hard part. Whatever communication fix you chose in L58 will collapse here if it has not consolidated, because difficulty consumes exactly the bandwidth that narration needs. Watch for it.

Implementing nothing because the full solution is not clear. Half a solution plus a stated plan beats an empty editor by an enormous margin. Implement the component you understand.

Not stating the position at the end. Even when you have failed, "here is what works, here is what does not, here is what I would try next, and the complexity would be O(n log n) if it completed" converts a failure into a demonstration of structured thinking.

Complexity

Session budget rather than an algorithm:

Stage allocation: brute force 0–8 min, probes 8–20 min, implementation 20–40 min, position statement 40–45 min. The stage boundaries are checkpoints — at each one, ask whether you are where you should be, and if not, move on regardless.

Expected outcome distribution: full solve is the minority case. Correct decomposition plus a working brute force plus a partial optimal implementation is the target and is a pass in most real loops.

Post-session cost: 20 minutes for the autopsy, using the same four buckets from L57 — classification, template, implementation, time. Then re-solve from scratch tomorrow whether or not you solved it today.

Recovery scripts

On a Hard you will blank. Rehearse the exit routes now so the reflex exists at minute twenty-two when it is needed.

Blank at the start — no idea what the problem even is. Go concrete. "Let me work the smallest non-trivial input by hand and see what I do." Solving n=3 manually and then asking what procedure you just followed regenerates an approach more reliably than staring at the constraints. Narrate the hand-trace; it is legitimate work and it is visible.

Blank after the brute force — no probe fires. Say the probes out loud as questions rather than thinking them. "Am I recomputing anything? — yes, this inner max. Can I precompute it? — yes." Externalising the search converts it from a vague feeling of stuckness into a checklist, and the interviewer can now hint against a specific question rather than against silence.

Committed to an approach and it is failing. Price the pivot out loud and then pivot: "This DP state does not capture the ordering constraint. I could add a second dimension, or switch to backtracking with pruning. The second dimension is closer to what I have; let me try that for five minutes and abandon it if it does not resolve." A time-boxed pivot with a stated fallback is a senior signal.

Out of time with broken code. Do not debug into the buzzer. "This passes the first two examples and fails on duplicates. The bug is in how I advance the left pointer on equal values. The approach is O(n log n) and correct; this is an implementation detail I would fix by adding a skip-duplicates loop here." Naming your own bug precisely is worth more than a silent half-fix.

Interviewer offers a hint and you feel embarrassed. Take it immediately and audibly: "That helps — so if I sort by end time first, the greedy choice becomes local." Hint-taking is expected on Hards. Resisting a hint to preserve pride burns minutes and reads badly.

Checkpoint

Spaced queue

Today's Hard enters the queue at whatever it earned. The ladder applies as usual — cold +60d, warm +21d, hint +7d, failed +2d then +7d — with one adjustment specific to Hards: a Hard you solved only after reading the editorial is failed, not hint. Hards decay faster than anything else and the standard is stricter.

Re-solve it from scratch tomorrow regardless of today's outcome. For a Hard, the second attempt is where most of the learning happens, because you now know the seam and can practise the implementation without the search.

Also check: did the L58 communication habit survive? If narration collapsed during the hard part, that goes back on the list for the L64 contest.