How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Find Shortest Queue with Few Calls | Google Coding Question

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.

Input: [[-1, -2], [5], [7, 8]]

Expected Output: (1, 5)

Explanation: The queue [5] is the shortest, with length 1 and sum 5.

Input: [[2, 2], [1, 1], [3, 3, 3]]

Expected Output: (2, 4)

Explanation: Two queues have minimum length 2. The reference solution returns the first shortest queue in input order, [2, 2], whose sum is 4.

Input: []

Expected Output: (0, 0)

Explanation: With no queues at all, the defined result is (0, 0).

Input: [[10, -3, 5]]

Expected Output: (3, 12)

Explanation: There is only one queue, so its length is 3 and its sum is 10 + (-3) + 5 = 12.

Hints

Instead of finishing one queue before moving to the next, think about processing all queues one level at a time.
At the start of round k, if one queue is already empty, then every queue that survived the previous k rounds must have length at least k.

Quick Overview

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.