Walmart Labs Interview Question


Country: India




Comment hidden because of low score. Click to expand.
1
of 1 vote

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).

This algorithm requires O(1) space and O(n) time.

- psykotic February 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 February 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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)!

- eugene.yarovoi February 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
                    }
      }
}

- hitman February 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not good what if two different paths lead to the same cell

- Anonymous February 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous July 03, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More