DSA Round: Maximum Score Grid Path
Updated
Problem statement
You are given a rectangular grid board of size N x M, where each cell contains an integer. A player starts from cell (0, p) in the top row. The objective is to reach the bottom row of the grid while maximizing the total score collected.
From a cell (i, j), the player may move to:
(i + 1, j - 1), diagonally left-down(i + 1, j), straight down(i + 1, j + 1), diagonally right-down(i + 2, j), using a special jump move
The player must always remain inside the grid boundaries. The special jump move (i + 2, j) may be used at most k times during the traversal.
The total score is equal to the sum of all visited cell values, including the starting cell and the final cell.
Complete the function maximizeGridPathScore. It should return a String[] with exactly three values:
result[0]: the maximum achievable score from the starting cell to any cell in the last row.result[1]: one path that produces the maximum score, formatted as coordinates joined by->, for example(0,1)->(1,1).result[2]: the number of distinct maximum-score paths modulo10^9 + 7.
If multiple maximum-score paths exist, return the lexicographically smallest coordinate sequence as the path in result[1]. Compare two paths by their coordinate pairs from left to right; the smaller row wins first, then the smaller column.
Overview
This problem is about maximizing score while moving through a rectangular integer grid. It has four allowed moves, including a limited special jump, and asks for the maximum score, one maximum-score path, and the count of maximum-score paths modulo 10^9 + 7.
Output rules
Return one maximum-score path; among ties, return the lexicographically smallest coordinate sequence.
Function
maximizeGridPathScore(board: int[][], p: int, k: int) → String[]Examples
Example 1
board = [[1,2,3,4],[5,6,1,2],[7,8,9,1],[3,2,5,6]]p = 1k = 1return = ["23","(0,1)->(1,1)->(2,2)->(3,3)","1"]One maximum-score path is (0,1)->(1,1)->(2,2)->(3,3).
- Visited values:
2 + 6 + 9 + 6 = 23. - The alternate valid jump path
(0,1)->(2,1)->(3,2)scores2 + 8 + 5 = 15, so it is not a maximum-score path. - There is exactly one maximum-score path for this example.
Constraints
boardis rectangular and contains integers.pis a valid column index in the top row.- The player may use the special jump at most
ktimes. - Return the maximum-path count modulo
10^9 + 7.
More OpenAI Onsite Interview questions
- Sparse Plant Infection SimulationPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Rectangle Point Coverage CountsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Message Event AggregationPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- 15-Minute Chat Session TrackerPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Segmented Durable Key-Value StorePHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Durable Work Queue OperationsPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Versioned Social NetworkPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Budgeted API Inference with Out-of-Order FeedbackONSITE INTERVIEW · Seen Oct 2026
- Plant Infection Simulation, Part 4: Death CountdownPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Count Friend CirclesPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Count Paths from the Top Left to the Bottom RightAmazon · ONSITE INTERVIEW
- Count Valid A-B-C Sequences Under a Modulo-Four RuleInfosys · OAInfosys interview questions
- Unique Grid PathsMorgan Stanley · PHONE SCREENMorgan Stanley interview questions
- Dungeon GameLotusFlare · ONSITE INTERVIEW
- Maximum Non-Adjacent Coins in Two RowsKotak Mahindra Bank · ONSITE INTERVIEWKotak Mahindra Bank interview questions
- Longest Increasing Path in a MatrixNew Relic · PHONE SCREEN · ONSITE INTERVIEW
- Longest Increasing Path in a MatrixVisa · ONSITE INTERVIEWVisa interview questions
- Maximal Rectangle in a Binary MatrixGoogle · ONSITE INTERVIEWGoogle interview questions
- Dungeon HealthGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Longest Decreasing Matrix Path with Limited RelaxationsDuolingo · ONSITE INTERVIEWDuolingo interview questions