subtree(users/wpcarro): docking briefcase at '24f5a642' r/3226

git-subtree-dir: users/wpcarro
git-subtree-mainline: 464bbcb15c09813172c79820bcf526bb10cf4208
git-subtree-split: 24f5a642af3aa1627bbff977f0a101907a02c69f
Change-Id: I6105b3762b79126b3488359c95978cadb3efa789

11 files changed, 594 insertions, 0 deletions

diff --git a/users/wpcarro/scratch/deepmind/part_one/balanced-binary-tree.py b/users/wpcarro/scratch/deepmind/part_one/balanced-binary-tree.py
new file mode 100644
index 000000000000..7fc174a2a9f3
--- /dev/null
+++ b/users/wpcarro/scratch/deepmind/part_one/balanced-binary-tree.py
@@ -0,0 +1,123 @@
+import unittest
+from collections import deque
+
+
+def is_balanced(node):
+    q, seen, ds = deque(), set(), set()
+    q.append((0, node))
+    while q:
+        d, node = q.popleft()
+        l, r = node.left, node.right
+        seen.add(node)
+        if not l and not r:
+            if d not in ds and len(ds) == 2:
+                return False
+            else:
+                ds.add(d)
+        if l and l not in seen:
+            q.append((d + 1, l))
+        if r and r not in seen:
+            q.append((d + 1, r))
+    return max(ds) - min(ds) <= 1
+
+
+# Tests
+class Test(unittest.TestCase):
+    class BinaryTreeNode(object):
+        def __init__(self, value):
+            self.value = value
+            self.left = None
+            self.right = None
+
+        def insert_left(self, value):
+            self.left = Test.BinaryTreeNode(value)
+            return self.left
+
+        def insert_right(self, value):
+            self.right = Test.BinaryTreeNode(value)
+            return self.right
+
+    def test_full_tree(self):
+        tree = Test.BinaryTreeNode(5)
+        left = tree.insert_left(8)
+        right = tree.insert_right(6)
+        left.insert_left(1)
+        left.insert_right(2)
+        right.insert_left(3)
+        right.insert_right(4)
+        result = is_balanced(tree)
+        self.assertTrue(result)
+
+    def test_both_leaves_at_the_same_depth(self):
+        tree = Test.BinaryTreeNode(3)
+        left = tree.insert_left(4)
+        right = tree.insert_right(2)
+        left.insert_left(1)
+        right.insert_right(9)
+        result = is_balanced(tree)
+        self.assertTrue(result)
+
+    def test_leaf_heights_differ_by_one(self):
+        tree = Test.BinaryTreeNode(6)
+        left = tree.insert_left(1)
+        right = tree.insert_right(0)
+        right.insert_right(7)
+        result = is_balanced(tree)
+        self.assertTrue(result)
+
+    def test_leaf_heights_differ_by_two(self):
+        tree = Test.BinaryTreeNode(6)
+        left = tree.insert_left(1)
+        right = tree.insert_right(0)
+        right_right = right.insert_right(7)
+        right_right.insert_right(8)
+        result = is_balanced(tree)
+        self.assertFalse(result)
+
+    def test_three_leaves_total(self):
+        tree = Test.BinaryTreeNode(1)
+        left = tree.insert_left(5)
+        right = tree.insert_right(9)
+        right.insert_left(8)
+        right.insert_right(5)
+        result = is_balanced(tree)
+        self.assertTrue(result)
+
+    def test_both_subtrees_superbalanced(self):
+        tree = Test.BinaryTreeNode(1)
+        left = tree.insert_left(5)
+        right = tree.insert_right(9)
+        right_left = right.insert_left(8)
+        right.insert_right(5)
+        right_left.insert_left(7)
+        result = is_balanced(tree)
+        self.assertFalse(result)
+
+    def test_both_subtrees_superbalanced_two(self):
+        tree = Test.BinaryTreeNode(1)
+        left = tree.insert_left(2)
+        right = tree.insert_right(4)
+        left.insert_left(3)
+        left_right = left.insert_right(7)
+        left_right.insert_right(8)
+        right_right = right.insert_right(5)
+        right_right_right = right_right.insert_right(6)
+        right_right_right.insert_right(9)
+        result = is_balanced(tree)
+        self.assertFalse(result)
+
+    def test_only_one_node(self):
+        tree = Test.BinaryTreeNode(1)
+        result = is_balanced(tree)
+        self.assertTrue(result)
+
+    def test_linked_list_tree(self):
+        tree = Test.BinaryTreeNode(1)
+        right = tree.insert_right(2)
+        right_right = right.insert_right(3)
+        right_right.insert_right(4)
+        result = is_balanced(tree)
+        self.assertTrue(result)
+
+
+unittest.main(verbosity=2)
diff --git a/users/wpcarro/scratch/deepmind/part_one/dijkstra.py b/users/wpcarro/scratch/deepmind/part_one/dijkstra.py
new file mode 100644
index 000000000000..6975dbe4d1d6
--- /dev/null
+++ b/users/wpcarro/scratch/deepmind/part_one/dijkstra.py
@@ -0,0 +1,26 @@
+# Doing a practice implementation of Dijkstra's algorithm: a priority-first
+# search.
+from heapq import heappush, heappop
+
+
+class Node(object):
+    def __init__(self, value, children):
+        self.value = value
+        self.children = children
+
+
+def shortest_path(a, b):
+    """Return the shortest path from `a` to `b`."""
+    q = []
+    seen = set()
+    heappush((a.value, a, [a]), q)
+
+    while q:
+        d, node, path = heappop(q)
+        if node == b:
+            return path
+        seen.add(node)
+        for child in node.children:
+            if child not in seen:
+                heappush((d + child.value, child, path + [child]), q)
+    raise Exception("Path between nodes A and B does not exist.")
diff --git a/users/wpcarro/scratch/deepmind/part_one/efficiency.org b/users/wpcarro/scratch/deepmind/part_one/efficiency.org
new file mode 100644
index 000000000000..89a45c52ad8a
--- /dev/null
+++ b/users/wpcarro/scratch/deepmind/part_one/efficiency.org
@@ -0,0 +1,6 @@
+* Sorting
+** Merge:	O(n*log(n))
+** Heap:	O(n*log(n))
+** Insertion:	O(n^2)
+** Quick:	O(n^2)
+** Bubble:	O(n^2)
diff --git a/users/wpcarro/scratch/deepmind/part_one/find-rotation-point.py b/users/wpcarro/scratch/deepmind/part_one/find-rotation-point.py
new file mode 100644
index 000000000000..5c21d5167ce9
--- /dev/null
+++ b/users/wpcarro/scratch/deepmind/part_one/find-rotation-point.py
@@ -0,0 +1,55 @@
+import unittest
+from math import floor
+
+
+def midpoint(a, b):
+    return a + floor((b - a) / 2)
+
+
+def do_find_rotation_point(a, b, xs):
+    i = midpoint(a, b)
+    count = b - a + 1
+
+    if count == 2:
+        if xs[a] > xs[b]:
+            return b
+        else:
+            return -1
+
+    if i in {a, b}:
+        return i
+
+    if xs[a] < xs[i]:
+        return do_find_rotation_point(i, b, xs)
+    else:
+        return do_find_rotation_point(a, i, xs)
+
+
+def find_rotation_point(xs):
+    return do_find_rotation_point(0, len(xs) - 1, xs)
+
+
+# Tests
+class Test(unittest.TestCase):
+    def test_small_list(self):
+        actual = find_rotation_point(['cape', 'cake'])
+        expected = 1
+        self.assertEqual(actual, expected)
+
+    def test_medium_list(self):
+        actual = find_rotation_point(
+            ['grape', 'orange', 'plum', 'radish', 'apple'])
+        expected = 4
+        self.assertEqual(actual, expected)
+
+    def test_large_list(self):
+        actual = find_rotation_point([
+            'ptolemaic', 'retrograde', 'supplant', 'undulate', 'xenoepist',
+            'asymptote', 'babka', 'banoffee', 'engender', 'karpatka',
+            'othellolagkage'
+        ])
+        expected = 5
+        self.assertEqual(actual, expected)
+
+
+unittest.main(verbosity=2)
diff --git a/users/wpcarro/scratch/deepmind/part_one/inflight-entertainment.py b/users/wpcarro/scratch/deepmind/part_one/inflight-entertainment.py
new file mode 100644
index 000000000000..2116b27b0b97
--- /dev/null
+++ b/users/wpcarro/scratch/deepmind/part_one/inflight-entertainment.py
@@ -0,0 +1,51 @@
+import unittest
+
+
+def can_two_movies_fill_flight(xs, t):
+    seeking = set()
+    for x in xs:
+        if x in seeking:
+            return True
+        else:
+            seeking.add(t - x)
+    return False
+
+
+# Tests
+
+
+class Test(unittest.TestCase):
+    def test_short_flight(self):
+        result = can_two_movies_fill_flight([2, 4], 1)
+        self.assertFalse(result)
+
+    def test_long_flight(self):
+        result = can_two_movies_fill_flight([2, 4], 6)
+        self.assertTrue(result)
+
+    def test_one_movie_half_flight_length(self):
+        result = can_two_movies_fill_flight([3, 8], 6)
+        self.assertFalse(result)
+
+    def test_two_movies_half_flight_length(self):
+        result = can_two_movies_fill_flight([3, 8, 3], 6)
+        self.assertTrue(result)
+
+    def test_lots_of_possible_pairs(self):
+        result = can_two_movies_fill_flight([1, 2, 3, 4, 5, 6], 7)
+        self.assertTrue(result)
+
+    def test_not_using_first_movie(self):
+        result = can_two_movies_fill_flight([4, 3, 2], 5)
+        self.assertTrue(result)
+
+    def test_only_one_movie(self):
+        result = can_two_movies_fill_flight([6], 6)
+        self.assertFalse(result)
+
+    def test_no_movies(self):
+        result = can_two_movies_fill_flight([], 2)
+        self.assertFalse(result)
+
+
+unittest.main(verbosity=2)
diff --git a/users/wpcarro/scratch/deepmind/part_one/kth-to-last.py b/users/wpcarro/scratch/deepmind/part_one/kth-to-last.py
new file mode 100644
index 000000000000..5335e419f7ec
--- /dev/null
+++ b/users/wpcarro/scratch/deepmind/part_one/kth-to-last.py
@@ -0,0 +1,64 @@
+import unittest
+
+
+def kth_to_last_node(k, x):
+    a, b = x, x
+
+    if k == 0:
+        raise Exception('Value of 0 for k is not supported')
+
+    for _ in range(k - 1):
+        if not a.next:
+            raise Exception('Value of {} for k is too large'.format(k))
+        a = a.next
+
+    while a.next:
+        a, b = a.next, b.next
+    return b
+
+
+class Test(unittest.TestCase):
+    class LinkedListNode(object):
+        def __init__(self, value, next=None):
+            self.value = value
+            self.next = next
+
+        def get_values(self):
+            node = self
+            values = []
+            while node is not None:
+                values.append(node.value)
+                node = node.next
+            return values
+
+    def setUp(self):
+        self.fourth = Test.LinkedListNode(4)
+        self.third = Test.LinkedListNode(3, self.fourth)
+        self.second = Test.LinkedListNode(2, self.third)
+        self.first = Test.LinkedListNode(1, self.second)
+
+    def test_first_to_last_node(self):
+        actual = kth_to_last_node(1, self.first)
+        expected = self.fourth
+        self.assertEqual(actual, expected)
+
+    def test_second_to_last_node(self):
+        actual = kth_to_last_node(2, self.first)
+        expected = self.third
+        self.assertEqual(actual, expected)
+
+    def test_first_node(self):
+        actual = kth_to_last_node(4, self.first)
+        expected = self.first
+        self.assertEqual(actual, expected)
+
+    def test_k_greater_than_linked_list_length(self):
+        with self.assertRaises(Exception):
+            kth_to_last_node(5, self.first)
+
+    def test_k_is_zero(self):
+        with self.assertRaises(Exception):
+            kth_to_last_node(0, self.first)
+
+
+unittest.main(verbosity=2)
diff --git a/users/wpcarro/scratch/deepmind/part_one/merging-ranges.py b/users/wpcarro/scratch/deepmind/part_one/merging-ranges.py
new file mode 100644
index 000000000000..23b40793b8f1
--- /dev/null
+++ b/users/wpcarro/scratch/deepmind/part_one/merging-ranges.py
@@ -0,0 +1,59 @@
+import unittest
+
+
+def merge_ranges(xs):
+    xs.sort()
+    result = [xs[0]]
+    for curr in xs[1:]:
+        a, z = result[-1]
+        if z >= curr[0]:
+            result[-1] = (a, max(z, curr[1]))
+        else:
+            result.append(curr)
+    return result
+
+
+# Tests
+class Test(unittest.TestCase):
+    def test_meetings_overlap(self):
+        actual = merge_ranges([(1, 3), (2, 4)])
+        expected = [(1, 4)]
+        self.assertEqual(actual, expected)
+
+    def test_meetings_touch(self):
+        actual = merge_ranges([(5, 6), (6, 8)])
+        expected = [(5, 8)]
+        self.assertEqual(actual, expected)
+
+    def test_meeting_contains_other_meeting(self):
+        actual = merge_ranges([(1, 8), (2, 5)])
+        expected = [(1, 8)]
+        self.assertEqual(actual, expected)
+
+    def test_meetings_stay_separate(self):
+        actual = merge_ranges([(1, 3), (4, 8)])
+        expected = [(1, 3), (4, 8)]
+        self.assertEqual(actual, expected)
+
+    def test_multiple_merged_meetings(self):
+        actual = merge_ranges([(1, 4), (2, 5), (5, 8)])
+        expected = [(1, 8)]
+        self.assertEqual(actual, expected)
+
+    def test_meetings_not_sorted(self):
+        actual = merge_ranges([(5, 8), (1, 4), (6, 8)])
+        expected = [(1, 4), (5, 8)]
+        self.assertEqual(actual, expected)
+
+    def test_one_long_meeting_contains_smaller_meetings(self):
+        actual = merge_ranges([(1, 10), (2, 5), (6, 8), (9, 10), (10, 12)])
+        expected = [(1, 12)]
+        self.assertEqual(actual, expected)
+
+    def test_sample_input(self):
+        actual = merge_ranges([(0, 1), (3, 5), (4, 8), (10, 12), (9, 10)])
+        expected = [(0, 1), (3, 8), (9, 12)]
+        self.assertEqual(actual, expected)
+
+
+unittest.main(verbosity=2)
diff --git a/users/wpcarro/scratch/deepmind/part_one/recursive-string-permutations.py b/users/wpcarro/scratch/deepmind/part_one/recursive-string-permutations.py
new file mode 100644
index 000000000000..f50db2838707
--- /dev/null
+++ b/users/wpcarro/scratch/deepmind/part_one/recursive-string-permutations.py
@@ -0,0 +1,56 @@
+import unittest
+from itertools import permutations
+
+
+class Node(object):
+    def __init__(self, x):
+        self.value = x
+        self.children = []
+
+
+def make_tree(c, xs):
+    root = Node(c)
+    for x in xs:
+        root.children.append(make_tree(x, xs - {x}))
+    return root
+
+
+def get_permutations(xs):
+    xs = set(xs)
+    root = make_tree("", xs)
+    q, perms = [], set()
+    q.append(("", root))
+    while q:
+        c, node = q.pop()
+        if not node.children:
+            perms.add(c)
+        else:
+            for child in node.children:
+                q.append((c + child.value, child))
+    return perms
+
+
+# Tests
+class Test(unittest.TestCase):
+    def test_empty_string(self):
+        actual = get_permutations('')
+        expected = set([''])
+        self.assertEqual(actual, expected)
+
+    def test_one_character_string(self):
+        actual = get_permutations('a')
+        expected = set(['a'])
+        self.assertEqual(actual, expected)
+
+    def test_two_character_string(self):
+        actual = get_permutations('ab')
+        expected = set(['ab', 'ba'])
+        self.assertEqual(actual, expected)
+
+    def test_three_character_string(self):
+        actual = get_permutations('abc')
+        expected = set(['abc', 'acb', 'bac', 'bca', 'cab', 'cba'])
+        self.assertEqual(actual, expected)
+
+
+unittest.main(verbosity=2)
diff --git a/users/wpcarro/scratch/deepmind/part_one/reverse-linked-list.py b/users/wpcarro/scratch/deepmind/part_one/reverse-linked-list.py
new file mode 100644
index 000000000000..82fac171d5d1
--- /dev/null
+++ b/users/wpcarro/scratch/deepmind/part_one/reverse-linked-list.py
@@ -0,0 +1,74 @@
+import unittest
+
+
+def reverse(node):
+    prev = None
+    next = None
+    curr = node
+
+    while curr:
+        next = curr.next
+        curr.next = prev
+        prev = curr
+        curr = next
+
+    return prev
+
+
+# Tests
+class Test(unittest.TestCase):
+    class LinkedListNode(object):
+        def __init__(self, value, next=None):
+            self.value = value
+            self.next = next
+
+        def get_values(self):
+            node = self
+            values = []
+            while node is not None:
+                values.append(node.value)
+                node = node.next
+            return values
+
+    def test_short_linked_list(self):
+        second = Test.LinkedListNode(2)
+        first = Test.LinkedListNode(1, second)
+
+        result = reverse(first)
+        self.assertIsNotNone(result)
+
+        actual = result.get_values()
+        expected = [2, 1]
+        self.assertEqual(actual, expected)
+
+    def test_long_linked_list(self):
+        sixth = Test.LinkedListNode(6)
+        fifth = Test.LinkedListNode(5, sixth)
+        fourth = Test.LinkedListNode(4, fifth)
+        third = Test.LinkedListNode(3, fourth)
+        second = Test.LinkedListNode(2, third)
+        first = Test.LinkedListNode(1, second)
+
+        result = reverse(first)
+        self.assertIsNotNone(result)
+
+        actual = result.get_values()
+        expected = [6, 5, 4, 3, 2, 1]
+        self.assertEqual(actual, expected)
+
+    def test_one_element_linked_list(self):
+        first = Test.LinkedListNode(1)
+
+        result = reverse(first)
+        self.assertIsNotNone(result)
+
+        actual = result.get_values()
+        expected = [1]
+        self.assertEqual(actual, expected)
+
+    def test_empty_linked_list(self):
+        result = reverse(None)
+        self.assertIsNone(result)
+
+
+unittest.main(verbosity=2)
diff --git a/users/wpcarro/scratch/deepmind/part_one/stock-price.py b/users/wpcarro/scratch/deepmind/part_one/stock-price.py
new file mode 100644
index 000000000000..7055b66af196
--- /dev/null
+++ b/users/wpcarro/scratch/deepmind/part_one/stock-price.py
@@ -0,0 +1,51 @@
+def get_max_profit(xs):
+    best_profit = xs[1] - xs[0]
+    lowest_buy = xs[0]
+
+    for x in xs[1:]:
+        best_profit = max(best_profit, x - lowest_buy)
+        lowest_buy = min(lowest_buy, x)
+    return best_profit
+
+
+# Tests
+
+import unittest
+
+
+class Test(unittest.TestCase):
+    def test_price_goes_up_then_down(self):
+        actual = get_max_profit([1, 5, 3, 2])
+        expected = 4
+        self.assertEqual(actual, expected)
+
+    def test_price_goes_down_then_up(self):
+        actual = get_max_profit([7, 2, 8, 9])
+        expected = 7
+        self.assertEqual(actual, expected)
+
+    def test_price_goes_up_all_day(self):
+        actual = get_max_profit([1, 6, 7, 9])
+        expected = 8
+        self.assertEqual(actual, expected)
+
+    def test_price_goes_down_all_day(self):
+        actual = get_max_profit([9, 7, 4, 1])
+        expected = -2
+        self.assertEqual(actual, expected)
+
+    def test_price_stays_the_same_all_day(self):
+        actual = get_max_profit([1, 1, 1, 1])
+        expected = 0
+        self.assertEqual(actual, expected)
+
+    def test_error_with_empty_prices(self):
+        with self.assertRaises(Exception):
+            get_max_profit([])
+
+    def test_error_with_one_price(self):
+        with self.assertRaises(Exception):
+            get_max_profit([1])
+
+
+unittest.main(verbosity=2)
diff --git a/users/wpcarro/scratch/deepmind/part_one/which-appears-twice.py b/users/wpcarro/scratch/deepmind/part_one/which-appears-twice.py
new file mode 100644
index 000000000000..c01379295d32
--- /dev/null
+++ b/users/wpcarro/scratch/deepmind/part_one/which-appears-twice.py
@@ -0,0 +1,29 @@
+import unittest
+
+
+def find_repeat(xs):
+    n = max(xs)
+    expected_sum = (n + 1) * n / 2
+    actual_sum = sum(xs)
+    return actual_sum - expected_sum
+
+
+# Tests
+class Test(unittest.TestCase):
+    def test_short_list(self):
+        actual = find_repeat([1, 2, 1])
+        expected = 1
+        self.assertEqual(actual, expected)
+
+    def test_medium_list(self):
+        actual = find_repeat([4, 1, 3, 4, 2])
+        expected = 4
+        self.assertEqual(actual, expected)
+
+    def test_long_list(self):
+        actual = find_repeat([1, 5, 9, 7, 2, 6, 3, 8, 2, 4])
+        expected = 2
+        self.assertEqual(actual, expected)
+
+
+unittest.main(verbosity=2)