I received this problem at virtual on-campus interview for Sprinklr for a Product Engineer Intern position. We spent about 20 mins. on this problem(2 questions in 45 mins. interview).

Given an n*m matrix consisting of 1s and 0s. Give total number of paths traveling from (0,0) to (n-1,m-1). You can only go in right or down direction and can only travel on cells marked 1. A vector of points showing coordinates of cells marked 0 will be given.

Constraints:

1<= n,m <= 10^5 (impossible to travel the matrix)

1<= number of cells marked 0 <= 2000

Example:
Input: n=2, m=2, 0_cell_array = []
Output: 2

Input: n=2, m=2, 0_cell_array = [[0,1]]
Output: 1

Input: n=3, m=3, 0_cell_array = [[0,2],[1,2],[2,0]]
Output: 2

I could only come up with naive brute force backtracking solution then optimizing it to standard DP one but as the size is large even DP solution wasn't acceptable. The required solution had something to do with combinatorics and that is all I could come up with at that time. Any ideas/suggestions/help will be appreciated.