From 8d36c6d00fc2abba9ac04e9e2d4cc620e375d770 Mon Sep 17 00:00:00 2001
From: William Carroll <wpcarro@gmail.com>
Date: Mon, 30 Mar 2020 14:14:02 +0100
Subject: Solve InterviewCake's compute nth Fibonacci

While the "Dynamic programming and recursion" section hosts this problem, the
optimal solution does not use recursion. Many cite the Fibonacci problem as a
quintessential dynamic programming question. I assume these people expect an
answer like:

```python
def fib(n):
  cache = {0: 0, 1: 1}
  def do_fib(n):
    if n in cache:
      return cache[n]
    else:
      cache[n - 1] = do_fib(n - 1)
      cache[n - 2] = do_fib(n - 2)
      return cache[n - 1] + cache[n - 2]
  return do_fib(n)
```

The cache turns the runtime of the classic Fibonacci solution...

```python
def fib(n):
  if n in {0, 1}:
    return n
  return fib(n - 1) + fib(n - 2)
```

... from O(2^n) to a O(n). But both the cache itself and the additional stacks
that the runtime allocates for each recursive call create an O(n) space
complexity.

InterviewCake wants the answer to be solved in O(n) time with O(1)
space. To achieve this, instead of solving fib(n) from the top-down, we solve it
from the bottom-up.

I found this problem to be satisfying to solve.
---
 scratch/deepmind/part_two/nth-fibonacci.py | 72 ++++++++++++++++++++++++++++++
 1 file changed, 72 insertions(+)
 create mode 100644 scratch/deepmind/part_two/nth-fibonacci.py

(limited to 'scratch/deepmind/part_two/nth-fibonacci.py')

diff --git a/scratch/deepmind/part_two/nth-fibonacci.py b/scratch/deepmind/part_two/nth-fibonacci.py
new file mode 100644
index 000000000000..14e176b62aab
--- /dev/null
+++ b/scratch/deepmind/part_two/nth-fibonacci.py
@@ -0,0 +1,72 @@
+import unittest
+
+
+# Compute the fibonacci using a bottom-up algorithm.
+def fib(n):
+    if n < 0:
+        raise Error('Cannot call fibonacci with negative values')
+    cache = [0, 1]
+    for i in range(n):
+        cache[0], cache[1] = cache[1], cache[0] + cache[1]
+    return cache[0]
+
+
+# Compute the fibonacci using memoization.
+def fib_memoized(n):
+    cache = {
+        0: 0,
+        1: 1,
+    }
+
+    def do_fib(n):
+        if n < 0:
+            raise Error('The fib function does not support negative inputs')
+
+        if n in cache:
+            return cache[n]
+
+        cache[n - 1] = do_fib(n - 1)
+        cache[n - 2] = do_fib(n - 2)
+        return cache[n - 1] + cache[n - 2]
+
+    return do_fib(n)
+
+
+# Tests
+class Test(unittest.TestCase):
+    def test_zeroth_fibonacci(self):
+        actual = fib(0)
+        expected = 0
+        self.assertEqual(actual, expected)
+
+    def test_first_fibonacci(self):
+        actual = fib(1)
+        expected = 1
+        self.assertEqual(actual, expected)
+
+    def test_second_fibonacci(self):
+        actual = fib(2)
+        expected = 1
+        self.assertEqual(actual, expected)
+
+    def test_third_fibonacci(self):
+        actual = fib(3)
+        expected = 2
+        self.assertEqual(actual, expected)
+
+    def test_fifth_fibonacci(self):
+        actual = fib(5)
+        expected = 5
+        self.assertEqual(actual, expected)
+
+    def test_tenth_fibonacci(self):
+        actual = fib(10)
+        expected = 55
+        self.assertEqual(actual, expected)
+
+    def test_negative_fibonacci(self):
+        with self.assertRaises(Exception):
+            fib(-1)
+
+
+unittest.main(verbosity=2)
-- 
cgit 1.4.1