Design II — Streams & Time

Review boundary and corrected contracts

TimeMap searches timestamps only, using bisect_right(..., key=...) on Python 3.10+. The original tuple sentinel works for values restricted to lowercase ASCII letters and digits, but not for arbitrary Unicode strings: a value beginning with U+10FFFF and followed by another character sorts after the one-character sentinel. Timestamps increase per key; median queries require a nonempty stream. The numeric negation heap technique below works across these Python versions; Python 3.14 also provides public max-heap APIs.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Own the two-heap median structure, then apply binary search over timestamps and k-way merge to the other two members of the streaming-design family.

Series: LeetCode — From Basics to Production-Ready · Session 52 / 65 · Phase 3 · Advanced & specialised

Watch first

Watch these before opening the editor. For the median video specifically: stop it the moment the two-heap split is described and try to derive addNum yourself — the three-line unconditional version is much easier to re-derive than to memorise, and re-derivation is what survives to design review day.

Optional watch-first resources

• Find Median from Data Stream — NeetCode: pause at the invariant and derive addNum.
• Time Based Key-Value Store — NeetCode: recognise the predecessor query on increasing timestamps.
• Design Twitter — NeetCode: follow the heap merge and compare read-time versus write-time work.

Optional fourth, only if k-way merge feels shaky: Merge K Sorted Lists (LC 23) — NeetCode. Design Twitter's feed merge is this problem wearing a different hat, and if the heap-over-k-iterators idea is not automatic, fix that first.

Why this session exists

The two-heap median is a beautiful reusable idea and it deserves a session on its own merits. The problem — maintain the median of a stream where elements keep arriving — looks like it needs a sorted structure, and sorted insertion is O(n) per element. Two heaps get it to O(log n) with a construction that takes thirty seconds to explain once you see it.

The construction: split the data at the median into a lower half and an upper half. Keep the lower half in a max-heap so its largest element — the one nearest the median — is at the root. Keep the upper half in a min-heap so its smallest is at the root. The median is now always one or both of the two roots, available in O(1). Insertion is a push, a cross-push to maintain the split, and a rebalance if the sizes drift apart.

The idea reappears. Sliding window median is the same structure with lazy deletion bolted on. IPO and various scheduling problems use two heaps for the same reason: you want cheap access to the boundary between two groups that are each internally ordered.

The other two problems today are different lessons. Time Based Key-Value Store is about recognising that "the value as of time T" is a predecessor search on a sorted array, which is binary search — and that append-only writes with increasing timestamps keep the array sorted for free, so you never sort. Design Twitter is about resisting the urge to precompute: merging k sorted feeds on demand with a heap is simpler and usually better than maintaining a materialised timeline per user.

All three share a theme: data arrives over time, and the structure you choose is the one whose invariant survives that arrival cheaply.

Blank-file warm-up

Five minutes, empty file, no notes. Write the two-heap median structure:

1. Both heaps declared, with a comment on how the max-heap is faked using negation.
2. The addNum sequence: push, cross-push, rebalance.
3. findMedian for both odd and even total counts.

The negation is worth stating explicitly because this version uses the min-heap API for both halves: heappush(low, -x) makes -low[0] the largest original value. Python 3.14 adds heappush_max and heappop_max, but changing API requires removing the matching negations consistently. Mixing the two representations breaks the invariant.

Pattern anatomy

The shape that summons this pattern: elements arrive one at a time, and after each arrival you must answer a query about the whole collection so far. Sorting the collection per query is O(n log n) each time; the design question is what incremental structure keeps the answer cheap.

The invariant for the two-heap median is three clauses, and all three must hold after every operation:

1. Every element in low is less than or equal to every element in high.
2. len(low) equals len(high) or len(low) == len(high) + 1.
3. low is a max-heap and high is a min-heap.

Clause 1 is what makes the roots the median candidates. Clause 2 fixes which side holds the extra element when the count is odd, so findMedian needs no case analysis beyond parity.

import heapq
 
