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.

Compute minimax grid path and network delay

Quick Overview

This question evaluates algorithmic problem-solving in shortest-path and path-optimization contexts, specifically minimax pathfinding on a grid and single-source reachability/timing in a weighted directed graph, testing graph modeling, alternative path cost metrics, edge-case handling, and working with large numeric weights.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

## Problem (two related shortest-path tasks) ### Part 1 — Minimize the maximum value along a grid path ("minimax" path) You are given an `m x n` integer grid `H`, where `H[r][c]` is the “difficulty/height” of cell `(r,c)`. - Start at `(0,0)` and want to reach `(m-1, n-1)`. - You may move **up/down/left/right** to adjacent cells (no diagonals). - The **cost of a path** is **not the sum** of values; instead it is: > the maximum `H[r][c]` value encountered on that path (including start and end). **Return** the minimum possible path cost (i.e., minimize the maximum cell value you ever step on). **Assumptions/constraints (typical interview constraints):** - `1 <= m,n <= 200` - `0 <= H[r][c] <= 10^9` ### Part 2 (follow-up) — Time for a signal to reach all nodes in a weighted graph You are given a weighted graph with `n` nodes labeled `1..n` and a list of directed edges `edges`, where each edge is `(u, v, w)` meaning it takes time `w > 0` to travel from `u` to `v`. A signal starts at node `k` at time `0` and travels along edges. - Let `dist[i]` be the shortest time for the signal to reach node `i`. - **Return**: - `max(dist[i])` over all nodes `i` if every node is reachable, or - `-1` if some node is unreachable. **Assumptions/constraints (typical interview constraints):** - `1 <= n <= 10^5` (or smaller in an interview) - `1 <= |edges| <= 2*10^5` - `1 <= w <= 10^9` ## Edge cases to consider - Start equals end (Part 1: `m=n=1`; Part 2: `n=1`). - Unreachable nodes (Part 2). - Multiple edges between the same nodes (Part 2). - Repeated states pushed into a heap/priority queue (both parts).

Quick Answer: This question evaluates algorithmic problem-solving in shortest-path and path-optimization contexts, specifically minimax pathfinding on a grid and single-source reachability/timing in a weighted directed graph, testing graph modeling, alternative path cost metrics, edge-case handling, and working with large numeric weights.

Part 1: Minimize the Maximum Value Along a Grid Path

You are given an `m x n` grid of non-negative integers `H`, where `H[r][c]` is the value of cell `(r, c)`. Starting at the top-left cell `(0, 0)`, you want to reach the bottom-right cell `(m - 1, n - 1)`. You may move one step at a time in the four cardinal directions: up, down, left, or right. The cost of a path is defined as the maximum cell value that appears anywhere on that path, including the start and end cells. Return the minimum possible path cost among all valid paths from the start to the destination.

Constraints

1 <= m, n <= 200
0 <= H[r][c] <= 10^9

Examples

Input: [[1, 10, 6], [1, 3, 2], [7, 2, 2]]

Expected Output: 3

Explanation: A best path is `(0,0) -> (1,0) -> (1,1) -> (1,2) -> (2,2)`, which visits values `1, 1, 3, 2, 2`. The maximum is `3`, and no path can do better.

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

Expected Output: 6

Explanation: Going down the left side and then across the bottom gives values `5, 4, 3, 6, 0`, so the path cost is `6`. Any route through the top or middle forces a maximum of at least `7` or `8`.

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

Expected Output: 3

Explanation: Both possible paths must end at the cell with value `3`, so the minimum possible maximum is `3`.

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

Expected Output: 9

Explanation: The starting cell counts toward the path cost. Since the start already has value `9`, the answer cannot be smaller than `9`.

Input: [[42]]

Expected Output: 42

Explanation: Start and end are the same cell, so the path cost is just that cell's value.

Hints

Think of the 'distance' to a cell as the smallest possible maximum value seen on any path to that cell.
A min-heap can help you always expand the cell with the best current minimax cost first.

Part 2: Network Delay Time in a Directed Weighted Graph

You are given a directed weighted graph with nodes labeled from `1` to `n`. Each directed edge is represented as `[u, v, w]`, meaning it takes `w` units of time for a signal to travel from node `u` to node `v`. A signal starts at node `k` at time `0` and travels along directed edges. Let `dist[i]` be the shortest time needed for the signal to reach node `i`. Return the time when the last node receives the signal, which is `max(dist[i])` over all nodes, if every node is reachable from `k`. If at least one node cannot be reached, return `-1`.

Constraints

1 <= n <= 10^5
0 <= len(edges) <= 2 * 10^5
1 <= u, v <= n
1 <= w <= 10^9
The graph is directed.
There may be multiple edges between the same pair of nodes.

Examples

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

Expected Output: 2

Explanation: From node `2`, the signal reaches nodes `1` and `3` in `1` unit, and node `4` in `2` units. The last arrival time is `2`.

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

Expected Output: -1

Explanation: Node `3` is unreachable from node `1`, so the answer is `-1`.

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

Expected Output: 3

Explanation: There are two edges from `1` to `2`; the shorter one with weight `1` should be used. Then node `3` is reached in `1 + 2 = 3`.

Input: ([], 1, 1)

Expected Output: 0

Explanation: There is only one node, and it is the starting node, so the signal is already everywhere at time `0`.

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

Expected Output: 2

Explanation: Although node `2` is first discovered with distance `10`, a shorter path `1 -> 3 -> 2` gives distance `2`. The farthest node is reached at time `2`.

Hints

Because all edge weights are positive, Dijkstra's algorithm is a strong fit.
After computing shortest distances, check whether any node is still unreached before taking the maximum distance.

Quick Overview