Implement a bottom-up fibonacci

The bottom-up solution run in O(n) time instead of O(2^n) time, which the
recursive solution runs as:

```
def fib(n):
    return fib(n - 2) + fib(n - 1)
```

Remember that exponential algorithms are usually recursive algorithms with
multiple sibling calls to itself.

1 files changed, 6 insertions, 0 deletions

diff --git a/scratch/facebook/interview-cake/nth-fibonacci.py b/scratch/facebook/interview-cake/nth-fibonacci.py
new file mode 100644
index 000000000000..4629798cf711
--- /dev/null
+++ b/scratch/facebook/interview-cake/nth-fibonacci.py
@@ -0,0 +1,6 @@
+def fib(n):
+    cache = (0, 1)
+    for _ in range(n):
+        a, b = cache
+        cache = (b, a + b)
+    return cache[0]