Skip to content

Find Shortest Queue

Level: L3-L4 Topics: Queues, Algorithm Design, Interleaving, Network-Aware Algorithms

Problem Statement

You are given an array of queues. Each queue supports only two operations:

  • pop() -- Remove and return the front element. This operation is expensive (it involves a network request and takes significant time).
  • empty() -- Returns true if the queue is empty, false otherwise. This is cheap (local check).

There is no size() method and no way to peek at elements without removing them.

Find the length of the shortest queue.

Background & Constraints

  • You have n queues.
  • Each queue contains non-negative integers.
  • pop() is the bottleneck -- you want to minimize the total number of pop() calls.
  • You must determine the exact length of the shortest queue.
  • After the algorithm runs, the queues may be modified (elements are removed).

Examples

queues = [
  Queue([1, 2, 3]),          # length 3
  Queue([4, 5]),              # length 2
  Queue([6, 7, 8, 9]),        # length 4
  Queue([10])                 # length 1
]

Shortest queue length: 1

Hints & Common Pitfalls

  1. Naive approach -- drain each queue: Pop all elements from each queue while counting. Return the minimum count. Total pops: sum of all queue lengths. This is wasteful because you drain long queues entirely even though you only care about the shortest.

  2. Better approach -- interleave pops: Pop one element from each non-empty queue in round-robin fashion. After each round, check which queues have become empty. The first queue to become empty is the shortest.

  3. Interleaving details:

    • Round 1: Pop once from every queue. Mark any that become empty.
    • Round 2: Pop once from every remaining non-empty queue. Mark newly empty ones.
    • Continue until at least one queue is empty.
    • The queues that emptied in the latest round all have the same length (equal to the round number).

  4. Worst case for interleaving: If the shortest queue has length k, you perform at most k pops from each of the n queues, for a total of n * k pops. This is much better than draining all queues when most are much longer than k.

  5. Common mistake: Popping all elements from one queue before moving to the next. This misses the opportunity to stop early when a shorter queue is found.

Follow-Up Questions

  1. Find the queue with the smallest sum: Instead of the shortest queue, find the queue whose elements sum to the smallest total. The elements are unsigned integers. Can you still use an interleaving strategy? How does it change?

  2. What if pop() is asynchronous? You can issue multiple pop() calls in parallel (to different queues) and they return results independently. How would you exploit parallelism to speed up the search?

  3. What if empty() is also expensive? If checking emptiness also requires a network call, how does your strategy change? Can you batch pop() and empty() calls?

  4. Can you find the shortest queue without modifying any queue? If non-destructive observation is impossible, is there a way to restore the queues after finding the answer? What data structure would you need?

  5. What is the expected number of pop() calls if queue lengths are uniformly distributed between 1 and M? How does the interleaving approach compare to the naive approach in the average case?