4 ms·

Am I the only one who thinks that his "Example 2: Write function to compute Nth fibonacci number" is a terrible resource hog? IMHO an iterative approach would

• RiderOfGiraffes 17y ago
  So, so many people miss the point(s) here. Firstly, in my direct, personal experience, just writing a candidate to write a program that compiles and runs gets rid of up to 90% of applicants. People here on HN are exceptional, but around 90% of recent applicants for a position I advertised couldn't write a FizzBuzz program that compiled and ran. Secondly, these are the starting points. From here you can ask what problems the program has. Yes, it's exponential in stack and runtime. You can write an iterative version that runs in constant stack and linear time. More subtle, and more probing, is how do you write a recursive version that also runs in small stack and time. These are the starting points, the initial cull. Don't assume they're the be all and end all.
  • falsestprophet 17y ago
    On paper? Or with a computer and compiler/interpreter?
    • silentbicycle 17y ago
      Writing pseudocode on paper will shift focus from correcting minor syntax errors to how well they understand concepts, which is arguably more important. It's still worth requiring them to produce at least a tiny piece of working code, though. I helped interview someone who couldn't explain the trade-offs between a couple different designs for a simple class hierarchy, even an obviously wrong one included as a canary. Then we asked him to write one out, and, after stalling and getting several hints from us, he nervously scratched out a (naive) MySQL schema. Despite what his resume claimed, his only programming experience consisted of PHP and a fairly shallow understanding of SQL.
    • RiderOfGiraffes 17y ago
      Some couldn't produce either. I look for someone to sketch a correct algorithm using any notation they choose. Independently I look for someone to produce working code with an editor and compiler. The former is usually for something like linked lists or quicksort, the second for something like FizzBuzz and then recursive and iterative Fibonnaci. Working code is essential for something, anything, at some point, although really what I want is someone who can then talk sensibly through the issues. Even so, working code for trivial problems is still only seen in about 10% of cases.
    • gjm11 17y ago
      I like to ask candidates to write real code (not pseudocode) on paper, but emphasize to them that I don't really care about superficial syntax errors. Most of the point of this is not in seeing the code they produce, but in watching them think and seeing how they react to questions and suggestions.
  • strlen 17y ago
    Entirely correct. The purpose of a phone screen is to rule out the cases where a candidate will come in, be scheduled for 6-8 hours of interviews and receive a "no" from every interviewer. Recursive Fibonacci numbers are also a good way to work Memoization into the picture.
• camccann 17y ago
  No, the iterative approach is only marginally less terrible. If, for some strange reason, you actually need a Fibonacci function that's efficient, you have two choices, depending on the return type: Are you returning a machine integer (long or otherwise)? Precompute them and use a freaking lookup table. The sequence grows so fast you'll never see more than maybe 60 or so terms. Are you returning an arbitrary-size bignum? Use the closed-form solution based on powers of the golden ratio. It still runs in non-constant time (bignum math isn't free), but will run much faster than pointlessly enumerating the sequence up to that point. Of course, I would be surprised if anyone asking about Fibonacci numbers in an interview has ever been looking for one of those answers. Usually it's a "FizzBuzz for recursion" question.
  • gjm11 17y ago
    I have asked a candidate about Fibonacci numbers in interview. We discussed a number of different implementations, the possibility of memoization, the practical differences between machine integers, machine floating-point, and bignums, etc. Incidentally, if you want arbitrary-sized bignum results as quickly as possible, you might do better with a "matrix-squaring" approach (equivalently: use the recurrences that give you F(2k) and F(2k-1) in terms of F(k) and F(k-1)) so that you stick with integer arithmetic. If your bignum library isn't clever about multiplication, I suspect that the simple iterative solution is about as fast as anything else, but most bignum libraries have at least Karatsuba multiplication.
    • camccann 17y ago
      Well, iterative (and smart tail recursive [0]) solutions are going to be roughly O(n) for the nth Fibonacci number, assuming addition is O(1). In bignum territory, addition isn't free, but is still pretty cheap. The closed form solution involves computing something raised to the power of n, so would be O(log n) assuming nonintegral multiplication is O(1), which is... not so much the case. Given that the (sqrt 5) factors will always be eliminated by the end you can manipulate things to work with only integers, at the expense of complicating the algorithm. The matrix-based solution, which I had forgotten, is also of the form x^n, so is probably isomorphic to a sufficiently clever handling of Binet's formula that completely avoids the (sqrt 5) terms. So, yes, good call, the matrix approach is better--you win this round. [0] The naive un-memoized recursive algorithm, such as the recursive solution in the linked article, is not only not tail-recursive, but manages to have time complexity of precisely O(fib(n)). If that doesn't make you die a little inside, you're made of sterner stuff than I.