There are several groups of test cases. One group is for low positive numbers. These are largely fixed (i.e. fib(0), fib(1), fib(10), etc) but some are random. Another group is for low negative integers, again, some fixed and some random. The last group is for higher n, generally n > 1000, with the last two tests for n > 1,000,000. Like the other groups, some inputs are fixed and some are random. This last group has the tests that tend to timeout. Note that failing anything within a group stops the testing at the end of the group. In other words if you fail something in the low positive numbers group, you don't ever see any tests from the negative or high positive numbers groups.

While your algorithm may be correct, if you are getting timeouts you may want to try some testing on you local machine. If fib(1000000) takes more than a few seconds, your algorithm is probably too slow and you need to rethink it.

I'm also getting the timeout error (in ruby). There seems so be a severe perfomance penalty at around fib(1_000_000). Fib(1M) returns almost instantly. Bumping it up to as little as fib(1.1M) almost always times out. The last two unit tests are for n > 1M.

Running on my computer (Windows 7x64, i7 2.0GHz, 8GB) doing fib(500_000) takes about 9 seconds while fib(100_000) takes about .5 seconds.

The upper range of n in this problem may need to be adjusted downward

Update: I do not believe this problem is intended to be solved with a linear time solution. Read all of "HINT II". The problem description is not as clear as it could be. I think the problem statement should address the possiblity of timeouts and that an optimized solution might be needed. Also, although minor, the negative fibonacci thing feels tacked on to the narrative of the problem. I feel like the narrative should be reworked or the negative unit tests should be dropped.