4 ms·
I was recently asked to calculate the fibonacci sequence value in an O(log n) time complexity. I had no clue how to do it and explained that I can solve it in O
by wapz 9y ago
I was recently asked to calculate the fibonacci sequence value in an O(log n) time complexity. I had no clue how to do it and explained that I can solve it in O(N) easily but don't even know how to approach the O(log n) method. I knew there must be some trick using factors but didn't even know how to start the problem. I looked it up later and one of the ways is using matrix multiplication (an implementation I still wouldn't be able to do without seeing pseudocode).
- murkle 9y agoI wonder what the interviewer would have said if you'd written down Binet's formula :) http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.ht...
- wapz 9y agoMaybe his response would have been "Thank you for memorizing obscure formulas. Unfortunately, we look for motivated employees who study relevant topics pertinent to work." Like really I don't know what to expect. I wonder what % of programmers can actually solve the problem without studying the solution (I'm sure there are many out there but I would guess most are from a mathematical field/background).