DSA interview question

Ninja and His Friends (Maximum Chocolates Collection)

Medium · Algorithms · Topics: dynamic programming, 3d dp, matrix

The problem

You're designing a mini-game feature for a mobile app. Two characters — Ninja and his friend — start at the top-left and top-right corners of a grid-shaped level filled with chocolates. Both move simultaneously, row by row, and on each row they can move to the cell diagonally left, straight down, or diagonally right. If both characters land on the same cell, only one of them gets to pick up the chocolate there (no double counting). Your task: compute the maximum total chocolates both characters can collect together by the time they reach the bottom row.

Example: a 3x3 grid where Ninja starts at (0,0) and friend starts at (0,2), both moving down to row 2 — figure out the best paths to maximize combined pickup.

Function signature

int maxChocolates(int n, int m, vector<vector<int>>& grid);
// n = number of rows, m = number of columns
// grid[i][j] = number of chocolates at cell (i, j)

Test cases

Input `grid`	n	m	Output	Explanation
`[[3,1,1],[2,5,1],[1,5,5],[2,1,1]]`	4	3	24	Both alligators collect optimally moving down, sharing no overlapping cells beyond necessity
`[[1,2,3],[4,5,6],[7,8,9]]`	3	3	37	Ninja from (0,0), friend from (0,2), best combined path
`[[5]]`	1	1	5	Both start and end on same single cell — counted once
`[[1,1],[1,1]]`	2	2	4	Small grid, straightforward paths
`[[0,0,0],[0,0,0]]`	2	3	0	No chocolates anywhere

(Always confirm: grid values are non-negative; both start on row 0 at columns 0 and m-1.)

How interviewers phrase it

"Two robots start at top-left and top-right of a grid and move down to the bottom, each step going diagonally-left, straight, or diagonally-right. Maximize total value collected, with shared cells counted once."
Often disguised as "Cherry Pickup II" (LeetCode 1463) — same exact problem, "cherries" instead of "chocolates".
May be phrased as a single-robot round-trip variant ("Cherry Pickup I" — LeetCode 741) — different and harder, be ready to distinguish.

Clarifying questions to ask

Do both characters start on row 0, at columns 0 and m-1 respectively, and must reach row n-1? Confirm boundary conditions.
On each move, can they go to 3 directions (left-diagonal, straight down, right-diagonal), or fewer?
If both land on the same cell, is the chocolate counted once or can each collect it independently (double count)? (This problem: counted once.)
Can characters move out of grid bounds — i.e., is movement restricted so column index stays within [0, m-1]?
Are chocolate values always non-negative, or can there be negative values (penalties)?

Follow-ups to expect

"Can you reduce space complexity?"
"What if there were 3 collectors instead of 2?"
"Cherry Pickup I: single robot goes from top-left to bottom-right and back to top-left, maximizing cherries, each cell usable once."
"What if diagonal moves aren't allowed, only up/down/left/right?"
"Can you reconstruct the actual paths, not just the max sum?"
"What's the time and space complexity, and can it be improved further?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview