4 ms·
During the my last technical interview, they asked my to write a fibonacci implementation in golang, i wrote the code, then they asked me to test it for like fb
by freecodyx 8y ago
During the my last technical interview, they asked my to write a fibonacci implementation in golang, i wrote the code, then they asked me to test it for like fb(180), i was surprised how slow it, then i was asked to come up with an optimisation in order to make it fast,
i come exactly with same fib-mem.go provided in this benchmark,
i was hired !
- bufferoverflow 8y agofib(180) without caching would take billions of years to complete, so "slow" is an understatement.
- person_of_color 8y agocause o^2n?
- ummonk 8y agoBillions of years is a gross understatement.
- bjoli 8y agoOr you write an iterative version of it that will not only be the simplest solution, it will be fast enough to compute fib(10000). There are constant time ones IIRC, but if someone comes up with such a solution in an interview without knowing it from before, they are probably over qualified for any job that uses the Fibonacci sequence as an interview question.
- sriram_malhar 8y agoSo you didn't write the non-recursive version?
- quickthrower2 8y agoYeah that fib-mem.go is just weird. It's almost a WTF.
- dangom 8y agoI guess if the point is to optimize fibonacci then wouldn't the smartest move be to use the closed form solution where Fib(n) is the closest integer to phi^n / sqrt(5), where phi = (1 + sqrt(5))/2? This is one of the examples in the beginning of SICP, if I remember correctly.
- FreeFull 8y agoThe identity involves going through real numbers to get the integer result, and if you're using floating point or fixed point calculations, you need a good amount of accuracy to get the correct integer out, which also won't be the fastest thing. Using https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form you can get a different way to calculate Fibonacci numbers recursively, which involves far fewer computations.
- Chinjut 8y agoFundamentally, the thing to do is to understand the N-th Fibonacci number as a + b, where φ^N = a + b * φ, where a and b are natural numbers and φ^2 = φ + 1. It's not important to understand phi as a floating point value; we can just work in the abstract arithmetic where we've added to the natural numbers a new entity phi defined to satisfy φ^2 = φ + 1 (just like complex numbers are the abstract arithmetic where we've added to ordinary arithmetic an i defined to satisfy i^2 = -1). Call these Fomplex numbers; a Fomplex number a + b * φ amounts to just a pair of natural numbers, and it's easy enough to add and multiply them with natural number arithmetic. To calculate the N-th Fibonacci number, just calculate φ^N and add together its coefficients, as noted. As for how to efficiently calculate φ^N, use the usual addition chain approach to exponentiation (e.g., "repeated squaring"), thus getting a result in Θ(log N) many additions and multiplications. This is incidentally the same as the matrix approach, essentially, but perhaps a cleaner perspective on it; at any rate, it is a way of thinking which will serve as a useful tool in your back pocket for other general problems about linear recurrences.
- edflsafoiewq 8y agoHow neat! Among its properties not the least interesting is that it has finally convinced me that the initial condition f(0) = f(1) = 1 is not arbitrary but perfectly natural.