Fibonacci Fail

The Non-Programming Programmer

(A meeting room somewhere in a giant office building. Early afternoon. Four people sitting around a table. It’s a typical job interview scene. On the table are coffee cups, a glass of water, pen and paper, a laptop.)

Co-worker: “Talking about Java, let’s start with something easy. What’s the difference between an interface and an abstract class?”
Candidate: “…”
Me: “Ok, let’s forget about the interface for now. What is an abstract class?”
Candidate: “…”
Me: “Ok, back to Java 101. Let’s assume we want to model a zoo. Would you use an abstract class to implement a lion?”
Candidate: “…I…guess…not…”
Me: “Thank you very much.” (start playing with my mobile phone)

Unfortunately, this is not an excerpt from a comedic play written to entertain the holy caste of software developers. This has actually happened less than a week ago. Repeat after me: “This actually happened.”

Last year I stumbled across Jeff Atwood’s blog post The Non-Programming Programmer. Which led to Why Can’t Programmers… Program? Which then led to Reginald Braithwaite’s Don’t Overthink FizzBuzz. All these posts fit in nicely with basically all the stuff Steve Yegge wrote about hiring as part of his Drunken Blog Rants.

Mr. Braithwaite’s conclusion:

I’ve come to discover that people who struggle to code don’t just struggle on big problems, or even smallish problems (i.e. write a implementation of a linked list). They struggle with tiny problems.

And even worse:

Like me, the author is having trouble with the fact that 199 out of 200 applicants for every programming job can’t write code at all. I repeat: they can’t write any code whatsoever.

Based on my recent experience I totally have to agree.

When I first read all that stuff about FizzBuzz, I assumed that this must be more or less just a bad joke. Or that it might apply to a specific job market. I would have never guessed what I was about to experience once we included a little exercise into our hiring process.

To be able to better compare applicants we restructured or interviewing process. Less chatter, more content. Identical questions for everybody, not too heavy. A little bit about object oriented programming, JPA, estimation techniques, testing and little coding challenge using pen and paper. Even pseudo code is fine.

Fibonacci Sequence

The coding challenge we are using is to make the candidate write a little function that returns a Fibonacci number.

Co-worker: “Have you heard of the Fibonacci sequence?”
Candidate: “…”
Co-worker: “Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 0 and 1, the first 10 terms will be: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. Could you please use the whiteboard and a pen to “implement” a function that prints out the n-th number of that sequence.
Candidate: “…”
Co-worker: “Feel free to use recursion.”

The Fibonacci numbers are actually part of a Project Euler problem that asks for the sum of the even-valued terms in a sequence whose values do not exceed four million. Give it a try.

So, what do we actually expect?

An iterative approach

Candidate: “Let’s see…I need a function. What about this? return 0 for now. Otherwise it won’t compile (bonus point).

screenshot_52.png

I assume that using int is fine for now. For the return value as well as for the parameter. OK? (Feedback loop, bonus point.)

So, what shall happen in case we call compute(0) or compute(1)? You said the first two numbers, 0 and 1, are always given?

screenshot_51.png

Hmm, what about compute(-1)? Is this defined? Let’s change this (bonus point again).

screenshot_53.png

Now I need to implement the actual algorithm. Let me introduce two variables here, a and b. Far from perfect variable names, but for now a and b should be sufficient.

screenshot_55.png

I need to loop…n <= 0 and n == 1 is taken care of. What about n == 2 and above?

screenshot_57.png

 I need the sum of a and b

screenshot_58.png

But I am not done yet…What do I want to return instead of 0? And I need to store my sum…Let’s store the sum in b…and return b

screenshot_59.png

Still not done…sum = 0 + 1 = 1b becomes 1…next iteration I need 1 + 1 = 2…and then 1 + 2 = 3 and then 2 + 3 = 5…give me a second here…what about…

screenshot_60.png
This should do the trick…Let me do a quick check…for n = 3…………………no, I guess I am done…that’s it.”

Me: (Tears of joy are running down my face.)

What about recursion?

Candidate: “You said I can use recursion if I want to? (Candidate to herself: “There must be a simple recursive way to do this…otherwise they wouldn’t have asked me.”). Let’s see…”

To speed things up, I skip the part up to the actual implementation. The if-else part remains identical.

screenshot_53.png

Bonus points if the candidate mentions that recursion needs to terminate. This is guaranteed by the if-statements already.

Candidate: “I need to compute(n), which basically is compute(n – 2) + compute(n – 1). So, what about this one?”

screenshot_61.png

Now we are talking. What’s the difference between the iterative approach and the recursive one in regards to speed? What about memory consumption?

Reality check

It took all our applicants ages to implement a function based on the given input. We’ve seen a lot of implementations that did not work at all. Did some candidates realize their code is not working? No, far from.

Only one candidate went for the recursive solution and he literally had to be carried across the finish line.

Conclusion

I put this exercise up on my Facebook page to ask my developer friends for their input. Replies and coding challenges came up all night between different time zones.

Here are my favorite replies from a friend working for Google:

There is a roughly correct solution in constant time. (Hint: Binet)

I heard of a guy at work who was asked to multiply two numbers of arbitrary size (larger than primitive int). He solved it in the most optimal way in 20 minutes.

For reference, the majority of candidates take 40 minutes to add two arbitrarily large numbers with the simplification of storing each digit in a separate array element. Plus, they tend to have bugs in their final solution.

One friend mentioned that this might not be an ideal question to figure out if the candidate is a great fit for a Java Enterprise environment or not. Because that’s what we are currently looking for. What about clean code, architecture skills, team work?

I can see his point BUT

  • This is a fairly trivial exercise. On the job, complexity will rather increase. For example, one of the applications my team is building allows the user to generate an Excel report based on the stored data. User input is simplified and highly dynamic. The report needs to generate permutations of the data though. I can’t expect someone who fails to implement an iterative solution to the Fibonacci sequence to recursively permute lists and lists-of-lists of variable size.
  • It’s not a good sign when one struggles in front of a whiteboard. When was the last time the applicant discussed a topic with his co-workers?  Away from an IDE?
  • We want to hear the candidate thinking. What goes on in his mind? Can he articulate his thoughts?
  • What about stress? And failure? Does the candidate completely break down once he failed this exercise? One of them did. As part of the testing challenges he came up with a test case “1 divided by 0” with the expected result of 0.
  • How does the candidate handle criticism? What about the help we provide?

FizzBuzz is reality! The industry is still booming and I think this is something we have to live with for now. We might have to adapt our hiring process to include a phone screening up front and some coding using a shared Google Doc, as suggested by one of my friends.

And most importantly, I have to keep writing this blog, not to get completely FizzBuzzed as well someday.

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s