Microsoft Interview Question: Probability of a knight makin... | Glassdoor.co.in

Interview Question

Senior Software Development Engineer Interview Hyderabad

Probability of a knight making a valid move on NxN matrix

  in m steps.
Answer

Interview Answer

4 Answers

0

Guess what , I got almost the same question on my first interview with Google , and I was applying as a new college grad ....i also can up with a DP solution with O(64m) ....
btw can you provide the link to the solution you came across ...??

mohan on 21-Feb-2012
0

@mohan: I don't have a link to solution, its something I worked out on a piece of paper.

vijay on 22-Feb-2012
2

Buddy,
I think you thinking a bit too complicatedly.
A knight on a chess board only has 8 legal moves. and if it is anywhere closer than being atleast 2 boxes from the border it will be less than 8. just take a input of all the pieces on the NxN matrix. check these 8 positions and calculate the probability

Aditya on 09-Jun-2012

One or more comments have been removed.
Please see our Community Guidelines or Terms of Service for more information.

Add Answers or Comments

To comment on this, Sign In or Sign Up.