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

What role is this question designed for?

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

Compute max reachable cells per threshold

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given: - An `m x n` integer matrix `terrain`. - An integer array `limits` of length `k`. For each query value `L = limits[i]`, you start at the top-left cell `(0, 0)` and may move repeatedly to any 4-directionally adjacent cell (up/down/left/right). Rules for scoring and movement: - You are allowed to step onto a cell `(r, c)` **only if** `L` is **strictly greater** than `terrain[r][c]`. - The **first time** you visit an allowed cell, you gain **1 point**. - You may revisit cells any number of times, but you do **not** gain additional points for revisits. - The process effectively ends when no additional moves to allowed (unvisited or visited) cells are possible under the rule above. Define `answer[i]` as the **maximum number of points** you can obtain for `limits[i]`. Return the array `answer`. **Function signature** - Input: `int[][] terrain, int[] limits` - Output: `int[] answer` **Example 1** ``` terrain = [ [1, 4, 2, 8], [0, 4, 0, 8], [1, 2, 0, 8] ] limits = [8, 2] answer = [9, 3] ``` **Example 2** ``` terrain = [ [2, 5, 7], [3, 5, 1] ] limits = [5, 6, 2] answer = [5, 8, 1] ``` Notes: - You should aim for an efficient solution when `k` is large (many queries). - `terrain` values may repeat; `limits` are arbitrary integers.

Quick Answer: This question evaluates a candidate's ability to reason about constrained grid reachability and efficient handling of multiple threshold queries, testing skills in reachability analysis, graph traversal concepts, and query-driven precomputation.

You are given an m x n integer matrix terrain and an integer array limits. For each query value L = limits[i], you start at the top-left cell (0, 0). You may move up, down, left, or right to adjacent cells, but you may step onto a cell only if L is strictly greater than that cell's terrain value. The first time you visit an allowed cell, you gain 1 point; revisiting a cell gives no extra points. For each query, return the maximum number of points you can obtain, which is the number of distinct allowed cells reachable from (0, 0). Return the answers in the same order as limits.

Constraints

1 <= m, n <= 1000
1 <= m * n <= 100000
1 <= len(limits) <= 100000
-10^9 <= terrain[r][c], limits[i] <= 10^9

Examples

Input: ([[1, 4, 2, 8], [0, 4, 0, 8], [1, 2, 0, 8]], [8, 2])

Expected Output: [9, 3]

Explanation: For L = 8, every cell except the three cells with value 8 is allowed and reachable, so the score is 9. For L = 2, only the connected component {(0,0), (1,0), (2,0)} is reachable.

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

Expected Output: [2, 5, 0]

Explanation: For L = 5, only values less than 5 are allowed, so you can reach (0,0) and (1,0). For L = 6, every cell except 7 is allowed and all 5 such cells are connected to the start. For L = 2, the start cell is not allowed, so the score is 0.

Input: ([[5]], [4, 5, 6])

Expected Output: [0, 0, 1]

Explanation: This checks the strict inequality. A limit of 4 or 5 cannot enter the only cell because 5 is not less than the limit. A limit of 6 can, so the score is 1.

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

Expected Output: [0, 3, 4]

Explanation: For L = -2, the start cell -1 is not allowed, so the score is 0. For L = 0, the three negative cells are reachable. For L = 3, all four cells are allowed and reachable.

Input: ([[1, 100, 1], [1, 100, 1], [1, 1, 1]], [2, 101, 1])

Expected Output: [7, 9, 0]

Explanation: For L = 2, all cells with value 1 are allowed, and all 7 of them are connected through the bottom path. For L = 101, every cell is allowed, so the score is 9. For L = 1, no cell is allowed because the rule is strictly greater.

Hints

If you sort the queries by threshold, the set of reachable cells only grows as the threshold increases.
Use a min-heap to expand the reachable frontier in order of terrain value, so each cell is processed at most once.

Quick Overview

This question evaluates a candidate's ability to reason about constrained grid reachability and efficient handling of multiple threshold queries, testing skills in reachability analysis, graph traversal concepts, and query-driven precomputation.