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.