Now, with New Coronavirus situation, this problem gives interesting epidemic simulation!

There is Palantir Technologies and one of our fellows had been interviewed there (for internship or junior developer position, I assume). He retold me this problem, as a curiosity, proposed to him at interview and suggested to add it as another task at CodeAbbey. After some googling I found the problem is known to some extent, so I did as suggested.

Here is the link to problem at CodeAbbey

Supposedly it may take from 30 minutes to 2 hours. But if you'll try solving it - please, share your experience!

Problem Statement

1. There is some quantity of cities and some quantity of travelers.
2. Every traveler has schedule to visit several cities in certain order, staying 1 day in each (and travelling speedily by night). When schedule ends, traveler just starts again.
3. Each traveler can be healthy, sick or recovering.
4. One who is sick will become recovering next day.
5. One who is recovering will become healthy next day.
6. One who is healthy will become sick next day if today he/she is in the city with someone sick or recovering (i.e. contagious).

For example look at the picture above. There are two persons and 4 cities. The time is increasing by days from left to right. One person travels between cities A and B (and is marked by blue lines). Another travels according to C-B-D schedule (purple lines).

The first (blue) is sick initially (let's call it day-1) - this is marked by red color. He/she moves to B on the day-2 and meets second (purple) here. Blue is recovering (pink) on the day-2, but some of his viruses land on Purple. Thanks to this, Purple becomes sick on day-3 when reaching city D.

Luckily in this example people density is small and both are soon healthy (green) for good. Epidemic doesn't happen.

The task is to simulate this for hundred days or while all become healthy. But we can invent more interesting questions. E.g. to figure out what people density leads to epidemic on average. Or even detect loop in situation change sequence over many days.

Problem seems to be pretty straightforward, not about some whimsical algorithm, but rather good coding exercise - to write it neatly, choose suitable data structures etc.