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

What role is this question designed for?

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

Compute ETA between two map nodes | Waymo Coding Question

Compute ETA between two map nodes

Company: Waymo

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem You are given a **semantic road map** represented as a weighted graph. Each node is an intersection/waypoint, and each edge represents a drivable road segment with an associated **travel time** (in seconds). Given two nodes `start` and `end`, compute the **ETA** (minimum travel time) from `start` to `end`. ## Clarifications to confirm with interviewer - Is the graph **directed** (one-way roads) or **undirected**? (Assume directed unless stated otherwise.) - Are travel times **non-negative**? (Assume yes.) - What should be returned if `end` is unreachable from `start`? (Return `-1`.) - Are there **multiple queries** or a single query? (Assume a single query unless specified.) ## Input / Output (one possible interface) - Input: - `n`: number of nodes labeled `0..n-1` - `edges`: list of roads, each as `(u, v, t)` meaning an edge from `u` to `v` taking `t` seconds - `start`, `end`: node IDs - Output: - Minimum travel time from `start` to `end`, or `-1` if unreachable ## Constraints - `1 <= n <= 2e5` - `0 <= |edges| <= 5e5` - `0 <= t <= 1e9` (non-negative) ## Example - `n = 5` - `edges = [(0,1,5),(1,2,2),(0,2,20),(2,3,1),(3,4,3)]` - `start = 0, end = 4` Shortest ETA path is `0->1->2->3->4` with total time `5+2+1+3 = 11`, so return `11`.

Quick Answer: This question evaluates proficiency in graph algorithms and shortest-path computation, specifically handling weighted directed graphs, non-negative travel times, and reachability.

You are given a semantic road map represented as a directed weighted graph. Each node is an intersection or waypoint labeled from 0 to n-1, and each edge (u, v, t) represents a drivable road from node u to node v that takes t seconds to travel. Compute the minimum travel time (ETA) from start to end. If end cannot be reached from start, return -1. All travel times are non-negative.

Constraints

1 <= n <= 200000
0 <= len(edges) <= 500000
0 <= u, v < n
0 <= t <= 1000000000
Travel times are non-negative

Examples

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

Expected Output: 11

Explanation: The fastest path is 0 -> 1 -> 2 -> 3 -> 4 with total time 5 + 2 + 1 + 3 = 11.

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

Expected Output: -1

Explanation: There are no roads, so node 2 is unreachable from node 0.

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

Expected Output: 0

Explanation: If start and end are the same node, the travel time is 0.

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

Expected Output: 8

Explanation: There are two roads from 0 to 1. Using the cheaper one gives path 0 -> 1 -> 2 -> 3 with total time 3 + 4 + 1 = 8.

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

Expected Output: 2

Explanation: The best route is 0 -> 1 -> 2 -> 3 with total time 0 + 0 + 2 = 2.

Hints

Because road times can vary, a normal BFS is not enough. Think about the shortest-path algorithm for graphs with non-negative edge weights.
Use a min-heap to always expand the node with the smallest known travel time, and keep an array of best distances found so far.

Quick Overview

This question evaluates proficiency in graph algorithms and shortest-path computation, specifically handling weighted directed graphs, non-negative travel times, and reachability.