Fibonacci Interview Exercise

"""

Write a Python function to return the Nth number in a Fibonacci sequence. 
Your algorithm can be either recursive or iterative.

Fibonnaci sequence: Starts with 0, 1. Each number after that is the sum 
of the two previous numbers (0,1,1,2,3,5,8 ...)

Examples:

fib(0) = 0
   fib(1) = 1
   fib(2) = 1
   fib(3) = 2
   fib(4) = 3
   fib(5) = 5
   fib(6) = 8
   
"""

def fib(n):
	# your code here...

# Increase this gradually if your tests all pass and are fast.
test_limit = 20 # Max is 500

# --- Test code: Do not edit below this line. ---

import time

test_cases = [
	(0, 0), (1, 1), (2, 1), (3, 2), (4, 3), (5, 5), (6, 8), (7, 13), (8, 21),
    (10, 55),
    (20, 6765),
    (30, 832040),
    (50,12586269025), 
    (100, 354224848179261915075), 
    (200, 280571172992510140037611932413038677189525),
    (300, 222232244629420445529739893461909967206666939096499764990979600),
    (500, 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125)
    ]

for(n, expected_result) in test_cases:
    if n > test_limit:
        break
    start = time.time() * 1000.0
    actual_result = fib(n)
    end = time.time() * 1000.0
    duration = end-start
    print "fib(%s): %s" % (n, actual_result),
    if actual_result == expected_result:
        print " // Pass. %0.0f ms" % duration
    else:
        print " // Fail. Expected: %s, %0.0f ms" % (expected_result, duration)

Browser Version Not Supported

Due to Python Fiddle's reliance on advanced JavaScript techniques, older browsers might have problems running it correctly. Please download the latest version of your favourite browser.
Chrome 10+ Firefox 4+ Safari 5+
IE 10+

Let me try anyway!

Python Fiddle

Python Cloud IDE