SDE - 1

There is a N X N ‘GRID’ in which some cells are empty while others are blocked. Empty cells are denoted by ‘.’ and blocked cells by ‘#’. Initially, the ninja is standing at the bottom of the GRID.

Ninja can start at any one of the bottom empty cells. He can take steps either up or right, i.e., from the cell ( i, j ) to cell ( i - 1, j ) or ( i, j + 1 ). The ninja can not move outside the grid. Once he has taken a step towards right then, he cannot take steps in any other direction.

You need to calculate the number of ways he can reach the right end of the grid.

Note: Ninja can not pass through the blocked cells.

Example:

Input:

‘N’ = 3
‘GRID’ = [ # . .  ] [ # . . ] [ # . . ]

Following are the possible ways:

( 2, 1 ) => ( 2, 2 )
( 2, 1 ) => ( 1, 1 ) => ( 1, 2 )
( 2, 1 ) => ( 1, 1 ) => ( 0, 1 ) => ( 0, 2 )
( 2, 2 )
( 2, 2 ) => ( 1, 2 )
( 2, 2 ) => ( 1, 2 ) => ( 0, 2 )

Where ( i, j ) denotes the cell GRID [ i ] [ j ].

Difference between Multi-programming vs Multi-tasking vs Multi-processing

TCP vs UDP

Explain 4 pillars of OOPS - Inheritance, Polymorphism, Abstraction, and Encapsulation.

What is Thrashing

what are Ambiguity in multiple inheritances in c++

What is Virtual Memory

what is Multi-threading

Tell me about Yourself

Why do you want to join Samsung ?

Why should we hire you?