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 Onsite rounds at Airbnb.

What role is this question designed for?

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

Find best downhill ski run from a start

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are given an `R x C` grid of integers representing elevations. A skier starts at a given cell `(sr, sc)`. From a cell, the skier may move up/down/left/right to a neighboring cell with **strictly lower** elevation. The skier can continue moving as long as the elevation strictly decreases. Define the skier’s score as the **maximum number of cells** that can be visited in a valid downhill run starting from `(sr, sc)` (including the start cell). Tasks: 1. Return the maximum possible score for a single skier starting at `(sr, sc)`. 2. Follow-up: if you are given **many skiers** (a list of starting cells), return the score for each efficiently. State your time/space complexity for both the single-skier and multi-skier versions.

Quick Answer: This question evaluates algorithmic problem-solving in grid graph traversal and dynamic programming, requiring computation of the maximum-length strictly decreasing path from a start cell plus analysis of time and space complexity.

Part 1: Maximum Downhill Score for One Skier

You are given a 2D grid of integers where each value is an elevation. A skier starts at cell (sr, sc). From any cell, the skier may move one step up, down, left, or right, but only to a neighboring cell with a strictly lower elevation. The skier may continue moving while the elevation strictly decreases. Return the maximum number of cells that can be visited in a valid downhill run starting from the given cell, including the start cell itself. If the grid is empty, return 0.

Constraints

0 <= R, C
If the grid is non-empty, all rows have the same length
If the grid is non-empty, 1 <= R * C <= 100000
-10^9 <= grid[r][c] <= 10^9
If the grid is non-empty, the given start cell is within bounds

Examples

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

Expected Output: 7

Explanation: One optimal run is 9 -> 8 -> 7 -> 6 -> 3 -> 2 -> 1, which visits 7 cells.

Input: ([[5, 5], [5, 5]], 0, 0)

Expected Output: 1

Explanation: No move is allowed because all neighboring cells have equal elevation, not lower.

Input: ([[42]], 0, 0)

Expected Output: 1

Explanation: A single-cell grid always has score 1 because the start cell counts.

Input: ([], 0, 0)

Expected Output: 0

Explanation: An empty grid has no cells to visit.

Hints

Think of each cell as a node in a graph. Because you can only move to a strictly lower elevation, cycles are impossible.
Use DFS with memoization so that the best downhill score from each cell is computed only once.

Part 2: Efficient Downhill Scores for Many Skiers

You are given a 2D grid of integers where each value is an elevation. A skier starting at cell (r, c) may move up, down, left, or right to a neighboring cell with a strictly lower elevation. The skier's score is the maximum number of cells that can be visited in a valid downhill run starting from that cell, including the starting cell. Now you are given many starting cells. Return the downhill score for each start efficiently. If the grid is empty, return 0 for every requested start.

Constraints

0 <= R, C
If the grid is non-empty, all rows have the same length
If the grid is non-empty, 1 <= R * C <= 100000
0 <= len(starts) <= 100000
-10^9 <= grid[r][c] <= 10^9
If the grid is non-empty, each start cell in starts is within bounds

Examples

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

Expected Output: [7, 5, 1]

Explanation: The scores are 7 from 9, 5 from 7, and 1 from 1.

Input: ([[5, 5], [5, 5]], [(0, 0), (1, 1)])

Expected Output: [1, 1]

Explanation: No skier can move because no neighboring cell has lower elevation.

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

Expected Output: []

Explanation: No starting cells were requested, so the result is an empty list.

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

Expected Output: [0, 0]

Explanation: With an empty grid, every requested score is 0.

Hints

The answer for a starting cell depends only on that cell, not on which skier asks for it.
Memoize the best downhill score from each cell once, then answer each query by reusing that stored value.

Quick Overview

This question evaluates algorithmic problem-solving in grid graph traversal and dynamic programming, requiring computation of the maximum-length strictly decreasing path from a start cell plus analysis of time and space complexity.