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 Technical Screen rounds at Google.

What role is this question designed for?

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

Solve Rooms and Top-K Streams | Google Coding Question

Quick Overview

This question evaluates algorithmic problem-solving skills across interval scheduling/resource allocation and streaming top-k maintenance, testing competency in data structures for ordered queries, tie-breaking logic, stateful stream processing, and analysis of time and space trade-offs.

Solve Rooms and Top-K Streams

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are asked to solve two independent coding problems. ### Problem 1: Minimum concurrent meeting rooms Given a list of meeting time intervals `intervals`, where each interval is `[start, end)` and `start < end`, return the minimum number of rooms required so that all meetings can be held. Rules and edge cases: - If `intervals` is empty, return `0`. - A meeting ending at time `t` frees its room for another meeting starting at time `t`. - Times are integers, but the algorithm should not depend on the time range being small. Example: ```text Input: [[0, 30], [5, 10], [15, 20]] Output: 2 ``` Follow-up discussion: - Explain a sweep-line or two-pointer approach. - Compare this with a min-heap approach. - What changes if the input is extremely large and cannot fit entirely in memory? - Analyze time and space complexity. ### Problem 2: Maintain the top K items in a stream You receive a stream of items, each represented as `(itemId, score)`. For a fixed integer `k`, maintain the current top `k` items with the largest scores after processing each new item. Implement a component with the following operation: ```text add(itemId, score): process a new item and update the maintained top k set ``` Return or expose the current top `k` items at any time. If fewer than `k` items have been seen, return all seen items. If scores tie, break ties by smaller `itemId` first. Follow-up discussion: - How would your design change if `k` can change over time? - How would you support deleting an item? - How would you support updating the score of an existing item? - Why is a heap a natural data structure here, and what are its limitations? - Analyze time and space complexity for the basic version and each follow-up.

Quick Answer: This question evaluates algorithmic problem-solving skills across interval scheduling/resource allocation and streaming top-k maintenance, testing competency in data structures for ordered queries, tie-breaking logic, stateful stream processing, and analysis of time and space trade-offs.

Part 1: Minimum Concurrent Meeting Rooms

Given a list of meeting intervals, return the minimum number of rooms required so that every meeting can be scheduled. Each interval is represented as [start, end), meaning the meeting starts at start and ends just before end. If one meeting ends at time t, another meeting starting at time t can use the same room. The algorithm should not depend on the time range being small.

Constraints

0 <= len(intervals) <= 200000
Each interval has exactly two integers: [start, end]
-10^9 <= start < end <= 10^9
Intervals may be given in any order
A meeting ending at time t does not overlap a meeting starting at time t

Examples

Input: ([[0, 30], [5, 10], [15, 20]],)

Expected Output: 2

Explanation: The meeting [0, 30) overlaps with both shorter meetings, but the shorter meetings do not overlap each other.

Input: ([],)

Expected Output: 0

Explanation: No meetings require no rooms.

Input: ([[1, 2], [2, 3], [3, 4]],)

Expected Output: 1

Explanation: Each meeting starts exactly when the previous one ends, so one room is enough.

Input: ([[1, 5], [2, 6], [3, 7], [4, 8]],)

Expected Output: 4

Explanation: All four meetings overlap during the time range [4, 5).

Input: ([[10, 20], [-5, 0], [0, 10], [5, 15]],)

Expected Output: 2

Explanation: Meetings at exact end/start boundaries can reuse rooms, but [0, 10) overlaps with [5, 15), and [5, 15) overlaps with [10, 20).

Hints

Separate the start times and end times, then process them in sorted order.
When the next meeting starts before the earliest current meeting ends, you need a new room.

Part 2: Maintain Top K Items in a Stream

You receive a stream of items. Each item is represented as [itemId, score]. For a fixed integer k, maintain the current top k items with the largest scores after each new item is processed. If fewer than k items have been seen, return all seen items. If scores tie, the item with the smaller itemId ranks higher. For this coding version, each itemId appears at most once in the stream, so there are no score updates or deletions.

Constraints

0 <= k <= 100000
0 <= len(stream) <= 200000
Each stream entry has exactly two integers: [itemId, score]
-10^9 <= itemId <= 10^9
-10^9 <= score <= 10^9
Each itemId appears at most once in stream

Examples

Input: (2, [[1, 50], [2, 60], [3, 55], [4, 60]])

Expected Output: [[[1, 50]], [[2, 60], [1, 50]], [[2, 60], [3, 55]], [[2, 60], [4, 60]]]

Explanation: After the final item, the two highest scores are both 60, ordered by smaller itemId first.

Input: (0, [[1, 10], [2, 20], [3, 30]])

Expected Output: [[], [], []]

Explanation: When k is 0, no items are maintained, but one empty snapshot is returned after each add.

Input: (3, [])

Expected Output: []

Explanation: An empty stream produces no snapshots.

Input: (5, [[10, -1], [5, -1], [7, 0]])

Expected Output: [[[10, -1]], [[5, -1], [10, -1]], [[7, 0], [5, -1], [10, -1]]]

Explanation: Because fewer than k items have been seen, all seen items are returned, sorted by ranking.

Input: (2, [[5, 10], [2, 10], [3, 10]])

Expected Output: [[[5, 10]], [[2, 10], [5, 10]], [[2, 10], [3, 10]]]

Explanation: All scores tie, so the two smallest itemIds are kept.

Hints

Keep only the best k items seen so far. The item you most want to remove is the worst item among the current top k.
Use a min-heap where the root is the worst kept item: lowest score first, and for equal scores, larger itemId first.

Quick Overview