A programmer walks into a job interview and is asked to write the most efficient program to output the first five primes. The programmer spends three hours implementing the Sieve of Atkin, a GPGPU shader. “Not what we’re looking for,” says the interviewer, pointing at the exit door. “Why? What did you want?” asks the programmer. The interviewer holds up a printout reading “print 2, 3, 5, 7, 11”.
When a friend posted this joke on Facebook it garnered a quick succession of Likes. Ha ha, silly programmers, always too cerebral and abstract!
A few days later, around came the “When is Cheryl’s birthday?” meme. Cheryl tells Albert the month of her birthday and Bernard the date. She tells both a list of possibilities. Albert says, “I don’t know when Cheryl’s birthday is.” Bernard says, “At first I didn’t know when Cheryl’s birthday is, but now I know.” Albert replies, “Now I know, too.” (If you haven’t tried it, click through to the link above and work it out. I’d expect an SD Times reader to be able to solve in a minute or two.)
(Related: The modern panopticon)
Imagine an interview where the challenge was making a program that solves Cheryl’s birthday. How would you judge a candidate whose answer was “print {the_correct_date}”? Just as with the prime exercise, it’s mechanically transcribing a value that’s produced, in some unknown manner, inside the programmer’s head. Just as with the prime exercise, it will suffice only as long as the conditions are utterly static. Just as with the prime exercise, it is utterly unmaintainable. Is it really indicative of how you want your devs to work? I wish that the problem with hiring was “too much algorithmic knowledge and overeagerness to create maintainable, flexible and extensible solutions.”
The trick to Cheryl’s birthday is realizing that the statement “I don’t know” is the same as saying “I cannot reduce the list of candidates to a single entry.” This, in turn, can be used to eliminate proposed candidates that are non-ambiguous.
This is not the easiest logic to capture in most programming languages. The solution depends on alternating filters between ambiguous (“doesn’t know”) and non-ambiguous (“does know”) statements. This is hard to express in most languages. One approach involves a lot of duplicated code that imperatively applies the new knowledge. Another involves higher-order functions that are so abstract that I’m not sure the “why” is any clearer than a program that simply spits out the date. And while a program that solved Cheryl’s birthday would be more flexible in the face of different dates, a program that would be flexible in the face of a different set of ambiguities and resolutions would be, well, not the sort of assignment you’d give in a programming interview.
I know of one programming language where solving Cheryl’s birthday in programmatic form would be par for the course in a programming interview. John Feminella wrote a post showing how Prolog can determine Cheryl’s birthday in about 30 lines of code (including ample comments). Indeed, tougher variations of Cheryl’s birthday are common exercises for students of Prolog. Instead of choosing a date, the challenge is usually an integer that satisfies two or three or four constraints (“Albert knows the answer is even,” “Bernard knows that the digits in the answer add up to 7,” etc.) and the sequence of “I still don’t know” statements is long enough to thwart manual disambiguation. Prolog excels at solving such problems because it automatically searches the entire solution space for values that satisfy the constraints of the problem.
Prolog is among my very favorite programming languages, but it’s regrettably rare. Yet problems that are best expressed and solved using constraint and logic programming (such as Cheryl’s birthday) are, I would argue, not rare at all. It’s more that the mainstream has a blind spot for this powerful problem-solving tool. So, if a candidate started sketching out a solution using Prolog, Microsoft Solver Foundation or JaCoP, I think they would be demonstrating exactly the broad knowledge and clarity of thought we look for in devs. But according to my Facebook friends, the candidate might be showing a fondness for over-complicated solutions.
There is a weakness displayed by the First Five Primes test, though. Ask a few follow-up questions before starting to code. “Do you just want a fixed set of values or a flexible solution?” in the case of the primes and, regarding Cheryl, “Can we just wait until Facebook tells us it’s her birthday?”
