8 ms·

It's a great showcase of how a flashy looking solution is the wrong approach. A good candidate will know it can be written in 2 lines recursively, but that the

• eru 6y ago
  In eg Python you can just add a memoization decoration, and get a linear solution from the naive recursive one. That's pretty neat.
  • dotancohen 6y ago
    In almost any language, a hashtable check after the base case check could be used in a similar manner.
    • eru 6y ago
      Yes. I just singled out Python, because the language is well-known, and adding the memoization is particularly straight-forward.
• dotancohen 6y ago
  > iterating with a for loop I'm struggling to understand what you mean? This is a learning opportunity for me, if you wouldn't mind posting a code sample or elaborating further.
  • ajuc 6y ago
    Something like this (might be subtly wrong, I wrote it in 2 minutes). int fib(int n) { if (n<=2) return 1; int fibNMinus2= 1; int fibNMinus1 = 1; int tmp; for (int i=3; i<=n; i++) { tmp = fibNMinus2+ fibNMinus1 ; fibNMinus2 = fibNMinus1; fibNMinus1 = tmp; } return fibNMinus1; } vs recursive solution which is pretty but slow (and will fail when you run out of stack) int fib(int n) { if (i<=2) return 1; return fib(n-1)+fib(n-2); }
    • eru 6y ago
      Of course, recursion vs iteration is mostly an implementation detail. Here's a recursive version (expressed in Python) that works better than your loop: def fib(n): if n =< 0: return (0, 1) else: a, b = f(n-1) return (b, a + b) (I say it works better, because it has the same asymptotic runtime, but fails better: When numbers get large, your C version will run into undefined behaviour that can cause arbitrary problems. The Python version will just crash with a well-defined exception. A better language than Python can run this recursive version for arbitrarily big numbers.)
      • ajuc 6y ago
        In practice iteration will be faster, even in Python (because there's less overhead). But yes, I should have written "naive recursive solution". There are many ways to fix it. It just wasn't what the question was about.
        • eru 6y ago
          In Python, yes. If you have a decent language and a good compiler / interpreter, then the recursion with function calls will have no overhead over iteration. (Basically, in Haskell or Scheme your recursion will be compiled into the same machine language sequence of straight-line code plus conditional jump as the iterative loop.) But, agreed with everything else you wrote!
          • ajuc 6y ago
            I can't be sure without measuring, but I strongly suspect the overhead will be mostly in tuple packing/unpacking and GC. And I instinctively distrust Sufficiently Smart Compilers ;)
            • eru 6y ago
              Oh, your compiler doesn't have to be sufficiently smart. It merely has to avoid premature optimization: see this classic paper https://dspace.mit.edu/handle/1721.1/5753 https://dspace.mit.edu/handle/1721.1/5753 by Guy Steele. > I can't be sure without measuring, but I strongly suspect the overhead will be mostly in tuple packing/unpacking and GC. I guess that's the same overhead as in this imperative version: a, b = 0, 1 for _ in range(n): a, b = b, a + b
• ForHackernews 6y ago
  Fibonacci has a closed-form solution! Forget writing loops, you can write one damn equation. Runs in constant time.
  • WJW 6y ago
    The closed form solution is technically O(phi^N), so still exponential. It comes mostly from exponentiation not being constant time, see https://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence https://stackoverflow.com/questions/360748/computational-com.... It'll only be constant time if your values fit into a hardware register and you can leverage the exponentiation instructions of your CPU. There is a O(log(N)) solution involving matrix exponentiation though, if you really need to get the big numbers.
    • Taek 6y ago
      Technically, Fib(n) at unbounded sizes is at least linear to compute. This is because the output of Fib(n) has O(n) bits in it. So even if the computation is free, it's still O(n) just to print the result. That's not the type of thing I would ever expect a candidate to know in an interview, just something fun I've run across.
• Thrymr 6y ago
  Or in this case, just compute it from the closed form expression with no loop at all.