5
$\begingroup$

This is an interview question I was asked, which I don't know how to approach. I would appreciate pointers to algorithms I should look up.

You are placed on the real line, and there also are $K$ lions on the real line, which are currently sleeping. You are given the wake up time of each lion. You can walk past a lion as long as it is sleeping. As soon as any lion wakes up, it starts walking towards you to eat you. Both you and the lions can walk at a maximum speed of 1m/s.

Given your starting position and the starting positions and wake up times of the lions, find the maximum time you can stay alive (can be infinite), and the strategy you should follow.

$\endgroup$
  • $\begingroup$ How slow the lions are! $\endgroup$ – xskxzr Nov 18 '18 at 5:55
  • 1
    $\begingroup$ I'm fairly sure that this is a question for the purpose of observing you tinker, not for seeing how many solutions you know by heart. $\endgroup$ – Raphael Nov 18 '18 at 11:33
  • $\begingroup$ Based on gnasher729's answer, I believe that a cleaner solution should be "move to some point $X$ and wait there until you are hit by two lions from different directions". What is the actual (fast) algorithm to find $X$? $\endgroup$ – Apass.Jack Nov 19 '18 at 6:01
2
$\begingroup$

Assume you start at zero. Lion #i is at $d_i$ and wakes up at $w_i$. If there is no lion with $d_i > 0$ and $w_i < d_i$ then you walk to the right and are safe. If there is no lion with $d_i < 0$ and $w_i < |d_i|$ then you walk to the left and are safe.

Otherwise, you die. There is always an optimal strategy of the form "move to some point X and stop, then wait until lions force you to move, and die when two lions from either side meet" - the point X is obviously not known. The point X is limited; if for example $d_i > 0$ and $w_i < d_i$ then you can walk only $(d_i + w_i)/2$ before you are forced back.

Just check the points X that are just before a sleeping lion, or just before one of the two points where you are forced back. For each of these points X, calculate at which time you will die, and pick the best one.

(To make this easier to visualise: If all lions wake up at the same time, and you can't escape, then you want to be within the largest gap between two lions that you can reach, at the moment they wake up. So the point to move to could be anywhere, depending on where the lions are).

$\endgroup$
  • $\begingroup$ Could you please elaborate or give a formal proof why the strategy is optimal? $\endgroup$ – xskxzr Nov 18 '18 at 6:08
  • $\begingroup$ Left as an exercise to the reader :-) $\endgroup$ – gnasher729 Nov 18 '18 at 14:21
  • $\begingroup$ But ask yourself whether you can improve your lifetime by walking slowly, or by walking / stopping / walking instead of just walking. $\endgroup$ – gnasher729 Nov 18 '18 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.