class MedianFinder:
    def __init__(self):
        self.low = []      # max-heap via negation: the smaller half
        self.high = []     # min-heap: the larger half
 
    def addNum(self, num: int) -> None:
        heapq.heappush(self.low, -num)                       # always land in low
        heapq.heappush(self.high, -heapq.heappop(self.low))  # cross-push the max
        if len(self.high) > len(self.low):                   # rebalance
            heapq.heappush(self.low, -heapq.heappop(self.high))
 
    def findMedian(self) -> float:
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2.0

The three-line addNum deserves attention because it looks like it does unnecessary work. Push unconditionally into low, then immediately move low's maximum into high. That guarantees clause 1 without any comparison: whatever ends up in high is at least as large as everything remaining in low, because it was the maximum of low after the insertion. Then one size check restores clause 2.

The alternative — compare the incoming number against the roots and decide which heap to push into — is also correct and is arguably more intuitive, but it needs two or three branches and each branch needs its own rebalance. The unconditional version is three lines with one branch. Write the three-line version.

Time Based KV is a different structure entirely:

import bisect
from collections import defaultdict
 
class TimeMap:
    def __init__(self):
        self.store = defaultdict(list)     # key -> list of (timestamp, value)
 
    def set(self, key: str, value: str, timestamp: int) -> None:
        self.store[key].append((timestamp, value))   # timestamps arrive increasing
 
    def get(self, key: str, timestamp: int) -> str:
        arr = self.store.get(key)
        if not arr:
            return ""
        # find the rightmost entry with timestamp <= the query
        i = bisect.bisect_right(arr, timestamp, key=lambda entry: entry[0])
        return arr[i - 1][1] if i else ""

The search key extracts only each entry’s timestamp; the query is already an integer and is not passed through the key function. Thus i is the first entry with timestamp greater than the query, and i - 1 is the predecessor. Searching tuples with (timestamp, chr(0x10FFFF)) works for values restricted to lowercase ASCII letters and digits, but is not a universal string upper bound: chr(0x10FFFF) + "x" compares greater than chr(0x10FFFF). Timestamp-only comparison removes that unnecessary value-domain dependency.

Design Twitter’s core decision is where to pay for the merge: materialise a timeline on writes, or merge the followed authors’ sorted feeds when reading. For this exercise, merge on read keeps posting independent of follower count. A hybrid is a possible production design, not a claim about every deployed service: precompute for some accounts and merge high-fan-out accounts at read time when the measured workload warrants it.

For a top-ten feed, seed one heap entry per nonempty followed feed including the reader’s own feed once. Pop the newest timestamp, append its tweet, then push that author’s next older tweet; stop after ten outputs or heap exhaustion. The heap always holds the newest unconsumed tweet of each feed, so its maximum is the next global answer. An author’s eleventh-newest tweet cannot enter the global top ten: ten newer tweets from that same author already dominate it. Keeping only ten per author is safe under this exercise’s no-deletion, no-filtering contract; deletions or per-tweet visibility would require rechecking that argument.

The cue

You are looking at a streaming-design problem when the statement contains these tells:

1. "Data stream", "as they arrive", "online" — elements come one at a time and you cannot see the future or re-read the past cheaply.
2. A query about a positional statistic — median, k-th largest, top-k. Positional statistics under insertion is the two-heap or single-heap signature.
3. A timestamp parameter on both the write and the read. That is versioned storage, and "the value at or before time T" is a predecessor query, which is binary search.
4. "Design" plus multiple entities with a many-to-many relation — users, follows, posts. Usually a merge or fan-out question.
5. Explicit per-operation complexity requirements like "get in O(1), add in O(log n)". The asymmetry tells you which operation to make cheap at the other's expense.

Tell 5 is worth internalising as a general design habit. When a spec makes one operation cheaper than another, it is telling you where to put the work. Cheap reads and expensive writes means precompute; the reverse means compute lazily.

Guided solve

Find Median from Data Stream — implement addNum(num) and findMedian(). Numbers arrive one at a time.

Start by rejecting the obvious approaches out loud, with reasons.

Keep an unsorted list, sort on each query. addNum is O(1) but findMedian is O(n log n). If queries are frequent this is hopeless.

