Given zombies walking in left or right direction indicated by -1 and +1, find the last zombie to die if they walk towards the left and right edges respectively. When a left zombie meets with a right zombie, they change their directions only.
EXPLANATION:
Count the number of zombies walking towards the left and let it be count_left. N- count_left gives the number of zombies walking towards right, that is count_right.
Whenever the zombies reach the ends, they’ll die. Counting the number of left and right zombies helps to eliminate the one on the left and one on the right simultaneously. Subtracting the total number of zombies by the larger count value gives the index of the required zombie.
If count_left < count_right , N+1 -count_right gives the index of the last zombie to die.
Else , N+1 -count_left gives the index of last zombie to die.
I thought briefly about modelling this, but coded it just using the count of “-1” zombies, which agreed with the test cases.
However I was curious about the state of the tunnel is when there are multiple consecutive zombies heading one way after the lead zombie collides. Using the given test case of
1 1 -1 1 1 1 -1 1
at time t=0, I made a little illustration using > for 1 and < for -1 with X indicating a collision in progress:
(of course some collisions happen on the half-second, not shown). What’s striking here is that the last zombie to die is at the low end or high end depending on the original walking directions at the other end of the tunnel.
This should mean that the answer for
-1 1 1 1 1 1 1 -1
should be 2, since the last zombie to die comes out of the low end:
Actually at first I had written code with the same exact algorithm as you did. This was a question given to me to solve in one of my interviews. The interviewer told me that he didn’t mention time so he told me to move the zombies after there are no collisions at all. Actually saying the question needs a clarity about the time.If possible just help me to add a sentence or two, to make the question more reasonable. As people won’t understand it untill they see the sample input-output. Thank you in advance.
I haven’t yet satisfied myself that it is always correct, but yes, “Zombies will run immediately to the end of the tunnel once they can see it” seems to fix things up in a lot of cases. It makes the question a little bit harder to read perhaps. Maybe there’s another way.
