Probably the most famous coding interview question has to do with the Fibonacci sequence:
Given a number F(0) = 0, and a number F(1) = 1
Write a program to find F(N) for any N > 2, given:
F(N) = F(N-1) + F(N-2)
There are all sorts of different solutions which use iteration, recursion, and even matrix multiplication. "Better" solutions talk about tail call optimization and other advanced programming concepts. But most of these solutions are still unbearably slow. The JavaScript solution posted here takes almost a second and a half to find the 15th Fibonacci number. Imagine how much time it would take to calculate F(1000000)!
One shortcut that lots of people aren't aware of is that the N-th Fibonacci number is related to the golden ratio by the rule:
F(N) = floor(pow(g,N) / sqrt(5) + 1/2)
for any N > 0
where g = the golden ratio = (1 + sqrt(5))/2
The best, most efficient (in terms of space and time) solution, is to use this relationship to calculate the Nth Fibonacci number. But the knee-jerk reaction of most programmers is to just brute force it, without fully understanding the problem beforehand. Doing a little research can save you a lot of CPU cycles and wasted RAM.
On that note, here's a problem for you that could be brute-forced, but can also be solved with just a pen and paper. Make some assumptions and use some logic to narrow the parameter space of your problem to just a few possible solutions, and then find the correct one(s)!
Francesco was born in a year where the product of the digits of the year equal the square of some natural number, n. The year is now 2005, and he's waiting for the year when his age will be equal to that natural number, n. What year was Francesco born and what year is he waiting for?
Good luck! I look forward to your solutions below. Feel free to ask any questions related to the prompt.
Top comments (5)
You make a very good point about brute-forcing vs solving mathematically. Studying fibonacci is a gateway to learning about recurrence relations, beauty of the golden ratio (phi), interesting relation between Fibonacci and Lukas numbers and how phi keeps cropping up in unexpected places :P
IMO, the main issue with using the direct formula is that there are possibilities of errors creeping at multiple stages due to floating point imprecision.
The matrix solution is beautiful. It is computing the formula mentioned behind the scenes. The only issue with that is again the limited range of machine integers. If we can do it with unlimited precision integers it is a very straight-forward way of solving a recurrence relation efficiently.
Yes. Python integers have unlimited precision out of the box. Java has BigInteger in standard library. Not sure about javascript.
Is that the only solution?
(I don't want to give away the game ;)...)
1988 is 3^2 * 8^2, and that's it.
Is there a way to hide the solution? PerlMonks have
<readmore>and<spoiler>.