Interview Question

Junior Trader Interview

-

Jane Street

During the third interview : imagine an infinite chess board. If the horse from 1 case, in how many cases can he possibly ends after 10 moves. You actually don't have to give a number but a 95% confidence interval. pen and paper allowed

AnswerAdd Tags

Interview Answers

12 Answers

13

The answer is actually 741. I probably wouldn't have thought of this super quickly during an interview, but just think about it this way: in 10 moves, the most the knight can move to the right (or to the left) is 20 spaces. So you are confined to a 41-by-41 box of spaces. Now just label each column (or row if you'd prefer, as this is obviously symmetric) 0-40 (so the knight begins on the center square of column 20). Then just ask yourself....how many spaces in column 0 can the knight land on in 10 moves? How about column 1? And so on. If you think of it this way the answer will become clear. To "candidate" I suspect you are solving the wrong problem. If you're looking at possible paths that a knight might take then maybe I'd believe your answer. But for spaces to land on this is definitely wrong. By the way, since this is only a confidence interval, my friend had a very good way of estimating this. Each knight moves along the diagonal of a triangle with legs 1 and 2; in other words, the knight moves sqrt{5} away from the center with each move. So the spaces that the knight could land on would be roughly inside a circle of radius 10sqrt{5}, which has area about 1500. But the knight can only land on half of those squares because in an even number of moves he must land on a square that's the same color as the square he started on. So your estimate would be 750, so take some reasonable interval around 750.

wlfgngpck on

2

no my bad, the can be reached 741 is correct, it's just in the case 2 that you have to substract these diagonals...

guest on

2

751

Anonymous on

2

Solution visualised : http://twitpic.com/9jegtb

aldwinaldwin on

2

Formula (no idea why, but it works) x=amount of steps (square(1+4*x) + 1) / 2 - square(4*x) / 16 Range as square : ( 2x + 1 + 2x ) * (2x + 1 + 2x) = 41*41 = 1681 Add centerpoint : + 1 / 1682 Only half of the fields will be posible : / 2 = 841 Corners are not reachable, 1/8th of each direction without center lines : ( 2x*2x / 2 ) /8 = 100 Result 841-100=741

aldwinaldwin on

1

sorry I meant to write that he can't reach (14;14), of course he can reach (19;9)

guest on

1

so my answer would be 741-4=737 cause he cant reach (14;14), (14;-14)and (-14,14) (-14;-14)

guest on

0

Don't really understand the question... the horse from 1 case? and whats the intuition of the answer given?

total on

0

«wlfgngpck» I did it the way you said by giving half the area of the circus of radius 10*sqrt(5) so 750 is not bad for a true answer of 741 (or 751 I don't remember)

Anonymous on

1

he can get to 20 spaces in all 4 directions. thats 41x41 = 1681. he cannot reach the corners which are composed of 10 + 9 + 8...+2+1 boxes = 55. so four corners are 220 boxes. that leaves him at 1461. subtract one for the one he is on currently -> 1460 and divide by 2 bc he cant land on the opposite color from where he started. answer is 731

md on

0

741 is too big, if the knight is at (0;0) can get to (20;10) in 10 moves but not to (19;9) in 10 moves...try it out with 2 moves...it's not 37 cases but only 33 because he can't get to (2;2) (-2;-2) (-2;2) (2;-2) in 2 moves...

guest on

0

I think it's much more than 751. I found 7938126 cases, and there are more.

candidate on

Add Answers or Comments

To comment on this, Sign In or Sign Up.