Java Interview Question - Merging Two Priority Queues
Priority queue, concept, code, examples and explanation.
Scenario
You are building a Spring Boot service that schedules background jobs.
Jobs come from two sources:
• User-triggered jobs (higher urgency)
• System maintenance jobs (lower urgency)
Each source currently maintains its own PriorityQueue<Job> ordered by execution time.
Now the scheduler must always execute the earliest job across both queues.
Here’s an example of how these queues might look:
How would you merge these queues so the scheduler always picks the next job efficiently?
Assume:
• Each queue can contain millions of jobs
• New jobs arrive continuously
• The scheduler runs concurrently
Naive Approach
This approach basically merges these two priority queue to a new priority queue , and then poll from that will always give us job that should run first.
PriorityQueue<Job> merged = new PriorityQueue<>();
merged.addAll(userQueue);
merged.addAll(systemQueue);
Job next = merged.poll();This is correct functionally, but problematic in real systems:
• Copies all elements (O(n))
• Doubles memory usage temporarily
• Adds latency spikes
• Breaks down if queues update continuously
Optimized Approach:
Each queue is already sorted by execution time, so the head is always the next job from that source.
By comparing just the two heads, we know which job should execute next globally.
public Job nextJob(PriorityQueue<Job> userQueue, PriorityQueue<Job> systemQueue) {
Job userHead = userQueue.peek();
Job systemHead = systemQueue.peek();
if (userHead == null) return systemQueue.poll();
if (systemHead == null) return userQueue.poll();
return userHead.getTime() <= systemHead.getTime()
? userQueue.poll()
: systemQueue.poll();
}This is the key insight — we don’t need to merge millions of jobs to know the next job.
Constant-time comparison
Only the top elements of the queues are compared.
O(1) time — doesn’t depend on the size of the queues.
Perfect for millions of jobs.
Why this works:
• Constant-time comparison
• No extra memory
• Handles continuously updating queues
• Mirrors real scheduler logic
PriorityQueue is not thread-safe.
For concurrent producers and consumers, use:
PriorityBlockingQueue<Job> userQueue = new PriorityBlockingQueue<>();
PriorityBlockingQueue<Job> systemQueue = new PriorityBlockingQueue<>();The same nextJob() logic works safely with these queues.
📢 Get actionable Java/Spring Boot insights every week — from practical code tips to real-world use-case based interview questions.
Join 6000+ subscribers and level up your Spring & backend skills with hand-crafted content — no fluff.
🎯 Early Supporter Offer
The first 100 paid subscribers get the annual membership at $50/year.
👉 67 already joined — only 33 spots left.
Not convinced? Check out the details of the past work
Better Approach
Instead of maintaining two separate queues (user jobs + system jobs) and constantly comparing their heads, we can combine everything into a single queue.
This approach uses a thread-safe priority queue, which automatically keeps jobs ordered by execution time.
PriorityBlockingQueue<Job> queue =
new PriorityBlockingQueue<>(100, Comparator.comparing(Job::getTime));Producers Push Jobs
queue.put(job);Any producer (user-triggered or system) inserts jobs into this unified queue.
put()is blocking-safe, meaning it handles concurrent insertions safely.No need to worry about two separate queues, merging, or comparing heads.
Scheduler Polls Jobs
Job next = queue.take();
execute(next);take()removes and returns the head of the queue.If the queue is empty,
take()blocks until a new job arrives.This ensures the scheduler always executes the earliest job, no extra logic needed.
How would you handle determinism for the jobs with same execution time
If two jobs have the same scheduled execution time, PriorityQueue may pick them in an unpredictable order. In production, this can cause inconsistent execution order, flaky tests, or unexpected behavior.
Solution: Use a secondary sort key, like a job ID, timestamp, or insertion order:
Comparator<Job> comparator =
Comparator.comparing(Job::getTime)
.thenComparing(Job::getId);comparing(Job::getTime)→ primary sort by scheduled execution time
thenComparing(Job::getId)→ tie-breaker for deterministic orderingGuarantees predictable execution order, even if jobs have the same scheduled time
Job job1 = new Job(1, 1000, "user");
Job job2 = new Job(2, 1000, "system"); // same execution time
PriorityQueue<Job> queue = new PriorityQueue<>(comparator);
queue.add(job1);
queue.add(job2);
System.out.println(queue.poll()); // Job{id=1, time=1000}
System.out.println(queue.poll()); // Job{id=2, time=1000}Expected output: Job 1 first, Job 2 second — deterministic.
How would you prevent starvation of low-priority jobs ?
High-priority jobs can keep arriving, and low-priority jobs never get executed — classic starvation problem
To solve this we can boost the effective priority of long-waiting jobs using priority aging:
long AGING_FACTOR = 10;
public long getEffectiveTime(Job job, long now) {
long waited = now - job.getEnqueueTime();
return job.getTime() - waited / AGING_FACTOR;
}Subtract a fraction of the waiting time from the scheduled time
Jobs that wait longer get a smaller effective time → higher effective priority
Scheduler automatically executes aged jobs sooner
Job low = new Job(1, 1000, "system"); // waiting 5s
Job high = new Job(2, 500, "user"); // just arrived
long now = System.currentTimeMillis();
System.out.println(getEffectiveTime(low, now)); // smaller than original due to waiting
System.out.println(getEffectiveTime(high, now)); // unchanged
// Result: low-priority job may run before the new high-priority jobLow-priority job eventually runs — starvation prevented.
Handle Cancelled Jobs
Some jobs may be cancelled while waiting. Removing them from a heap can be expensive (O(n)), so we use a soft-cancel approach.
if (job.isCancelled()) {
continue; // skip without removing immediately
}Jobs remain in the queue but are skipped during execution
A background cleanup can periodically remove cancelled jobs to avoid heap bloat
Ensures scheduler remains efficient and thread-safe
Job job1 = new Job(1, 1000, "user");
Job job2 = new Job(2, 800, "system");
job2.cancel(); // mark as cancelled
PriorityQueue<Job> queue = new PriorityQueue<>(Comparator.comparing(Job::getTime));
queue.add(job1);
queue.add(job2);
while (!queue.isEmpty()) {
Job next = queue.poll();
if (next.isCancelled()) continue;
System.out.println("Executing " + next);
}Only job1 is executed; cancelled jobs are skipped.
📚 Helpful Resources (5)
Subscribe | Sponsor | LinkedIn | Twitter
Happy Coding 🚀
Suraj