[wapz]

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]

I wonder what the interviewer would have said if you'd written down Binet's formula :)

http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.ht...

[wapz]

Maybe 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).