Interviewstreet | Zombie March
<p>I am trying to solve below problem.</p>

<p>Zombies have placed themselves at every junction in a city. Each junction 'i' initially has a presence of a(i) number of zombies. At every timestep each zombie randomly chooses one of its neighboring junctions and walks towards it. Each neighboring junction is choosen by the zombie with an equal probability. In order to safegaurd the citizens of the city we need to find out the No of zombies in the Top 5 highly populated junctions after 'k' timesteps.</p>

<p>After a lot of thinking following two methods come to my mind.</p>

<p><strong>Method 1</strong> : First method is by keeping track the number of zombies at each junction after every timestamp.But implementing this looks impossible to me as junction can have n number of zombies and m number of neighbours at a time 't'.So for time 't+1' total number of zombies gone out of that junction is possible in n^m ways and also number of zombies coming in the junction from neighbours can be anything from 0 to m .I don't know how will I be able to keep track each zombie.</p>

<p><strong>Method 2</strong> : Second method is by considering each zombie at a time.Starting from first junction,if I start with first zombie.It is possible to calculate the total number of paths and all the final positions of a zombie after k timestamps .Doing the same thing for all the zombies .This sounds simple.But the thing is that in the end I will have to map each position of a zombie with every other zombie so that I get some x arrays where each array would represent the status of total number of zombies at each junction.But according to the question I have to find out the No of zombies in the Top 5 highly populated junctions after 'k' timesteps. It looks like there is only one way but I would end up with some x arrays.</p>

<p>Please suggest If there is any other approach that would help.</p>

<p>Source :https://www.interviewstreet.com/challenges/dashboard/#problem/4ff1484963063</p>
