Katkat
Back

Implement exponentiation and fill grid distances

MetaMachine Learning Engineer · Online Assessment
MediumMachine Learning EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests proficiency in efficient modular exponentiation (binary exponentiation) and multi-source Breadth-First Search (BFS) for computing shortest distances in a grid.

Part 1: Modular Exponentiation

Implement a function power(base, exp, mod) that computes (base^exp) % mod efficiently.

  • Constraints: exp can be up to 10^18, mod up to 10^9 + 7.
  • The solution must run in O(log exp) time complexity.

Part 2: Grid Distance

Given a 2D binary matrix grid of size m x n where 1 represents a source and 0 represents an empty cell, compute a matrix of the same dimensions where each cell contains the shortest Manhattan distance to the nearest 1.

  • Function signature: def update_distances(grid: List[List[int]]) -> List[List[int]]:
  • Constraints: m, n <= 500.

Examples

Part 1

Input: power(2, 10, 1000) Output: 24 (Since 1024 % 1000 = 24)

Part 2

Input:

[[0, 0, 0],
 [0, 1, 0],
 [0, 0, 0]]

Output:

[[2, 1, 2],
 [1, 0, 1],
 [2, 1, 2]]

Explanation: Every cell's value is the shortest number of steps to reach the single 1 at (1, 1).

Edge Cases

  • Part 1: exp = 0 (result is 1), mod = 1 (result is 0).
  • Part 2: Grid with no 1s (return all distances as infinity or -1), grid with all 1s.

Hints

Hint 1

For modular exponentiation, use the property that if exp is even, base^exp = (base^2)^(exp/2), and if odd, base^exp = base * base^(exp-1).

Hint 2

For the grid problem, initialize a queue with all cells containing `1` and set their distance to 0, then run a multi-source BFS.

Hint 3

Ensure you track visited cells in the grid to avoid cycles and redundant computations, or update distances in-place using a distance matrix initialized to infinity.

Follow-up questions

  • How would the space complexity change if you were required to solve the grid distance problem in O(1) auxiliary space (modifying the input grid directly)?
  • If the grid values represented obstacles (`1`) and empty paths (`0`), how would you find the shortest path from a specific source to a destination using A* search?
  • In the modular exponentiation problem, how would you handle negative bases?