Mock 04 — Hard LeetCode

Interview type: LC hard, FAANG onsite-level Target role: SWE-II → Senior; FAANG onsite second round Time limit: 60 minutes Format: 1 hard problem (or 1 medium + 1 hard if you finish hard early) Hints policy: One free hint at 20 min; additional -2 each. After 3 hints, the round is “failed” by FAANG standards. Primary goal: Reach the optimal algorithm under pressure, implement correctly, handle the hard follow-ups.

What This Mock Tests

Hards are where mid-level engineers separate from senior. The bar:

  • Recognize the non-obvious pattern (binary search on answer, segment tree, DP on intervals, etc.) within 10 minutes
  • Articulate why the optimal works, with correctness sketch
  • Implement under time pressure
  • Handle 2+ follow-up extensions

Scoring emphasizes Problem Understanding (#1), Optimization (#4), Correctness (#5), and Tradeoff Reasoning (#13).

Pick One Problem

Problem A — Median of Two Sorted Arrays (LC 4)

Given two sorted arrays nums1 and nums2 of sizes m and n, return the median of the combined sorted array. Must run in O(log(m+n)) time.

Examples:

[1, 3], [2]         → 2.0    (merged: [1, 2, 3])
[1, 2], [3, 4]      → 2.5    (merged: [1, 2, 3, 4])
[],     [1]         → 1.0
[1, 2], []          → 1.5

Constraints: 0 ≤ m, n ≤ 1000. m + n ≥ 1. -10^6 ≤ values ≤ 10^6.

Problem B — Trapping Rain Water (LC 42)

Given heights of bars height[i], compute how much water it can trap after raining.

Examples:

[0,1,0,2,1,0,1,3,2,1,2,1] → 6
[4,2,0,3,2,5]              → 9

Constraints: 1 ≤ |height| ≤ 2×10^4. 0 ≤ height[i] ≤ 10^5.

Problem C — Merge K Sorted Lists (LC 23)

Given an array of k sorted linked lists, merge them into one sorted list.

Examples:

[[1,4,5], [1,3,4], [2,6]] → [1,1,2,3,4,4,5,6]
[]                         → []
[[]]                       → []

Constraints: 0 ≤ k ≤ 10^4. 0 ≤ |lists[i]| ≤ 500. Sum of all lengths ≤ 10^4.

Expected Communication Style

  1. Restate with input/output types and the explicit complexity constraint (where given).
  2. Ask precise clarifying questions: O(log) vs O(m+n) required? Negative numbers? Empty arrays? Duplicates?
  3. State a baseline: the obvious O(m+n) for A, O(N) two-pointer for B, O(N log K) for C.
  4. Identify whether the baseline meets the constraint. If not, derive the harder approach.
  5. Articulate the key insight before coding. (“For A, I’ll binary search on the partition position in the shorter array such that the left halves of both arrays combined form the lower half of the merged array.”)
  6. Code carefully — hards have boundary conditions everywhere.
  7. Test 3+ cases including the boundary (empty array, both arrays size 1, large mismatch).

Solution Sketches

A. Median of Two Sorted: binary search on the partition i in the shorter array. For each i, j = (m + n + 1) // 2 - i. Check if nums1[i-1] ≤ nums2[j] and nums2[j-1] ≤ nums1[i]. If so, median is computed from the boundary 4 values. O(log(min(m, n))). Edge cases: i=0 (no left in nums1) or i=m; same for j.

B. Rain Water: two-pointer. Maintain left_max and right_max. At each step, the side with the smaller max determines how much water can sit at that index. Move that pointer inward. O(N) time, O(1) space. Alternative: precompute left_max and right_max arrays, O(N) time and space.

C. Merge K Lists: min-heap of (value, list_index, node). Pop the smallest, push its next. O(N log K) where N = total nodes. Alternative: divide-and-conquer pairwise merge, same complexity, no heap.

Common Failure Modes

  1. A: Submitted O(m+n) by merging. Works but fails the complexity requirement — interviewer marks as fail at FAANG bar.
  2. A: Off-by-one in the partition formula. Most common bug.
  3. A: Didn’t handle empty arrays. Crash on [], [1].
  4. B: Used DP with O(N) space when O(1) two-pointer works. Acceptable but downgrades the “Optimization” score.
  5. B: Forgot to handle bars that don’t trap any water (descending then ascending).
  6. C: Used O(N · K) approach — for each output element, scan all K heads. Too slow for K = 10^4.
  7. C: Forgot null check on lists[i] — common test failure on [[]].

Passing Bar

  • Total score: 45/70 (average 3.2)
  • Optimal complexity reached (or a serious attempt with clear awareness of the gap)
  • Correct on given examples + 2 boundary cases
  • Hint usage ≤ 1
  • Time ≤ 60 min
  • Articulated correctness argument (not just “trust me”)

Follow-up Questions

For A:

  • Generalize to k-th smallest in two sorted arrays. → Same binary search, partition at k-1 in total. O(log(min(m, n))).
  • Median of K sorted streams (K small). → Heap-based; not log-time anymore.
  • Median of unsorted data? → Quickselect or median-of-medians, O(N).
  • Memory-bound large-K case. → External merge sort; k-way merge with bounded heap.

For B:

  • 3D rain water (LC 407). → Heap of boundary cells, BFS inward. Much harder.
  • Approximate version with O(1) memory for a stream. → Doesn’t exist in general; needs two-pass for exact.
  • Trapping with non-zero ground (irregular shape). → Doesn’t fundamentally change.

For C:

  • Streaming K sorted streams, K huge (10^6+). → Tournament tree (O(log K) per element), or distributed merge.
  • Lists are not in memory (each is a file). → External k-way merge with bounded buffers.
  • K-way merge with timestamps + de-dup. → Same algorithm + dedup pass.
  • Latency-sensitive variant: emit elements as soon as possible. → Stream the heap output without buffering.

Required Tests

  • All given examples
  • Both arrays empty (A), all bars zero (B), all lists empty (C)
  • One huge + one tiny array (A) — stresses the binary search edges
  • Strictly increasing input (B), strictly decreasing input (B)
  • K = 1 (C: single list pass-through), K = 0 (C: empty)
  • One adversarial input you design

Required Complexity Explanation

  • Time complexity, with reasoning
  • Space complexity
  • Whether the bound is tight or merely upper
  • For A: explicitly justify why O(log) is achievable

Self-Evaluation Template

Mock 04 — Hard LC
Date: _______
Problem: _______
Time: ___ / 60 min
Hints used: ___

Scores (1–5):
___ Total /70

Time to reach optimal idea: _____ min
Time to first correct submission: _____ min
Number of bugs hit and fixed:

Was the correctness argument articulated? Y/N
Were 2+ follow-ups answered? Y/N

Strongest dimension:
Weakest dimension:
Action item for next session:

What to Do If You Fail

  • Score 38–44: Repeat with a different problem; you nearly passed.
  • Score <38: Step back to mediums; ensure 3+ consecutive passes of Mock 03 before retrying hard.
  • Couldn’t reach optimal complexity: Review Phase 2 (binary search), Phase 5 (DP), Phase 4 (graphs) — which patterns did you miss?
  • Bug-storm on implementation: Phase 10 Lab 04 (correctness proofs) and Lab 05 (stress testing).
  • Failed follow-ups: You knew the algorithm but didn’t know its variants; do 5 related problems before the next attempt.
  • Pass twice in a row before moving to Mock 05.