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

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.

Loading coding console...

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