Microsoft Interview Question
Web:
www.microsoft.com
|
HQ:
Redmond, WA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,056 Interview Reviews |
Back to all Microsoft Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Engineer at Microsoft:
Apr 29, 2009
How many unique paths are there from B-L point to the T-R point of a chess table? What would be your approach to calculate this?
| Tags: | recursive algorithm, chess See more , See less 8 |
Add Tags
[?]
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (6)
May 5, 2009
No it wouldn't. The question asks how many unique paths there are, not how many unique paths a certain piece can make. Also, I think we must assume the unstated rule that a given square may only be crossed in a given path once - otherwise the answer is infinity!
Helpful Answer?
Yes |
No
Inappropriate?
Sep 16, 2009
@NCLrry: If you can only move up and right, but not left or down, then there are fewer paths and that is usually how I have seen this puzzle worded.
Helpful Answer?
Yes |
No
Inappropriate?
0 of 2 people found this helpful
Nov 3, 2009
Use dynamic programming.
Helpful Answer?
Yes |
No
Inappropriate?
0 of 3 people found this helpful
Nov 4, 2009
3432
Helpful Answer?
Yes |
No
Inappropriate?
1 of 1 people found this helpful
Oct 11, 2010
If only allow moving in vertical or horizontal direction:
f(x, y) = f(x-1, y) + f(x, y-1); where f(1,1) = 1
f(8,8) = 3432
If allow moving in vertical or horizontal or diagonal direction:
f(x, y) = f(x-1, y) + f(x, y-1) + f(x-1, y-1); where f(1,1) = 1
f(8,8) = 48639
f(x, y) = f(x-1, y) + f(x, y-1); where f(1,1) = 1
f(8,8) = 3432
If allow moving in vertical or horizontal or diagonal direction:
f(x, y) = f(x-1, y) + f(x, y-1) + f(x-1, y-1); where f(1,1) = 1
f(8,8) = 48639
Helpful Answer?
Yes |
No
Inappropriate?
Members can
answer or comment on this question
–
Join Now (It's Free) or
Sign In
You might also be interested in: Interview Questions, Software Engineer Interview Questions, Microsoft Interview
0 of 2 people found this helpful
by B.P.: