Problem porposal
Back to General discussions forum
Hey. So, I took a programming test for palantir, an IT company. There I was presented with a problem called Sick Travellers. I think it is exciting enought and hard enought to be on Code Abbey
The problem statement is as follows. You are given a list of people with their names, their condition (sick, recovering or healthy) and the list of cities they visited. It is assumed that people visit the same office at the same city.
the list is as follows:
John Sick NewYork Washington Seatle Chicago NewYork Chicago Chicago
Marie Healthy CityName CityName CityName
Bob Recovering CityName CityName CityName
If two or more people visit the same office the interaction between them is a follows.
If you are healthy and you are in contact with sick or recovering person you become sick. It takes one day to go from sick to recovering and from recovering to healthy, no matter who you are in contact with.
You are to present a list of names with the amount of days for each them to become healthy. if it takes more than 365 days to be healthy for a person you just write >365.
EX.
John 10
Marie >365
Bob 7
I hope admins can add this problem.
P.S I was give 75 min to solve this task, but I failed....
Hi there!
Thanks for bringing this to us - really at least problem statement looks funny :)
> I hope admins can add this problem.
Well, admin should first understand and solve it! Luckily I have more than 75 minutes...
Do I understand right (just clarifying the statement) that:
- traveller visits each city (from his/her list) for 1 day in a given order
- when list of cities ends, traveller restarts the list from beginning
- the day person "becomes healthy" is one after which he/she will never get sick anymore
Is this correct?
Seems there could be no more than 365 cities, though nothing is said about about maximal amount of people...
If I got it right, the problem is not top-difficult but it provides good challenge for implementation and optimization... For example I've just found some guy's solution on the web, written in "neat OOP style" but extremely ineffective as it checks each-for-each people on each day (though it is effective enough if there are many sick people)...
Hey. Thanks for your answer.
1. Traveller visits one city per day, However I remember some list of cities beeing longer than others. So
2. If the list ends the traveller stays there for the rest of the simulation, which no more than 365 days. So there is a possiblity of two or more travellers staying in on city and interacting with each other and never get healthy again.
3. Become healthy indeed means they never get sick again.
My idea was to track each city and see how travellers interact with each other there, but I didnt have time to implement it fully
If you have any more questions I would be happy to answer them
Thanks for this additional info!
It'll take some time (I think few days) for me to write and test some basic data generator for this task (as we want input data to be random but yet leading to non-trivial results) - so hopefullyl soon we shall see your problem here!
(I think that staying in the "final" city means that most of people will stay for the most time of 365 day period if the lists of cities are not long enough - so probably I'll prefer the idea with "looping" city lists - anyway this won't seriously affect solution)
Your idea seems to be correct, it is a form of "dynamic programming" - we should, day by day, mark cities as healthy or unhealthy. I think that putting people into three sets (healthy, sick and recovering) will help to mark cities in one pass on each day... I shall try myself :) Not sure there is a general way of speeding it further...