patternDSA/Multi-threaded

Core Pattern → Pattern 31 · Final Pattern

Multi-threaded

Left and right subtrees are completely independent — spawn a thread per subtree, run in parallel, join before combining. The producer-consumer pattern handles lazy iteration with bounded memory.

Frequency:★★☆☆☆

·~25 min·Intermediate·3 problems

PrevFinal

The Core Shock

Sequential DFS visits left then right — but they share zero data. Run them on separate threads: same O(n) work, half the wall-clock time.

Sequential DFS

T seconds

Left then right — right waits for left to finish despite being completely independent.

Parallel DFS

~T/2 seconds

Thread-L and Thread-R run simultaneously. Join before combining results. Same work, half latency.

Rule: if two subtasks share no data → run on separate threads
Submit ALL futures first, then collect results — never call .result() before submitting the next task
Shared flag: use mismatch=[False] list wrapper — mutable in nested scope

Python Threading Primitives

Four primitives cover 95% of multi-threaded interview problems.

Lock

lock = threading.Lock()
with lock:
    shared_state = True

Shared mutable state — any variable multiple threads write to.

Semaphore

sem = threading.Semaphore(n)
with sem:
    pass  # ≤ n threads here

Rate-limiting — bounded buffer, max concurrent workers.

Event

e = threading.Event()
e.set()    # signal on
e.wait()   # block until set

Thread A waits for Thread B's signal. Producer notifies consumer.

Barrier

b = threading.Barrier(2)
b.wait()  # blocks until
          # 2 threads arrive

Rendezvous — both threads complete Phase 1 before Phase 2 starts.

The 3-Step Framework

Identify independence → submit all → collect results → protect shared writes.

Identify the independent subproblems

Left and right subtrees share no nodes — always independent. Same Tree: left check AND right check. Invert Tree: invert left AND invert right. Any divide-and-conquer with independent halves is a candidate.

# Ask: does left need any result from right (or vice versa)?
# Binary tree left/right: always NO
# → spawn Thread-L and Thread-R

For linked lists, access is sequential — harder to parallelise. For trees, the structure guarantees independence.

Submit ALL tasks before calling .result() on any

Future.result() blocks. If you call it before submitting the second task, the second task doesn't start until the first finishes — you've serialised. Always submit all, then collect all.

# CORRECT — both submitted before either blocks
f1 = ex.submit(fn, left)
f2 = ex.submit(fn, right)
r1 = f1.result()  # both already running
r2 = f2.result()

This is the #1 parallelism bug in interviews. Silent — no error, just sequential speed.

Protect shared state — list wrapper or Lock

Writing to a plain variable in a nested function creates a local. Use a list wrapper [False] — mutating an existing object works across nested scopes. For counters or complex state, use a Lock explicitly.

mismatch = [False]   # list wrapper
def check(a, b):
    mismatch[0] = True  # mutates list — outer sees it
    # NOT: mismatch = True  (creates new local!)

Python 3 alternative: nonlocal mismatch. But list wrapper is more common in interviews — works without nonlocal keyword.

Pattern Recognition

'parallel subtrees', 'concurrent traversal', 'BST iterator' → multi-threaded.

Use When

Same Tree: parallel left/right subtree check

Invert Binary Tree: parallel subtree inversion

BST Iterator: producer thread + bounded Queue

Any binary tree problem with independent subtrees

Parallel merge sort (independent halves)

Producer-consumer with bounded buffer / backpressure

I/O-bound tasks: web requests, file reads in parallel

LeetCode problems tagged 'multi-threaded'

Pitfalls

Calling f1.result() before submitting f2 — silent serialisation

Writing to plain var in nested fn — creates local, not shared

Python GIL: threads don't speed up CPU-bound work

Not joining threads — main exits, work lost mid-traversal

Forgetting Lock on shared counter — race condition

Non-daemon producer — program hangs after main exits

BST Iterator: has_next() must check both queue AND thread alive

Using mutable default args as shared state — bug per call

On this page