After my interview (my code was terrible) the guy running the interview suggested a simple program design that made use of caching. Googling any simple fibonacci generation code will get you these results.