Few interview problems are as notorious as the “Fibonacci” interview question. At first glance, it seems good: Most people know something about the problem, and there are several clever ways to achieve a linear time solution. Usually, in interviews, the linear time solution is the expected solution. However, the Fibonacci problem is unique among interview problems in that the expected solution is not the optimal solution. There is an $O(1)$ solution, and to get there, we need a little bit of linear algebra.

Hello everyone, and welcome to my blog. I am an ex-Google senior engineer focused on systems programming and performance optimization. My past experience includes hardware engineering, numerical analysis, and high-frequency trading. Here, we will be talking about software engineering, performance, computer systems and foundations, interesting math concepts, electrical engineering, hardware acceleration, FPGAs, and more. We may also branch out to non-technical topics including companies, organizational psychology, and the stock market.