Google Interview Question DSA Sept 2022

Problem:

Students are laid out in a grid of desks in the classroom. They want to pass notes to each other but the teacher doesn’t want them to.

The closer to the teacher they are, the higher their chances of getting caught are. The first row has a 90% chance of getting caught when passing notes horizontally.

Passing a note horizontally is much more likely for them to be caught than passing vertically.

The first row has a 50% chance of being caught when passing the note to the row behind them. With each subsequent row, the risk is halved.

// (0, 0) (0, 1) -> 0.9

// (0, 0) (0, 1) (0, 2) -> ??

/*

A B C D

E F G H

A -> B -> C -> G

(0, 0) -> (0, 1) -> (0, 2) -> (1, 2)

*/

Find the solution and comment below

Thanks