Meta·Software Engineer·Onsite - System Design / Architecture·Senior

SeniorPrefer not to say

May 2026

Summary

Meta system design round, one big question that took the whole session. The problem was meaty enough that I kept second-guessing my own design halfway through explaining it.

Questions Asked (1)

Design and implement a thread-safe job scheduler where jobs have expiry timestamps. The system needs to handle concurrent job submissions from multiple producer threads, a background cleanup thread that removes expired jobs, and worker threads that pull valid jobs in order. Walk through your data structure choices, locking strategy, and how you prevent races between the cleanup thread and the workers.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

I jumped straight to a priority queue and then realized mid-sentence I hadn't thought about what happens when the reaper pulls an expired job at the same moment a worker is trying to dequeue it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a priority queue (min-heap) ordered by expiry timestamp, protected by a mutex or lock-free structure. Explain how producers, workers, and the cleanup thread interact, and detail race prevention using condition variables and atomic operations.

Pro tip: Mention that you would use a min-heap with lazy deletion or a timing wheel for efficiency, and that you would benchmark under high contention to choose between coarse-grained and fine-grained locking.

1. Clarify Requirements and Constraints

Ask about expected throughput, latency, job ordering guarantees, and whether jobs can be cancelled or rescheduled. Confirm if the scheduler is in-memory or persistent.

2. Choose Data Structures

Propose a min-heap keyed by expiry timestamp for O(log n) insertion and extraction. Consider a timing wheel for high-throughput scenarios with many timers.

3. Design Concurrency Control

Use a mutex to protect the heap and condition variables to signal workers when jobs are available. For the cleanup thread, either integrate it with workers or use a separate lock with careful ordering to avoid deadlocks.

4. Prevent Races Between Cleanup and Workers

Ensure atomic operations when checking and removing expired jobs. Use a single lock for both cleanup and worker extraction, or employ a lock-free queue with atomic compare-and-swap. Consider marking jobs as expired and letting workers skip them.

5. Discuss Trade-offs and Optimizations

Compare coarse-grained locking (simple but contended) vs. fine-grained (complex but scalable). Mention lazy deletion, batching, and backpressure. Address fairness and starvation.

Key Points to Mention

Min-heap (priority queue) ordered by expiry timestamp for efficient retrieval of the earliest job.
Mutex and condition variables for synchronization; avoid busy-waiting.
Race prevention: atomic check-and-remove, or single lock for both cleanup and workers.
Lazy deletion: mark expired jobs and let workers skip them to reduce contention.
Trade-offs: coarse vs. fine-grained locking, lock-free structures, and timing wheels.
Handling edge cases: empty queue, all jobs expired, and high contention.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.