Concurrency, Scheduling, and State Machines

What's being tested

These problems test building and reasoning about an async primitive (like CompletableFuture) and scheduling: safe callback registration, correct completion state machine, and efficient timer/task multiplexing onto a thread-pool. Interviewers probe race-free state transitions, cancellation, ordering guarantees, and scalable timer/scheduler data structures.

Patterns & templates

• State machine with explicit states (e.g., PENDING → COMPLETING → COMPLETED/FAILED/CANCELLED) and a single CAS transition per completion to avoid races.

• Callback list appended atomically with compareAndSet and drained by the thread that wins completion, avoiding locking on hot path.

• Use volatile for result/state visibility and minimal locking; prefer lock-free for low-latency futures, fallback to short critical sections when necessary.

• Implement timers with a min-heap priority queue for correctness, or a timer wheel for large-scale (~10^6 timers) amortized O(1) ticks.

• Use ForkJoinPool / work-stealing for parallel array processing; prefer divide-and-conquer recursively to maximize locality and CPU utilization.

• Cancellation: mark state then attempt to remove scheduled tasks; for heap-based timers, use lazy deletion flags to avoid O(n) removals.

• Batch wakeups: coalesce scheduled callbacks and run them on a worker thread (execute()), avoid running user callbacks under internal locks to prevent deadlocks.

Common pitfalls

Pitfall: Failing to make state transitions atomic leads to double-completion or lost callbacks when two threads try to complete concurrently.

Pitfall: Running user callbacks while holding internal locks causes deadlocks or long GC pauses; always invoke callbacks outside locks.

Pitfall: Assuming notify() without rechecking condition — handle spurious wakeups and always loop on the predicate when using wait()/notify().