diff options
Diffstat (limited to 'scratch/deepmind')
19 files changed, 945 insertions, 0 deletions
diff --git a/scratch/deepmind/part_one/balanced-binary-tree.py b/scratch/deepmind/part_one/balanced-binary-tree.py new file mode 100644 index 000000000000..7fc174a2a9f3 --- /dev/null +++ b/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/scratch/deepmind/part_one/dijkstra.py b/scratch/deepmind/part_one/dijkstra.py new file mode 100644 index 000000000000..6975dbe4d1d6 --- /dev/null +++ b/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/scratch/deepmind/part_one/efficiency.org b/scratch/deepmind/part_one/efficiency.org new file mode 100644 index 000000000000..89a45c52ad8a --- /dev/null +++ b/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/scratch/deepmind/part_one/find-rotation-point.py b/scratch/deepmind/part_one/find-rotation-point.py new file mode 100644 index 000000000000..5c21d5167ce9 --- /dev/null +++ b/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/scratch/deepmind/part_one/inflight-entertainment.py b/scratch/deepmind/part_one/inflight-entertainment.py new file mode 100644 index 000000000000..2116b27b0b97 --- /dev/null +++ b/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/scratch/deepmind/part_one/kth-to-last.py b/scratch/deepmind/part_one/kth-to-last.py new file mode 100644 index 000000000000..5335e419f7ec --- /dev/null +++ b/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/scratch/deepmind/part_one/merging-ranges.py b/scratch/deepmind/part_one/merging-ranges.py new file mode 100644 index 000000000000..23b40793b8f1 --- /dev/null +++ b/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/scratch/deepmind/part_one/recursive-string-permutations.py b/scratch/deepmind/part_one/recursive-string-permutations.py new file mode 100644 index 000000000000..f50db2838707 --- /dev/null +++ b/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/scratch/deepmind/part_one/reverse-linked-list.py b/scratch/deepmind/part_one/reverse-linked-list.py new file mode 100644 index 000000000000..82fac171d5d1 --- /dev/null +++ b/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/scratch/deepmind/part_one/stock-price.py b/scratch/deepmind/part_one/stock-price.py new file mode 100644 index 000000000000..7055b66af196 --- /dev/null +++ b/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/scratch/deepmind/part_one/which-appears-twice.py b/scratch/deepmind/part_one/which-appears-twice.py new file mode 100644 index 000000000000..c01379295d32 --- /dev/null +++ b/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/scratch/deepmind/part_two/.envrc b/scratch/deepmind/part_two/.envrc new file mode 100644 index 000000000000..b80e28b4b815 --- /dev/null +++ b/scratch/deepmind/part_two/.envrc @@ -0,0 +1,2 @@ +source_up +eval "$(lorri direnv)" diff --git a/scratch/deepmind/part_two/delete-node.py b/scratch/deepmind/part_two/delete-node.py new file mode 100644 index 000000000000..4ed02ec30832 --- /dev/null +++ b/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/scratch/deepmind/part_two/misc/matrix-traversals.py b/scratch/deepmind/part_two/misc/matrix-traversals.py new file mode 100644 index 000000000000..52354f990e11 --- /dev/null +++ b/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/scratch/deepmind/part_two/package-lock.json b/scratch/deepmind/part_two/package-lock.json new file mode 100644 index 000000000000..94c89c5979c4 --- /dev/null +++ b/scratch/deepmind/part_two/package-lock.json @@ -0,0 +1,73 @@ +{ + "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 + }, + "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/scratch/deepmind/part_two/package.json b/scratch/deepmind/part_two/package.json new file mode 100644 index 000000000000..c9ef307ca0ee --- /dev/null +++ b/scratch/deepmind/part_two/package.json @@ -0,0 +1,15 @@ +{ + "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": { + "ts-node": "^8.6.2", + "typescript": "^3.7.5" + } +} diff --git a/scratch/deepmind/part_two/reverse-string-in-place.ts b/scratch/deepmind/part_two/reverse-string-in-place.ts new file mode 100644 index 000000000000..d714dfef997f --- /dev/null +++ b/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/scratch/deepmind/part_two/shell.nix b/scratch/deepmind/part_two/shell.nix new file mode 100644 index 000000000000..606dd7167f7c --- /dev/null +++ b/scratch/deepmind/part_two/shell.nix @@ -0,0 +1,10 @@ +{ pkgs ? import <nixpkgs> {}, ... }: + +pkgs.mkShell { + buildInputs = with pkgs; [ + nodejs + python3 + go + goimports + ]; +} diff --git a/scratch/deepmind/part_two/todo.org b/scratch/deepmind/part_two/todo.org new file mode 100644 index 000000000000..510073e6e2cd --- /dev/null +++ b/scratch/deepmind/part_two/todo.org @@ -0,0 +1,77 @@ +* Array and string manipulation +** TODO Merging Meeting Times +** DONE Reverse String in Place +** TODO Reverse Words +** TODO Merge Sorted Arrays +** TODO Cafe Order Checker +* Hashing and hash tables +** TODO Inflight Entertainment +** TODO Permutation Palindrome +** TODO Word Cloud Data +** TODO Top Scores +* Greedy Algorithms +** TODO Apple Stocks +** TODO Highest Product of 3 +** TODO Product of All Other Numbers +** TODO Cafe Order Checker +** TODO In-Place Shuffle +* Sorting, searching, and logarithms +** TODO Find Rotation Point +** TODO Find Repeat, Space Edition +** TODO Top Scores +** TODO Merging Meeting Times +* Trees and graphs +** TODO Balanced Binary Tree +** TODO Binary Search Tree Checker +** TODO 2nd Largest Item in a Binary Search Tree +** TODO Graph Coloring +** TODO MeshMessage +** TODO Find Repeat, Space Edition BEAST MODE +* Dynamic programming and recursion +** TODO Recursive String Permutations +** TODO Compute nth Fibonacci Number +** TODO Making Change +** TODO The Cake Thief +** TODO Balanced Binary Tree +** TODO Binary Search Tree Checker +** TODO 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 +** TODO 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 +** TODO 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 |