# Java LLD: Cracking the Priority Queue for FAANG You've probably seen it on a whiteboard: "Design a system that processes tasks with varying priorities." Or, "Implement a custom task scheduler." Immediately, your brain should scream *priority queue*. It's a foundational data structure, yes, but in Java LLD (Low-Level Design) interviews, they don't just want you to regurgitate `java.util.PriorityQueue`. They want to see how you *think* about its implications, its underlying heap, and how you'd bend it to a business need. This isn't about memorizing API calls; it's about understanding the "why" and "how" behind the "what." ### The `PriorityQueue` Isn't Magic: It's a Heap Let's get this straight: `PriorityQueue` in Java isn't some mystical, self-organizing entity. It's an array-based binary heap. Specifically, a min-heap by default. What does that mean for your LLD? It means the element with the *lowest* value (as determined by natural ordering or a `Comparator`) is always at the root. When you `poll()`, you get that root, and the heap re-organizes in *O(log N)* time. When you `offer()`, it adds the element and percolates it up, also *O(log N)*. This matters. A lot. You need to be able to sketch out a basic heap structure—even just conceptually—when discussing operations. Don't just say "it's fast"; explain *why* it's fast. Think about a system where you need to retrieve the *highest* priority item. The default `PriorityQueue` gives you the lowest. This is your first design decision: do you wrap your items in a custom object that inverts the priority for comparison, or do you pass a `Comparator` that sorts in reverse? The latter is cleaner and more idiomatic. For instance, `new PriorityQueue<>(Collections.reverseOrder())` gives you a max-heap instantly for `Comparable` objects. Or, `new PriorityQueue<>((a, b) -> b.getPriority() - a.getPriority())` for custom `Task` objects. Always consider both options and pick the one that makes your code more readable and maintainable. ### When a Simple `PriorityQueue` Falls Short: Custom Elements & State Most LLD problems involving a priority queue won't be as simple as "store integers and poll the smallest." You'll usually deal with custom objects: `Task`, `Order`, `Request`, etc. These objects will have multiple attributes, and priority might be a composite of several of them. Consider a `Task` object with `id`, `priorityLevel` (an enum like `HIGH`, `MEDIUM`, `LOW`), `creationTime`, and `deadline`. How do you define "priority" for such an object? This is where your `Comparator` becomes crucial. Your `Comparator` might look like this: ```java class Task { String id; PriorityLevel priorityLevel; // Enum: HIGH, MEDIUM, LOW long creationTimeMillis; long deadlineMillis; // Constructor, getters... enum PriorityLevel { HIGH(3), MEDIUM(2), LOW(1); final int level; PriorityLevel(int level) { this.level = level; } } } class TaskComparator implements Comparator { @Override public int compare(Task t1, Task t2) { // Higher priorityLevel comes first int levelComparison = Integer.compare(t2.priorityLevel.level, t1.priorityLevel.level); if (levelComparison != 0) { return levelComparison; } // For same priorityLevel, earlier deadline comes first int deadlineComparison = Long.compare(t1.deadlineMillis, t2.deadlineMillis); if (deadlineComparison != 0) { return deadlineComparison; } // For same priorityLevel and deadline, older tasks come first (FIFO for ties) return Long.compare(t1.creationTimeMillis, t2.creationTimeMillis); } } ``` This `TaskComparator` demonstrates a multi-level prioritization strategy: 1. **Primary:** Higher `priorityLevel` wins. 2. **Secondary:** If `priorityLevel` is the same, an earlier `deadline` wins. 3. **Tertiary:** If both `priorityLevel` and `deadline` are the same, the older task (smaller `creationTime`) wins, ensuring fairness. This level of detail shows you understand how real-world prioritization works. Don't just say "I'll use a `Comparator`"; actually sketch out the logic for a complex scenario. This is what distinguishes an average candidate from a top-tier one. What if a task's priority *changes* while it's already in the queue? This is a common curveball. A standard `PriorityQueue` doesn't directly support `update(element, newPriority)`. You can't just modify an element and expect the heap to magically re-organize. Its position is determined by its *initial* priority when `offer()`ed. Your options for handling updates: 1. **Remove and Re-add:** This is the simplest approach. `queue.remove(task); task.setPriority(newPriority); queue.offer(task);` This can be *O(N)* for the `remove` operation, as `remove` might have to scan the entire underlying array to find the element. If updates are rare, this is fine. If updates are frequent, this becomes a bottleneck. 2. **Lazy Deletion:** When a task's priority changes, mark the old entry as "invalid" or "stale" in some way (e.g., set a boolean flag on the `Task` object). Add the new, updated `Task` object to the queue. When you `poll()`, if the retrieved task is invalid, just discard it and `poll()` again. This avoids the *O(N)* `remove` but adds `O(log N)` for each update and potentially more `poll()` calls. You'll also need a strategy to clean up the invalid entries periodically to prevent memory leaks if they accumulate. 3. **Indexed Priority Queue (Custom Implementation):** For highly performant scenarios where updates are frequent, you might need a custom priority queue that maintains a mapping from element ID to its index in the heap. This allows you to quickly locate an element, update its priority, and then "heapify up" or "heapify down" from that specific index in *O(log N)* time. This is a much more complex implementation and you'd only attempt it if explicitly asked or if the performance requirements are extremely stringent. You'd likely need a `Map elementIdToIndex` alongside your heap array. This is usually beyond the scope of a typical LLD interview unless they are specifically testing your data structure implementation skills. For most cases, option 1 or 2 is what they're looking for you to discuss. This thought process—identifying the limitations of the standard library and proposing solutions with their trade-offs—is what interviewers want to see. ### Thread Safety: The Elephant in the Room `java.util.PriorityQueue` is *not* thread-safe. Period. If your LLD involves multiple threads interacting with the queue (e.g., multiple workers polling tasks, multiple producers adding tasks), you absolutely *must* address concurrency. How do you make it thread-safe? 1. **External Synchronization:** Wrap every access to the `PriorityQueue` in `synchronized` blocks or use `ReentrantLock`. This is the simplest approach. ```java class ConcurrentTaskScheduler { private final PriorityQueue taskQueue; private final Object lock = new Object(); // Or ReentrantLock public ConcurrentTaskScheduler(Comparator comparator) { this.taskQueue = new PriorityQueue<>(comparator); } public void addTask(Task task) { synchronized (lock) { taskQueue.offer(task); // Potentially notify waiting threads } } public Task getNextTask() throws InterruptedException { synchronized (lock) { while (taskQueue.isEmpty()) { // Wait if no tasks lock.wait(); } return taskQueue.poll(); } } } ``` This approach is simple but can lead to contention if there are many producers and consumers. 2. **`PriorityBlockingQueue`:** This is the preferred, off-the-shelf solution from `java.util.concurrent`. It's a concurrent, unbounded blocking queue that uses the same heap-based priority ordering. It handles all the synchronization internally using a `ReentrantLock` and condition variables, so you don't have to. It's generally more efficient than external synchronization for common concurrent patterns. ```java class ConcurrentTaskScheduler { private final PriorityBlockingQueue taskQueue; public ConcurrentTaskScheduler(Comparator comparator) { this.taskQueue = new PriorityBlockingQueue<>(10, comparator); // Initial capacity, comparator } public void addTask(Task task) { taskQueue.offer(task); // This is thread-safe } public Task getNextTask() throws InterruptedException { return taskQueue.take(); // Blocks until an element is available } } ``` When discussing concurrency, state your choice clearly and explain *why* you chose it. "I'd use `PriorityBlockingQueue` because it's designed for concurrent scenarios, provides blocking operations, and handles synchronization efficiently, saving me from writing error-prone manual locks." That's a strong answer. ### Common LLD Scenarios & How Priority Queues Fit In You'll see priority queues pop up in various LLD problems. Here are a few common patterns and how to approach them: 1. **Task Schedulers:** This is the most direct application. Tasks have priorities and/or due times. A `PriorityQueue` where `ScheduledTask` compares based on its `nextExecutionTime` or `priorityLevel` is the core. You'll often combine this with a `ThreadPoolExecutor` to actually run the tasks, and perhaps a `Timer` or `ScheduledExecutorService` to periodically poll the `PriorityQueue` and submit ready tasks. 2. **Event Processors / Simulators:** Systems that need to process events in chronological order, or simulate a sequence of events. Each event gets an `eventTime` and might have a `priority`. The `PriorityQueue` stores `Event` objects, ordered by `eventTime`. When `poll()`ed, the system processes the earliest event. 3. **Log Aggregators / Metrics Systems (Top K):** Imagine you have millions of logs, and you want to find the top 10 most frequent errors in real-time. Or, the top 5 slowest API calls. A min-heap of size K can maintain the top K elements. You iterate through all incoming elements. If the heap size is less than K, add the element. If it's already K, compare the incoming element with the `peek()` (smallest element). If the incoming element is "more important" than `peek()`, `poll()` the smallest and `offer()` the new one. This keeps the heap always containing the K largest (most frequent, slowest, etc.) elements. This is a classic "Top K" problem. 4. **Load Balancers (Least Connections / Least Latency):** This is a bit more nuanced. While a simple `PriorityQueue` won't directly implement a full load balancer, you could use its *concept* for server selection. For example, a `PriorityQueue` where `Server` objects are ordered by their current load (e.g., number of active connections). The load balancer `poll()`s the least loaded server, assigns a request, and then updates that server's load (which means `remove` and `offer` if using `PriorityQueue`, or a custom Indexed Priority Queue if performance is critical). 5. **Caching with Expiry/Eviction (LRU/LFU variants):** While `LinkedHashMap` handles LRU well, variations like LFU (Least Frequently Used) or custom expiration policies could involve a priority queue. For LFU, you'd store `CacheEntry` objects ordered by their `accessCount`. For expiry, `CacheEntry` objects ordered by `expiryTime`. When the cache is full, you `poll()` the least "valuable" item to evict. When you get an LLD prompt, mentally run through these common patterns. Does the problem require ordering? Does it involve finding the "best" or "worst" item repeatedly? Does it need to handle dynamic changes in order? Does it have concurrency needs? Your answer for the priority queue will flow from these questions. ### Scaling Beyond a Single JVM: Distributed Priority Queues Here's an honest caveat: a `java.util.PriorityQueue` lives in a single JVM's memory. For many LLD problems, especially at FAANG scale, they're looking for solutions that can handle *distributed* systems. If your queue needs to span multiple machines, process millions of items, or be highly available, a simple `PriorityQueue` won't cut it. You'd be looking at solutions like: * **Kafka/RabbitMQ with Priority Queues:** Message brokers often support priorities. For Kafka, you'd typically use separate topics or partitions for different priority levels, or process messages in batches and sort them. RabbitMQ has native priority queue features, but they come with performance overhead. * **Database-backed queues:** Use a relational database table with an `order_by` clause on a `priority` column. Polling involves `SELECT ... ORDER BY priority ASC LIMIT 1 FOR UPDATE`. This provides durability and distributed access but is much slower than in-memory. You'd need careful indexing and transaction management. * **Distributed Caches (Redis Sorted Sets):** Redis's `ZADD` and `ZRANGE` commands can implement a highly performant distributed priority queue. Elements are members, and their score acts as the priority. `ZRANGE 0 0` gets the top priority item. This is often an excellent choice for distributed, high-throughput scenarios where you need fast access to the highest priority items. When discussing distributed solutions, acknowledge the limitations of `java.util.PriorityQueue` and then pivot to how you'd achieve similar functionality in a distributed environment. "While an in-memory `PriorityQueue` works for a single node, for a distributed system, I'd consider using Redis Sorted Sets. Each task would be a member, its score being its priority. This gives us O(log N) operations for adding and removing, and O(1) for peeking at the highest priority item, all while being durable and horizontally scalable." This shows a broader understanding of [system design](/en/interview-prep). ### Practice Tips: Sketch, Discuss, Justify Don't just code. Interviewers want to see your design process. 1. **Understand the Requirements:** What are the entities? What defines their priority? What operations are needed? (add, remove, peek, update, poll, size) What are the scale requirements (N, QPS, latency)? 2. **Start Simple:** Begin with the basic `java.util.PriorityQueue`. Explain its default behavior (min-heap), its underlying data structure (array-based binary heap), and its time complexities (O(log N) for offer/poll, O(N) for remove). 3. **Identify Gaps:** * **Max-heap vs. Min-heap:** How will you handle "highest priority" when the default is "lowest value"? (Comparator or `Collections.reverseOrder()`) * **Custom Objects:** How will you compare your custom objects? (Custom `Comparator`) * **Concurrency:** Is it single-threaded or multi-threaded? (External sync vs. `PriorityBlockingQueue`) * **Updates:** What happens if an element's priority changes? (Remove/re-add, lazy deletion, custom indexed PQ) * **Persistence/Distribution:** Does it need to survive restarts or span multiple machines? (Database, Redis Sorted Set, Message Queue) 4. **Propose Solutions and Trade-offs:** For each gap, offer 2-3 solutions and discuss their pros and cons (performance, complexity, memory, consistency, availability). *This is where you shine.* Don't just say "I'd use `PriorityBlockingQueue`." Explain *why* it's better than manual synchronization for *this specific scenario*. 5. **Sketch it Out:** Draw class diagrams (UML or simplified boxes/arrows). Show the key classes (`Task`, `TaskScheduler`, `TaskComparator`), their relationships, and the core methods. Illustrate data flow. If discussing updates, draw how the heap would change. 6. **Justify Your Choices:** Be ready to defend why you picked a `PriorityBlockingQueue` over a manual `synchronized` block, or why you opted for remove/re-add instead of a custom indexed priority queue. Your justification should tie back to the problem's requirements and constraints. If the interviewer pushes back, engage in a constructive discussion about alternatives. Remember, they're not looking for a perfect solution on the first try. They're looking for your thought process, your ability to identify problems, propose solutions, and understand the implications of those choices. The `PriorityQueue` is a fantastic lens through which to evaluate these crucial LLD skills. ## Ready to Ace Your Next Interview? Practice with AI-powered [mock interview](/en/interview-prep)s tailored to your target role and company. [Start Practicing for Free](/sign-up) | [Explore Interview Prep](/en/interview-prep)