Keep a sorted list, insert in position. findMedian is O(1) but insertion into an array is O(n) because of the shifting, even though finding the position is O(log n) by binary search. Note the subtlety here: bisect.insort is often mistaken for O(log n), but the search is logarithmic and the insertion is linear.

Use a balanced BST with subtree sizes. O(log n) for both, and genuinely correct — this is what a language with an order-statistic tree would do. Python has no such structure in the standard library, and writing one under a tight review is not a good use of time.

Now the two-heap insight. You do not need the collection sorted. You need one or two specific elements: the middle one, or the middle two. So maintain just enough order to know what those are.

Split the data at the median. Everything at or below it goes in low; everything above goes in high. If low is a max-heap, its root is the largest of the smaller half — a median candidate. If high is a min-heap, its root is the smallest of the larger half — the other candidate. When the total count is odd, put the extra element in low by convention, and the median is low's root. When it is even, the median is the average of the two roots.

That is the design. Now the operations.

Insertion. The new number belongs in low if it is at most low's root, and in high otherwise. The three-line trick sidesteps that comparison: push into low unconditionally, then pop low's maximum and push it into high. If the new number was large, it is the thing that just moved to high — correct. If it was small, something else moved instead and the new number stays in low — also correct. The invariant holds either way.

Rebalancing. After the cross-push, high may have one more element than low, violating the convention. Move high's minimum back to low. Sizes now differ by at most one with low never smaller.

Query. If the sizes differ, low has the extra element and its root is the median. If they are equal, average the two roots. Cast to float or use / 2.0, because integer division on an even count is a real and easy bug.

Trace: add 1. low = [-1], cross-push makes low = [], high = [1], rebalance moves it back so low = [-1], high = []. Median is 1. Add 2. Push gives low = [-2, -1], cross-push moves 2 to high, so low = [-1], high = [2]. Sizes equal, median is 1.5. Add 3. Push gives low = [-3, -1], cross-push moves 3, so low = [-1], high = [2, 3]; rebalance moves 2 back, giving low = [-2, -1], high = [3]. Median is 2. Correct throughout.

Solo timed

Fifteen minutes each, timer running, no editorial until it fires.

• Find Median from Data Stream — the full two-heap structure. Target six minutes; it is short once the invariant is clear.
• Time Based Key-Value Store — write the binary search by hand rather than using bisect on tuples. Decide before you code whether you want the rightmost entry with timestamp at most the query, and which of lo or hi holds it when the loop ends.
• Design Twitter — merge on read with a heap. Cap each user's stored posts at ten if you like; think about whether that cap is safe.

Common failure modes

Sign errors in the negated max-heap. Push -num, read -low[0], and when moving between heaps negate exactly once. A single missed negation gives a structure that maintains the wrong halves and produces medians that look almost right.

Rebalancing in only one direction. With the unconditional-push formulation only high can become oversized, so one check suffices. If you write the comparison-based insertion instead, both directions can drift and you need two checks. Match your rebalance to your insertion.

Integer division on the even case. (a + b) // 2 on the roots gives 1 instead of 1.5. Use / 2.0, or make one operand a float.

Sorting the timestamp list in TimeMap. If timestamps are guaranteed strictly increasing across calls — and the problem states this — appends keep the list sorted for free. Sorting on every set turns O(1) writes into O(n log n) and is pure waste.

Binary search returning the wrong side in TimeMap. You want the rightmost entry with timestamp at most the query. Off by one gives the next entry, which is a value from the future. Test with an exact timestamp match and with a query before every stored timestamp.

Choosing fan-out without a workload. A materialised timeline costs O(followers) work per post; a read-time merge scans followed feeds. Merge-on-read is a simple solution here, not a universally better production architecture. Compare posting, reading and follow-change rates before choosing.

Myth: To maintain a running median you must keep the data sorted, so insertion is inherently O(n) or you need a balanced BST.

Why: You do not need the data sorted; you need one or two specific elements. That distinction is the whole idea. Two heaps maintain exactly enough order to identify the middle elements and no more — within each half the ordering is only partial, which is precisely why a heap can insert in O(log n) while a sorted array cannot. The general lesson is worth carrying: ask what the query actually needs, not what would be convenient to have. Full sortedness is almost always more information than a positional query requires, and maintaining information you do not need is where the cost comes from.

