Katkat
Back

Compute minimax grid path and network delay

GoogleSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to solve pathfinding problems using non-standard cost metrics: first, finding a minimax path in a grid, and second, calculating the earliest arrival time in a network with weighted edges.

Part 1: Minimax Path in a Grid

Given an n x m grid where each cell (r, c) has a value grid[r][c], find a path from (0, 0) to (n-1, m-1) such that the maximum value encountered on the path is minimized. You can only move down or right.

def minimize_max_path(grid: list[list[int]]) -> int:
    pass

Example: Input: grid = [[1, 5], [4, 2]] Output: 4 Explanation: Path (0,0) -> (1,0) -> (1,1) visits [1, 4, 2], max is 4. Path (0,0) -> (0,1) -> (1,1) visits [1, 5, 2], max is 5. Minimum of these is 4.

Part 2: Network Delay

You are given a set of nodes 0 to n-1 and a list of directed edges (u, v, w), where w is the time it takes to travel from u to v. If a signal is sent from a starting node source, calculate the earliest time it takes for the signal to reach every other node in the network. If a node is unreachable, return -1.

def network_delay(n: int, edges: list[tuple[int, int, int]], source: int) -> list[int]:
    pass

Constraints:

  • n up to 10^4, edges up to 10^5.
  • Weights are positive integers.
  • Grid size up to 500x500.

Edge Cases:

  • Disconnected graphs.
  • Grids with only one row or one column.

Hints

Hint 1

For the grid problem, consider using binary search on the possible values of the result or dynamic programming where `dp[r][c]` stores the minimax value to reach that cell.

Hint 2

For the network delay problem, this is a classic shortest-path calculation which can be solved efficiently using Dijkstra's algorithm with a priority queue.

Hint 3

In the grid problem, remember that the smallest possible answer is `max(grid[0][0], grid[n-1][m-1])`.

Follow-up questions

  • How would the grid solution change if you were allowed to move in all four directions instead of just down and right?
  • What is the time complexity of your network delay solution, and can you optimize it for sparse graphs?
  • How would you handle a scenario where edges in the network have negative weights, provided there are no negative cycles?