Number of Ways of Cutting a Pizza

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

A rectangular pizza is given as pizza, an array of equal-length strings where 'A' marks a cell with an apple and '.' an empty cell. You must cut it into exactly k pieces using k - 1 cuts. Each cut is made along a grid line of the **remaining** pizza. A horizontal cut hands the part above the line to someone and keeps the part below; a vertical cut hands the part left of the line to someone and keeps the part to the right. After the final cut, the remaining part is the last piece. Every piece handed out, including the last one, must contain **at least one apple**. Return the number of different cutting sequences modulo 1_000_000_007. Two sequences differ if some cut is at a different position or orientation.

Examples

Input: pizza = ["A..","AAA","..."], k = 3
Output: 3
Three sequences of two cuts leave every piece with an apple.
Input: pizza = ["A..","AA.","..."], k = 3
Output: 1
Only one sequence works.
Input: pizza = ["A..","A..","..."], k = 1
Output: 1
No cuts are made; the whole pizza has apples.

Constraints

  • 1 <= pizza.length, pizza[i].length <= 50
  • pizza[i] contains only 'A' and '.'
  • 1 <= k <= 10

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