Steps 1: Because the median is defined by position rather than by value, answering it requires knowing only the element or elements at the middle index.

Steps 2: Because a heap gives O(1) access to its extremum while only partially ordering everything else, it maintains a boundary element far more cheaply than a sorted structure maintains a full order.

Steps 3: Because splitting the data into a lower half and an upper half places the median at the boundary between them, the two extrema facing that boundary are exactly the median candidates.

Steps 4: Because a max-heap on the lower half and a min-heap on the upper half put those two candidates at the respective roots, the query becomes O(1).

Steps 5: Because insertion is a bounded number of heap pushes and pops, each O(log n), and the size invariant needs only one comparison, insertion is O(log n).

Steps 6: The proof bounds heap work by O(log n) per insertion, versus O(n) shifted references for sorted-array insertion. It does not predict a wall-clock ratio: Python implementation costs, input order, allocation and cache behaviour still matter.

Picture: Two buckets of water joined at a shared rim, one holding the small numbers and one the large. You always pour into the small bucket, then tip the top of it over the rim into the large one, then level the buckets so they hold within one unit of each other. The waterline at the shared rim is the median, and you can read it without looking inside either bucket.

Trigger: Fires when a stream requires a positional statistic — median, k-th largest, or the boundary between two ordered groups.

Name: Two heaps

Gain: O(log n) insert and O(1) query with a small constant; entirely standard-library; the invariant is three clauses you can state and check

Cost: Deleting an arbitrary element is not supported, so a sliding-window variant needs lazy deletion with a tombstone map, which needs tombstones, root pruning and live-size bookkeeping

Name: Sorted list with bisect.insort

Gain: Trivially short — one line to insert, one to read the middle; supports arbitrary deletion directly; easy to inspect while debugging

Cost: Insertion and arbitrary deletion shift O(n) array entries; logarithmic search does not remove that movement. There is no fixed thousand-fold runtime ratio to heaps.

Pick: Use two heaps for a growing stream with frequent median queries when logarithmic insertion matters. Use a sorted list for a small collection or a simple prototype, and measure rather than assuming a universal size threshold. Arbitrary deletion is easy to express on a list but still linear.

Complexity

MedianFinder.addNum: O(log n). One push, one pop, one push, and at most one more pop-push pair for the rebalance — a bounded number of heap operations, each logarithmic in the current size.

MedianFinder.findMedian: O(1). Reading one or two heap roots and doing arithmetic. No traversal.

Space: O(n) — every element is stored exactly once across the two heaps.

TimeMap.set: O(1) amortised — a single list append, valid because timestamps arrive in increasing order and the list therefore stays sorted with no work. TimeMap.get: O(log n) in the number of entries for that key, by binary search. Space O(total writes), since nothing is ever overwritten — this is versioned, append-only storage.

Design Twitter with merge-on-read: list append is amortised O(1); set follow/unfollow is expected O(1). Let k include the reader and followed authors. Collecting one head from each feed and calling heapify costs O(k); extracting at most ten tweets and replacing their feed heads costs O(10 log(k + 1)). Repeated heappush seeding instead costs O(k log(k + 1)). Feed reads use O(k) heap space, independent of total historical tweets. A materialised top-ten timeline moves work to posts and follow changes; it is not free O(1) maintenance.

Self-check (answer follows each question).

Q: State the three invariants the two-heap median structure maintains.

A: Every element in low is at most every element in high; the sizes are equal or low has exactly one more; low is a max-heap and high is a min-heap.

Q: Why does addNum push into low unconditionally and then cross-push to high?

A: Popping low's maximum after the insertion guarantees that whatever moves to high is at least as large as everything left in low, so the ordering invariant holds with no comparison and no branching. One size check then restores the balance invariant.

Q: How do you build a max-heap in Python, and where do the sign errors appear?

A: Negate on push and negate again on read: heappush(low, -x) and read -low[0]. Errors appear when moving elements between heaps, where you must negate exactly once — a missed or doubled negation silently maintains the wrong halves.

