(This is the continuation of an article about the use and abuse of brainteasers in job interviews. This page contains the second of three examples drawn from actual interviews.)
The problem, as posed, reiterated:
A wheel is painted half black and half white. You can place two
stationary sensors anywhere on the surface of the wheel. The sensors tell you what color they see. How can you tell which way the wheel is spinning? And how long does it take before you know?
I actually think that, properly used, this could be a good question in an interview. It's very open-ended, but it doesn't completely defy solution. However, what follows is a story about an interviewer thinking he understood the problem more completely than he did and a candidate who didn't quickly intuit what the interviewer wanted.
The candidate started out by asking When you say 'half white and
half black', can I assume it's divided in half by a single straight line
that runs through the center and that the center of the disk is the point
around which it rotates?
The candidate's
question was reasonable, if a bit pedantic;
the answer, of course, was
Yes.
Next the candidate observed, and the interviewer agreed, that it didn't matter how far from the center you placed the sensors: a sensor along any given radius of the wheel would observe the same color as at any other point along that radius, and one on the opposite side of the same diameter would always detect the opposite color, providing no additional information. This, in turn, led to the (correct) conclusion that the sensors have to be placed on two different diameters of the wheel, since on any single diameter all you'll get is an alternation of equal amounts of black and white, which gives you no clue at all which way the wheel is spinning.
So far so good. Then came the disjunction. The candidate asked,
What's the sampling rate?
The interviewer said, I
don't know, why?
The candidate said, Because without
knowing something about a sampling rate we're going to have an aliasing
problem here.
Interviewer: An aliasing problem?
Candidate: Yeah, like when a wheel spinning really fast seems
to be going the other way?
Interviewer: Hmmm, I don't know, pick a sampling
rate.
Candidate: Well is there any upper bound on the angular
velocity of the wheel?
Interviewer: I don't know, I don't think so.
Candidate: Because my intuition tells me that without an
upper bound on that you just can't get rid of the aliasing
effect.
As it happens, the candidate's intuition was right: any set of observations can be explained by an aliasing effect and a sufficiently high speed of rotation. Without an upper bound on the angular velocity of the wheel, the problem cannot actually be solved. Unsurprisingly, in the pressured situation of a job interview, and with additional other questions coming at him, the candidate did not get close to a proof of this. All he had was his intuition, which was not shared by the interviewer.
The mismatch here is an interesting one, and a really good interviewer could have used this very positively: he or she would have learned that the candidate had a certain intuitions about actual physical systems and was immediately considering the actual mechanics of the sensory apparatus that would be necessary for actual computer algorithms, which always need to deal with a discrete sampling rate. Meanwhile, the interviewer was focused on a very abstract level of the problem, probably imagining some kind of idealized continuous sampling (which doesn't exist in nature). In fact, this is a pair of people who might have complemented eash other's skills very well, except that in this artificial, high-pressure situation, they never discovered it.
So, assuming again that you have some affection for brainteasers, let's assume a constant speed of rotation, let's assume a high enough sampling rate (let's not even push the limit: assume at least eight samples per rotation of the wheel). Where do you ideally want to put the sensors? How many samples do you have to take before you know which way the wheel is spinning?
Solution >>>Copyleft: With appropriate notification and appropriate credit, non-commercial reproduction is welcome: contact me if you have any desire to reproduce these materials in whole or in part.
My e-mail address is jmabel@joemabel.com. Normally, I check this at least every 48 hours, more often during the working week.