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.

Solve meeting-room scheduling and shortest paths

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are asked to solve two algorithmic problems. ## Part A: Meeting-room scheduling (intervals) You are given an array of meeting time intervals `intervals`, where each interval is `[start, end)` with `0 <= start < end`. 1. **Attend-all check**: Return `true` if a single person can attend all meetings (i.e., no overlaps), else `false`. 2. **Minimum rooms**: Return the minimum number of conference rooms required to host all meetings. 3. **Room assignment / most-used room (optional extension)**: You have `n` rooms labeled `0..n-1`. Schedule meetings in start-time order using the lowest-index available room; if none are available at a meeting’s start, delay the meeting until the earliest room becomes free (preserving meeting duration). Return the room index that hosted the most meetings (tie → smallest index). ### Constraints (assume) - `1 <= intervals.length <= 2e5` - Times are integers up to `1e9` ## Part B: Shortest path in a weighted directed graph Given a weighted **directed** graph with `V` nodes labeled `0..V-1` and `E` edges. Each edge is `(u, v, w)` with `w > 0`. - Input: `V`, edge list, `source s`, `target t`. - Output: the shortest distance from `s` to `t` (and optionally the actual path). If `t` is unreachable, return `-1`. ### Constraints (assume) - `1 <= V <= 2e5`, `0 <= E <= 2e5` - Weights are positive integers.

Quick Answer: This question evaluates proficiency in interval scheduling and resource allocation as well as shortest-path computation in weighted directed graphs, emphasizing event ordering, efficient priority structures and graph traversal techniques.

Meeting Rooms: Attend-All, Minimum Rooms, and Most-Used Room

You are given an array of meeting time intervals `intervals`, where each interval is `[start, end)` with `0 <= start < end`, and an integer `n` (the number of available rooms labeled `0..n-1`). Return a list `[canAttendAll, minRooms, mostUsedRoom]`: 1. **canAttendAll** (bool): `true` if a single person can attend all meetings (no two meetings overlap), else `false`. Note intervals are half-open, so a meeting ending exactly when another starts does NOT overlap. 2. **minRooms** (int): the minimum number of conference rooms required to host all meetings simultaneously. 3. **mostUsedRoom** (int): with `n` rooms, schedule meetings in start-time order, always using the lowest-index available room. If no room is free at a meeting's start, delay that meeting until the earliest room becomes free (preserving the meeting's duration). Return the index of the room that hosted the most meetings; on a tie, return the smallest index. For an empty `intervals` list, return `[true, 0, 0]`. ### Constraints - `1 <= intervals.length <= 2*10^5` - `0 <= start < end <= 10^9` - `1 <= n <= intervals.length`

Constraints

1 <= intervals.length <= 2*10^5
0 <= start < end <= 10^9
1 <= n <= intervals.length
Intervals are half-open [start, end): touching endpoints do not overlap

Examples

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

Expected Output: [false, 2, 1]

Explanation: Meetings [0,30] and [5,10] overlap so attend-all is false. Peak concurrency is 2 (at t=5, [0,30] and [5,10]). With 2 rooms: [0,30]->room0, [5,10]->room1, [15,20]-> room1 is free at 10 so ->room1; room1 hosts 2 meetings.

Input: ([[7, 10], [2, 4]], 2)

Expected Output: [true, 1, 0]

Explanation: Sorted [2,4],[7,10] do not overlap, so attend-all is true and only 1 room is ever needed; room0 hosts both.

Input: ([[1, 5], [8, 9], [8, 9]], 2)

Expected Output: [false, 2, 0]

Explanation: The two identical [8,9] meetings overlap each other, so attend-all is false and 2 rooms are needed at t=8. room0 hosts [1,5] then [8,9] (2 meetings) vs room1's single [8,9]; tie-break/most -> room0.

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

Expected Output: [false, 3, 0]

Explanation: All three overlap around t=3, so 3 rooms are needed and attend-all is false. Each room hosts exactly one meeting; smallest index wins -> 0.

Input: ([], 1)

Expected Output: [true, 0, 0]

Explanation: Empty schedule: nobody needs a room.

Input: ([[5, 10]], 1)

Expected Output: [true, 1, 0]

Explanation: A single meeting: attendable, 1 room, hosted by room0.

Input: ([[0, 10], [1, 5], [2, 7], [3, 4]], 2)

Expected Output: [false, 4, 0]

Explanation: At t=3 all four meetings are live, so 4 rooms minimum and attend-all false. With only n=2 rooms, delays push counts to [2,2]; tie -> room0.

Hints

Sort the meetings by start time first; it serves all three parts.
For minimum rooms, sweep meetings in start order and keep a min-heap of end times; pop every meeting that has already ended before the current start. The peak heap size is the answer.
For most-used room, keep one heap of free room indices (to pick the lowest index) and one heap of (free_time, room_index) for busy rooms. When nothing is free, pop the earliest-freeing busy room and re-insert it pushed forward by the meeting's duration.

Shortest Path in a Weighted Directed Graph

Given a weighted **directed** graph with `V` nodes labeled `0..V-1` and an edge list `edges`, where each edge is `[u, v, w]` meaning a directed edge from `u` to `v` with positive weight `w`. Given a source node `s` and target node `t`, return the shortest total distance from `s` to `t`. If `t` is unreachable from `s`, return `-1`. The distance from a node to itself is `0`. ### Constraints - `1 <= V <= 2*10^5` - `0 <= edges.length <= 2*10^5` - `0 <= u, v < V`, `1 <= w <= 10^9` (positive integer weights) - `0 <= s, t < V`

Constraints

1 <= V <= 2*10^5
0 <= edges.length <= 2*10^5
1 <= w <= 10^9 (positive weights only)
Directed edges: [u, v, w] does not imply [v, u, w]
Return -1 when t is unreachable; distance to self is 0

Examples

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

Expected Output: 4

Explanation: 0->2 (1) ->1 (2) ->3 (1) = 4, which beats 0->1->3 = 5 and 0->2->3 = 6.

Input: (2, [[0, 1, 7]], 0, 1)

Expected Output: 7

Explanation: Single edge of weight 7.

Input: (3, [[0, 1, 5]], 0, 2)

Expected Output: -1

Explanation: Node 2 has no incoming edges, so it is unreachable.

Input: (1, [], 0, 0)

Expected Output: 0

Explanation: Source equals target with no edges; distance to self is 0.

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

Expected Output: 12

Explanation: 0->1->2->3 = 1+1+10 = 12; the cycle 0->1->2->0 never helps.

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

Expected Output: -1

Explanation: Only nodes 0 and 1 are connected; node 2 is isolated and unreachable.

Input: (6, [[0, 1, 7], [0, 2, 9], [0, 5, 14], [1, 2, 10], [1, 3, 15], [2, 3, 11], [2, 5, 2], [3, 4, 6], [5, 4, 9]], 0, 4)

Expected Output: 20

Explanation: 0->2 (9) ->5 (2) ->4 (9) = 20, which beats 0->2->3->4 = 26 and 0->5->4 = 23.

Hints

All weights are positive, so Dijkstra's algorithm applies — no need for Bellman-Ford.
Use a min-heap of (distance, node). Skip a popped entry if its distance is greater than the best known distance for that node (lazy deletion).
You can stop early and return as soon as you pop the target t, since Dijkstra finalizes nodes in nondecreasing distance order.

Quick Overview

This question evaluates proficiency in interval scheduling and resource allocation as well as shortest-path computation in weighted directed graphs, emphasizing event ordering, efficient priority structures and graph traversal techniques.