diff options
| author | Vincent Ambo <mail@tazj.in> | 2021-12-13T22·51+0300 |
|---|---|---|
| committer | Vincent Ambo <mail@tazj.in> | 2021-12-13T23·15+0300 |
| commit | 019f8fd2113df4c5247c3969c60fd4f0e08f91f7 (patch) | |
| tree | 76a857f61aa88f62a30e854651e8439db77fd0ea /users/wpcarro/scratch/deepmind | |
| parent | 464bbcb15c09813172c79820bcf526bb10cf4208 (diff) | |
| parent | 6123e976928ca3d8d93f0b2006b10b5f659eb74d (diff) | |
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
Diffstat (limited to 'users/wpcarro/scratch/deepmind')
44 files changed, 3185 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) diff --git a/users/wpcarro/scratch/deepmind/part_two/.envrc b/users/wpcarro/scratch/deepmind/part_two/.envrc new file mode 100644 index 000000000000..a4a62da526d3 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/.envrc @@ -0,0 +1,2 @@ +source_up +use_nix diff --git a/users/wpcarro/scratch/deepmind/part_two/balanced-binary-tree.py b/users/wpcarro/scratch/deepmind/part_two/balanced-binary-tree.py new file mode 100644 index 000000000000..03de0350d898 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/balanced-binary-tree.py @@ -0,0 +1,126 @@ +import unittest +from collections import deque + + +# is_balanced :: Node(a) -> Bool +def is_balanced(node): + q = deque() + q.append((0, node)) + mn, mx = None, None + + while q: + depth, node = q.popleft() + # Current node is a leaf node + if not node.left and not node.right: + mx = depth if mx is None else max(mx, depth) + mn = depth if mn is None else min(mn, depth) + if mx - mn > 1: + return False + if node.left: + q.append((depth + 1, node.left)) + if node.right: + q.append((depth + 1, node.right)) + + return mx - mn <= 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_two/bst-checker.py b/users/wpcarro/scratch/deepmind/part_two/bst-checker.py new file mode 100644 index 000000000000..fd0374a9ce91 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/bst-checker.py @@ -0,0 +1,110 @@ +import unittest +from collections import deque + + +# While this function solves the problem, it uses O(n) space since we're storing +# all of the less-thans and greater-thans. +def is_binary_search_tree_first_attempt(root): + q = deque() + q.append((set(), set(), root)) + + while q: + lts, gts, node = q.popleft() + + if not all([node.value < lt for lt in lts]): + return False + if not all([node.value > gt for gt in gts]): + return False + + if node.left: + q.append((lts | {node.value}, gts, node.left)) + if node.right: + q.append((lts, gts | {node.value}, node.right)) + + return True + + +# While I did not originally solve this problem this way, when I learned that I +# could condense the space of my solution's runtime, I wrote this. +def is_binary_search_tree(root): + q = deque() + q.append((None, None, root)) + + while q: + lt, gt, node = q.popleft() + + if not lt is None and node.value >= lt: + return False + if not gt is None and node.value <= gt: + return False + + if node.left: + q.append((node.value, gt, node.left)) + if node.right: + q.append((lt, node.value, node.right)) + + return True + + +# 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_valid_full_tree(self): + tree = Test.BinaryTreeNode(50) + left = tree.insert_left(30) + right = tree.insert_right(70) + left.insert_left(10) + left.insert_right(40) + right.insert_left(60) + right.insert_right(80) + result = is_binary_search_tree(tree) + self.assertTrue(result) + + def test_both_subtrees_valid(self): + tree = Test.BinaryTreeNode(50) + left = tree.insert_left(30) + right = tree.insert_right(80) + left.insert_left(20) + left.insert_right(60) + right.insert_left(70) + right.insert_right(90) + result = is_binary_search_tree(tree) + self.assertFalse(result) + + def test_descending_linked_list(self): + tree = Test.BinaryTreeNode(50) + left = tree.insert_left(40) + left_left = left.insert_left(30) + left_left_left = left_left.insert_left(20) + left_left_left.insert_left(10) + result = is_binary_search_tree(tree) + self.assertTrue(result) + + def test_out_of_order_linked_list(self): + tree = Test.BinaryTreeNode(50) + right = tree.insert_right(70) + right_right = right.insert_right(60) + right_right.insert_right(80) + result = is_binary_search_tree(tree) + self.assertFalse(result) + + def test_one_node_tree(self): + tree = Test.BinaryTreeNode(50) + result = is_binary_search_tree(tree) + self.assertTrue(result) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/deepmind/part_two/cafe-order-checker.py b/users/wpcarro/scratch/deepmind/part_two/cafe-order-checker.py new file mode 100644 index 000000000000..0e31214b830d --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/cafe-order-checker.py @@ -0,0 +1,64 @@ +import unittest + + +# Solution +def is_first_come_first_served(xs, ys, zs): + i, j = 0, 0 + for z in zs: + if i < len(xs) and z == xs[i]: + i += 1 + elif j < len(ys) and z == ys[j]: + j += 1 + else: + return False + return i == len(xs) and j == len(ys) + + +# Tests +class Test(unittest.TestCase): + def test_both_registers_have_same_number_of_orders(self): + result = is_first_come_first_served([1, 4, 5], [2, 3, 6], + [1, 2, 3, 4, 5, 6]) + self.assertTrue(result) + + def test_registers_have_different_lengths(self): + result = is_first_come_first_served([1, 5], [2, 3, 6], [1, 2, 6, 3, 5]) + self.assertFalse(result) + + def test_one_register_is_empty(self): + result = is_first_come_first_served([], [2, 3, 6], [2, 3, 6]) + self.assertTrue(result) + + def test_served_orders_is_missing_orders(self): + result = is_first_come_first_served([1, 5], [2, 3, 6], [1, 6, 3, 5]) + self.assertFalse(result) + + def test_served_orders_has_extra_orders(self): + result = is_first_come_first_served([1, 5], [2, 3, 6], + [1, 2, 3, 5, 6, 8]) + self.assertFalse(result) + + def test_one_register_has_extra_orders(self): + result = is_first_come_first_served([1, 9], [7, 8], [1, 7, 8]) + self.assertFalse(result) + + def test_one_register_has_unserved_orders(self): + result = is_first_come_first_served([55, 9], [7, 8], [1, 7, 8, 9]) + self.assertFalse(result) + + # Bonus + def test_handles_repeats(self): + actual = is_first_come_first_served([1, 2, 1], [3, 4, 5, 5], + [3, 4, 1, 5, 5, 2, 1]) + self.assertTrue(actual) + + def test_kitchen_didnt_serve(self): + actual = is_first_come_first_served([1, 2], [3, 4], [1, 3, 4]) + self.assertFalse(actual) + + def test_customer_didnt_pay(self): + actual = is_first_come_first_served([2], [3, 4], [1, 3, 4]) + self.assertFalse(actual) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/deepmind/part_two/coin.ts b/users/wpcarro/scratch/deepmind/part_two/coin.ts new file mode 100644 index 000000000000..8aa8de8bb87a --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/coin.ts @@ -0,0 +1,102 @@ +// The denomination of a coin. +type Coin = number; + +// The amount of change remaining. +type Amount = number; + +// Mapping of Coin -> Int +type CoinBag = Map<Coin, number>; + +function createCoinBag(coins: Coin[]): CoinBag { + const result = new Map(); + + for (const coin of coins) { + result.set(coin, 0); + } + + return result; +} + +// This algorithm should work conceptual, but it does not actually +// work. JavaScript uses reference equality when constructing a Set<Map<A,B>>, +// so my result.size returns a higher number than I expect because it contains +// many duplicate entries. +// +// Conceptually, I'm not sure this solution is optimal either -- even after I +// can dedupe the entries in `result`. +function changePossibilities(amt: Amount, coins: Coin[]): number { + if (amt === 0) { + return 1; + } + const result: Set<CoinBag> = new Set(); + + const q: [Coin, Amount, CoinBag][] = []; + + for (const coin of coins) { + const bag = createCoinBag(coins); + bag.set(coin, 1); + q.push([coin, amt - coin, bag]); + } + + while (q.length > 0) { + const [coin, amt, bag] = q.shift(); + + console.log([coin, amt, bag]); + + if (amt === 0) { + result.add(bag); + } else if (amt < 0) { + continue; + } else { + for (const c of coins) { + const bagCopy = new Map(bag); + const value = bagCopy.get(c); + bagCopy.set(c, value + 1); + q.push([c, amt - c, bagCopy]); + } + } + } + console.log(result); + return result.size; +} + +// Tests +let desc = "sample input"; +let actual = changePossibilities(4, [1, 2, 3]); +let expected = 4; +assertEqual(actual, expected, desc); + +desc = "one way to make zero cents"; +actual = changePossibilities(0, [1, 2]); +expected = 1; +assertEqual(actual, expected, desc); + +desc = "no ways if no coins"; +actual = changePossibilities(1, []); +expected = 0; +assertEqual(actual, expected, desc); + +desc = "big coin value"; +actual = changePossibilities(5, [25, 50]); +expected = 0; +assertEqual(actual, expected, desc); + +desc = "big target amount"; +actual = changePossibilities(50, [5, 10]); +expected = 6; +assertEqual(actual, expected, desc); + +// I think InterviewCake designed this assertion to be computationally +// expensive. +desc = "change for one dollar"; +actual = changePossibilities(100, [1, 5, 10, 25, 50]); +expected = 292; +assertEqual(actual, expected, desc); + +function assertEqual(a, b, desc) { + if (a === b) { + console.log(`${desc} ... PASS`); + } else { + console.log(`${desc} ... FAIL: ${a} != ${b}`); + } +} diff --git a/users/wpcarro/scratch/deepmind/part_two/delete-node.py b/users/wpcarro/scratch/deepmind/part_two/delete-node.py new file mode 100644 index 000000000000..4ed02ec30832 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/delete-node.py @@ -0,0 +1,57 @@ +import unittest + + +def delete_node(node): + if node.next: + node.value = node.next.value + node.next = node.next.next + else: + raise Exception( + "We cannot delete the last node in a linked list using this function" + ) + + +# 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 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_node_at_beginning(self): + delete_node(self.first) + actual = self.first.get_values() + expected = [2, 3, 4] + self.assertEqual(actual, expected) + + def test_node_in_middle(self): + delete_node(self.second) + actual = self.first.get_values() + expected = [1, 3, 4] + self.assertEqual(actual, expected) + + def test_node_at_end(self): + with self.assertRaises(Exception): + delete_node(self.fourth) + + def test_one_node_in_list(self): + unique = Test.LinkedListNode(1) + with self.assertRaises(Exception): + delete_node(unique) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/deepmind/part_two/find-duplicate-optimize-for-space-beast-mode.py b/users/wpcarro/scratch/deepmind/part_two/find-duplicate-optimize-for-space-beast-mode.py new file mode 100644 index 000000000000..c9edc32c8856 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/find-duplicate-optimize-for-space-beast-mode.py @@ -0,0 +1,114 @@ +import unittest + + +################################################################################ +# InterviewCake's solution +################################################################################ +def cycle_len(xs, i): + """ + Returns the length of a cycle that contains no duplicate items. + """ + result = 1 + checkpt = i + current = xs[checkpt - 1] + + while current != checkpt: + current = xs[current - 1] + result += 1 + + return result + + +def theirs(xs): + """ + This is InterviewCake's solution. + """ + i = xs[-1] + for _ in range(len(xs) - 1): + i = xs[i - 1] + + cycle_length = cycle_len(xs, i) + + p0 = xs[-1] + p1 = xs[-1] + for _ in range(cycle_length): + p1 = xs[p1 - 1] + + while p0 != p1: + p0 = xs[p0 - 1] + p1 = xs[p1 - 1] + + print(p0, p1) + + return p0 + + +################################################################################ +# My solution +################################################################################ +def mine(xs): + """ + This is the solution that I came up with, which differs from InterviewCake's + solution. + """ + i = xs[-1] + offset = 1 if len(xs) % 2 == 0 else 2 + + for _ in range(len(xs) - offset): + i = xs[i - 1] + + return i + + +use_mine = True +find_duplicate = mine if use_mine else theirs + + +# Tests +class Test(unittest.TestCase): + def test_just_the_repeated_number(self): + # len(xs) even + actual = find_duplicate([1, 1]) + expected = 1 + self.assertEqual(actual, expected) + + def test_short_list(self): + # len(xs) even + actual = find_duplicate([1, 2, 3, 2]) + expected = 2 + self.assertEqual(actual, expected) + + def test_medium_list(self): + # len(xs) even + actual = find_duplicate([1, 2, 5, 5, 5, 5]) + expected = 5 + self.assertEqual(actual, expected) + + def test_long_list(self): + # len(xs) odd + actual = find_duplicate([4, 1, 4, 8, 3, 2, 7, 6, 5]) + expected = 4 + self.assertEqual(actual, expected) + + ############################################################################ + # Additional examples from InterviewCake.com + ############################################################################ + def test_example_a(self): + # len(xs) even + actual = find_duplicate([3, 4, 2, 3, 1, 5]) + expected = 3 + self.assertTrue(actual, expected) + + def test_example_b(self): + # len(xs) even + actual = find_duplicate([3, 1, 2, 2]) + expected = 2 + self.assertEqual(actual, expected) + + def test_example_c(self): + # len(xs) odd BUT multiple duplicates + actual = find_duplicate([4, 3, 1, 1, 4]) + self.assertTrue(actual in {1, 4}) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/deepmind/part_two/find-duplicate-optimize-for-space.ts b/users/wpcarro/scratch/deepmind/part_two/find-duplicate-optimize-for-space.ts new file mode 100644 index 000000000000..98f5bb144e76 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/find-duplicate-optimize-for-space.ts @@ -0,0 +1,70 @@ +function findRepeatBruteForce(xs: Array<number>): number { + // InterviewCake asks us to write a function that optimizes for space. Using + // brute force, we can write a function that returns an answer using constant + // (i.e. O(1)) space at the cost of a quadratic (i.e. O(n^2)) runtime. + // + // I did not think of this myself; InterviewCake's "Tell me more" hints + // did. Since I think this idea is clever, I wrote a solution from memory to + // help me internalize the solution. + for (let i = 0; i < xs.length; i += 1) { + let seeking = xs[i]; + for (let j = i + 1; j < xs.length; j += 1) { + if (xs[j] === seeking) { + return seeking; + } + } + } +} + +function findRepeatSort(xs: Array<number>): number { + // This version first sorts xs, which gives the function a time-complexity of + // O(n*log(n)), which is better than the quadratic complexity of the + // brute-force solution. The space requirement here is constant. + // + // Since we need to sort xs in-place to avoid paying a O(n) space cost for + // storing the newly sorted xs, we're mutating our input. InterviewCake + // advises us to not mutate our input. + xs.sort(); + let i = 0; + let j = 1; + for (; j < xs.length; ) { + if (xs[i] === xs[j]) { + return xs[i]; + } + i += 1; + j += 1; + } +} + +function findRepeat(xs: Array<number>): number { + return 0; +} + +// Tests +let desc = "just the repeated number"; +let actual = findRepeat([1, 1]); +let expected = 1; +assertEqual(actual, expected, desc); + +desc = "short array"; +actual = findRepeat([1, 2, 3, 2]); +expected = 2; +assertEqual(actual, expected, desc); + +desc = "medium array"; +actual = findRepeat([1, 2, 5, 5, 5, 5]); +expected = 5; +assertEqual(actual, expected, desc); + +desc = "long array"; +actual = findRepeat([4, 1, 4, 8, 3, 2, 7, 6, 5]); +expected = 4; +assertEqual(actual, expected, desc); + +function assertEqual(a, b, desc) { + if (a === b) { + console.log(`${desc} ... PASS`); + } else { + console.log(`${desc} ... FAIL: ${a} != ${b}`); + } +} diff --git a/users/wpcarro/scratch/deepmind/part_two/find-rotation-point.ts b/users/wpcarro/scratch/deepmind/part_two/find-rotation-point.ts new file mode 100644 index 000000000000..7bf1a484454d --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/find-rotation-point.ts @@ -0,0 +1,68 @@ +function findRotationPoint(xs: Array<string>): number { + // Find the rotation point in the vector. + let beg = 0; + let end = xs.length - 1; + + while (beg != end) { + let mid = beg + Math.floor((end - beg) / 2); + + if (beg === mid) { + return xs[beg] < xs[end] ? beg : end; + } + + if (xs[end] <= xs[mid]) { + beg = mid; + end = end; + } else { + beg = beg; + end = mid; + } + } + + return beg; +} + +// Tests +let desc; +let actual; +let expected; + +desc = "small array one"; +actual = findRotationPoint(["cape", "cake"]); +expected = 1; +assertEquals(actual, expected, desc); + +desc = "small array two"; +actual = findRotationPoint(["cake", "cape"]); +expected = 0; +assertEquals(actual, expected, desc); + +desc = "medium array"; +actual = findRotationPoint(["grape", "orange", "plum", "radish", "apple"]); +expected = 4; +assertEquals(actual, expected, desc); + +desc = "large array"; +actual = findRotationPoint([ + "ptolemaic", + "retrograde", + "supplant", + "undulate", + "xenoepist", + "asymptote", + "babka", + "banoffee", + "engender", + "karpatka", + "othellolagkage" +]); +expected = 5; +assertEquals(actual, expected, desc); + +function assertEquals(a, b, desc) { + if (a === b) { + console.log(`${desc} ... PASS`); + } else { + console.log(`${desc} ... FAIL: ${a} != ${b}`); + } +} diff --git a/users/wpcarro/scratch/deepmind/part_two/graph-coloring.ts b/users/wpcarro/scratch/deepmind/part_two/graph-coloring.ts new file mode 100644 index 000000000000..a0b6d5dbae53 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/graph-coloring.ts @@ -0,0 +1,232 @@ +type Color = string; + +interface GraphNode { + label: string; + neighbors: Set<GraphNode>; + color: string; +} + +class GraphNode { + constructor(label: string) { + this.label = label; + this.neighbors = new Set(); + this.color = null; + } +} + +interface Queue<A> { + xs: Array<A>; +} + +class Queue<A> { + constructor() { + this.xs = []; + } + isEmpty(): boolean { + return this.xs.length === 0; + } + enqueue(x: A): void { + this.xs.push(x); + } + dequeue(): A { + return this.xs.shift(); + } +} + +type Graph = Array<GraphNode>; + +// Return a set of all of the colors from the neighbor nodes of `node`. +function neighborColors(node: GraphNode): Set<Color> { + const result: Set<Color> = new Set(); + + for (const x of node.neighbors) { + if (typeof x.color === 'string') { + result.add(x.color); + } + } + + return result; +} + +// Returns the set difference between sets `xs`, and `ys`. +function setDifference<A>(xs: Set<A>, ys: Set<A>): Set<A> { + const result: Set<A> = new Set(); + + for (const x of xs) { + if (!ys.has(x)) { + result.add(x); + } + } + + return result; +} + +// Returns an element from the set, `xs`. +// Throwns an error if `xs` is an empty set. +function choose<A>(xs: Set<A>): A { + if (xs.size === 0) { + throw new Error('Cannot choose an element from an empty set.'); + } else { + return xs.values().next().value; + } +} + +// Returns true if `node` is present in `node.neighbors`. +function isCyclic(node: GraphNode): boolean { + for (const x of node.neighbors) { + if (x === node) { + return true; + } + } +} + +function colorGraph(graph: Graph, colors: Array<Color>): void { + const allColors = new Set(colors); + + for (const node of graph) { + if (isCyclic(node)) { + throw new Error('InterviewCake would like me to invalidate this'); + } + if (typeof node.color !== 'string') { + node.color = choose(setDifference(allColors, neighborColors(node))); + } + } +} + + +// Tests +const colors = ['red', 'green', 'blue', 'orange', 'yellow', 'white']; + +let graph = []; +{ + const nodeA = new GraphNode('A'); + const nodeB = new GraphNode('B'); + const nodeC = new GraphNode('C'); + const nodeD = new GraphNode('D'); + nodeA.neighbors.add(nodeB); + nodeB.neighbors.add(nodeA); + nodeB.neighbors.add(nodeC); + nodeC.neighbors.add(nodeB); + nodeC.neighbors.add(nodeD); + nodeD.neighbors.add(nodeC); + graph = [nodeA, nodeB, nodeC, nodeD]; +} +colorGraph(graph, colors); +assertEqual(validateGraphColoring(graph), true, 'line graph'); + +{ + const nodeA = new GraphNode('A'); + const nodeB = new GraphNode('B'); + const nodeC = new GraphNode('C'); + const nodeD = new GraphNode('D'); + nodeA.neighbors.add(nodeB); + nodeB.neighbors.add(nodeA); + nodeC.neighbors.add(nodeD); + nodeD.neighbors.add(nodeC); + graph = [nodeA, nodeB, nodeC, nodeD]; +} +colorGraph(graph, colors); +assertEqual(validateGraphColoring(graph), true, 'separate graph'); + +{ + const nodeA = new GraphNode('A'); + const nodeB = new GraphNode('B'); + const nodeC = new GraphNode('C'); + nodeA.neighbors.add(nodeB); + nodeA.neighbors.add(nodeC); + nodeB.neighbors.add(nodeA); + nodeB.neighbors.add(nodeC); + nodeC.neighbors.add(nodeA); + nodeC.neighbors.add(nodeB); + graph = [nodeA, nodeB, nodeC]; +} +colorGraph(graph, colors); +assertEqual(validateGraphColoring(graph), true, 'triangle graph'); + +{ + const nodeA = new GraphNode('A'); + const nodeB = new GraphNode('B'); + const nodeC = new GraphNode('C'); + const nodeD = new GraphNode('D'); + const nodeE = new GraphNode('E'); + nodeA.neighbors.add(nodeB); + nodeA.neighbors.add(nodeC); + nodeB.neighbors.add(nodeA); + nodeB.neighbors.add(nodeC); + nodeB.neighbors.add(nodeD); + nodeB.neighbors.add(nodeE); + nodeC.neighbors.add(nodeA); + nodeC.neighbors.add(nodeB); + nodeC.neighbors.add(nodeD); + nodeC.neighbors.add(nodeE); + nodeD.neighbors.add(nodeB); + nodeD.neighbors.add(nodeC); + nodeD.neighbors.add(nodeE); + nodeE.neighbors.add(nodeB); + nodeE.neighbors.add(nodeC); + nodeE.neighbors.add(nodeD); + graph = [nodeA, nodeB, nodeC, nodeD, nodeE]; +} +colorGraph(graph, colors); +assertEqual(validateGraphColoring(graph), true, 'envelope graph'); + +{ + const nodeA = new GraphNode('A'); + nodeA.neighbors.add(nodeA); + graph = [nodeA]; +} +assertThrows(() => { + colorGraph(graph, colors); +}, 'loop graph'); + +function validateGraphColoring(graph) { + + const maxDegree = Math.max(...graph.map(node => node.neighbors.size)); + + const colorsUsed = new Set(); + + graph.forEach(node => { + colorsUsed.add(node.color); + }); + + if (colorsUsed.has(null)) { + return false; + } + + if (colorsUsed.size > maxDegree + 1) { + return false; + } + + let badEdges = 0; + + graph.forEach(node => { + node.neighbors.forEach(neighbor => { + if (neighbor.color === node.color) { + badEdges += 1; + } + }); + }); + + if (badEdges > 0) { + return false; + } + + return true; +} + +function assertEqual(a, b, desc) { + if (a === b) { + console.log(`${desc} ... PASS`); + } else { + console.log(`${desc} ... FAIL: ${a} != ${b}`); + } +} + +function assertThrows(func, desc) { + try { + func(); + console.log(`${desc} ... FAIL`); + } catch (e) { + console.log(`${desc} ... PASS`); + } +} diff --git a/users/wpcarro/scratch/deepmind/part_two/highest-product-of-3.py b/users/wpcarro/scratch/deepmind/part_two/highest-product-of-3.py new file mode 100644 index 000000000000..8ebb5cf29a4f --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/highest-product-of-3.py @@ -0,0 +1,81 @@ +import unittest +import sys +import trace + + +def highest_product_of_3(xs): + if len(xs) < 3: + raise Exception("List needs to contain at least three elements.") + hp3 = xs[0] * xs[1] * xs[2] + hp2 = xs[0] * xs[1] + lp2 = xs[0] * xs[1] + hn = max(xs[0], xs[1]) + ln = min(xs[0], xs[1]) + for x in xs[2:]: + hp3 = max(hp3, hp2 * x, lp2 * x) + hp2 = max(hp2, hn * x, ln * x) + lp2 = min(lp2, hn * x, ln * x) + hn = max(hn, x) + ln = min(ln, x) + return hp3 + + +# Tests +class Test(unittest.TestCase): + def test_short_list(self): + actual = highest_product_of_3([1, 2, 3, 4]) + expected = 24 + self.assertEqual(actual, expected) + + def test_longer_list(self): + actual = highest_product_of_3([6, 1, 3, 5, 7, 8, 2]) + expected = 336 + self.assertEqual(actual, expected) + + def test_list_has_one_negative(self): + actual = highest_product_of_3([-5, 4, 8, 2, 3]) + expected = 96 + self.assertEqual(actual, expected) + + def test_list_has_two_negatives(self): + actual = highest_product_of_3([-10, 1, 3, 2, -10]) + expected = 300 + self.assertEqual(actual, expected) + + def test_list_is_all_negatives(self): + actual = highest_product_of_3([-5, -1, -3, -2]) + expected = -6 + self.assertEqual(actual, expected) + + def test_error_with_empty_list(self): + with self.assertRaises(Exception): + highest_product_of_3([]) + + def test_error_with_one_number(self): + with self.assertRaises(Exception): + highest_product_of_3([1]) + + def test_error_with_two_numbers(self): + with self.assertRaises(Exception): + highest_product_of_3([1, 1]) + + def test_custom(self): + actual = highest_product_of_3([9, 5, 2, 1, 7, 3]) + expected = 9 * 7 * 5 + self.assertEqual(actual, expected) + + +unittest.main(verbosity=2) + + +def main(): + highest_product_of_3([-5, -1, -3, -2]) + + +tracer = trace.Trace(ignoredirs=[sys.prefix, sys.exec_prefix], + trace=0, + count=1) + +tracer.run('main()') +r = tracer.results() +r.write_results(show_missing=True, coverdir=".") diff --git a/users/wpcarro/scratch/deepmind/part_two/inflight-entertainment.ts b/users/wpcarro/scratch/deepmind/part_two/inflight-entertainment.ts new file mode 100644 index 000000000000..d6da1db3d313 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/inflight-entertainment.ts @@ -0,0 +1,85 @@ +function canTwoMoviesFillFlightBonus( + xs: Array<number>, + duration: number +): boolean { + // Returns true if two movies exist that can fill the flight duration +/- 20 + // minutes. + const seeking = {}; + + for (let x of xs) { + for (let i = 0; i < 40; i += 1) { + if (seeking[x + i + 1]) { + return true; + } + } + for (let i = 1; i <= 20; i += 1) { + seeking[duration - x - i] = true; + seeking[duration - x + i] = true; + } + } + + return false; +} + +function canTwoMoviesFillFlight(xs: Array<number>, duration: number): boolean { + const seeking = {}; + + for (let x of xs) { + if (seeking[x]) { + return true; + } else { + seeking[duration - x] = true; + } + } + + return false; +} + +// Tests +let desc = "short flight"; +let actual = canTwoMoviesFillFlight([2, 4], 1); +let expected = false; +assertEquals(actual, expected, desc); + +desc = "long flight"; +actual = canTwoMoviesFillFlight([2, 4], 6); +expected = true; +assertEquals(actual, expected, desc); + +desc = "one movie half flight length"; +actual = canTwoMoviesFillFlight([3, 8], 6); +expected = false; +assertEquals(actual, expected, desc); + +desc = "two movies half flight length"; +actual = canTwoMoviesFillFlight([3, 8, 3], 6); +expected = true; +assertEquals(actual, expected, desc); + +desc = "lots of possible pairs"; +actual = canTwoMoviesFillFlight([1, 2, 3, 4, 5, 6], 7); +expected = true; +assertEquals(actual, expected, desc); + +desc = "not using first movie"; +actual = canTwoMoviesFillFlight([4, 3, 2], 5); +expected = true; +assertEquals(actual, expected, desc); + +desc = "only one movie"; +actual = canTwoMoviesFillFlight([6], 6); +expected = false; +assertEquals(actual, expected, desc); + +desc = "no movies"; +actual = canTwoMoviesFillFlight([], 2); +expected = false; +assertEquals(actual, expected, desc); + +function assertEquals(a, b, desc) { + if (a === b) { + console.log(`${desc} ... PASS`); + } else { + console.log(`${desc} ... FAIL: ${a} != ${b}`); + } +} diff --git a/users/wpcarro/scratch/deepmind/part_two/merge-sorted-arrays.ts b/users/wpcarro/scratch/deepmind/part_two/merge-sorted-arrays.ts new file mode 100644 index 000000000000..2d478e0e37de --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/merge-sorted-arrays.ts @@ -0,0 +1,63 @@ +function mergeArrays(xs: Array<number>, ys: Array<number>): Array<number> { + let i = 0; + let j = 0; + const result = []; + + for (let q = 0; q < xs.length + ys.length; q += 1) { + if (i === xs.length) { + while (j < ys.length) { + result.push(ys[j]); + j += 1; + } + } else if (j === ys.length) { + while (i < xs.length) { + result.push(xs[i]); + i += 1; + } + } else if (xs[i] < ys[j]) { + result.push(xs[i]); + i += 1; + } else { + result.push(ys[j]); + j += 1; + } + } + + return result; +} + +// Tests +let desc = "both arrays are empty"; +let actual = mergeArrays([], []); +let expected = []; +assertDeepEqual(actual, expected, desc); + +desc = "first array is empty"; +actual = mergeArrays([], [1, 2, 3]); +expected = [1, 2, 3]; +assertDeepEqual(actual, expected, desc); + +desc = "second array is empty"; +actual = mergeArrays([5, 6, 7], []); +expected = [5, 6, 7]; +assertDeepEqual(actual, expected, desc); + +desc = "both arrays have some numbers"; +actual = mergeArrays([2, 4, 6], [1, 3, 7]); +expected = [1, 2, 3, 4, 6, 7]; +assertDeepEqual(actual, expected, desc); + +desc = "arrays are different lengths"; +actual = mergeArrays([2, 4, 6, 8], [1, 7]); +expected = [1, 2, 4, 6, 7, 8]; +assertDeepEqual(actual, expected, desc); + +function assertDeepEqual(a: Array<number>, b: Array<number>, desc: string) { + const aStr = JSON.stringify(a); + const bStr = JSON.stringify(b); + if (aStr !== bStr) { + console.log(`${desc} ... FAIL: ${aStr} != ${bStr}`); + } else { + console.log(`${desc} ... PASS`); + } +} diff --git a/users/wpcarro/scratch/deepmind/part_two/merging-ranges.py b/users/wpcarro/scratch/deepmind/part_two/merging-ranges.py new file mode 100644 index 000000000000..23d0813d1524 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/merging-ranges.py @@ -0,0 +1,115 @@ +import unittest +import timeit + + +# Solution that uses O(n) space to store the result. +def not_in_place(xs): + xs.sort() + result = [xs[0]] + for ca, cb in xs[1:]: + pa, pb = result[-1] + if ca <= pb: + result[-1] = (pa, max(pb, cb)) + else: + result.append((ca, cb)) + return result + + +# Solution that uses O(1) space to store the result. +def in_place(xs): + xs.sort() + i = 0 + j = i + 1 + while j < len(xs): + pa, pb = xs[i] + ca, cb = xs[j] + if ca <= pb: + xs[i] = (pa, max(pb, cb)) + del xs[j] + else: + i = j + j += 1 + return xs + + +def test_nip(): + inputs = [ + [(1, 3), (2, 4)], + [(5, 6), (6, 8)], + [(1, 8), (2, 5)], + [(1, 3), (4, 8)], + [(1, 4), (2, 5), (5, 8)], + [(5, 8), (1, 4), (6, 8)], + [(1, 10), (2, 5), (6, 8), (9, 10), (10, 12)], + [(0, 1), (3, 5), (4, 8), (10, 12), (9, 10)], + ] + for x in inputs: + not_in_place(x) + + +def test_ip(): + inputs = [ + [(1, 3), (2, 4)], + [(5, 6), (6, 8)], + [(1, 8), (2, 5)], + [(1, 3), (4, 8)], + [(1, 4), (2, 5), (5, 8)], + [(5, 8), (1, 4), (6, 8)], + [(1, 10), (2, 5), (6, 8), (9, 10), (10, 12)], + [(0, 1), (3, 5), (4, 8), (10, 12), (9, 10)], + ] + for x in inputs: + in_place(x) + + +merge_ranges = in_place + +setup = 'from __main__ import test_nip, test_ip' +print(timeit.timeit('test_nip()', number=10000, setup=setup)) +print(timeit.timeit('test_ip()', number=10000, setup=setup)) + + +# 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_two/mesh-message.py b/users/wpcarro/scratch/deepmind/part_two/mesh-message.py new file mode 100644 index 000000000000..a265296ab066 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/mesh-message.py @@ -0,0 +1,183 @@ +import unittest +from collections import deque +from heapq import heappush, heappop + + +################################################################################ +# InterviewCake.com +################################################################################ +# construct_path :: Map String String -> String -> String -> [String] +def construct_path(paths, beg, end): + """ + Reconstruct the path from `beg` to `end`. + """ + result = [] + current = end + + print(paths) + print(beg, end) + print('-----') + while current: + result.append(current) + current = paths[current] + + result.reverse() + return result + + +def get_path_ic(graph, beg, end): + """ + InterviewCake uses a dictionary and back-tracking to store and reconstruct + the path instead of storing the path as state on each node. + This reduces the memory costs. See get_path_bft for an example of this less + optimal solution. + """ + if beg not in graph: + raise Exception('Origin node absent from graph.') + + if end not in graph: + raise Exception('Destination node absent from graph.') + + q = deque() + q.append(beg) + paths = {beg: None} + + while q: + node = q.popleft() + + if node == end: + print(graph) + return construct_path(paths, beg, end) + + for x in graph[node]: + if x not in paths: + paths[x] = node + q.append(x) + + return None + + +################################################################################ +# Per-node state +################################################################################ +def get_path_bft(graph, beg, end): + """ + Here we find the shortest path from `beg` to `end` in `graph` by doing a BFT + from beg to end and storing the path state alongside each node in the queue. + """ + if beg not in graph: + raise Exception('Origin node absent from graph.') + + if end not in graph: + raise Exception('Destination node absent from graph.') + + q = deque() + seen = set() + q.append([beg]) + + while q: + path = q.popleft() + node = path[-1] + seen.add(node) + + if node == end: + return path + + for x in graph[node]: + if x not in seen: + q.append(path + [x]) + + +################################################################################ +# Dijkstra's Algorithm +################################################################################ +def get_path(graph, beg, end): + """ + Here we find the shortest path using Dijkstra's algorithm, which is my + favorite solution. + """ + if beg not in graph: + raise Exception( + 'The origin node, {}, is not present in the graph'.format(beg)) + + if end not in graph: + raise Exception( + 'The origin node, {}, is not present in the graph'.format(end)) + + q = [] + seen = set() + heappush(q, (1, [beg])) + + while q: + weight, path = heappop(q) + node = path[-1] + seen.add(node) + + if node == end: + return path + + for x in graph[node]: + if x not in seen: + heappush(q, (weight + 1, path + [x])) + + return None + + +# Tests +class Test(unittest.TestCase): + def setUp(self): + self.graph = { + 'a': ['b', 'c', 'd'], + 'b': ['a', 'd'], + 'c': ['a', 'e'], + 'd': ['b', 'a'], + 'e': ['c'], + 'f': ['g'], + 'g': ['f'], + } + + def test_two_hop_path_1(self): + actual = get_path(self.graph, 'a', 'e') + expected = ['a', 'c', 'e'] + self.assertEqual(actual, expected) + + def test_two_hop_path_2(self): + actual = get_path(self.graph, 'd', 'c') + expected = ['d', 'a', 'c'] + self.assertEqual(actual, expected) + + def test_one_hop_path_1(self): + actual = get_path(self.graph, 'a', 'c') + expected = ['a', 'c'] + self.assertEqual(actual, expected) + + def test_one_hop_path_2(self): + actual = get_path(self.graph, 'f', 'g') + expected = ['f', 'g'] + self.assertEqual(actual, expected) + + def test_one_hop_path_3(self): + actual = get_path(self.graph, 'g', 'f') + expected = ['g', 'f'] + self.assertEqual(actual, expected) + + def test_zero_hop_path(self): + actual = get_path(self.graph, 'a', 'a') + expected = ['a'] + self.assertEqual(actual, expected) + + def test_no_path(self): + actual = get_path(self.graph, 'a', 'f') + expected = None + self.assertEqual(actual, expected) + + def test_start_node_not_present(self): + with self.assertRaises(Exception): + get_path(self.graph, 'h', 'a') + + def test_end_node_not_present(self): + with self.assertRaises(Exception): + get_path(self.graph, 'a', 'h') + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/deepmind/part_two/misc/matrix-traversals.py b/users/wpcarro/scratch/deepmind/part_two/misc/matrix-traversals.py new file mode 100644 index 000000000000..52354f990e11 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/misc/matrix-traversals.py @@ -0,0 +1,104 @@ +# Herein I'm practicing two-dimensional matrix traversals in all directions of +# which I can conceive: +# 0. T -> B; L -> R +# 1. T -> B; R -> L +# 2. B -> T; L -> R +# 3. B -> T; R -> L +# +# Commentary: +# When I think of matrices, I'm reminded of cartesian planes. I think of the +# cells as (X,Y) coordinates. This has been a pitfall for me because matrices +# are usually encoded in the opposite way. That is, to access a cell at the +# coordinates (X,Y) given a matrix M, you index M like this: M[Y][X]. To attempt +# to avoid this confusion, instead of saying X and Y, I will prefer saying +# "column" and "row". +# +# When traversing a matrix, you typically traverse vertically and then +# horizontally; in other words, the rows come first followed by the columns. As +# such, I'd like to refer to traversal orders as "top-to-bottom, left-to-right" +# rather than "left-to-right, top-to-bottom". +# +# These practices are all in an attempt to rewire my thinking. + +# This is a list of matrices where the index of a matrix corresponds to the +# order in which it should be traversed to produce the sequence: +# [1,2,3,4,5,6,7,8,9]. +boards = [[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[3, 2, 1], [6, 5, 4], [9, 8, 7]], + [[7, 8, 9], [4, 5, 6], [1, 2, 3]], [[9, 8, 7], [6, 5, 4], [3, 2, 1]]] + +# T -> B; L -> R +board = boards[0] +result = [] +for row in board: + for col in row: + result.append(col) +print(result) + +# T -> B; R -> L +board = boards[1] +result = [] +for row in board: + for col in reversed(row): + result.append(col) +print(result) + +# B -> T; L -> R +board = boards[2] +result = [] +for row in reversed(board): + for col in row: + result.append(col) +print(result) + +# B -> T; R -> L +board = boards[3] +result = [] +for row in reversed(board): + for col in reversed(row): + result.append(col) +print(result) + +################################################################################ +# Neighbors +################################################################################ + +import random + + +# Generate a matrix of size `rows` x `cols` where each cell contains an item +# randomly selected from `xs`. +def generate_board(rows, cols, xs): + result = [] + for _ in range(rows): + row = [] + for _ in range(cols): + row.append(random.choice(xs)) + result.append(row) + return result + + +# Print the `board` to the screen. +def print_board(board): + print('\n'.join([' '.join(row) for row in board])) + + +board = generate_board(4, 5, ['R', 'G', 'B']) +print_board(board) + + +# Return all of the cells horizontally and vertically accessible from a starting +# cell at `row`, `col` in `board`. +def neighbors(row, col, board): + result = {'top': [], 'bottom': [], 'left': [], 'right': []} + for i in range(row - 1, -1, -1): + result['top'].append(board[i][col]) + for i in range(row + 1, len(board)): + result['bottom'].append(board[i][col]) + for i in range(col - 1, -1, -1): + result['left'].append(board[row][i]) + for i in range(col + 1, len(board[0])): + result['right'].append(board[row][i]) + return result + + +print(neighbors(1, 2, board)) diff --git a/users/wpcarro/scratch/deepmind/part_two/nth-fibonacci.py b/users/wpcarro/scratch/deepmind/part_two/nth-fibonacci.py new file mode 100644 index 000000000000..14e176b62aab --- /dev/null +++ b/users/wpcarro/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) diff --git a/users/wpcarro/scratch/deepmind/part_two/package-lock.json b/users/wpcarro/scratch/deepmind/part_two/package-lock.json new file mode 100644 index 000000000000..340aad9f5ce2 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/package-lock.json @@ -0,0 +1,79 @@ +{ + "name": "deepmind-part-two", + "version": "1.0.0", + "lockfileVersion": 1, + "requires": true, + "dependencies": { + "arg": { + "version": "4.1.3", + "resolved": "https://registry.npmjs.org/arg/-/arg-4.1.3.tgz", + "integrity": "sha512-58S9QDqG0Xx27YwPSt9fJxivjYl432YCwfDMfZ+71RAqUrZef7LrKQZ3LHLOwCS4FLNBplP533Zx895SeOCHvA==", + "dev": true + }, + "buffer-from": { + "version": "1.1.1", + "resolved": "https://registry.npmjs.org/buffer-from/-/buffer-from-1.1.1.tgz", + "integrity": "sha512-MQcXEUbCKtEo7bhqEs6560Hyd4XaovZlO/k9V3hjVUF/zwW7KBVdSK4gIt/bzwS9MbR5qob+F5jusZsb0YQK2A==", + "dev": true + }, + "diff": { + "version": "4.0.2", + "resolved": "https://registry.npmjs.org/diff/-/diff-4.0.2.tgz", + "integrity": "sha512-58lmxKSA4BNyLz+HHMUzlOEpg09FV+ev6ZMe3vJihgdxzgcwZ8VoEEPmALCZG9LmqfVoNMMKpttIYTVG6uDY7A==", + "dev": true + }, + "make-error": { + "version": "1.3.5", + "resolved": "https://registry.npmjs.org/make-error/-/make-error-1.3.5.tgz", + "integrity": "sha512-c3sIjNUow0+8swNwVpqoH4YCShKNFkMaw6oH1mNS2haDZQqkeZFlHS3dhoeEbKKmJB4vXpJucU6oH75aDYeE9g==", + "dev": true + }, + "prettier": { + "version": "2.0.2", + "resolved": "https://registry.npmjs.org/prettier/-/prettier-2.0.2.tgz", + "integrity": "sha512-5xJQIPT8BraI7ZnaDwSbu5zLrB6vvi8hVV58yHQ+QK64qrY40dULy0HSRlQ2/2IdzeBpjhDkqdcFBnFeDEMVdg==", + "dev": true + }, + "source-map": { + "version": "0.6.1", + "resolved": "https://registry.npmjs.org/source-map/-/source-map-0.6.1.tgz", + "integrity": "sha512-UjgapumWlbMhkBgzT7Ykc5YXUT46F0iKu8SGXq0bcwP5dz/h0Plj6enJqjz1Zbq2l5WaqYnrVbwWOWMyF3F47g==", + "dev": true + }, + "source-map-support": { + "version": "0.5.16", + "resolved": "https://registry.npmjs.org/source-map-support/-/source-map-support-0.5.16.tgz", + "integrity": "sha512-efyLRJDr68D9hBBNIPWFjhpFzURh+KJykQwvMyW5UiZzYwoF6l4YMMDIJJEyFWxWCqfyxLzz6tSfUFR+kXXsVQ==", + "dev": true, + "requires": { + "buffer-from": "^1.0.0", + "source-map": "^0.6.0" + } + }, + "ts-node": { + "version": "8.6.2", + "resolved": "https://registry.npmjs.org/ts-node/-/ts-node-8.6.2.tgz", + "integrity": "sha512-4mZEbofxGqLL2RImpe3zMJukvEvcO1XP8bj8ozBPySdCUXEcU5cIRwR0aM3R+VoZq7iXc8N86NC0FspGRqP4gg==", + "dev": true, + "requires": { + "arg": "^4.1.0", + "diff": "^4.0.1", + "make-error": "^1.1.1", + "source-map-support": "^0.5.6", + "yn": "3.1.1" + } + }, + "typescript": { + "version": "3.7.5", + "resolved": "https://registry.npmjs.org/typescript/-/typescript-3.7.5.tgz", + "integrity": "sha512-/P5lkRXkWHNAbcJIiHPfRoKqyd7bsyCma1hZNUGfn20qm64T6ZBlrzprymeu918H+mB/0rIg2gGK/BXkhhYgBw==", + "dev": true + }, + "yn": { + "version": "3.1.1", + "resolved": "https://registry.npmjs.org/yn/-/yn-3.1.1.tgz", + "integrity": "sha512-Ux4ygGWsu2c7isFWe8Yu1YluJmqVhxqK2cLXNQA5AcC3QfbGNpM7fu0Y8b/z16pXLnFxZYvWhd3fhBY9DLmC6Q==", + "dev": true + } + } +} diff --git a/users/wpcarro/scratch/deepmind/part_two/package.json b/users/wpcarro/scratch/deepmind/part_two/package.json new file mode 100644 index 000000000000..1f10668ec861 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/package.json @@ -0,0 +1,16 @@ +{ + "name": "deepmind-part-two", + "version": "1.0.0", + "description": "Practicing coding interview questions", + "main": "index.js", + "scripts": { + "test": "echo \"Error: no test specified\" && exit 1" + }, + "author": "William Carroll", + "license": "MIT", + "devDependencies": { + "prettier": "^2.0.2", + "ts-node": "^8.6.2", + "typescript": "^3.7.5" + } +} diff --git a/users/wpcarro/scratch/deepmind/part_two/permutation-palindrome.py b/users/wpcarro/scratch/deepmind/part_two/permutation-palindrome.py new file mode 100644 index 000000000000..730b4bfdc873 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/permutation-palindrome.py @@ -0,0 +1,37 @@ +import unittest +from collections import Counter + + +def has_palindrome_permutation(xs): + vs = Counter(xs).values() + return len([v for v in vs if v % 2 == 1]) in {0, 1} + + +# Tests +class Test(unittest.TestCase): + def test_permutation_with_odd_number_of_chars(self): + result = has_palindrome_permutation('aabcbcd') + self.assertTrue(result) + + def test_permutation_with_even_number_of_chars(self): + result = has_palindrome_permutation('aabccbdd') + self.assertTrue(result) + + def test_no_permutation_with_odd_number_of_chars(self): + result = has_palindrome_permutation('aabcd') + self.assertFalse(result) + + def test_no_permutation_with_even_number_of_chars(self): + result = has_palindrome_permutation('aabbcd') + self.assertFalse(result) + + def test_empty_string(self): + result = has_palindrome_permutation('') + self.assertTrue(result) + + def test_one_character_string(self): + result = has_palindrome_permutation('a') + self.assertTrue(result) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/deepmind/part_two/product-of-other-numbers.py b/users/wpcarro/scratch/deepmind/part_two/product-of-other-numbers.py new file mode 100644 index 000000000000..6f7858ff4e5b --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/product-of-other-numbers.py @@ -0,0 +1,68 @@ +import unittest + + +# get_products_of_all_ints_except_at_index :: [Int] -> [Int] +def get_products_of_all_ints_except_at_index(xs): + n = len(xs) + if n < 2: + raise Exception("Cannot computer without 2 or elements") + # lhs + befores = [None] * n + befores[0] = 1 + for i in range(1, n): + befores[i] = befores[i - 1] * xs[i - 1] + + # rhs + afters = [None] * n + afters[-1] = 1 + for i in range(n - 2, -1, -1): + afters[i] = afters[i + 1] * xs[i + 1] + + result = [None] * n + for i in range(n): + result[i] = befores[i] * afters[i] + return result + + +# Tests +class Test(unittest.TestCase): + def test_small_list(self): + actual = get_products_of_all_ints_except_at_index([1, 2, 3]) + expected = [6, 3, 2] + self.assertEqual(actual, expected) + + def test_longer_list(self): + actual = get_products_of_all_ints_except_at_index([8, 2, 4, 3, 1, 5]) + expected = [120, 480, 240, 320, 960, 192] + self.assertEqual(actual, expected) + + def test_list_has_one_zero(self): + actual = get_products_of_all_ints_except_at_index([6, 2, 0, 3]) + expected = [0, 0, 36, 0] + self.assertEqual(actual, expected) + + def test_list_has_two_zeros(self): + actual = get_products_of_all_ints_except_at_index([4, 0, 9, 1, 0]) + expected = [0, 0, 0, 0, 0] + self.assertEqual(actual, expected) + + def test_one_negative_number(self): + actual = get_products_of_all_ints_except_at_index([-3, 8, 4]) + expected = [32, -12, -24] + self.assertEqual(actual, expected) + + def test_all_negative_numbers(self): + actual = get_products_of_all_ints_except_at_index([-7, -1, -4, -2]) + expected = [-8, -56, -14, -28] + self.assertEqual(actual, expected) + + def test_error_with_empty_list(self): + with self.assertRaises(Exception): + get_products_of_all_ints_except_at_index([]) + + def test_error_with_one_number(self): + with self.assertRaises(Exception): + get_products_of_all_ints_except_at_index([1]) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/deepmind/part_two/recursive-string-permutations.ts b/users/wpcarro/scratch/deepmind/part_two/recursive-string-permutations.ts new file mode 100644 index 000000000000..cb930d9ad648 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/recursive-string-permutations.ts @@ -0,0 +1,85 @@ +// Returns a new string comprised of every characters in `xs` except for the +// character at `i`. +function everyOtherChar(xs: string, i: number): string[] { + const result = []; + + for (let j = 0; j < xs.length; j += 1) { + if (i !== j) { + result.push(xs[j]); + } + } + + return [xs[i], result.join('')]; +} + +function getPermutations(xs: string): Set<string> { + if (xs === '') { + return new Set(['']); + } + + const result: Set<string> = new Set; + + for (let i = 0; i < xs.length; i += 1) { + const [char, rest] = everyOtherChar(xs, i); + const perms = getPermutations(rest); + + for (const perm of perms) { + result.add(char + perm); + } + } + + return result; +} + +// Tests +let desc = 'empty string'; +let input = ''; +let actual = getPermutations(input); +let expected = new Set(['']); +assert(isSetsEqual(actual, expected), desc); + +desc = 'one character string'; +input = 'a'; +actual = getPermutations(input); +expected = new Set(['a']); +assert(isSetsEqual(actual, expected), desc); + +desc = 'two character string'; +input = 'ab'; +actual = getPermutations(input); +expected = new Set(['ab', 'ba']); +assert(isSetsEqual(actual, expected), desc); + +desc = 'three character string'; +input = 'abc'; +actual = getPermutations(input); +expected = new Set(['abc', 'acb', 'bac', 'bca', 'cab', 'cba']); +assert(isSetsEqual(actual, expected), desc); + +desc = 'four character string'; +input = 'abca'; +actual = getPermutations(input); +expected = new Set([ + 'abca', 'abac', 'acba', 'acab', 'aabc', 'aacb', 'baca', 'baac', 'bcaa', + 'bcaa', 'baac', 'baca', 'caba', 'caab', 'cbaa', 'cbaa', 'caab', 'caba', + 'aabc', 'aacb', 'abac', 'abca', 'acab', 'acba' +]); +assert(isSetsEqual(actual, expected), desc); + +function isSetsEqual(as, bs) { + if (as.size !== bs.size) { + return false; + } + for (let a of as) { + if (!bs.has(a)) return false; + } + return true; +} + +function assert(condition, desc) { + if (condition) { + console.log(`${desc} ... PASS`); + } else { + console.log(`${desc} ... FAIL`); + } +} diff --git a/users/wpcarro/scratch/deepmind/part_two/reverse-string-in-place.ts b/users/wpcarro/scratch/deepmind/part_two/reverse-string-in-place.ts new file mode 100644 index 000000000000..d714dfef997f --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/reverse-string-in-place.ts @@ -0,0 +1,13 @@ +// Reverse array of characters, `xs`, mutatively. +function reverse(xs: Array<string>) { + let i: number = 0; + let j: number = xs.length - 1; + + while (i < j) { + let tmp = xs[i]; + xs[i] = xs[j] + xs[j] = tmp + i += 1 + j -= 1 + } +} diff --git a/users/wpcarro/scratch/deepmind/part_two/reverse-words.py b/users/wpcarro/scratch/deepmind/part_two/reverse-words.py new file mode 100644 index 000000000000..033d11244ca7 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/reverse-words.py @@ -0,0 +1,74 @@ +import unittest + + +def reverse(xs, i, j): + """Reverse array of characters, xs, in-place.""" + while i < j: + xs[i], xs[j] = xs[j], xs[i] + i += 1 + j -= 1 + + +def reverse_words(xs): + punctuation = None + if len(xs) > 0 and xs[-1] in ".?!": + punctuation = xs.pop() + reverse(xs, 0, len(xs) - 1) + i = 0 + j = i + while j < len(xs): + while j < len(xs) and xs[j] != ' ': + j += 1 + reverse(xs, i, j - 1) + j += 1 + i = j + if punctuation: + xs.append(punctuation) + + +# Tests +class Test(unittest.TestCase): + def test_one_word(self): + message = list('vault') + reverse_words(message) + expected = list('vault') + self.assertEqual(message, expected) + + def test_two_words(self): + message = list('thief cake') + reverse_words(message) + expected = list('cake thief') + self.assertEqual(message, expected) + + def test_three_words(self): + message = list('one another get') + reverse_words(message) + expected = list('get another one') + self.assertEqual(message, expected) + + def test_multiple_words_same_length(self): + message = list('rat the ate cat the') + reverse_words(message) + expected = list('the cat ate the rat') + self.assertEqual(message, expected) + + def test_multiple_words_different_lengths(self): + message = list('yummy is cake bundt chocolate') + reverse_words(message) + expected = list('chocolate bundt cake is yummy') + self.assertEqual(message, expected) + + def test_empty_string(self): + message = list('') + reverse_words(message) + expected = list('') + self.assertEqual(message, expected) + + def test_bonus_support_punctuation(self): + message = list('yummy is cake bundt chocolate this!') + reverse_words(message) + expected = list('this chocolate bundt cake is yummy!') + self.assertEqual(message, expected) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/deepmind/part_two/second-largest-item-in-bst.ts b/users/wpcarro/scratch/deepmind/part_two/second-largest-item-in-bst.ts new file mode 100644 index 000000000000..4c5e57607d87 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/second-largest-item-in-bst.ts @@ -0,0 +1,219 @@ +/******************************************************************************* + * Setup + ******************************************************************************/ + +interface BinaryTreeNode { + value: number; + left: BinaryTreeNode; + right: BinaryTreeNode; +} + +class BinaryTreeNode { + constructor(value: number) { + this.value = value; + this.left = null; + this.right = null; + } + + insertLeft(value: number): BinaryTreeNode { + this.left = new BinaryTreeNode(value); + return this.left; + } + + insertRight(value: number): BinaryTreeNode { + this.right = new BinaryTreeNode(value); + return this.right; + } +} + +/******************************************************************************* + * First solution + ******************************************************************************/ + +/** + * I first solved this problem using O(n) space and O(n*log(n)) + * time. InterviewCake informs me that we can improve both the time and the + * space performance. + */ +function findSecondLargest_first(node: BinaryTreeNode): number { + const stack: Array<BinaryTreeNode> = []; + const xs: Array<number> = []; + stack.push(node); + + while (stack.length > 0) { + const node = stack.pop() + + xs.push(node.value); + + if (node.left) { + stack.push(node.left); + } + if (node.right) { + stack.push(node.right); + } + } + + xs.sort(); + + if (xs.length < 2) { + throw new Error('Cannot find the second largest element in a BST with fewer than two elements.'); + } else { + return xs[xs.length - 2]; + } +} + +/******************************************************************************* + * Second solution + ******************************************************************************/ + +/** + * My second solution accumulates a list of the values in the tree using an + * in-order traversal. This reduces the runtime costs from O(n*log(n)) from the + * previous solution to O(n). The memory cost is still O(n), which InterviewCake + * informs me can be reduced to O(1). + */ +function findSecondLargest_second(node: BinaryTreeNode): number { + const xs: Array<number> = accumulateInorder(node); + + if (xs.length < 2) { + throw new Error('Cannot find the second largest element in a BST with fewer than two elements.'); + } else { + return xs[xs.length - 2]; + } +} + +/** + * Returns an array containing the values of the tree, `node`, sorted in-order + * (i.e. from smallest-to-largest). + */ +function accumulateInorder(node: BinaryTreeNode): Array<number> { + let result = []; + + if (node.left) { + result = result.concat(accumulateInorder(node.left)); + } + result.push(node.value) + if (node.right) { + result = result.concat(accumulateInorder(node.right)); + } + + return result; +} + +/******************************************************************************* + * Third solution + ******************************************************************************/ + +/** + * Returns the largest number in a BST. + */ +function findLargest(node: BinaryTreeNode): number { + let curr: BinaryTreeNode = node; + + while (curr.right) { + curr = curr.right; + } + + return curr.value; +} + +/** + * Returns the second largest number in a BST + */ +function findSecondLargest(node: BinaryTreeNode): number { + let curr = node; + let parent = null; + + while (curr.right) { + parent = curr; + curr = curr.right + } + + if (curr.left) { + return findLargest(curr.left); + } + else { + return parent.value; + } +} + + +// Tests +let desc = 'full tree'; +let treeRoot = new BinaryTreeNode(50); +let leftNode = treeRoot.insertLeft(30); +leftNode.insertLeft(10); +leftNode.insertRight(40); +let rightNode = treeRoot.insertRight(70); +rightNode.insertLeft(60); +rightNode.insertRight(80); +assertEquals(findSecondLargest(treeRoot), 70, desc); + +desc = 'largest has a left child'; +treeRoot = new BinaryTreeNode(50); +leftNode = treeRoot.insertLeft(30); +leftNode.insertLeft(10); +leftNode.insertRight(40); +rightNode = treeRoot.insertRight(70); +rightNode.insertLeft(60); +assertEquals(findSecondLargest(treeRoot), 60, desc); + +desc = 'largest has a left subtree'; +treeRoot = new BinaryTreeNode(50); +leftNode = treeRoot.insertLeft(30); +leftNode.insertLeft(10); +leftNode.insertRight(40); +rightNode = treeRoot.insertRight(70); +leftNode = rightNode.insertLeft(60); +leftNode.insertRight(65); +leftNode = leftNode.insertLeft(55); +leftNode.insertRight(58); +assertEquals(findSecondLargest(treeRoot), 65, desc); + +desc = 'second largest is root node'; +treeRoot = new BinaryTreeNode(50); +leftNode = treeRoot.insertLeft(30); +leftNode.insertLeft(10); +leftNode.insertRight(40); +rightNode = treeRoot.insertRight(70); +assertEquals(findSecondLargest(treeRoot), 50, desc); + +desc = 'descending linked list'; +treeRoot = new BinaryTreeNode(50); +leftNode = treeRoot.insertLeft(40); +leftNode = leftNode.insertLeft(30); +leftNode = leftNode.insertLeft(20); +leftNode = leftNode.insertLeft(10); +assertEquals(findSecondLargest(treeRoot), 40, desc); + +desc = 'ascending linked list'; +treeRoot = new BinaryTreeNode(50); +rightNode = treeRoot.insertRight(60); +rightNode = rightNode.insertRight(70); +rightNode = rightNode.insertRight(80); +assertEquals(findSecondLargest(treeRoot), 70, desc); + +desc = 'one node tree'; +treeRoot = new BinaryTreeNode(50); +assertThrowsError(() => findSecondLargest(treeRoot), desc); + +desc = 'when tree is empty'; +treeRoot = null; +assertThrowsError(() => findSecondLargest(treeRoot), desc); + +function assertEquals(a, b, desc) { + if (a === b) { + console.log(`${desc} ... PASS`); + } else { + console.log(`${desc} ... FAIL: ${a} != ${b}`) + } +} + +function assertThrowsError(func, desc) { + try { + func(); + console.log(`${desc} ... FAIL`); + } catch (e) { + console.log(`${desc} ... PASS`); + } +} diff --git a/users/wpcarro/scratch/deepmind/part_two/shell.nix b/users/wpcarro/scratch/deepmind/part_two/shell.nix new file mode 100644 index 000000000000..6080171bb835 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/shell.nix @@ -0,0 +1,11 @@ +let + briefcase = import <briefcase> {}; + pkgs = briefcase.third_party.pkgs; +in pkgs.mkShell { + buildInputs = with pkgs; [ + nodejs + python3 + go + goimports + ]; +} diff --git a/users/wpcarro/scratch/deepmind/part_two/shuffle.py b/users/wpcarro/scratch/deepmind/part_two/shuffle.py new file mode 100644 index 000000000000..fdc5a8bd80ab --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/shuffle.py @@ -0,0 +1,20 @@ +import random + + +def get_random(floor, ceiling): + return random.randrange(floor, ceiling + 1) + + +def shuffle(xs): + n = len(xs) + for i in range(n - 1): + j = get_random(i + 1, n - 1) + xs[i], xs[j] = xs[j], xs[i] + + +sample_list = [1, 2, 3, 4, 5] +print('Sample list:', sample_list) + +print('Shuffling sample list...') +shuffle(sample_list) +print(sample_list) diff --git a/users/wpcarro/scratch/deepmind/part_two/stock-price.py b/users/wpcarro/scratch/deepmind/part_two/stock-price.py new file mode 100644 index 000000000000..56a3c20ea05b --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/stock-price.py @@ -0,0 +1,54 @@ +import unittest + + +def get_max_profit(xs): + if len(xs) < 2: + raise Exception('Can only trade with two or more ticker values.') + lowest_buy = xs[0] + max_profit = None + for x in xs[1:]: + if not max_profit: + max_profit = x - lowest_buy + else: + max_profit = max(max_profit, x - lowest_buy) + lowest_buy = min(lowest_buy, x) + return max_profit + + +# Tests +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_two/todo.org b/users/wpcarro/scratch/deepmind/part_two/todo.org new file mode 100644 index 000000000000..9c76da754167 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/todo.org @@ -0,0 +1,77 @@ +* Array and string manipulation +** DONE Merging Meeting Times +** DONE Reverse String in Place +** DONE Reverse Words +** DONE Merge Sorted Arrays +** DONE Cafe Order Checker +* Hashing and hash tables +** DONE Inflight Entertainment +** DONE Permutation Palindrome +** DONE Word Cloud Data +** DONE Top Scores +* Greedy Algorithms +** DONE Apple Stocks +** DONE Highest Product of 3 +** DONE Product of All Other Numbers +** DONE Cafe Order Checker +** DONE In-Place Shuffle +* Sorting, searching, and logarithms +** DONE Find Rotation Point +** TODO Find Repeat, Space Edition +** DONE Top Scores +** DONE Merging Meeting Times +* Trees and graphs +** DONE Balanced Binary Tree +** DONE Binary Search Tree Checker +** DONE 2nd Largest Item in a Binary Search Tree +** DONE Graph Coloring +** DONE MeshMessage +** DONE Find Repeat, Space Edition BEAST MODE +* Dynamic programming and recursion +** DONE Recursive String Permutations +** DONE Compute nth Fibonacci Number +** TODO Making Change +** TODO The Cake Thief +** DONE Balanced Binary Tree +** DONE Binary Search Tree Checker +** DONE 2nd Largest Item in a Binary Search Tree +* Queues and stacks +** TODO Largest Stack +** TODO Implement A Queue With Two Stacks +** TODO Parenthesis Matching +** TODO Bracket Validator +* Linked lists +** DONE Delete Node +** TODO Does This Linked List Have A Cycle? +** TODO Reverse A Linked List +** TODO Kth to Last Node in a Singly-Linked List +** DONE Find Repeat, Space Edition BEAST MODE +* System design +** TODO URL Shortener +** TODO MillionGazillion +** TODO Find Duplicate Files +* General programming +** TODO Rectangular Love +** TODO Temperature Tracker +* Bit manipulation +** TODO Binary Numbers +** TODO The Stolen Breakfast Drone +* Combinatorics, probability, and other math +** TODO Which Appears Twice +** TODO Find in Ordered Set +** DONE In-Place Shuffle +** TODO Simulate 5-sided die +** TODO Simulate 7-sided die +** TODO Two Egg Problem +* JavaScript +** TODO JavaScript Scope +** TODO What's Wrong with This JavaScript? +* Coding interview tips +** TODO How The Coding Interview Works +** TODO General Coding Interview Advice +** TODO Impostor Syndrome +** TODO Why You Hit Dead Ends +** TODO Tips for Getting Unstuck +** TODO The 24 Hours Before Your Interview +** TODO Beating Behavioral Questions +** TODO Managing Your Interview Timeline diff --git a/users/wpcarro/scratch/deepmind/part_two/top-scores.py b/users/wpcarro/scratch/deepmind/part_two/top-scores.py new file mode 100644 index 000000000000..0ac349c1f880 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/top-scores.py @@ -0,0 +1,47 @@ +import unittest + + +def sort_scores(xs, highest_possible_score): + result = [] + buckets = [0] * highest_possible_score + + for x in xs: + buckets[x - 1] += 1 + + for i in range(highest_possible_score - 1, -1, -1): + if buckets[i] > 0: + for _ in range(buckets[i]): + result.append(i + 1) + + return result + + +# Tests +class Test(unittest.TestCase): + def test_no_scores(self): + actual = sort_scores([], 100) + expected = [] + self.assertEqual(actual, expected) + + def test_one_score(self): + actual = sort_scores([55], 100) + expected = [55] + self.assertEqual(actual, expected) + + def test_two_scores(self): + actual = sort_scores([30, 60], 100) + expected = [60, 30] + self.assertEqual(actual, expected) + + def test_many_scores(self): + actual = sort_scores([37, 89, 41, 65, 91, 53], 100) + expected = [91, 89, 65, 53, 41, 37] + self.assertEqual(actual, expected) + + def test_repeated_scores(self): + actual = sort_scores([20, 10, 30, 30, 10, 20], 100) + expected = [30, 30, 20, 20, 10, 10] + self.assertEqual(actual, expected) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/deepmind/part_two/top-scores.ts b/users/wpcarro/scratch/deepmind/part_two/top-scores.ts new file mode 100644 index 000000000000..79c10c883211 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/top-scores.ts @@ -0,0 +1,57 @@ +function sortScores(xs: Array<number>, highest: number): Array<number> { + const counts: Array<number> = []; + const result: Array<number> = []; + + // Initialize counts + for (let i = 0; i <= highest; i += 1) { + counts.push(0); + } + + for (let i = 0; i < xs.length; i += 1) { + counts[xs[i]] += 1; + } + + for (let i = highest; i >= 0; i -= 1) { + let count: number = counts[i]; + + for (let j = 0; j < count; j += 1) { + result.push(i); + } + } + + return result; +} + +// Tests +let desc = "no scores"; +let actual = sortScores([], 100); +let expected = []; +assertEqual(JSON.stringify(actual), JSON.stringify(expected), desc); + +desc = "one score"; +actual = sortScores([55], 100); +expected = [55]; +assertEqual(JSON.stringify(actual), JSON.stringify(expected), desc); + +desc = "two scores"; +actual = sortScores([30, 60], 100); +expected = [60, 30]; +assertEqual(JSON.stringify(actual), JSON.stringify(expected), desc); + +desc = "many scores"; +actual = sortScores([37, 89, 41, 65, 91, 53], 100); +expected = [91, 89, 65, 53, 41, 37]; +assertEqual(JSON.stringify(actual), JSON.stringify(expected), desc); + +desc = "repeated scores"; +actual = sortScores([20, 10, 30, 30, 10, 20], 100); +expected = [30, 30, 20, 20, 10, 10]; +assertEqual(JSON.stringify(actual), JSON.stringify(expected), desc); + +function assertEqual(a, b, desc) { + if (a === b) { + console.log(`${desc} ... PASS`); + } else { + console.log(`${desc} ... FAIL: ${a} != ${b}`); + } +} diff --git a/users/wpcarro/scratch/deepmind/part_two/tsconfig.json b/users/wpcarro/scratch/deepmind/part_two/tsconfig.json new file mode 100644 index 000000000000..9b6918ca37d8 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/tsconfig.json @@ -0,0 +1,7 @@ +{ + "compilerOptions": { + "downlevelIteration": true, + "target": "es5", + "lib": ["es6", "dom"] + } +} diff --git a/users/wpcarro/scratch/deepmind/part_two/word-cloud.py b/users/wpcarro/scratch/deepmind/part_two/word-cloud.py new file mode 100644 index 000000000000..36ace8405f71 --- /dev/null +++ b/users/wpcarro/scratch/deepmind/part_two/word-cloud.py @@ -0,0 +1,79 @@ +import unittest +import re +from collections import Counter + + +class WordCloudData(object): + def __init__(self, x): + x = x.replace('...', ' ').replace(' - ', ' ') + x = ''.join(c for c in x if c not in ',.!?;:') + self.words_to_counts = dict( + Counter(x.lower() for x in re.split(r'\s+', x))) + + +# Tests +class Test(unittest.TestCase): + def test_simple_sentence(self): + input = 'I like cake' + + word_cloud = WordCloudData(input) + actual = word_cloud.words_to_counts + + expected = {'i': 1, 'like': 1, 'cake': 1} + self.assertEqual(actual, expected) + + def test_longer_sentence(self): + input = 'Chocolate cake for dinner and pound cake for dessert' + + word_cloud = WordCloudData(input) + actual = word_cloud.words_to_counts + + expected = { + 'and': 1, + 'pound': 1, + 'for': 2, + 'dessert': 1, + 'chocolate': 1, + 'dinner': 1, + 'cake': 2, + } + self.assertEqual(actual, expected) + + def test_punctuation(self): + input = 'Strawberry short cake? Yum!' + + word_cloud = WordCloudData(input) + actual = word_cloud.words_to_counts + + expected = {'cake': 1, 'strawberry': 1, 'short': 1, 'yum': 1} + self.assertEqual(actual, expected) + + def test_hyphenated_words(self): + input = 'Dessert - mille-feuille cake' + + word_cloud = WordCloudData(input) + actual = word_cloud.words_to_counts + + expected = {'cake': 1, 'dessert': 1, 'mille-feuille': 1} + self.assertEqual(actual, expected) + + def test_ellipses_between_words(self): + input = 'Mmm...mmm...decisions...decisions' + + word_cloud = WordCloudData(input) + actual = word_cloud.words_to_counts + + expected = {'mmm': 2, 'decisions': 2} + self.assertEqual(actual, expected) + + def test_apostrophes(self): + input = "Allie's Bakery: Sasha's Cakes" + + word_cloud = WordCloudData(input) + actual = word_cloud.words_to_counts + + expected = {"bakery": 1, "cakes": 1, "allie's": 1, "sasha's": 1} + self.assertEqual(actual, expected) + + +unittest.main(verbosity=2) |