Coding: Dynamic Programming Problem

Interviewer

Given a grid with obstacles, find the number of unique paths from top-left to bottom-right. You can only move down or right. Obstacles are marked as 1, empty cells as 0.

Candidate

Let me think about this. We need to count paths, which suggests DP since the problem has overlapping subproblems. Define dp[i][j] = number of ways to reach cell (i, j). Base case: dp[0][0] = 1 if the start isn't an obstacle. For each cell, if it's not an obstacle: dp[i][j] = dp[i-1][j] + dp[i][j-1] (from top and left neighbors). If it is an obstacle, dp[i][j] = 0. We can optimize space by using a single row array. Initialize first row, then for each subsequent row, update left-to-right: dp[j] += dp[j-1] (if not obstacle, else set to 0).

Interviewer

What's the time and space complexity?

Candidate

Time: O(MxN) where M and N are grid dimensions. We visit each cell once. Space: O(N) with the single-row optimization, or O(MxN) for the full table. For a grid up to 100x100, either is fine.