FastPrepDSA Round: Maximum Score Grid Path
Problems/DSA Round: Maximum Score Grid Path

DSA Round: Maximum Score Grid Path

OpenAI logoOpenAI● HardFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

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:

  1. result[0]: the maximum achievable score from the starting cell to any cell in the last row.
  2. result[1]: one path that produces the maximum score, formatted as coordinates joined by ->, for example (0,1)->(1,1).
  3. result[2]: the number of distinct maximum-score paths modulo 10^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"]
board
012301234156122789133256

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) scores 2 + 8 + 5 = 15, so it is not a maximum-score path.
  • There is exactly one maximum-score path for this example.

Constraints

  • board is rectangular and contains integers.
  • p is a valid column index in the top row.
  • The player may use the special jump at most k times.
  • 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
All OpenAI interview questionsSee OpenAI hiring insights
Saved
class Solution {
    public String[] maximizeGridPathScore(int[][] board, int p, int k) {
      // write your code here
    }
}
Checking account…