Tech Interview

Treasure Island

You find an old treasure map in your grandma’s attic. the map shows a cannon, a coconut tree, and a palm tree. the map states that to find the treasure you must:

a. start at the cannon, walk toward the palm tree while counting your paces. when you reach the palm tree, turn 90 degrees to your left and walk the same number of paces. mark that spot on the ground with a stake.

b. start at the cannon again, walk toward the coconut tree while counting your steps. when you reach the coconut tree, turn 90 degrees to your right and walk the same number of paces. mark that spot on the ground with a stake.

c. find the midpoint between the two stakes and dig for the treasure.

you set off in secrecy to the deserted island. upon reaching the shore you site the coconut tree and the palm tree, but someone has removed the cannon. without digging randomly all over the island, is it still possible to find the treasure?

Solution

this just takes basic geometry skills. when we get to the island all we see are the coconut and palm trees. so lets lay out our coordinate system such that the palm tree is at (0,0) and the coconut tree is at (1,0). it honestly doesn’t matter how you describe the coordinate system – you could say the coconut is at (c,0) if you like, or even (0,c) or (0,1). we are just placing our own coordinate system on top of the existing surface. if you use a different system, you will get a different numerical answer but the same positional answer in the real world.

Here is our island. the cannon is at (x,y) because we have no idea where it is, so x and y are the unknowns. (note the cannon doesn’t have to be in the upper right quadrant but it won’t make a difference in the solution because x and y could be negative if we want them to be).

if we walk to the palm and turn right we can easily see the way it lays out in the diagram. you basically have just transposed the x and y positions.

it might be easier to think of it as a triangle, and flipping the triangle around to find the point for the next stake at (y, -x)

we do the same thing with the coconut tree, although here its only a tiny bit trickier because we have to factor in the position of the coconut tree at (1,0) or (c,0).

we use the idea of a triangle to help us better understand that the stake will end up at (1-y, x+1) or (c-y, x+c).

then to find the midpoint of the two points which is just the first position + the second position divided by two.

(y, -x) and (1-y, x+1)
((y - y + 1)/2, (x - x + 1)/2)
(1/2, 1/2)

hence our answer is (1/2,1/2) – although we’ll see that if we had use the constant C for the coconut tree we would have ended up with (c/2, c/2). this is important because even though we laid out the island in our own coordinate system, its not always the case that c must be positive. i think (and i’ve seen this solution elsewhere, but can’t really come up with a repro, so let me know if i’m wrong here) there really are two places the treasure could be because c could also be negative. so if we use our first answer of (1/2,1/2) we must also search at (-1/2, -1/2). if the cannon was in the lower half of the coordinate system you can see that the treasure would actually be in that quadrant also.

Exit mobile version