Find Shortest Queue with Few Calls
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a list of queues of integers. For each queue, the only available operations are `isEmpty()` and `poll()`, where `poll()` removes and returns the front element. You do not have access to `size()`, indexing, or iteration.
Design an algorithm that uses as few total API calls as possible to determine:
1. The minimum length among all queues.
2. The sum of elements in a queue whose length equals that minimum.
You may consume the queues destructively while processing them. If multiple queues have the same minimum length, returning the sum for any one of those shortest queues is acceptable.
Explain the strategy and its call complexity.
Quick Answer: This question evaluates algorithm design and analysis skills, focusing on working with restricted data structure APIs and minimizing total operations through API call optimization while processing queues.
You are given a list of queues of integers. Each inner list represents one queue from front to back.
Conceptually, the only allowed operations on a queue are:
- `isEmpty()` -> tells whether the queue has no elements
- `poll()` -> removes and returns the front element
You do not have access to `size()`, indexing, or iteration over a queue. You may consume queues destructively while processing them.
Return a tuple `(min_length, queue_sum)` where:
1. `min_length` is the minimum length among all queues.
2. `queue_sum` is the sum of elements in any queue whose length equals `min_length`.
If multiple queues are tied for shortest, returning the sum for any one of them is acceptable. For this reference solution, ties are broken by returning the first shortest queue encountered in input order.
If the outer list of queues is empty, return `(0, 0)`.
Your goal is to design an algorithm that minimizes total queue API calls. In particular, avoid fully consuming long queues once you already know they cannot be shorter than the current best answer.
Constraints
- 0 <= number of queues <= 10^5
- 0 <= total number of integers across all queues <= 2 * 10^5
- -10^9 <= each queue element <= 10^9
Examples
Input: [[1, 2, 3], [4, 5], [6, 7, 8, 9]]
Expected Output: (2, 9)
Explanation: The shortest queue is [4, 5], so the minimum length is 2 and the sum is 4 + 5 = 9.
Input: [[], [1, 2, 3], [4]]
Expected Output: (0, 0)
Explanation: An empty queue already exists, so the minimum length is 0 and the sum of that queue is 0.