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.

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.

|Home/Coding & Algorithms/Airbnb
Airbnb logo
Airbnb
Jan 19, 2026, 12:00 AM
hardSoftware EngineerOnsiteCoding & Algorithms
23
0

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.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...