Q: Why does TimeMap need no sorting despite supporting timestamp predecessor queries?

A: The problem guarantees timestamps arrive strictly increasing, so appending to a per-key list keeps it sorted for free. Binary search then answers the predecessor query directly.

Q: For Design Twitter, why is merge-on-read preferable to fan-out-on-write here?

A: Posting is amortised O(1) regardless of follower count. A read scans the followed authors and merges their feed heads, so it costs O(k + 10 log(k + 1)) with heapify, not work proportional to all historical tweets. Whether that trade is preferable depends on the operation mix; followee count need not be small.

Q: Sliding Window Median needs the same two-heap structure plus deletion, which heaps do not support. How do you handle it?

A: Lazy deletion: keep counts of values scheduled for removal and prune any marked root before reading or transferring it. Track live sizes separately from physical lengths: expiring a buried value changes its heap’s live size immediately, but leaves its physical entry until it reaches the root. Rebalance by live sizes and prune newly exposed roots. For example, expiring 1 from a lower half containing 1 and 2 can leave 1 buried under root 2; using physical length would count that expired entry as live. Duplicates need deletion counts, not a set. This is an extension design, not a complete sliding-window implementation; stale buried entries may require periodic rebuilding if memory must remain O(window size).

Stretch: true

Timing rubric

75 minutes. Design problems overrun because the class scaffolding feels like progress while the actual invariant is still undecided. Budget against that.

• 0–5 min · Blank-file warm-up. Two heaps, addNum, findMedian. No notes.
• 5–20 min · MedianFinder guided. Spend the first 4 minutes on the three invariants in words before any code. If you cannot state clause 1, do not type.
• 20–35 min · TimeMap solo, timed. Hand-rolled binary search on timestamps only — not bisect on tuples. A tuple sentinel is safe only with a stated value alphabet; timestamp-only comparison makes that dependency unnecessary.
• 35–55 min · Design Twitter solo, timed. Hard rule: state the fan-out decision out loud in the first 3 minutes, then commit. Waffling between the two designs is the main way this problem eats twenty minutes.
• 55–70 min · Sliding Window Median stretch. Lazy deletion on top of the two-heap structure. If time is short, write only the deletion bookkeeping and skip the driver loop.
• 70–75 min · Invariant recital. For each structure, say the invariants aloud and name which line restores each one.

Per-operation budget for the design review itself: you should be able to write MedianFinder end to end in under 6 minutes and TimeMap in under 8. If either is over 10, the gap is the API, not the algorithm — drill the skeleton, not the idea.

Self-scoring checklist

Two points each, per problem.

