A friend was asked the following riddle in a Google interview yesterday. I found it quite interesting. If you have the right background it is trivial, however, if you do not then it can be rather tricky. Feel free to post a solution.
An enemy submarine is somewhere on the number line (consider only integers for this problem). It is moving at some rate (again, integral units per minute). You know neither its position nor its velocity.
You can launch a torpedo each minute at any integer on the number line. If the the submarine is there, you hit it and it sinks. You have all the time and torpedoes you want. You must sink this enemy sub - devise a strategy that is guaranteed to eventually hit the enemy sub.
Note: This was copied from here. That page contains at least one other questions I was asked in my interviews with Google.
Posts
But this is trivial!
ReplyDeleteThe enemy submarine is at at+k where t is a known integer (time), k is the initial location and a is the rate of movement.
ReplyDeleteLaunch torpedoes at positions at+k in this order:
[a=1, k=0]
[a=2, k=0]
[a=1, k=-1]
[a=1, k=+1]
[a=2, k=-1]
[a=2, k=+1]
[a=3, k=0]
[a=1, k=-2]
[a=1, k=+2]
[a=2, k=-2]
[a=2, k=+2]
[a=3, k=+1]
[a=3, k=-1]
[a=4, k=0]
etc, etc.
In other words after incrementing a, go back and test an extra k value on each side for all preceding a values.
You will eventually hit the correct value of a and k. Since t is known, when you compute the position of the sub using at+k, you'll hit it.
No? Tricky since I do not have a naval/military background.