I was asked this problem in a recent interview and I was not able to come up with the solution so asking for opinions from you all. This is not the exact problem, but the closest possible version of it (nevertheless, it'll help me solve the problem).

Problem statement:

You're given a 2D maze which has some cells blocked denoted by #, empty space denoted by . and exactly 1 exit denoted by E. There will be a rat in a maze which needs to reach the exit cell and it can move up, down, left and right from any cell.

Provide a sequence of moves for the rat so that it can reach the exit cell no matter what starting position of the rat be i.e. the starting point of the rat can be any empty space. While following this sequence, it the rat tries to move to a blocked cell, it will simply ignore that move and take the next move in the sequence. If the rat reaches the exit cell during this sequence of moves, it achieves its goal and will not need to follow the rest of the moves.

Note that all the edges of this maze are blocked, and the input is such that it's always possible to reach the exit cell from every empty space.

Example:

Input:

######
#.#E.#
#....#
######

Answer: Down -> Right -> Right -> Up -> Left

Explanation:

• If the rat starts at position (1, 1), it will go (1, 1) -> (2, 1) -> (2, 2) -> (2, 3) -> (2, 4) -> (1, 4) -> (1, 3) exit reached.

• If the rat starts at (2, 3), it will go (2, 3) -> (2, 3) down ignored -> (2, 4) -> (2, 4) right ignored -> (1, 4) -> (1, 3) exit reached.

Similarly, we can see that no matter what is the starting position of the rat, it will always reach the exit by following the sequence (and ignoring some moves if it's not possible).

What can be an optimal way to solve this problem? Can this be solved in polynomial time complexity?

TIA

I have questions about the following problems from one of the hiring tests of CodeNation:

Problem 1 : Given a tree, find number of subgraphs of the tree which have diameter equal to x. Print answer for all x. 1 <= x <= N. Constraints : 2 <= N <= 20

My question : Since N <= 20, can't we just try all possible sub graphs and find their diameters? I was thinking O(2^N * N) complexity should work with such small N? I also thought of some kind of a solution for a little larger N though.

Problem 2 : N men pick elements from a bag of N distinct elements. Each man pick a element one by one. If a man picks an element that is greater than all the previous picked element, then we say that this man is promoted. Each element is equi-probable to be picked. Find the expected value of promoted men. Print answer in pq^-1 mod M form. 1 <= N <= 1e5. N is the only given input.

For Example : if N = 2, then bag can contain (1, 2). All combinations are (1, 2) and (2, 1). In (1, 2) , 1 and 2 both get promoted. In (2, 1) , only 2 get promoted. Answer for N = 2 is hence 1*(1/2) + 2*(1/2) = 3/2

My question : How to approach and solve this problem? I feel like there are many ways to approach expected value problems and I got confused as to which direction to think in.