## Deshaw Inc Interview Question for Analysts

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

``````Here is position to catch the robber

The position in which both the cops are in the diagonally opposite position.

A------B
|\    /|
| E--F |
| |  | |
| G--H |
|/    \|
C------D

If the cops are at the position C & F then they can easily catch the robber.``````

Comment hidden because of low score. Click to expand.
0

but you have not thought about putting the robber. You cannt fit the robber here as there is no location(edge) "inside" this square.

Comment hidden because of low score. Click to expand.
0

I guess this solution works, as Each cop cover 3 different planes. Hence covering the cube entirely.

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

simple and nice answer -> Ashutosh :)

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

Not possible..

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

I think so too. The cops may never be able to catch the robber, as a long as the robber always makes the right move.

The reason, I think, is because of the 3-dimensionality. At the start, all that the robber has to do is to sit and wait at a vertex. As the 2 cops approach 2 of the adjacent corners, the robber should run in the direction of the 3rd edge. There on it shouldn't be aproblem to keep avoiding the cops.

Comment hidden because of low score. Click to expand.
0

That's a dumb strategy for the cops.

``````A------B
|\    /|
| E--F |
| |  | |
| G--H |
|/    \|
C------D``````

Suppose for the moment that the robber is at A and the cops are at D, not H. Working alone Cop #1 can confine the robber to A, E, and the interiors of their incident edges by moving in direction (-dx,-dy,dz) when the robber moves in direction (dx,dy,dz). Since the robber is confined to a tree, Cop #2 easily catches him (this is a topological thing: Cop #2 still wins even if he's been eating donuts and is much, much slower than the robber).

Now, in the actual problem, the cops start at H. Cop #1 should stay at H and Cop #2 should chase the robber. If the robber ever arrives at B, C, or E, Cop #1 begins the previous strategy and is caught. Therefore, the robber is in effect confined to A and its incident edges, which form a tree, so Cop #2 can once again catch him if he does not make a move.

tl;dr: Cops win, even if one of them has been eating donuts and runs arbitrarily slowly.

Comment hidden because of low score. Click to expand.
0

D'oh, that's not the right direction for Cop #1.

``````A---B
|   |
|   |
C---D``````

Put A at (0,0,z) and D at (1,1,z). Cop #1 should move in direction (-dy,-dx,dz).

Comment hidden because of low score. Click to expand.
0

Really??? you mean to say one can catch the robber....I don't think so robber will always have three direction to go to. As every one can see the move of every other one, there is no way two cops can catch the robber....... What ever strategy you apply...cops can never catch the robber.

Comment hidden because of low score. Click to expand.
0

That's my point: one cop running at the same speed as the robber can effectively take away two directions.

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

Its always possible, because one cop can stay at his place, and another can stop. Now the robber has to move and any step brings him one step closer to the stopping cop.

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

i think its not possible. Suppose we are having a robber at some edge say (x,y). There will be four escape edges for him. 2 cops can cover just all scenarios of 2 escape edges. Thus they cannt catch the robber.

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

there are several cases possible with Ashutosh answer
it depends if robber starts moving after watching cops direction (diff cases for 1 and 2 cops) or if 1st robber moves...

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

It is not possible to catch him for the specific reason.

Each Edge has 3 different paths
Cops can only block 2 paths
There is a possibility that the cops are never able to catch the thief.

Even if the cops are at the 2 opposite of the cube, thus for sure having 1 cops next to the thief, he would need to move on the thief position.
While he does that move, he walk using 1 path, the thief have 2 paths open to escape during that move...
Knowing that there is 3 paths all the time, it is impossible to catch him.
Unless you claim the movement aren't simultaneous but a turn by turn approach, then you can catch him easily, just get the 2 cops at the 2 opposite point of the cube and you catch him in 1 turn. But it shouldn't be like that from the way the question was initially stated.

Comment hidden because of low score. Click to expand.
0

u are right.

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

A---------B
| \ / |
| E----F |
| | | |
| G----H |
| / \ |
C---------D

If initially 1st cop is at E, 2nd cop at H and the robber at C, the robber will definately be caught by any 1 of the cops.
Explntn:
If the robber runs toward A, 1st cop will also run towards A.
If the robber runs toward D, 2nd cop will also run towards D.
If the robber runs toward G, both the cops (or any 1) will run towards G.
If the robber changes the direction mid way and runs in the oppst dirctn, the cops also will go back.

Comment hidden because of low score. Click to expand.
0

Consider the above diagrams in case this one's is not clear.

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.

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