diff options
Diffstat (limited to 'users/wpcarro/scratch/deepmind/part_one')
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 0000000000..7fc174a2a9 --- /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 0000000000..6975dbe4d1 --- /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 0000000000..89a45c52ad --- /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 0000000000..5c21d5167c --- /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 0000000000..2116b27b0b --- /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 0000000000..5335e419f7 --- /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 0000000000..23b40793b8 --- /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 0000000000..f50db28387 --- /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 0000000000..82fac171d5 --- /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 0000000000..7055b66af1 --- /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 0000000000..c01379295d --- /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) |