Interview Question: Cars on a Road

by Mikael

The question was posed roughly like this:

Suppose there is a very long road. Suppose there is a sequence of cars, C1, C2, C3, … that each move with its own constant speed that is such that C1 is slower than C2 which is slower than C3, and so on. The cars enter the road in the same sequence (C1 then C2 etc.) but at random locations. They are not allowed to overtake each other, so if a faster car catches up to a slower one, the faster must reduce speed and fall in behind.

After some time, how many groups of cars will there be on the road?

Hint: Actually we can only calculate the expected number of groups since there is randomness involved. Even so… Some may get annoyed after considering this problem for a while. That is probably because there is still something undefined in it: What is the “time” we are talking about? What on earth is meant by “random” here?

If you are lucky you may be able to get a straight answer to this from your interviewer. However, there is also a considerable probability that he has either not understood the problem well himself, or is playing evil. But it is not so hard to figure out… The road is “very long”; that usually means we can pretend it is infinite. It is unlikely, however, that we want to get into tricky questions about math with infinities. Assume that there are N cars that all enter the road within some finite interval. It should be fairly obvious that after some (finite) time, the cars will have formed “groups” such that the first group is faster than the second which is faster than the third and so on (possibly there is only one group or groups with only one car).

If we don’t want to play with infinities, then obviously we can’t have the cars enter the infinite road at uniformly random locations. What is meant here is likely that the probability car Ci enters the road before C1 but behind whatever car is in front of C1, is the same as that of it entering before C2 and behind whatever car is in front of C2 at that time, irrespective of what the distances may be between the different cars at that precise time.

I think it would be prudent to check this point with the interviewer. One might try something else, but it seems unlikely that another set of assumptions would lead to an “interview time” solvable problem with a non-trivial answer.

Solution: Let C1 enter the road, now there is one group. Let C2 enter the road and a sufficiently long time pass; with probability 0.5 it entered before C1 and there will always be two groups. With probability 0.5 it entered behind and there is eventually only one group of cars once C2 catches up to C1. Continue like this: Let Ci enter the road – there is a probability of “1/i” that it enters in front of the first car, in which case the number of groups increase by 1. In all other cases Ci will eventually catch up with and join some other group.

I will not explain further but simply state as follows that:

After the n:th car has entered the road the expected number of groups is

E[ Gn ] = 1 + 1/2 + 1/3 + … + 1/n = H(n).

H(n) is called the Harmonic number, a fact that you probably don’t need to know. However with some possible feedback and coaxing from the interviewer I think it is not unreasonable to expect a good candidate to arrive at the summation of reciprocals.

This question appeals to me because it forces us to creatively inquire and make manageable assumption, a very important skill. Obviously the assumptions are very unrealistic in practice (if the objects are really cars), but remember the old maxim (George Pólya): If you can’t solve a problem, then there is an easier problem you can solve: find it.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: