Cherry Pickup

HardDynamic Programming2d dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an n x n grid where 1 is a cherry, 0 is an empty cell and -1 is a thorn you cannot pass. Start at the top-left cell (0, 0), walk to the bottom-right cell (n-1, n-1) moving only **right or down**, then walk back to (0, 0) moving only **left or up**. Stepping on a cherry cell picks the cherry, and the cell becomes empty, so a cell visited on both trips counts only once. Return the maximum number of cherries you can collect. If there is no valid path from the top-left to the bottom-right, return 0. The start and end cells are never thorns.

Examples

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5
Go down, down, right, right to collect 4. On the way back take left, up, up, left, which picks the remaining cherry at (0,1), for 5 total.
Input: grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
Output: 0
Thorns block every route to the bottom-right corner, so the answer is 0.

Constraints

  • 1 <= n <= 50
  • `grid[i][j]` is -1, 0 or 1
  • `grid[0][0] != -1` and `grid[n-1][n-1] != -1`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More 2d dp problems