I like the large-company version with baroque OO/Java appendages hanging off of everything. Those flourishes make it feel safer and more reassuring, I guess.<p>The math PhD one seemed possibly unfair. It looked more like something that would come from a CS PhD who did his thesis in PL.<p>It's hard to judge what the right solution would look like. You could go many careers without ever having a real reason to write that function outside of an interview. Fibonacci numbers occasionally come about as a by-product of doing something interesting and useful; in cases where they would be interesting in and of themselves, you would probably be using a library or language, like Mathematica, that would have that built-in.
Don't forget the tests of each. The startup's tests are all commented out because they failed at some point or another, the large company's tests are five times as long as the actual code they test, and all other categories consist of the stubs provided by the IDE.