diff options
Diffstat (limited to 'universe/deepmind')
| -rw-r--r-- | universe/deepmind/balanced-binary-tree.py | 123 | ||||
| -rw-r--r-- | universe/deepmind/dijkstra.py | 26 | ||||
| -rw-r--r-- | universe/deepmind/efficiency.org | 6 | ||||
| -rw-r--r-- | universe/deepmind/find-rotation-point.py | 55 | ||||
| -rw-r--r-- | universe/deepmind/inflight-entertainment.py | 51 | ||||
| -rw-r--r-- | universe/deepmind/kth-to-last.py | 64 | ||||
| -rw-r--r-- | universe/deepmind/merging-ranges.py | 59 | ||||
| -rw-r--r-- | universe/deepmind/recursive-string-permutations.py | 56 | ||||
| -rw-r--r-- | universe/deepmind/reverse-linked-list.py | 74 | ||||
| -rw-r--r-- | universe/deepmind/stock-price.py | 51 | ||||
| -rw-r--r-- | universe/deepmind/which-appears-twice.py | 29 |
11 files changed, 0 insertions, 594 deletions
diff --git a/universe/deepmind/balanced-binary-tree.py b/universe/deepmind/balanced-binary-tree.py deleted file mode 100644 index 7fc174a2a9f3..000000000000 --- a/universe/deepmind/balanced-binary-tree.py +++ /dev/null @@ -1,123 +0,0 @@ -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/universe/deepmind/dijkstra.py b/universe/deepmind/dijkstra.py deleted file mode 100644 index 6975dbe4d1d6..000000000000 --- a/universe/deepmind/dijkstra.py +++ /dev/null @@ -1,26 +0,0 @@ -# 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/universe/deepmind/efficiency.org b/universe/deepmind/efficiency.org deleted file mode 100644 index 89a45c52ad8a..000000000000 --- a/universe/deepmind/efficiency.org +++ /dev/null @@ -1,6 +0,0 @@ -* 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/universe/deepmind/find-rotation-point.py b/universe/deepmind/find-rotation-point.py deleted file mode 100644 index 5c21d5167ce9..000000000000 --- a/universe/deepmind/find-rotation-point.py +++ /dev/null @@ -1,55 +0,0 @@ -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/universe/deepmind/inflight-entertainment.py b/universe/deepmind/inflight-entertainment.py deleted file mode 100644 index 2116b27b0b97..000000000000 --- a/universe/deepmind/inflight-entertainment.py +++ /dev/null @@ -1,51 +0,0 @@ -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/universe/deepmind/kth-to-last.py b/universe/deepmind/kth-to-last.py deleted file mode 100644 index 5335e419f7ec..000000000000 --- a/universe/deepmind/kth-to-last.py +++ /dev/null @@ -1,64 +0,0 @@ -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/universe/deepmind/merging-ranges.py b/universe/deepmind/merging-ranges.py deleted file mode 100644 index 23b40793b8f1..000000000000 --- a/universe/deepmind/merging-ranges.py +++ /dev/null @@ -1,59 +0,0 @@ -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/universe/deepmind/recursive-string-permutations.py b/universe/deepmind/recursive-string-permutations.py deleted file mode 100644 index f50db2838707..000000000000 --- a/universe/deepmind/recursive-string-permutations.py +++ /dev/null @@ -1,56 +0,0 @@ -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/universe/deepmind/reverse-linked-list.py b/universe/deepmind/reverse-linked-list.py deleted file mode 100644 index 82fac171d5d1..000000000000 --- a/universe/deepmind/reverse-linked-list.py +++ /dev/null @@ -1,74 +0,0 @@ -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/universe/deepmind/stock-price.py b/universe/deepmind/stock-price.py deleted file mode 100644 index 7055b66af196..000000000000 --- a/universe/deepmind/stock-price.py +++ /dev/null @@ -1,51 +0,0 @@ -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/universe/deepmind/which-appears-twice.py b/universe/deepmind/which-appears-twice.py deleted file mode 100644 index c01379295d32..000000000000 --- a/universe/deepmind/which-appears-twice.py +++ /dev/null @@ -1,29 +0,0 @@ -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) |