My blog has moved! Redirecting...

You should be automatically redirected. If not, visit and update your bookmarks.

12 February 2008

What You Need to Know to Work For Me

If you are ever interviewed by me and I happen to ask you, say, to write a function that returns the nth element in the Fibonacci Series, you had better not give me the recursive solution.

It appears that about 90% of the people asked this give this solution straight away, without asking the examiner anything about efficiency. I find this appalling.

Even if efficiency is not always the number one criteria (or even in the top 5), in this instance the recursive solution is much worse (exponential VS linear complexity) than the non-recursive solution AND is not much simpler to code. The difference is about 3 lines of code.

I expect programmers to anticipate and consider such concerns, and even if not asked specifically to give an efficient solution, in such a case they should (unless of course they ask the examiner if efficiency is a concern and get a negative answer).


There are some acceptable recursive solutions. For example, from Wikipedia:

public void run(int n)
if (n <= 0)



private void run(int n, int eax, int ebx)

if (n == 0)



I don't object to the actual recursion, just to the exponential inefficiency.


Eli Bendersky said...

When I was still young and innocent, I was interviewing to Intel as a student (it was the year 2000). They asked me the famous "an ant climbs the stairs - either 1 or 2 at the time, how many ways to reach the Nth step" to which the answer is Fibonacci.

When asked to provide a solution I, naturally, wrote the recursive one in C. For which I was severely punished, because the interviewer slyly grinned and asked me to write it in assembly.

A double recursion in assembly. Now that's fun ! For me as a 3rd semester student it wasn't easy, but eventually I guess I managed, because they accepted me (though I went to IBM).

ripper234 said...

I've always hated assembly. For me, it's always some other people had to do, but my best qualities are in the domain of more abstract programming languages. I would have definitely failed that test :)

What I love about programming is that it's enough to do something once. If you do it once, you box it up and can reuse it however you want. The more advanced programming languages we have today keep inventing new ways to reuse code, which is great for a lazy person like me (I think laziness is a desired quality in a programmer).