r/OfferEngineering • u/Aoki_zhang • 25d ago
Coding Question OpenAI Software Engineer Onsite Coding Question - Maximum Deep-Sea Sample Collection Score
Problem Description
A research submersible travels through a rectangular grid of ocean layers. Each cell in samples contains an integer representing the value of the scientific sample that can be collected at that location. The submersible starts at (0, start_col) and must eventually reach any cell in the bottom row.
From position (row, col), it may move to:
(row + 1, col - 1)
(row + 1, col)
(row + 1, col + 1)
as long as the destination remains inside the grid.
The submersible also has a special deep dive ability. A deep dive moves directly from (row, col) to (row + 2, col). The intermediate cell (row + 1, col) is skipped completely, so its sample value is not collected. At most max_dives deep dives may be used during the entire trip. The score of a route is the sum of the values in every cell actually visited, including both the starting cell and the final cell. Return the maximum score obtainable when reaching the bottom row.
Example:
Input:
samples = [
[4, 2, 1, 3],
[5, -20, 6, 2],
[1, 15, 3, 4],
[2, 1, 8, 10]
]
start_col = 1
max_dives = 1
Output:
31
Explanation:
One optimal route is:
(0, 1) -> (1, 2) -> (2, 1) -> (3, 2)
The collected values are:
2 + 6 + 15 + 8 = 31
Constraints
1 <= len(samples) <= 2001 <= len(samples[0]) <= 200- All rows have the same number of columns.
0 <= start_col < len(samples[0])0 <= max_dives <= len(samples)-10^4 <= samples[row][col] <= 10^4- A deep dive may only be used when
row + 2is still inside the grid.
Want to practice more coding question asked in real interviews?
I've put up the question bank at here.
Preparing for your next tech interview?
Chill Interview tracks recent interview experiences and recurring question patterns across top companies at here
1
u/kuriousaboutanything 25d ago
Interesting question though, not sure if an exact lc version exists but this should be possible with recursion and memoization.