1. Invariants stated before code? (2 = written out; 1 = verbal; 0 = discovered while debugging.)
2. Every mutating method mapped to the invariant it restores? (2 = all; 1 = some; 0 = none.)
3. Negation handled correctly on first write? (2 = clean; 1 = one sign bug; 0 = more. Sign bugs are the #1 defect here.)
4. Complexity given per operation, not per class? (2 = each method separately; 0 = one blanket answer.)
5. Design tradeoff articulated unprompted? (2 = you named fan-out on read vs. write and why; 0 = you just coded one.)

8–10 → cold, 60 days. 5–7 → warm, 21 days. 3–4 → hint, 7 days. 0–2 → failed, 2 then 7.

Design problems get a stricter interval than the standard ladder, because the API surface decays faster than the idea does. You will remember "two heaps" for a year and forget the cross-push order in three weeks.

Problem set with company attribution

These are practice selections by mechanism, not verified current company-frequency claims. The links identify the problems; they do not establish hiring predictions.

• Find Median from Data Stream (295) — Hard · the anchor structure.
• Time Based Key-Value Store (981) — Medium · predecessor search on append-only data.
• Design Twitter (355) — Medium · fan-out decision.
• Sliding Window Median (480) — Hard · two heaps plus lazy deletion.
• Merge k Sorted Lists (23) — Hard · the merge primitive behind the feed.
• Kth Largest Element in a Stream (703) — Easy · the single-heap warm-up; do this first if heaps feel cold.
• IPO (502) — Hard · two heaps for a different reason: cheap access to a moving boundary.
• Design Hit Counter (362) — Medium · time-bucketed streaming counts; the natural follow-up to TimeMap.

Recovery scripts

Design blanks feel different from algorithm blanks. You usually know roughly what structure you want and cannot recall the mechanics. That is recoverable out loud.

If you cannot remember the cross-push order:

"Let me re-derive rather than recall. I need every element in low to be at most every element in high. The cheapest way to guarantee that unconditionally is: push into low, then move low's current maximum into high — that element is by construction at least everything left in low. Then one size check."

This is better than remembering it, because it is checkable in real time.

If you blank on the whole structure:

"Naively I'd keep a sorted list — that's O(n) insertion, correct but too slow. What I actually need isn't the sorted order, it's the element at the middle position. Let me see if I can maintain just the boundary rather than the whole ordering."

Stating what you do not need is often what unlocks the structure. Say it.

If you get a sign error and the tests fail:

"That's a negation bug — this implementation represents the max-heap by negation, and the risk is negating zero times or twice when moving between heaps. Let me trace three insertions by hand."

Naming the class of bug before hunting it shows you understand your own code. Trace by hand; do not shotgun sign flips.

If a reviewer pushes on scale:

"For this exercise I would merge on read. At service scale I would measure read rate, posting rate and follow-degree distribution before considering a hybrid: precomputed timelines for some authors and read-time merging for high-fan-out authors."

If you are 10 minutes in with no working method:

Ship the O(n) sorted-list version and say so: "I'll get a correct baseline in with sorted insertion, then replace it with the two-heap version." A correct slow class beats a broken fast one, and the migration path is a good conversation.

Common failure modes in the room

Beyond the algorithmic ones above — these cost points with correct code.

Building the class shell first. Writing __init__, method stubs, and docstrings before deciding the invariant. It looks productive and is not. Decide the invariant, then the shell falls out in thirty seconds.

One blanket complexity answer. Design problems have per-operation complexity. "O(log n)" is not an answer; "addNum is O(log n), findMedian is O(1)" is.

Silently choosing the fan-out design. The choice is the question. Announce it and justify it, or you have answered a coding problem instead of a design one.

Ignoring the degenerate cases. Empty structure, single element, all-equal elements, and — for TimeMap — a query timestamp before every write. Name them before a reviewer does.

You can now…

• State the three two-heap invariants and name the line that restores each.

• Write MedianFinder from scratch in under six minutes with correct negation.

• Explain why the unconditional push-then-cross-push needs no comparison.

• Recognise 'value as of time T' as a predecessor binary search.

• Explain why append-only increasing timestamps mean you never sort.

• Choose and justify fan-out on read vs. on write, and name the real-world hybrid.

• Give per-operation complexity for every method, unprompted.

• Extend the two-heap structure with lazy deletion for a sliding window.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

The two-heap structure is worth a shorter interval than the ladder suggests, because the negation details decay quickly even when the idea does not. Re-derive the invariants each time rather than recalling the code.

• You rarely need the data sorted — you need specific elements. Two heaps maintain exactly enough order for the median and no more.

• Max-heap on the lower half, min-heap on the upper half, sizes within one. The median is one or both roots, in O(1).

• Push into low unconditionally, cross-push low's max into high, then rebalance. Three lines, one branch, invariant preserved.

• This implementation uses negation for the lower max-heap; negate on push/read and exactly once on cross-heap moves. Python 3.14 also has public max-heap operations, which use a different representation.

• Versioned storage with increasing timestamps stays sorted for free — never sort, just binary search for the predecessor.

• When a spec makes one operation cheaper than another, that asymmetry is telling you whether to precompute or compute lazily.

Corrective source notes

• bisect — Array bisection algorithm — Python 3.14 documentation — bisect supports an element-key function; the search value is not transformed by it. Checked 2026-10-09.

• heapq — Python 3.14 documentation — public max-heap functions were added in 3.14; negation remains valid for numeric data. Checked 2026-10-09.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.