Walmart Labs Interview Question
Country: India
I told the similar solution but then he said at the end the sum of all probabilities will become > 1 . So i suggested that as the next move is different experiment so according to theory of probability it should be multiple of p(n,x,y)x p(n-1 , x' ,y').
@tomb: That's because you probably didn't divide by 8.
I balked at the O(N) analysis at first, but if we assume the chessboard to always be 8x8 (O(1) in size), then yes. If the board were AxB, we'd need O(N*A*B) time with this algorithm. This is also assuming we can discard the horse after it leaves the board. That's what I would think too, but I would confirm with the interviewer that the horse can't get back on the board by subsequent moves - otherwise, we'd have to simulate the horse off the board and our virtual board wouldn't have size O(1)!
i think the solution is to do a dfs from the x,y node and keep a counter passed to the parameters that should be incremented each new call in the dfs, and whenever this counter is N we will increment the size of the sample space, and if that node is inside the board increment counter M.
then the result will be M / size of sample space
code:
int sample_space = 0;
int m = 0;
void dfs( node , counter)
{
if(counter == N)
{
sample_space ++;
if( inside_board[node])
m ++;
return;
}
if(!visisted[node])
{
visited[node] = true;
for all adjacent nodes
if(!vis[adj])
{
dfs(adj, counter +1);
}
}
}
P(horse stays on the chess board) = 1 - P(horse moves out of the board).
Now, calculating the probability that the horse moves out of the board is simple. With every move, the horse's position (x,y) increases by 1 or 2 with equal probability (i.e., x becomes x+1 or x+2 with equal probability) or decreases by 1 or 2. Same story for y.
Now, we need to calculate the probabilities that after n moves, horse progresses (8-x) steps in positive x-direction and x steps in negative x-direction and add them up to get the desired probability.
Calculation of progress after n steps of the horse can be done using random walk on a line (see en.wikipedia.org/wiki/Random_walk#One-dimensional_random_walk). I can't remember the details but you may have to calculate the expectation of progress and then use markov's inequality to calculate the position after n steps.
Let next(x, y) be the set of possible next positions starting from (x, y), i.e. next(x, y) = {(x+2, y+1), (x+1, y+2), ...}. The base case is P[0, x, y] = 1 for x and y between 0 and 8. For all n, P[n, x, y] = 0 when either x or y are outside 0 and 8. For n > 0, P[n, x, y] is the sum over P[n-1, x', y'] for all (x', y') in next(x, y), divided by the size of next(x, y) (which is 8).
- psykotic February 16, 2012This algorithm requires O(1) space and O(n) time.