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 hard 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.

Minimize travel time with optional meeting point

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a connected graph representing travel between locations. - Each node is a location. - Each edge has a non-negative travel time (if your interviewer prefers “steps”, treat each edge as weight 1). - Person **A** starts at node `startA`. - Person **B** starts at node `startB`. - Both need to reach the same destination node `dest`. They are allowed to **meet at any node `m` (possibly `startA`, `startB`, or `dest`)**, and after they meet, they **travel together** from `m` to `dest`. Assume: - A and B can travel simultaneously before meeting. - They can only continue together after both have arrived at the meeting node. ### Task Compute the **minimum possible arrival time** for both people to reach `dest` under this strategy. ### Output Return the minimum arrival time (and optionally the meeting node `m` that achieves it). ### Constraints (reasonable interview defaults) - `n` nodes, `m` edges - Edge weights are non-negative - Graph can be directed or undirected (state your assumption and adapt)

Quick Answer: This question evaluates a candidate's understanding of graph shortest-path computation and meeting-point optimization, testing skills in handling weighted edges, aggregating path costs, and reasoning about simultaneous movements on a network.

You are given a graph with nodes labeled from 0 to n - 1 and weighted edges (u, v, w). Person A starts at startA, person B starts at startB, and both want to reach the same destination node dest. They may choose any meeting node m, including startA, startB, or dest. Before meeting, they travel independently and simultaneously, so the time to complete the pre-meeting phase is the slower of the two arrival times at m. After both have arrived at m, they travel together from m to dest along a shortest path. If directed is False, every edge can be used in both directions; otherwise edges can only be used from u to v. Return [minimum_arrival_time, meeting_node]. If multiple meeting nodes achieve the same minimum arrival time, return the smallest meeting node index. If no valid strategy exists, return [-1, -1].

Constraints

1 <= n <= 200000
0 <= len(edges) <= 300000
0 <= u, v < n
0 <= w <= 10^9
Edge weights are non-negative integers
For undirected inputs, assume the graph is connected; for directed inputs, some nodes may be unreachable

Examples

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

Expected Output: [4, 1]

Explanation: Meeting at node 1 gives max(2, 1) + 2 = 4. Meeting at node 3 also gives 4, so choose the smaller node index 1.

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

Expected Output: [5, 1]

Explanation: In the directed graph, meeting at node 1 gives max(2, 3) + 2 = 5. Meeting directly at dest also gives 5, so the smaller meeting node 1 is returned.

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

Expected Output: [0, 0]

Explanation: Both people already start at the destination, so the answer is 0 with meeting node 0.

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

Expected Output: [-1, -1]

Explanation: There is no node that both people can reach and from which they can continue to the destination.

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

Expected Output: [3, 0]

Explanation: Since both start at node 0, they can meet immediately there and then travel together to node 3 in time 3.

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

Expected Output: [2, 4]

Explanation: The best strategy is to meet at the destination itself. A reaches 4 in 2, B reaches 4 in 2, and no additional travel is needed.

Hints

For a fixed meeting node m, the total arrival time is max(dist(startA, m), dist(startB, m)) + dist(m, dest).
To get dist(m, dest) for every node in a directed graph, run Dijkstra once from dest on the reversed graph.

Quick Overview

This question evaluates a candidate's understanding of graph shortest-path computation and meeting-point optimization, testing skills in handling weighted edges, aggregating path costs, and reasoning about simultaneous movements on a network.