Tidy up structure of briefcase

I had a spare fifteen minutes and decided that I should tidy up my
monorepo. The work of tidying up is not finished; this is a small step in the
right direction.

TL;DR
- Created a tools directory
- Created a scratch directory (see README.md for more information)
- Added README.md to third_party
- Renamed delete_dotfile_symlinks -> symlinkManager
- Packaged symlinkManager as an executable symlink-mgr using buildGo

52 files changed, 3737 insertions, 0 deletions

diff --git a/scratch/data_structures_and_algorithms/array-traversals.py b/scratch/data_structures_and_algorithms/array-traversals.py
new file mode 100644
index 000000000000..35cb4392812e
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/array-traversals.py
@@ -0,0 +1,87 @@
+# This is practice for various types of list traversals that turn up.
+
+xs = range(10)
+n = len(xs)
+
+print('---')
+# pythonic left-to-right traversal
+result = ''
+for x in xs:
+    result += str(x)
+print(result)
+
+print('---')
+# left-to-right traversal
+result = ''
+for i in range(n):
+    result += str(xs[i])
+print(result)
+
+print('---')
+# right-to-left traversal
+result = ''
+for i in range(n):
+    result += str(xs[n - 1 - i])
+print(result)
+
+print('---')
+# 2x left-to-right traversal
+result = ''
+for i in range(2 * n):
+    result += str(xs[i % n])
+print(result)
+
+print('---')
+# 2x right-to-left traversal
+result = ''
+for i in range(2 * n):
+    result += str(xs[(n - 1 - i) % n])
+print(result)
+
+################################################################################
+# Table traversals
+################################################################################
+
+table = [[row * 10 + i for i in range(10)] for row in range(3)]
+row_ct = len(table)
+col_ct = len(table[0])
+
+print('---')
+# 3x10 table traversal
+result = ''
+for row in table:
+    r = ''
+    for col in row:
+        r += '{:3d}'.format(col)
+    result += r + '\n'
+print(result[0:-1])
+
+print('---')
+# 3x10 table traversal
+result = ''
+for row in range(row_ct):
+    r = ''
+    for col in range(col_ct):
+        r += '{:3d}'.format(table[row][col])
+    result += r + '\n'
+print(result[0:-1])
+
+print('---')
+# 3x10 table traversal (reverse)
+result = ''
+for row in range(row_ct):
+    r = ''
+    for col in range(col_ct):
+        r += '{:3d}'.format(table[row_ct - 1 - row][col_ct - 1 - col])
+    result += r + '\n'
+print(result)
+
+print('---')
+# 3x10 column-row traversal
+result = ''
+for col in range(col_ct):
+    r = ''
+    for row in range(row_ct):
+        r += '{:3d}'.format(table[row][col])
+    result += r + '\n'
+print(result)
diff --git a/scratch/data_structures_and_algorithms/balanced-binary-tree.py b/scratch/data_structures_and_algorithms/balanced-binary-tree.py
new file mode 100644
index 000000000000..01fd965fd540
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/balanced-binary-tree.py
@@ -0,0 +1,145 @@
+import unittest
+from itertools import combinations
+
+
+def balanced(xs):
+    """Return True if `xs` contains no two values that differ by more than
+    one."""
+    if len(xs) == 0 or len(xs) == 1:
+        return True
+    if len(xs) == 2:
+        return math.abs(xs[0] - xs[1]) <= 1
+    else:
+        pass
+
+
+def is_leaf(node):
+    return node.left is None and node.right is None
+
+
+def is_balanced(tree_root):
+    """Returns True if the difference between the depths of any two leaf nodes
+    does not exceed 1."""
+    depths = set()
+    populate_depths(tree_root, 0, depths)
+
+    # cartesian product - only the top half
+    for diff in set(abs(a - b) for a, b in combinations(depths, 2)):
+        if diff > 1:
+            return False
+
+    return True
+
+
+def populate_depths(node, depth, depths):
+    if is_leaf(node):
+        depths.add(depth)
+    else:
+        if node.left is not None:
+            populate_depths(node.left, depth + 1, depths)
+        if node.right is not None:
+            populate_depths(node.right, depth + 1, depths)
+
+
+################################################################################
+# 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/data_structures_and_algorithms/bit-manipulation.py b/scratch/data_structures_and_algorithms/bit-manipulation.py
new file mode 100644
index 000000000000..dc30bb508887
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/bit-manipulation.py
@@ -0,0 +1,32 @@
+def test(x, i):
+    return x & (1 << i) != 0
+
+
+def set(x, i):
+    return x | (1 << i)
+
+
+def clear(x, i):
+    return x & ~(1 << i)
+
+
+def toggle(x, i):
+    if test(x, i):
+        return clear(x, i)
+    else:
+        return set(x, i)
+
+
+def test_single(x):
+    if x == 0:
+        return False
+    else:
+        return x & (x - 1) == 0
+
+
+print(test(0b1010, 3))
+print('{0:b}'.format(set(0b1010, 1)))
+print('{0:b}'.format(clear(0b1010, 1)))
+print('{0:b}'.format(toggle(0b1010, 2)))
+print(test_single(0b1010))
+print(test_single(0b1000))
diff --git a/scratch/data_structures_and_algorithms/bracket-validator.py b/scratch/data_structures_and_algorithms/bracket-validator.py
new file mode 100644
index 000000000000..a50f8b074e55
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/bracket-validator.py
@@ -0,0 +1,63 @@
+import unittest
+
+
+################################################################################
+# Solution
+################################################################################
+# is_valid :: String -> Boolean
+def is_valid(xs):
+    s = []
+    seeking = {
+        '}': '{',
+        ']': '[',
+        ')': '(',
+    }
+    openers = seeking.values()
+    closers = seeking.keys()
+    for c in xs:
+        if c in openers:
+            s.append(c)
+        elif c in closers:
+            if not s:
+                return False
+            elif s[-1] != seeking.get(c):
+                return False
+            else:
+                s.pop()
+    return len(s) == 0
+
+
+################################################################################
+# Tests
+################################################################################
+class Test(unittest.TestCase):
+    def test_valid_short_code(self):
+        result = is_valid('()')
+        self.assertTrue(result)
+
+    def test_valid_longer_code(self):
+        result = is_valid('([]{[]})[]{{}()}')
+        self.assertTrue(result)
+
+    def test_interleaved_openers_and_closers(self):
+        result = is_valid('([)]')
+        self.assertFalse(result)
+
+    def test_mismatched_opener_and_closer(self):
+        result = is_valid('([][]}')
+        self.assertFalse(result)
+
+    def test_missing_closer(self):
+        result = is_valid('[[]()')
+        self.assertFalse(result)
+
+    def test_extra_closer(self):
+        result = is_valid('[[]]())')
+        self.assertFalse(result)
+
+    def test_empty_string(self):
+        result = is_valid('')
+        self.assertTrue(result)
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/data_structures_and_algorithms/bst-checker.py b/scratch/data_structures_and_algorithms/bst-checker.py
new file mode 100644
index 000000000000..689be97a8503
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/bst-checker.py
@@ -0,0 +1,121 @@
+import unittest
+
+
+################################################################################
+# Implementation
+################################################################################
+# is_leaf :: Node(a) -> Boolean
+def is_leaf(node):
+    return not node.left and not node.right
+
+
+# is_binary_search_tree :: Node(Integer) -> Set(Int) -> Set(Int) -> Boolean
+def is_binary_search_tree_a(node, la=set(), ra=set()):
+    """My first solution for this problem."""
+    for x in la:
+        if not node.value < x:
+            return False
+    for x in ra:
+        if not node.value > x:
+            return False
+    if is_leaf(node):
+        return True
+    elif not node.left:
+        return is_binary_search_tree(
+            node.right,
+            la=la,
+            ra=ra ^ {node.value},
+        )
+    elif not node.right:
+        return is_binary_search_tree(node.left, la=la ^ {node.value}, ra=ra)
+    else:
+        return all([
+            is_binary_search_tree(node.left, la=la ^ {node.value}, ra=ra),
+            is_binary_search_tree(node.right, la=la, ra=ra ^ {node.value})
+        ])
+
+
+# is_binary_search_tree :: Node(Int) -> Maybe(Int) -> Maybe(Int) -> Boolean
+def is_binary_search_tree(node, lb=None, ub=None):
+    if lb:
+        if node.value < lb:
+            return False
+    if ub:
+        if node.value > ub:
+            return False
+    if is_leaf(node):
+        return True
+    elif not node.right:
+        return is_binary_search_tree(node.left, lb=lb, ub=node.value)
+    elif not node.left:
+        return is_binary_search_tree(node.right, lb=node.value, ub=ub)
+    else:
+        return is_binary_search_tree(
+            node.left, lb=lb, ub=node.value) and is_binary_search_tree(
+                node.right, lb=node.value, ub=ub)
+
+
+################################################################################
+# 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/scratch/data_structures_and_algorithms/cafe-order-checker.py b/scratch/data_structures_and_algorithms/cafe-order-checker.py
new file mode 100644
index 000000000000..e34a2b136ab6
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/cafe-order-checker.py
@@ -0,0 +1,91 @@
+import unittest
+
+
+################################################################################
+# Implementation
+################################################################################
+def is_first_come_first_served(to, di, xs):
+    # All the guards, assertions we should need.
+    if to == di == xs == []:
+        return True
+    elif to == di == []:
+        return False
+    elif to == []:
+        return di == xs
+    elif to == []:
+        return di == xs
+    elif di == []:
+        return to == xs
+    elif xs == []:
+        return False
+    elif len(xs) != (len(to) + len(di)):
+        return False
+
+    fst, snd = to, di
+
+    if xs[0] == to[0]:
+        fst, snd = to, di
+    elif xs[0] == di[0]:
+        fst, snd = di, to
+    else:
+        return False
+
+    fst_done, snd_done = False, False
+    fi, si = 1, 0
+
+    for i in range(1, len(xs)):
+        # Short-circuit and avoid index-out-of-bounds without introducing overly
+        # defensive, sloppy code.
+        if fst_done:
+            return snd[si:] == xs[i:]
+        elif snd_done:
+            return fst[fi:] == xs[i:]
+
+        if fst[fi] == xs[i]:
+            fi += 1
+        elif snd[si] == xs[i]:
+            si += 1
+        else:
+            return False
+
+        fst_done, snd_done = fi == len(fst), si == len(snd)
+
+    return True
+
+
+################################################################################
+# 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)
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/data_structures_and_algorithms/cake-thief.py b/scratch/data_structures_and_algorithms/cake-thief.py
new file mode 100644
index 000000000000..9eddb34b2db3
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/cake-thief.py
@@ -0,0 +1,71 @@
+import unittest
+from math import floor
+
+
+################################################################################
+# Solution
+################################################################################
+def max_duffel_bag_value(xs, cap):
+    ct = (cap + 1)
+    maxes = [0] * ct
+    for c in range(cap + 1):
+        for w, v in xs:
+            if w == 0 and v > 0:
+                return float('inf')
+            if w == c:
+                maxes[c:] = [max(maxes[c], v)] * (ct - c)
+            elif w < c:
+                d = c - w
+                maxes[c:] = [max(maxes[c], v + maxes[d])] * (ct - c)
+            else:
+                continue
+    return maxes[cap]
+
+
+################################################################################
+# Tests
+################################################################################
+class Test(unittest.TestCase):
+    def test_one_cake(self):
+        actual = max_duffel_bag_value([(2, 1)], 9)
+        expected = 4
+        self.assertEqual(actual, expected)
+
+    def test_two_cakes(self):
+        actual = max_duffel_bag_value([(4, 4), (5, 5)], 9)
+        expected = 9
+        self.assertEqual(actual, expected)
+
+    def test_only_take_less_valuable_cake(self):
+        actual = max_duffel_bag_value([(4, 4), (5, 5)], 12)
+        expected = 12
+        self.assertEqual(actual, expected)
+
+    def test_lots_of_cakes(self):
+        actual = max_duffel_bag_value([(2, 3), (3, 6), (5, 1), (6, 1), (7, 1),
+                                       (8, 1)], 7)
+        expected = 12
+        self.assertEqual(actual, expected)
+
+    def test_value_to_weight_ratio_is_not_optimal(self):
+        actual = max_duffel_bag_value([(51, 52), (50, 50)], 100)
+        expected = 100
+        self.assertEqual(actual, expected)
+
+    def test_zero_capacity(self):
+        actual = max_duffel_bag_value([(1, 2)], 0)
+        expected = 0
+        self.assertEqual(actual, expected)
+
+    def test_cake_with_zero_value_and_weight(self):
+        actual = max_duffel_bag_value([(0, 0), (2, 1)], 7)
+        expected = 3
+        self.assertEqual(actual, expected)
+
+    def test_cake_with_non_zero_value_and_zero_weight(self):
+        actual = max_duffel_bag_value([(0, 5)], 5)
+        expected = float('inf')
+        self.assertEqual(actual, expected)
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/data_structures_and_algorithms/coins.py b/scratch/data_structures_and_algorithms/coins.py
new file mode 100644
index 000000000000..eb5754f98210
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/coins.py
@@ -0,0 +1,57 @@
+import unittest
+from math import floor
+
+################################################################################
+# Solution
+################################################################################
+
+# change_possibilities :: Int -> [Int] -> Int
+def change_possibilities(n, xs):
+    combinations = [0] * (n + 1)
+    combinations[0] = 1
+
+    for x in xs:
+        for i in range(len(combinations)):
+            if i >= x:
+                combinations[i] += combinations[i - x]
+
+    return combinations[n]
+
+
+################################################################################
+# Tests
+################################################################################
+class Test(unittest.TestCase):
+
+    def test_sample_input(self):
+        actual = change_possibilities(4, (1, 2, 3))
+        expected = 4
+        self.assertEqual(actual, expected)
+
+    def test_one_way_to_make_zero_cents(self):
+        actual = change_possibilities(0, (1, 2))
+        expected = 1
+        self.assertEqual(actual, expected)
+
+    def test_no_ways_if_no_coins(self):
+        actual = change_possibilities(1, ())
+        expected = 0
+        self.assertEqual(actual, expected)
+
+    def test_big_coin_value(self):
+        actual = change_possibilities(5, (25, 50))
+        expected = 0
+        self.assertEqual(actual, expected)
+
+    def test_big_target_amount(self):
+        actual = change_possibilities(50, (5, 10))
+        expected = 6
+        self.assertEqual(actual, expected)
+
+    def test_change_for_one_dollar(self):
+        actual = change_possibilities(100, (1, 5, 10, 25, 50))
+        expected = 292
+        self.assertEqual(actual, expected)
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/data_structures_and_algorithms/conways-game-of-life.py b/scratch/data_structures_and_algorithms/conways-game-of-life.py
new file mode 100644
index 000000000000..3836bcd0c653
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/conways-game-of-life.py
@@ -0,0 +1,78 @@
+from itertools import product
+from random import choice
+from time import sleep
+from os import system
+from math import floor
+from colorama import Back, Fore, Style
+
+################################################################################
+# Simulation of Conway's Game of Life. The goal here was to write this with a
+# small amount of code as a proof-of-concept that could be run in the terminal.
+#
+# If you'd like to tinker with the rules, see the conditionals defined in the
+# `advance/1` function. For other parameters, like the board size and refresh
+# rate, refer to the while-loop defined at the bottom of this file.
+################################################################################
+
+
+def init_board(n, init_alive_percentage):
+    """Initialize a board of size `n` by `n`. Supply a percentage,
+    `init_alive_percentage`, representing the number of cells in the board that
+    should be alive from the start."""
+    alive_count = floor(n * init_alive_percentage)
+    distribution = [True] * alive_count + [False] * (n - alive_count)
+    return [[choice(distribution) for _ in range(n)] for _ in range(n)]
+
+
+def neighbors(coord, board):
+    """Return the neighbors for a given `coord` on a `board`."""
+    n = len(board)
+    row, col = coord
+    return [
+        board[(row + row_d) % n][(col + col_d) % n]
+        for row_d, col_d in product([-1, 0, 1], [-1, 0, 1])
+        if (row_d, col_d) != (0, 0)
+    ]
+
+
+def advance(board):
+    """Advance the state of the `board` from T[n] to T[n+1]."""
+    n = len(board)
+    new_board = [[False for _ in range(n)] for _ in range(n)]
+    for row in range(n):
+        for col in range(n):
+            alive_count = len([x for x in neighbors((row, col), board) if x])
+            # Loneliness
+            if alive_count == 0:
+                new_board[row][col] = False
+            # Status Quo
+            elif alive_count == 1:
+                new_board[row][col] = board[row][col]
+            # Cooperation
+            elif alive_count == 2:
+                new_board[row][col] = True
+            # Resource starvation
+            elif alive_count >= 3:
+                new_board[row][col] = False
+    return new_board
+
+
+def print_board(board):
+    """Print the game `board` in a human-readable way."""
+    result = ''
+    for row in board:
+        for col in row:
+            if col:
+                result += Back.GREEN + '1 ' + Style.RESET_ALL
+            else:
+                result += Back.RED + '0 ' + Style.RESET_ALL
+        result += '\n'
+    print(result)
+
+
+board = init_board(100, 0.50)
+while True:
+    system('clear')
+    print_board(board)
+    sleep(0.15)
+    board = advance(board)
diff --git a/scratch/data_structures_and_algorithms/delete-node.py b/scratch/data_structures_and_algorithms/delete-node.py
new file mode 100644
index 000000000000..7e431e224962
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/delete-node.py
@@ -0,0 +1,60 @@
+import unittest
+
+
+################################################################################
+# Solution
+################################################################################
+def delete_node(x):
+    if not x.next:
+        raise Exception('Cannot delete the last node in a linked list.')
+    else:
+        x.value = x.next.value
+        x.next = x.next.next
+
+
+################################################################################
+# 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/data_structures_and_algorithms/dft.py b/scratch/data_structures_and_algorithms/dft.py
new file mode 100644
index 000000000000..127d48c1864b
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/dft.py
@@ -0,0 +1,65 @@
+from random import choice
+
+
+class Node(object):
+    def __init__(self, value=None, left=None, right=None):
+        self.value = value
+        self.left = left
+        self.right = left
+
+
+def p(node, indent=0):
+    print(indent * ' ' + '|-' + str(node.value))
+    if node.left is not None:
+        p(node.left, indent=indent + 2)
+    if node.right is not None:
+        p(node.right, indent=indent + 2)
+
+
+# read trees (i.e. traversing, parsing)
+# write trees (i.e. generating, printing)
+def random(d=0):
+    left = None
+    right = None
+
+    if choice([True, False]):
+        left = random(d + 1)
+
+    if choice([True, False]):
+        right = random(d + 1)
+
+    return Node(
+        value=d,
+        left=left,
+        right=right,
+    )
+
+
+################################################################################
+# DFTs can be:
+# - imperative (mutable)
+# - functional (immutable)
+# - iterative
+# - recursive
+################################################################################
+
+
+# Iterative
+def traverse(node, f):
+    stack = [(node, 0)]
+
+    while len(stack):
+        node, depth = stack.pop()
+        f(node, depth)
+        print(depth)
+
+        if node.left is not None:
+            stack.append((node.left, depth + 1))
+        if node.right is not None:
+            stack.append((node.right, depth + 1))
+
+
+print('----------------------------------------------------------------------')
+for _ in range(10):
+    traverse(random(), lambda _, d: print(d))
+print()
diff --git a/scratch/data_structures_and_algorithms/dijkstra-shortest-path.py b/scratch/data_structures_and_algorithms/dijkstra-shortest-path.py
new file mode 100644
index 000000000000..03907f604044
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/dijkstra-shortest-path.py
@@ -0,0 +1,48 @@
+from collections import deque
+from heapq import heappush, heappop
+from fixtures import weighted_graph
+
+
+def put(t, x, xs):
+    if t == 'stack':
+        return xs.append(x)
+    if t == 'queue':
+        return xs.append(x)
+    if t == 'priority':
+        return heappush(xs, x)
+
+
+def pop(t, xs):
+    if t == 'stack':
+        return xs.pop()
+    if t == 'queue':
+        return xs.popleft()
+    if t == 'priority':
+        return heappop(xs)
+
+
+# shortest_path :: Vertex -> Vertex -> Graph -> [Vertex]
+def shortest_path(a, b, g):
+    """Returns the shortest path from vertex a to vertex b in graph g."""
+    t = 'priority'
+    xs = []
+    seen = set()
+    # Map(Weight, [Vertex])
+    m = {}
+
+    put(t, (0, [a], a), xs)
+
+    while xs:
+        w0, path, v = pop(t, xs)
+
+        seen.add(v)
+        if v == b:
+            m[w0] = path
+        for w1, x in g.get(v):
+            if x not in seen:
+                put(t, (w0 + w1, path + [x], x), xs)
+
+    return m
+
+
+print(shortest_path('a', 'f', graph_a))
diff --git a/scratch/data_structures_and_algorithms/find-duplicate-optimize-for-space-beast.py b/scratch/data_structures_and_algorithms/find-duplicate-optimize-for-space-beast.py
new file mode 100644
index 000000000000..93fdd9eed2d6
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/find-duplicate-optimize-for-space-beast.py
@@ -0,0 +1,56 @@
+import unittest
+
+
+################################################################################
+# Solution
+################################################################################
+def find_duplicate(xs):
+    self_ref_count = 0
+    for i in range(len(xs)):
+        if xs[i] == i + 1:
+            self_ref_count += 1
+    hops = len(xs) - 1 - self_ref_count
+    current = xs[-1]
+    while hops > 0:
+        current = xs[current - 1]
+        hops -= 1
+    return current
+
+
+################################################################################
+# Tests
+################################################################################
+class Test(unittest.TestCase):
+    # TODO: Debug why this fails.
+    def test_darren_from_interview_cake(self):
+        actual = find_duplicate([4, 1, 8, 3, 2, 7, 6, 5, 4])
+        expected = 4
+        self.assertEqual(actual, expected)
+
+    def test_just_the_repeated_number(self):
+        actual = find_duplicate([1, 1])
+        expected = 1
+        self.assertEqual(actual, expected)
+
+    def test_short_list(self):
+        actual = find_duplicate([1, 2, 3, 2])
+        expected = 2
+        self.assertEqual(actual, expected)
+
+    def test_last_cycle(self):
+        actual = find_duplicate([3, 4, 2, 3, 1, 5])
+        expected = 3
+        self.assertEqual(actual, expected)
+
+    def test_medium_list(self):
+        actual = find_duplicate([1, 2, 5, 5, 5, 5])
+        expected = 5
+        self.assertEqual(actual, expected)
+
+    def test_long_list(self):
+        actual = find_duplicate([4, 1, 4, 8, 3, 2, 7, 6, 5])
+        expected = 4
+        self.assertEqual(actual, expected)
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/data_structures_and_algorithms/find-duplicate-optimize-for-space.py b/scratch/data_structures_and_algorithms/find-duplicate-optimize-for-space.py
new file mode 100644
index 000000000000..e2739f0f6055
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/find-duplicate-optimize-for-space.py
@@ -0,0 +1,61 @@
+from math import floor
+import unittest
+
+
+################################################################################
+# Solution
+################################################################################
+def bounds(r):
+    ct = len(r)
+    if ct % 2 == 0:
+        h = int(ct / 2)
+        return ct, h
+    else:
+        h = floor(ct / 2)
+        return ct, h
+
+
+def find_repeat(xs):
+    ct, h = bounds(xs)
+    rl = range(1, h + 1)
+    rr = range(h + 1, ct)
+    while True:
+        nl = len([None for x in xs if x in rl])
+        nr = len([None for x in xs if x in rr])
+        branch = rl if nl > nr else rr
+        if len(branch) == 1:
+            return branch[0]
+        ct, h = bounds(branch)
+        rl = range(branch[0], branch[0])
+        rr = range(branch[0] + h, branch[-1] + 1)
+    raise Exception(
+        'We could not find any duplicates in xs. Perhaps xs did not adhere to the usage contract.'
+    )
+
+
+################################################################################
+# Tests
+################################################################################
+class Test(unittest.TestCase):
+    def test_just_the_repeated_number(self):
+        actual = find_repeat([1, 1])
+        expected = 1
+        self.assertEqual(actual, expected)
+
+    def test_short_list(self):
+        actual = find_repeat([1, 2, 3, 2])
+        expected = 2
+        self.assertEqual(actual, expected)
+
+    def test_medium_list(self):
+        actual = find_repeat([1, 2, 5, 5, 5, 5])
+        expected = 5
+        self.assertEqual(actual, expected)
+
+    def test_long_list(self):
+        actual = find_repeat([4, 1, 4, 8, 3, 2, 7, 6, 5])
+        expected = 4
+        self.assertEqual(actual, expected)
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/data_structures_and_algorithms/find-rotation-point.py b/scratch/data_structures_and_algorithms/find-rotation-point.py
new file mode 100644
index 000000000000..2103a5b84f75
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/find-rotation-point.py
@@ -0,0 +1,59 @@
+import unittest
+
+
+################################################################################
+# Solution
+################################################################################
+def find_rotation_point(xs):
+    """Usage of `visited` here is a hack, but works for the test cases
+    (gulp)."""
+    i = 0
+    j = round(len(xs) / 2)
+    result = None
+    visited = set()
+    while not result:
+        if i in visited:
+            i += 1
+        if j in visited:
+            j -= 1
+        visited.add(i)
+        visited.add(j)
+        if xs[j - 1] > xs[j]:
+            result = j
+        elif xs[i] < xs[j]:
+            i = j
+            j += round((len(xs) - j) / 2)
+        elif xs[i] >= xs[j]:
+            i = j
+            j -= round((j - i) / 2)
+    return result
+
+
+################################################################################
+# 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)
+
+    # Are we missing any edge cases?
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/data_structures_and_algorithms/find-unique-int-among-duplicates.py b/scratch/data_structures_and_algorithms/find-unique-int-among-duplicates.py
new file mode 100644
index 000000000000..dfa5de42cc0b
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/find-unique-int-among-duplicates.py
@@ -0,0 +1,45 @@
+import unittest
+
+
+################################################################################
+# Solution
+################################################################################
+def find_unique_delivery_id(xs):
+    a = 0
+    for x in xs:
+        a ^= x
+    return a
+
+
+################################################################################
+# Tests
+################################################################################
+class Test(unittest.TestCase):
+    def test_one_drone(self):
+        actual = find_unique_delivery_id([1])
+        expected = 1
+        self.assertEqual(actual, expected)
+
+    def test_unique_id_comes_first(self):
+        actual = find_unique_delivery_id([1, 2, 2])
+        expected = 1
+        self.assertEqual(actual, expected)
+
+    def test_unique_id_comes_last(self):
+        actual = find_unique_delivery_id([3, 3, 2, 2, 1])
+        expected = 1
+        self.assertEqual(actual, expected)
+
+    def test_unique_id_in_middle(self):
+        actual = find_unique_delivery_id([3, 2, 1, 2, 3])
+        expected = 1
+        self.assertEqual(actual, expected)
+
+    def test_many_drones(self):
+        actual = find_unique_delivery_id(
+            [2, 5, 4, 8, 6, 3, 1, 4, 2, 3, 6, 5, 1])
+        expected = 8
+        self.assertEqual(actual, expected)
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/data_structures_and_algorithms/fixtures.py b/scratch/data_structures_and_algorithms/fixtures.py
new file mode 100644
index 000000000000..27689ca76d04
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/fixtures.py
@@ -0,0 +1,110 @@
+# Using this module to store commonly used, but annoying to create, data
+# structures for my test inputs.
+#
+# Use like:
+# from fixtures import graph_a
+
+################################################################################
+# Constants
+################################################################################
+
+edge_list = [
+    ('a', 'b'),
+    ('a', 'c'),
+    ('a', 'e'),
+    ('b', 'c'),
+    ('b', 'd'),
+    ('c', 'e'),
+    ('d', 'f'),
+    ('e', 'd'),
+    ('e', 'f'),
+]
+
+unweighted_graph = {
+    'a': {'b', 'c', 'e'},
+    'b': {'c', 'd'},
+    'c': {'e'},
+    'd': {'f'},
+    'e': {'d', 'f'},
+    'f': set(),
+}
+
+adjacencies = {
+    'a': {
+        'a': False,
+        'b': False
+    },
+    'a': [],
+    'a': [],
+    'a': [],
+    'a': [],
+    'a': [],
+    'a': [],
+}
+
+weighted_graph = {
+    'a': {(4, 'b'), (2, 'c'), (4, 'e')},
+    'b': {(5, 'c'), (10, 'd')},
+    'c': {(3, 'e')},
+    'd': {(11, 'f')},
+    'e': {(4, 'd'), (5, 'f')},
+    'f': set(),
+}
+
+# This is `weighted_graph` with each of its weighted edges "expanded".
+expanded_weights_graph = {
+    'a': ['b-1', 'c-1', 'e-1'],
+    'b-1': ['b-2'],
+    'b-2': ['b-3'],
+    'b-3': ['b'],
+    'c-1': ['c'],
+    'e-1': ['e-2'],
+    'e-2': ['e-3'],
+    'e-3': ['e'],
+    # and so on...
+}
+
+unweighted_digraph = {
+    '5': {'2', '0'},
+    '4': {'0', '1'},
+    '3': {'1'},
+    '2': {'3'},
+    '1': set(),
+    '0': set(),
+}
+
+################################################################################
+# Functions
+################################################################################
+
+
+def vertices(xs):
+    result = set()
+    for a, b in xs:
+        result.add(a)
+        result.add(b)
+    return result
+
+
+def edges_to_neighbors(xs):
+    result = {v: set() for v in vertices(xs)}
+    for a, b in xs:
+        result[a].add(b)
+    return result
+
+
+def neighbors_to_edges(xs):
+    result = []
+    for k, ys in xs.items():
+        for y in ys:
+            result.append((k, y))
+    return result
+
+
+def edges_to_adjacencies(xs):
+    return xs
+
+
+# Skipping handling adjacencies because I cannot think of a reasonable use-case
+# for it when the vertex labels are items other than integers. I can think of
+# ways of handling this, but none excite me.
diff --git a/scratch/data_structures_and_algorithms/graph-coloring.py b/scratch/data_structures_and_algorithms/graph-coloring.py
new file mode 100644
index 000000000000..bc7f7ceea562
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/graph-coloring.py
@@ -0,0 +1,180 @@
+import unittest
+from collections import deque
+
+
+################################################################################
+# Solution
+################################################################################
+class GraphNode:
+    def __init__(self, label):
+        self.label = label
+        self.neighbors = set()
+        self.color = None
+
+
+# color_graph :: G(V, E) -> Set(Color) -> IO ()
+def color_graph(graph, colors):
+    q = deque()
+    seen = set()
+    q.append(graph[0])
+
+    while q:
+        node = q.popleft()
+
+        illegal = {n.color for n in node.neighbors}
+        for x in colors:
+            if x not in illegal:
+                node.color = x
+
+        seen.add(node)
+
+        for x in node.neighbors:
+            if x not in seen:
+                q.append(x)
+
+        # TODO: Is this the best way to traverse separate graphs?
+        for x in graph:
+            if x not in seen:
+                q.append(x)
+
+    return 0
+
+
+################################################################################
+# Tests
+################################################################################
+class Test(unittest.TestCase):
+    def setUp(self):
+        self.colors = frozenset([
+            'red',
+            'green',
+            'blue',
+            'orange',
+            'yellow',
+            'white',
+        ])
+
+    def assertGraphColoring(self, graph, colors):
+        self.assertGraphHasColors(graph, colors)
+        self.assertGraphColorLimit(graph)
+        for node in graph:
+            self.assertNodeUniqueColor(node)
+
+    def assertGraphHasColors(self, graph, colors):
+        for node in graph:
+            msg = 'Node %r color %r not in %r' % (node.label, node.color,
+                                                  colors)
+            self.assertIn(node.color, colors, msg=msg)
+
+    def assertGraphColorLimit(self, graph):
+        max_degree = 0
+        colors_found = set()
+        for node in graph:
+            degree = len(node.neighbors)
+            max_degree = max(degree, max_degree)
+            colors_found.add(node.color)
+        max_colors = max_degree + 1
+        used_colors = len(colors_found)
+        msg = 'Used %d colors and expected %d at most' % (used_colors,
+                                                          max_colors)
+        self.assertLessEqual(used_colors, max_colors, msg=msg)
+
+    def assertNodeUniqueColor(self, node):
+        for adjacent in node.neighbors:
+            msg = 'Adjacent nodes %r and %r have the same color %r' % (
+                node.label,
+                adjacent.label,
+                node.color,
+            )
+            self.assertNotEqual(node.color, adjacent.color, msg=msg)
+
+    def test_line_graph(self):
+        node_a = GraphNode('a')
+        node_b = GraphNode('b')
+        node_c = GraphNode('c')
+        node_d = GraphNode('d')
+
+        node_a.neighbors.add(node_b)
+        node_b.neighbors.add(node_a)
+        node_b.neighbors.add(node_c)
+        node_c.neighbors.add(node_b)
+        node_c.neighbors.add(node_d)
+        node_d.neighbors.add(node_c)
+
+        graph = [node_a, node_b, node_c, node_d]
+        tampered_colors = list(self.colors)
+        color_graph(graph, tampered_colors)
+        self.assertGraphColoring(graph, self.colors)
+
+    def test_separate_graph(self):
+        node_a = GraphNode('a')
+        node_b = GraphNode('b')
+        node_c = GraphNode('c')
+        node_d = GraphNode('d')
+
+        node_a.neighbors.add(node_b)
+        node_b.neighbors.add(node_a)
+        node_c.neighbors.add(node_d)
+        node_d.neighbors.add(node_c)
+
+        graph = [node_a, node_b, node_c, node_d]
+        tampered_colors = list(self.colors)
+        color_graph(graph, tampered_colors)
+        self.assertGraphColoring(graph, self.colors)
+
+    def test_triangle_graph(self):
+        node_a = GraphNode('a')
+        node_b = GraphNode('b')
+        node_c = GraphNode('c')
+
+        node_a.neighbors.add(node_b)
+        node_a.neighbors.add(node_c)
+        node_b.neighbors.add(node_a)
+        node_b.neighbors.add(node_c)
+        node_c.neighbors.add(node_a)
+        node_c.neighbors.add(node_b)
+
+        graph = [node_a, node_b, node_c]
+        tampered_colors = list(self.colors)
+        color_graph(graph, tampered_colors)
+        self.assertGraphColoring(graph, self.colors)
+
+    def test_envelope_graph(self):
+        node_a = GraphNode('a')
+        node_b = GraphNode('b')
+        node_c = GraphNode('c')
+        node_d = GraphNode('d')
+        node_e = GraphNode('e')
+
+        node_a.neighbors.add(node_b)
+        node_a.neighbors.add(node_c)
+        node_b.neighbors.add(node_a)
+        node_b.neighbors.add(node_c)
+        node_b.neighbors.add(node_d)
+        node_b.neighbors.add(node_e)
+        node_c.neighbors.add(node_a)
+        node_c.neighbors.add(node_b)
+        node_c.neighbors.add(node_d)
+        node_c.neighbors.add(node_e)
+        node_d.neighbors.add(node_b)
+        node_d.neighbors.add(node_c)
+        node_d.neighbors.add(node_e)
+        node_e.neighbors.add(node_b)
+        node_e.neighbors.add(node_c)
+        node_e.neighbors.add(node_d)
+
+        graph = [node_a, node_b, node_c, node_d, node_e]
+        tampered_colors = list(self.colors)
+        color_graph(graph, tampered_colors)
+        self.assertGraphColoring(graph, self.colors)
+
+    def test_loop_graph(self):
+        node_a = GraphNode('a')
+        node_a.neighbors.add(node_a)
+        graph = [node_a]
+        tampered_colors = list(self.colors)
+        with self.assertRaises(Exception):
+            color_graph(graph, tampered_colors)
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/data_structures_and_algorithms/graph-to-graphviz.py b/scratch/data_structures_and_algorithms/graph-to-graphviz.py
new file mode 100644
index 000000000000..0e7e97a20ca7
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/graph-to-graphviz.py
@@ -0,0 +1,39 @@
+from graphviz import Digraph
+from collections import deque
+from fixtures import weighted_graph
+
+# There are three ways to model a graph:
+# 1. Edge list: [(Vertex, Vertex)]
+# 2. Neighbors table: Map(Vertex, [Vertex])
+# 3. Adjacency matrix: [[Boolean]]
+#
+# The following graph is a neighbors table.
+
+
+# to_graphviz :: Vertex -> Map(Vertex, [(Vertex, Weight)]) -> String
+def to_graphviz(start, g):
+    """Compiles the graph into GraphViz."""
+    d = Digraph()
+    q = deque()
+    seen = set()
+
+    q.append(start)
+
+    while q:
+        v = q.popleft()
+        if v in seen:
+            continue
+        d.node(v, label=v)
+
+        for w, x in g[v]:
+            d.edge(v, x, label=str(w))
+            q.append(x)
+        seen.add(v)
+
+    return d.source
+
+
+with open('/tmp/test.gv', 'w') as f:
+    src = to_graphviz('a', weighted_graph)
+    f.write(src)
+    print('/tmp/test.gv created!')
diff --git a/scratch/data_structures_and_algorithms/highest-product-of-3.py b/scratch/data_structures_and_algorithms/highest-product-of-3.py
new file mode 100644
index 000000000000..889663e058da
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/highest-product-of-3.py
@@ -0,0 +1,89 @@
+import unittest
+
+
+################################################################################
+# Solution
+################################################################################
+# f :: [Int] -> Int
+def highest_product_of_3(xs):
+    """Here we're greedily storing:
+    - current max
+    - largest product of two
+    - largest positive number
+    - second largest positive number
+    - largest negative number
+    """
+    if len(xs) < 3:
+        raise Exception
+
+    cm = None
+    ld = xs[0] * xs[1]
+    l2 = min(xs[0], xs[1])
+    if xs[0] < 0 or xs[1] < 0:
+        ln = min(xs[0], xs[1])
+    else:
+        ln = 1
+    l = max(xs[0], xs[1])
+
+    for x in xs[2:]:
+        if not cm:
+            cm = max(x * ln * l, ld * x, x * l * l2)  # beware
+            ld = max(ld, x * ln, x * l)
+            ln = min(ln, x)
+            l = max(l, x)
+            if x < l:
+                l2 = max(l2, x)
+        else:
+            cm = max(cm, x * ln * l, x * ld, x * l * l2)
+            ld = max(ld, x * ln, x * l)
+            ln = min(ln, x)
+            l = max(l, x)
+            if x < l:
+                l2 = max(l2, x)
+
+    return cm
+
+
+################################################################################
+# 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])
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/data_structures_and_algorithms/inflight-entertainment.py b/scratch/data_structures_and_algorithms/inflight-entertainment.py
new file mode 100644
index 000000000000..6e17baef3709
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/inflight-entertainment.py
@@ -0,0 +1,35 @@
+# possible :: Int -> [Int] -> Bool
+def possible(flight_duration, film_durations):
+    seeking = set()
+
+    for x in film_durations:
+        if x in seeking:
+            return True
+        else:
+            seeking.add(flight_duration - x)
+
+    return False
+
+
+should = [
+    (10, [1, 9, 8, 8, 8]),
+    (10, [1, 9]),
+    (10, [1, 9, 5, 5, 6]),
+    (1, [0.5, 0.5]),
+    (1, [0.5, 0.5]),
+]
+
+for a, b in should:
+    print("Testing: %s %s" % (a, b))
+    assert possible(a, b)
+
+shouldnt = [
+    (10, [1, 10, 1, 2, 1, 12]),
+    (1, [0.25, 0.25, 0.25, 0.25]),
+    (5, [1, 2, 2]),
+]
+for a, b in shouldnt:
+    print("Testing: %s %s" % (a, b))
+    assert not possible(a, b)
+
+print("Tests pass")
diff --git a/scratch/data_structures_and_algorithms/knapsack-0-1.py b/scratch/data_structures_and_algorithms/knapsack-0-1.py
new file mode 100644
index 000000000000..c72d19d4ed73
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/knapsack-0-1.py
@@ -0,0 +1,38 @@
+import unittest
+from math import floor
+
+
+def knapify(xs, capacity=None):
+    assert capacity is not None
+    n = len(xs)
+    # For 0/1 Knapsack, we must use a table, since this will encode which values
+    # work for which items. This is cleaner than including a separate data
+    # structure to capture it.
+    maxes = [[0 for x in range(capacity + 1)] for x in range(n + 1)]
+
+    # Build table maxes[][] in bottom up manner
+    for row in range(n + 1):
+        for col in range(capacity + 1):
+            if row == 0 or col == 0:
+                maxes[row][col] = 0
+            elif xs[row - 1][0] <= col:
+                maxes[row][col] = max(
+                    xs[row - 1][1] + maxes[row - 1][col - xs[row - 1][0]],
+                    maxes[row - 1][col])
+            else:
+                maxes[row][col] = maxes[row - 1][col]
+
+    return maxes[-1][capacity]
+
+
+################################################################################
+# Tests
+################################################################################
+class Test(unittest.TestCase):
+    def test_one_cake(self):
+        actual = knapify([(3, 10), (2, 15), (7, 2), (12, 20)], capacity=12)
+        expected = None
+        self.assertEqual(actual, expected)
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/data_structures_and_algorithms/kth-to-last.py b/scratch/data_structures_and_algorithms/kth-to-last.py
new file mode 100644
index 000000000000..8291e54533d5
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/kth-to-last.py
@@ -0,0 +1,82 @@
+import unittest
+
+
+################################################################################
+# Solution
+################################################################################
+def length(x):
+    if not x:
+        return 0
+    else:
+        count = 1
+        while x:
+            x = x.next
+            count += 1
+        return count
+
+
+def kth_to_last_node(k, x):
+    hops = length(x) - 1
+    dest = hops - k
+
+    if k == 0:
+        raise Exception("Our God doesn't support this kind of behavior.")
+
+    if dest < 0:
+        raise Exception('Value k to high for list.')
+
+    while dest > 0:
+        x = x.next
+        dest -= 1
+
+    return x
+
+
+################################################################################
+# 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_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/data_structures_and_algorithms/largest-stack.py b/scratch/data_structures_and_algorithms/largest-stack.py
new file mode 100644
index 000000000000..aab9671eb6d3
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/largest-stack.py
@@ -0,0 +1,107 @@
+import unittest
+
+
+class Stack(object):
+    def __init__(self):
+        """Initialize an empty stack"""
+        self.items = []
+
+    def push(self, item):
+        """Push a new item onto the stack"""
+        self.items.append(item)
+
+    def pop(self):
+        """Remove and return the last item"""
+        # If the stack is empty, return None
+        # (it would also be reasonable to throw an exception)
+        if not self.items:
+            return None
+
+        return self.items.pop()
+
+    def peek(self):
+        """Return the last item without removing it"""
+        if not self.items:
+            return None
+        return self.items[-1]
+
+
+class MaxStack(object):
+    # Implement the push, pop, and get_max methods
+    def __init__(self):
+        self.m = Stack()
+        self.stack = Stack()
+
+    def push(self, item):
+        if self.m.peek() is None:
+            self.m.push(item)
+        elif item >= self.m.peek():
+            self.m.push(item)
+        self.stack.push(item)
+
+    def pop(self):
+        x = self.stack.pop()
+        if x == self.m.peek():
+            self.m.pop()
+        return x
+
+    def get_max(self):
+        return self.m.peek()
+
+
+################################################################################
+# Tests
+################################################################################
+class Test(unittest.TestCase):
+    def test_stack_usage(self):
+        max_stack = MaxStack()
+
+        max_stack.push(5)
+
+        actual = max_stack.get_max()
+        expected = 5
+        self.assertEqual(actual, expected)
+
+        max_stack.push(4)
+        max_stack.push(7)
+        max_stack.push(7)
+        max_stack.push(8)
+
+        actual = max_stack.get_max()
+        expected = 8
+        self.assertEqual(actual, expected)
+
+        actual = max_stack.pop()
+        expected = 8
+        self.assertEqual(actual, expected)
+
+        actual = max_stack.get_max()
+        expected = 7
+        self.assertEqual(actual, expected)
+
+        actual = max_stack.pop()
+        expected = 7
+        self.assertEqual(actual, expected)
+
+        actual = max_stack.get_max()
+        expected = 7
+        self.assertEqual(actual, expected)
+
+        actual = max_stack.pop()
+        expected = 7
+        self.assertEqual(actual, expected)
+
+        actual = max_stack.get_max()
+        expected = 5
+        self.assertEqual(actual, expected)
+
+        actual = max_stack.pop()
+        expected = 4
+        self.assertEqual(actual, expected)
+
+        actual = max_stack.get_max()
+        expected = 5
+        self.assertEqual(actual, expected)
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/data_structures_and_algorithms/linked-list-cycles.py b/scratch/data_structures_and_algorithms/linked-list-cycles.py
new file mode 100644
index 000000000000..75a4b993944c
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/linked-list-cycles.py
@@ -0,0 +1,88 @@
+import unittest
+
+
+################################################################################
+# Solution
+################################################################################
+def contains_cycle(x):
+    if not x:
+        return False
+    elif not x.next:
+        return False
+
+    a = x
+    b = x.next
+
+    while b.next:
+        if a == b:
+            return True
+
+        a = a.next
+        b = b.next.next
+
+    return False
+
+
+################################################################################
+# Tests
+################################################################################
+class Test(unittest.TestCase):
+    class LinkedListNode(object):
+        def __init__(self, value, next=None):
+            self.value = value
+            self.next = next
+
+    def test_linked_list_with_no_cycle(self):
+        fourth = Test.LinkedListNode(4)
+        third = Test.LinkedListNode(3, fourth)
+        second = Test.LinkedListNode(2, third)
+        first = Test.LinkedListNode(1, second)
+        result = contains_cycle(first)
+        self.assertFalse(result)
+
+    def test_cycle_loops_to_beginning(self):
+        fourth = Test.LinkedListNode(4)
+        third = Test.LinkedListNode(3, fourth)
+        second = Test.LinkedListNode(2, third)
+        first = Test.LinkedListNode(1, second)
+        fourth.next = first
+        result = contains_cycle(first)
+        self.assertTrue(result)
+
+    def test_cycle_loops_to_middle(self):
+        fifth = Test.LinkedListNode(5)
+        fourth = Test.LinkedListNode(4, fifth)
+        third = Test.LinkedListNode(3, fourth)
+        second = Test.LinkedListNode(2, third)
+        first = Test.LinkedListNode(1, second)
+        fifth.next = third
+        result = contains_cycle(first)
+        self.assertTrue(result)
+
+    def test_two_node_cycle_at_end(self):
+        fifth = Test.LinkedListNode(5)
+        fourth = Test.LinkedListNode(4, fifth)
+        third = Test.LinkedListNode(3, fourth)
+        second = Test.LinkedListNode(2, third)
+        first = Test.LinkedListNode(1, second)
+        fifth.next = fourth
+        result = contains_cycle(first)
+        self.assertTrue(result)
+
+    def test_empty_list(self):
+        result = contains_cycle(None)
+        self.assertFalse(result)
+
+    def test_one_element_linked_list_no_cycle(self):
+        first = Test.LinkedListNode(1)
+        result = contains_cycle(first)
+        self.assertFalse(result)
+
+    def test_one_element_linked_list_cycle(self):
+        first = Test.LinkedListNode(1)
+        first.next = first
+        result = contains_cycle(first)
+        self.assertTrue(result)
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/data_structures_and_algorithms/merge-sort.py b/scratch/data_structures_and_algorithms/merge-sort.py
new file mode 100644
index 000000000000..6dbe0fa0f3c3
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/merge-sort.py
@@ -0,0 +1,28 @@
+
+
+
+# merge :: [a] -> [a] -> [a]
+# merge([], []): []
+# merge(xs, []): xs
+# merge([], ys): ys
+# merge(xs@[x|xs'], ys@[y|ys'])
+#   when y =< x: cons(y, merge(xs, ys'))
+#   when x < y:  cons(x, merge(xs', ys))
+def merge(xs, ys):
+    if xs == [] and ys == []:
+        return []
+    elif ys == []:
+        return xs
+    elif xs == []:
+        return ys
+    else:
+        x = xs[0]
+        y = ys[0]
+
+        if y <= x:
+            return [y] + merge(xs, ys[1:])
+        else:
+            return [x] + merge(xs[1:], ys)
+        
+print(merge([3, 4, 6, 10, 11, 15],
+            [1, 5, 8, 12, 14, 19]))
diff --git a/scratch/data_structures_and_algorithms/merging-ranges.py b/scratch/data_structures_and_algorithms/merging-ranges.py
new file mode 100644
index 000000000000..4e3604d5bcca
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/merging-ranges.py
@@ -0,0 +1,94 @@
+import unittest
+
+
+################################################################################
+# Solution
+################################################################################
+# do_merge_ranges :: [(Int, Int)] -> [(Int, Int)] -> [(Int, Int)]
+def do_merge_ranges(prev, xs):
+    if len(xs) == 0:
+        return prev
+    elif len(xs) == 1:
+        return prev + xs
+    else:
+        a1, a2 = xs[0]
+        b1, b2 = xs[1]
+        rest = xs[2:]
+        if b1 <= a2:
+            return do_merge_ranges(prev, [(a1, max(a2, b2))] + rest)
+        else:
+            return do_merge_ranges(prev + [(a1, a2)], [(b1, b2)] + rest)
+
+
+# merge_ranges :: [(Int, Int)] -> [(Int, Int)]
+def merge_ranges(xs):
+    xs = xs[:]
+    xs.sort()
+    return do_merge_ranges([], xs)
+
+
+# merge_ranges_b :: [(Int, Int)] -> [(Int, Int)]
+def merge_ranges_b(xs):
+    fi = 0
+    ci = 1
+    result = []
+    xs = xs[:]
+    xs.sort()
+    while ci < len(xs):
+        while ci < len(xs) and xs[ci][0] <= xs[fi][1]:
+            xs[fi] = xs[fi][0], max(xs[ci][1], xs[fi][1])
+            ci += 1
+        result.append(xs[fi])
+        fi = ci
+        ci += 1
+    if fi < len(xs):
+        result.append(xs[fi])
+    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/data_structures_and_algorithms/mesh-message.gv b/scratch/data_structures_and_algorithms/mesh-message.gv
new file mode 100644
index 000000000000..1e67c3954f5f
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/mesh-message.gv
@@ -0,0 +1,11 @@
+strict graph {
+    Min -- {William, Jayden, Omar}
+    William -- {Min, Noam}
+    Jayden -- {Min, Amelia, Ren, Noam}
+    Adam -- {Amelia, Miguel, Sofia, Lucas}
+    Ren -- {Jayden, Omar}
+    Amelia -- {Jayden, Adam, Miguel}
+    Miguel -- {Amelia, Adam, Liam, Nathan}
+    Noam -- {Nathan, Jayden, William}
+    Omar -- {Ren, Min, Scott}
+}
diff --git a/scratch/data_structures_and_algorithms/mesh-message.py b/scratch/data_structures_and_algorithms/mesh-message.py
new file mode 100644
index 000000000000..c9d7d9d74151
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/mesh-message.py
@@ -0,0 +1,97 @@
+import unittest
+from collections import deque
+
+
+################################################################################
+# Solution
+################################################################################
+# get_path :: G(V, E) -> V -> V -> Maybe([V])
+def get_path(g, src, dst):
+    q = deque()
+    result = None
+    seen = set()
+    q.append(([], src))
+
+    if src not in g or dst not in g:
+        raise Exception
+
+    while q:
+        p, node = q.popleft()
+
+        seen.add(node)
+
+        if node == dst:
+            if not result:
+                result = p + [node]
+            elif len(p + [node]) < len(result):
+                result = p + [node]
+        else:
+            if node not in g:
+                raise Exception
+            for x in g.get(node):
+                if not x in seen:
+                    q.append((p + [node], x))
+
+    return result
+
+
+################################################################################
+# Tests
+################################################################################
+class Test(unittest.TestCase):
+    def setUp(self):
+        self.graph = {
+            'a': ['b', 'c', 'd'],
+            'b': ['a', 'd'],
+            'c': ['a', 'e'],
+            'd': ['a', 'b'],
+            '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/scratch/data_structures_and_algorithms/norman.py b/scratch/data_structures_and_algorithms/norman.py
new file mode 100644
index 000000000000..379ba92abba8
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/norman.py
@@ -0,0 +1,78 @@
+
+
+
+# Write a function with the following type signature:L
+# equal? :: String -> String -> Bool
+#
+# Determine equality between two inputs with backspace characters encoded as
+# "<".
+
+################################################################################
+# Solution 1
+################################################################################
+
+# from collections import deque
+
+# def equal(a, b):
+#     sa = deque()
+#     sb = deque()
+
+#     for c in a:
+#         if c == '<':
+#             sa.pop()
+#         else:
+#             sa.append(c)
+
+#     for c in b:
+#         if c == '<':
+#             sb.pop()
+#         else:
+#             sb.append(c)
+
+#     return sa == sb
+
+################################################################################
+# Solution 2
+################################################################################
+
+def handle_dels(num_dels, i, xs):
+    if i < 0:
+        return -1
+
+    while xs[i] == '<':
+        num_dels += 1
+        i -= 1
+
+    while num_dels > 0 and xs[i] != '<':
+        num_dels -= 1
+        i -= 1
+
+    if xs[i] == '<':
+        return handle_dels(num_dels, i, xs)
+    else:
+        return i
+
+def update_index(i, xs):
+    # TODO: Indexing into non-available parts of a string.
+    if xs[i] != '<' and xs[i - 1] != '<':
+        return i - 1
+
+    elif xs[i - 1] == '<':
+        return handle_dels(0, i - 1, xs)
+
+def equal(a, b):
+    ia = len(a) - 1
+    ib = len(b) - 1
+
+    while ia >= 0 and ib >= 0:
+        if a[ia] != b[ib]:
+            return False
+        ia = update_index(ia, a)
+        ib = update_index(ib, b)
+
+    if ia != 0:
+        return update_index(ia, a) <= -1
+    if ib != 0:
+        return update_index(ib, b) <= -1
+
+    return True
diff --git a/scratch/data_structures_and_algorithms/nth-fibonacci.py b/scratch/data_structures_and_algorithms/nth-fibonacci.py
new file mode 100644
index 000000000000..cdb2846ea338
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/nth-fibonacci.py
@@ -0,0 +1,59 @@
+import unittest
+
+
+################################################################################
+# Solution
+################################################################################
+def fib(n):
+    """This should be accomplishable in O(1) space."""
+    if n in {0, 1}:
+        return n
+    a = 0  # i = 0
+    b = 1  # i = 1
+    for x in range(2, n + 1):
+        result = a + b
+        a = b
+        b = result
+    return result
+
+
+################################################################################
+# 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/scratch/data_structures_and_algorithms/optimal-stopping.py b/scratch/data_structures_and_algorithms/optimal-stopping.py
new file mode 100644
index 000000000000..af13239941d0
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/optimal-stopping.py
@@ -0,0 +1,49 @@
+from random import choice
+from math import floor
+
+# Applying Chapter 1 from "Algorithms to Live By", which describes optimal
+# stopping problems. Technically this simulation is invalid because the
+# `candidates` function takes a lower bound and an upper bound, which allows us
+# to know the cardinal number of an individual candidates. The "look then leap"
+# algorithm is ideal for no-information games - i.e. games when upper and lower
+# bounds aren't known. The `look_then_leap/1` function is ignorant of this
+# information, so it behaves as if in a no-information game. Strangely enough,
+# this algorithm will pick the best candidate 37% of the time.
+#
+# Chapter 1 describes two algorithms:
+# 1. Look-then-leap: ordinal numbers - i.e. no-information games. Look-then-leap
+#    finds the best candidate 37% of the time.
+# 2. Threshold: cardinal numbers - i.e. where upper and lower bounds are
+#    known. The Threshold algorithm finds the best candidate ~55% of the time.
+#
+# All of this and more can be studied as "optimal stopping theory". This applies
+# to finding a spouse, parking a car, picking an apartment in a city, and more.
+
+
+# candidates :: Int -> Int -> Int -> [Int]
+def candidates(lb, ub, ct):
+    xs = list(range(lb, ub + 1))
+    return [choice(xs) for _ in range(ct)]
+
+
+# look_then_leap :: [Integer] -> Integer
+def look_then_leap(candidates):
+    best = candidates[0]
+    seen_ct = 1
+    ignore_ct = floor(len(candidates) * 0.37)
+    for x in candidates[1:]:
+        if ignore_ct > 0:
+            ignore_ct -= 1
+            best = max(best, x)
+        else:
+            if x > best:
+                print('Choosing the {} candidate.'.format(seen_ct))
+                return x
+        seen_ct += 1
+    print('You may have waited too long.')
+    return candidates[-1]
+
+
+candidates = candidates(1, 100, 100)
+print(candidates)
+print(look_then_leap(candidates))
diff --git a/scratch/data_structures_and_algorithms/perm-tree.py b/scratch/data_structures_and_algorithms/perm-tree.py
new file mode 100644
index 000000000000..0eb389c26bb9
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/perm-tree.py
@@ -0,0 +1,83 @@
+import unittest
+
+
+################################################################################
+# Answer
+################################################################################
+class Node(object):
+    def __init__(self, value, children=set()):
+        self.value = value
+        self.children = children
+
+
+# treeify :: Char -> Set(Char) -> Node(Char)
+def treeify(x, xs):
+    return Node(x, [treeify(c, xs - {c}) for c in xs])
+
+
+# dft :: Node(Char) -> [String]
+def dft(node):
+    result = []
+    s = []
+
+    s.append(('', node))
+
+    while s:
+        p, n = s.pop()
+        p += str(n.value)
+
+        if not n.children:
+            result.append(p)
+        else:
+            for c in n.children:
+                s.append((p, c))
+
+    return result
+
+
+# main :: String -> Set(String)
+def get_permutations(xs):
+    if xs == '':
+        return set([''])
+
+    ys = set(xs)
+    trees = []
+
+    for y in ys:
+        trees.append(treeify(y, ys - {y}))
+
+    result = set()
+
+    for t in trees:
+        for d in dft(t):
+            result.add(d)
+
+    return result
+
+
+################################################################################
+# 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/data_structures_and_algorithms/permutation-palindrome.py b/scratch/data_structures_and_algorithms/permutation-palindrome.py
new file mode 100644
index 000000000000..0a2136a408f2
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/permutation-palindrome.py
@@ -0,0 +1,49 @@
+from collections import Counter
+import unittest
+
+
+################################################################################
+# Impl
+################################################################################
+# palindromifiable :: String -> Boolean
+def has_palindrome_permutation(x):
+    bag = Counter(x)
+    odd_entries_ct = 0
+
+    for _, y in bag.items():
+        if y % 2 != 0:
+            odd_entries_ct += 1
+
+    return odd_entries_ct 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/scratch/data_structures_and_algorithms/permutations.py b/scratch/data_structures_and_algorithms/permutations.py
new file mode 100644
index 000000000000..fc2c1ef7eebc
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/permutations.py
@@ -0,0 +1,55 @@
+class Node(object):
+    # ctor :: a -> [a] -> Node(a)
+    def __init__(self, value, children=[]):
+        self.value = value
+        self.children = children
+
+
+# is_leaf :: Node(a) -> Boolean
+def is_leaf(node):
+    return len(node.children) == 0
+
+
+# enumerate :: Node(a) -> Set(List(a))
+def enumerate(node):
+    current = []
+    result = []
+    q = []
+
+    q.append(node)
+
+    while q:
+        x = q.pop()
+        print(x.value)
+
+        for c in x.children:
+            q.append(c)
+
+        current.append(x.value)
+        print(current)
+
+        if is_leaf(x):
+            result.append(current)
+            print("Reseting current")
+            current = []
+
+    return result
+
+
+node = Node('root', [
+    Node('a', [
+        Node('b', [Node('c')]),
+        Node('c', [Node('b')]),
+    ]),
+    Node('b', [
+        Node('a', [Node('c')]),
+        Node('c', [Node('a')]),
+    ]),
+    Node('c', [
+        Node('a', [Node('b')]),
+        Node('b', [Node('a')]),
+    ])
+])
+
+print('----------')
+print(enumerate(node))
diff --git a/scratch/data_structures_and_algorithms/plot.py b/scratch/data_structures_and_algorithms/plot.py
new file mode 100644
index 000000000000..5601891a0d9b
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/plot.py
@@ -0,0 +1,9 @@
+import numpy as np
+import matplotlib.pyplot as plt
+
+rng = np.random.RandomState(10)  # deterministic random data
+a = np.hstack((rng.normal(size=1000), rng.normal(loc=5, scale=2, size=1000)))
+_ = plt.hist(a, bins='auto')  # arguments are passed to np.histogram
+plt.title("Histogram with 'auto' bins")
+Text(0.5, 1.0, "Histogram with 'auto' bins")
+plt.show()
diff --git a/scratch/data_structures_and_algorithms/product-of-other-numbers.py b/scratch/data_structures_and_algorithms/product-of-other-numbers.py
new file mode 100644
index 000000000000..d05e82d42b02
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/product-of-other-numbers.py
@@ -0,0 +1,68 @@
+import unittest
+
+
+################################################################################
+# Solution
+################################################################################
+# f :: [Int] -> [Int]
+def get_products_of_all_ints_except_at_index(xs):
+    if len(xs) in {0, 1}:
+        raise Exception
+
+    ct = len(xs)
+    lefts = [1] * ct
+    rights = [1] * ct
+    result = []
+
+    for i in range(1, ct):
+        lefts[i] = lefts[i - 1] * xs[i - 1]
+    for i in range(ct - 2, -1, -1):
+        rights[i] = rights[i + 1] * xs[i + 1]
+
+    return [lefts[i] * rights[i] for i in range(ct)]
+
+
+################################################################################
+# 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/scratch/data_structures_and_algorithms/queue-two-stacks.py b/scratch/data_structures_and_algorithms/queue-two-stacks.py
new file mode 100644
index 000000000000..63da08ebf79a
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/queue-two-stacks.py
@@ -0,0 +1,66 @@
+import unittest
+
+
+################################################################################
+# Solution
+################################################################################
+class QueueTwoStacks(object):
+    def __init__(self):
+        self.a = []
+        self.b = []
+
+    def enqueue(self, x):
+        self.a.append(x)
+
+    def dequeue(self):
+        if self.b:
+            return self.b.pop()
+        else:
+            while self.a:
+                self.b.append(self.a.pop())
+            return self.dequeue()
+
+
+################################################################################
+# Tests
+################################################################################
+class Test(unittest.TestCase):
+    def test_basic_queue_operations(self):
+        queue = QueueTwoStacks()
+        queue.enqueue(1)
+        queue.enqueue(2)
+        queue.enqueue(3)
+        actual = queue.dequeue()
+        expected = 1
+        self.assertEqual(actual, expected)
+        actual = queue.dequeue()
+        expected = 2
+        self.assertEqual(actual, expected)
+        queue.enqueue(4)
+        actual = queue.dequeue()
+        expected = 3
+        self.assertEqual(actual, expected)
+        actual = queue.dequeue()
+        expected = 4
+        self.assertEqual(actual, expected)
+
+    def test_error_when_dequeue_from_new_queue(self):
+        queue = QueueTwoStacks()
+        with self.assertRaises(Exception):
+            queue.dequeue()
+
+    def test_error_when_dequeue_from_empty_queue(self):
+        queue = QueueTwoStacks()
+        queue.enqueue(1)
+        queue.enqueue(2)
+        actual = queue.dequeue()
+        expected = 1
+        self.assertEqual(actual, expected)
+        actual = queue.dequeue()
+        expected = 2
+        self.assertEqual(actual, expected)
+        with self.assertRaises(Exception):
+            queue.dequeue()
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/data_structures_and_algorithms/rectangular-love.py b/scratch/data_structures_and_algorithms/rectangular-love.py
new file mode 100644
index 000000000000..47c0f53979c6
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/rectangular-love.py
@@ -0,0 +1,246 @@
+import unittest
+
+
+################################################################################
+# Solution
+################################################################################
+# bottom :: Rectangle -> Int
+def bottom(x):
+    return x.get('bottom_y')
+
+
+# top :: Rectangle -> Int
+def top(x):
+    return bottom(x) + x.get('height')
+
+
+# left :: Rectangle -> Int
+def left(x):
+    return x.get('left_x')
+
+
+# right :: Rectangle -> Int
+def right(x):
+    return left(x) + x.get('width')
+
+
+# sort_highest :: Rectangle -> Rectangle -> (Rectangle, Rectangle)
+def sort_highest(x, y):
+    if top(x) >= top(y):
+        return x, y
+    else:
+        return y, x
+
+
+# sort_leftmost :: Rectangle -> Rectangle -> (Rectangle, Rectangle)
+def sort_leftmost(x, y):
+    if left(x) <= left(y):
+        return x, y
+    else:
+        return y, x
+
+
+# rectify :: Int -> Int -> Int -> Int -> Rectify
+def rectify(top=None, bottom=None, left=None, right=None):
+    assert top >= bottom
+    assert left <= right
+    return {
+        'left_x': left,
+        'bottom_y': bottom,
+        'width': right - left,
+        'height': top - bottom,
+    }
+
+
+# empty_rect :: Rectangle
+def empty_rect():
+    return {
+        'left_x': None,
+        'bottom_y': None,
+        'width': None,
+        'height': None,
+    }
+
+
+# find_rectangular_overlap :: Rectangle -> Rectangle -> Maybe(Rectangle)
+def find_rectangular_overlap(x, y):
+    ha, hb = sort_highest(x, y)
+    la, lb = sort_leftmost(x, y)
+
+    if bottom(hb) <= top(hb) <= bottom(ha) <= top(ha):
+        return empty_rect()
+
+    if left(la) <= right(la) <= left(lb) <= right(lb):
+        return empty_rect()
+
+    # We should have an intersection here.
+    verts = [bottom(ha), top(ha), bottom(hb), top(hb)]
+    verts.sort()
+    horzs = [left(la), right(la), left(lb), right(lb)]
+    horzs.sort()
+    return rectify(top=verts[2],
+                   bottom=verts[1],
+                   left=horzs[1],
+                   right=horzs[2])
+
+
+################################################################################
+# Tests
+################################################################################
+class Test(unittest.TestCase):
+    def test_overlap_along_both_axes(self):
+        rect1 = {
+            'left_x': 1,
+            'bottom_y': 1,
+            'width': 6,
+            'height': 3,
+        }
+        rect2 = {
+            'left_x': 5,
+            'bottom_y': 2,
+            'width': 3,
+            'height': 6,
+        }
+        expected = {
+            'left_x': 5,
+            'bottom_y': 2,
+            'width': 2,
+            'height': 2,
+        }
+        actual = find_rectangular_overlap(rect1, rect2)
+        self.assertEqual(actual, expected)
+
+    def test_one_rectangle_inside_another(self):
+        rect1 = {
+            'left_x': 1,
+            'bottom_y': 1,
+            'width': 6,
+            'height': 6,
+        }
+        rect2 = {
+            'left_x': 3,
+            'bottom_y': 3,
+            'width': 2,
+            'height': 2,
+        }
+        expected = {
+            'left_x': 3,
+            'bottom_y': 3,
+            'width': 2,
+            'height': 2,
+        }
+        actual = find_rectangular_overlap(rect1, rect2)
+        self.assertEqual(actual, expected)
+
+    def test_both_rectangles_the_same(self):
+        rect1 = {
+            'left_x': 2,
+            'bottom_y': 2,
+            'width': 4,
+            'height': 4,
+        }
+        rect2 = {
+            'left_x': 2,
+            'bottom_y': 2,
+            'width': 4,
+            'height': 4,
+        }
+        expected = {
+            'left_x': 2,
+            'bottom_y': 2,
+            'width': 4,
+            'height': 4,
+        }
+        actual = find_rectangular_overlap(rect1, rect2)
+        self.assertEqual(actual, expected)
+
+    def test_touch_on_horizontal_edge(self):
+        rect1 = {
+            'left_x': 1,
+            'bottom_y': 2,
+            'width': 3,
+            'height': 4,
+        }
+        rect2 = {
+            'left_x': 2,
+            'bottom_y': 6,
+            'width': 2,
+            'height': 2,
+        }
+        expected = {
+            'left_x': None,
+            'bottom_y': None,
+            'width': None,
+            'height': None,
+        }
+        actual = find_rectangular_overlap(rect1, rect2)
+        self.assertEqual(actual, expected)
+
+    def test_touch_on_vertical_edge(self):
+        rect1 = {
+            'left_x': 1,
+            'bottom_y': 2,
+            'width': 3,
+            'height': 4,
+        }
+        rect2 = {
+            'left_x': 4,
+            'bottom_y': 3,
+            'width': 2,
+            'height': 2,
+        }
+        expected = {
+            'left_x': None,
+            'bottom_y': None,
+            'width': None,
+            'height': None,
+        }
+        actual = find_rectangular_overlap(rect1, rect2)
+        self.assertEqual(actual, expected)
+
+    def test_touch_at_a_corner(self):
+        rect1 = {
+            'left_x': 1,
+            'bottom_y': 1,
+            'width': 2,
+            'height': 2,
+        }
+        rect2 = {
+            'left_x': 3,
+            'bottom_y': 3,
+            'width': 2,
+            'height': 2,
+        }
+        expected = {
+            'left_x': None,
+            'bottom_y': None,
+            'width': None,
+            'height': None,
+        }
+        actual = find_rectangular_overlap(rect1, rect2)
+        self.assertEqual(actual, expected)
+
+    def test_no_overlap(self):
+        rect1 = {
+            'left_x': 1,
+            'bottom_y': 1,
+            'width': 2,
+            'height': 2,
+        }
+        rect2 = {
+            'left_x': 4,
+            'bottom_y': 6,
+            'width': 3,
+            'height': 6,
+        }
+        expected = {
+            'left_x': None,
+            'bottom_y': None,
+            'width': None,
+            'height': None,
+        }
+        actual = find_rectangular_overlap(rect1, rect2)
+        self.assertEqual(actual, expected)
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/data_structures_and_algorithms/recursive-string-permutations.py b/scratch/data_structures_and_algorithms/recursive-string-permutations.py
new file mode 100644
index 000000000000..70461ddf5dac
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/recursive-string-permutations.py
@@ -0,0 +1,37 @@
+import unittest
+
+
+################################################################################
+# Implementation
+################################################################################
+# get_permutations :: String -> Set(String)
+def get_permutations(string):
+    pass
+
+
+################################################################################
+# 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/data_structures_and_algorithms/reverse-linked-list.py b/scratch/data_structures_and_algorithms/reverse-linked-list.py
new file mode 100644
index 000000000000..b7396b20ce3f
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/reverse-linked-list.py
@@ -0,0 +1,79 @@
+import unittest
+
+
+################################################################################
+# Solution
+################################################################################
+# reverse :: List(a) -> List(a)
+def reverse(node):
+    curr = node
+    prev = None
+    while curr:
+        nxt = curr.next
+        curr.next = prev
+        prev = curr
+        curr = nxt
+    # Make sure to understand the spec! Debugging takes time. Rewriting takes
+    # time.
+    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/data_structures_and_algorithms/reverse-words.py b/scratch/data_structures_and_algorithms/reverse-words.py
new file mode 100644
index 000000000000..5df12ebabdc7
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/reverse-words.py
@@ -0,0 +1,181 @@
+from collections import deque
+import unittest
+
+################################################################################
+# Solution
+################################################################################
+
+
+def rev(xs, i, j):
+    """Reverse xs in place from [i, j]"""
+    while i < j:
+        xs[i], xs[j] = xs[j], xs[i]
+        i += 1
+        j -= 1
+
+
+def rotate(xs, n, i=None, j=None):
+    """Mutably rotates list, xs, n times. Positive n values rotate right while
+    negative n values rotate left. Rotate within window [i, j]."""
+    i = i or 0
+    j = j or len(xs) - 1
+    ct = j - i
+
+    if n < 0:
+        n = abs(n)
+        p = i + n - 1
+        rev(xs, i, p)
+        rev(xs, p + 1, j)
+        rev(xs, i, j)
+    else:
+        p = j - (n - 1)
+        rev(xs, p, j)
+        rev(xs, i, p - 1)
+        rev(xs, i, j)
+    return xs
+
+
+def rev_words(xs, i, j):
+    if j + 1 == len(xs):
+        return 0
+
+    while j + 1 < len(xs):
+        while j + 1 < len(xs) and xs[j + 1] != ' ':
+            j += 1
+
+        rev(xs, i, j)
+        j += 2
+        i = j
+
+    return 0
+
+
+def reverse_words(xs):
+    # first reverse everything
+    rev(xs, 0, len(xs) - 1)
+    return rev_words(xs, 0, 0)
+
+
+def reverse_words_bak(xs, i=None, j=None):
+    i = i or 0
+    j = j or len(xs) - 1
+    w0, w1 = [], []
+
+    if i >= j:
+        return 0
+
+    pi = i
+    while pi < len(xs) and xs[pi] != ' ':
+        w0.append(xs[pi])
+        pi += 1
+
+    if pi == len(xs):
+        return 0
+
+    pj = j
+    while xs[pj] != ' ':
+        w1.append(xs[pj])
+        pj -= 1
+
+    d = len(w0) - len(w1)
+
+    rotate(xs, -1 * d, i, j)
+
+    for k in range(len(w1)):
+        xs[i + k] = w1[len(w1) - 1 - k]
+
+    for k in range(len(w0)):
+        xs[j - k] = w0[len(w0) - 1 - k]
+
+    while i != j and xs[i] != ' ' and xs[j] != ' ':
+        i += 1
+        j -= 1
+
+    if i == j:
+        return 0
+
+    elif xs[i] == ' ':
+        while j > 0 and xs[j] != ' ':
+            j -= 1
+        if j == 0:
+            return 0
+    elif xs[j] == ' ':
+        while i < len(xs) and xs[i] != ' ':
+            i += 1
+        if i == len(xs):
+            return 0
+    return reverse_words(xs, i + 1, j - 1)
+
+
+################################################################################
+# Tests
+################################################################################
+class Test(unittest.TestCase):
+    def test_rev(self):
+        xs = [1, 2, 3, 4, 5]
+        rev(xs, 0, len(xs) - 1)
+        self.assertEqual(xs, [5, 4, 3, 2, 1])
+
+    def test_rotate(self):
+        ys = [1, 2, 3, 4, 5]
+        xs = ys[:]
+        self.assertEqual(rotate(xs, 1, 1, 3), [1, 4, 2, 3, 5])
+        xs = ys[:]
+        self.assertEqual(rotate(xs, -1, 1, 3), [1, 3, 4, 2, 5])
+        xs = ys[:]
+        self.assertEqual(rotate(xs, 1), [5, 1, 2, 3, 4])
+        xs = ys[:]
+        self.assertEqual(rotate(xs, -1), [2, 3, 4, 5, 1])
+        xs = ys[:]
+        self.assertEqual(rotate(xs, -2), [3, 4, 5, 1, 2])
+        xs = ys[:]
+        self.assertEqual(rotate(xs, -5), [1, 2, 3, 4, 5])
+        xs = ys[:]
+        self.assertEqual(rotate(xs, 5), [1, 2, 3, 4, 5])
+        xs = ys[:]
+        self.assertEqual(rotate(xs, 3), [3, 4, 5, 1, 2])
+
+    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('at rat house')
+        reverse_words(message)
+        expected = list('house rat at')
+        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)
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/data_structures_and_algorithms/second-largest-item-bst.py b/scratch/data_structures_and_algorithms/second-largest-item-bst.py
new file mode 100644
index 000000000000..bc167d975a7b
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/second-largest-item-bst.py
@@ -0,0 +1,179 @@
+import unittest
+from collections import deque
+
+
+################################################################################
+# Implementation
+################################################################################
+def is_leaf(node):
+    return node.left is None and node.right is None
+
+
+def find_largest(node):
+    current = node
+    while current.right is not None:
+        current = current.right
+    return current.value
+
+
+def find_second_largest(node):
+    history = deque()
+    current = node
+
+    while current.right:
+        history.append(current)
+        current = current.right
+
+    if current.left:
+        return find_largest(current.left)
+    elif history:
+        return history.pop().value
+    else:
+        raise TypeError
+
+
+def find_second_largest_backup(node):
+    history = deque()
+    current = node
+
+    # traverse -> largest
+    while current.right:
+        history.append(current)
+        current = current.right
+
+    if current.left:
+        return find_largest(current.left)
+    elif history:
+        return history.pop().value
+    else:
+        raise ArgumentError
+
+
+# Write a iterative version to avoid consuming memory with the call stack.
+# Commenting out the recursive code for now.
+def find_second_largest_backup(node):
+    if node.left is None and node.right is None:
+        raise ArgumentError
+
+    elif node.right is None and is_leaf(node.left):
+        return node.left.value
+
+    # recursion
+    # elif node.right is None:
+    #     return find_largest(node.left)
+
+    # iterative version
+    elif node.right is None:
+        current = node.left
+        while current.right is not None:
+            current = current.right
+        return current.value
+
+    # recursion
+    # TODO: Remove recursion from here.
+    elif not is_leaf(node.right):
+        return find_second_largest(node.right)
+
+    # could do an else here, but let's be more assertive.
+    elif is_leaf(node.right):
+        return node.value
+
+    else:
+        raise ArgumentError
+
+
+################################################################################
+# 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(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)
+        actual = find_second_largest(tree)
+        expected = 70
+        self.assertEqual(actual, expected)
+
+    def test_largest_has_a_left_child(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)
+        actual = find_second_largest(tree)
+        expected = 60
+        self.assertEqual(actual, expected)
+
+    def test_largest_has_a_left_subtree(self):
+        tree = Test.BinaryTreeNode(50)
+        left = tree.insert_left(30)
+        right = tree.insert_right(70)
+        left.insert_left(10)
+        left.insert_right(40)
+        right_left = right.insert_left(60)
+        right_left_left = right_left.insert_left(55)
+        right_left.insert_right(65)
+        right_left_left.insert_right(58)
+        actual = find_second_largest(tree)
+        expected = 65
+        self.assertEqual(actual, expected)
+
+    def test_second_largest_is_root_node(self):
+        tree = Test.BinaryTreeNode(50)
+        left = tree.insert_left(30)
+        tree.insert_right(70)
+        left.insert_left(10)
+        left.insert_right(40)
+        actual = find_second_largest(tree)
+        expected = 50
+        self.assertEqual(actual, expected)
+
+    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)
+        actual = find_second_largest(tree)
+        expected = 40
+        self.assertEqual(actual, expected)
+
+    def test_ascending_linked_list(self):
+        tree = Test.BinaryTreeNode(50)
+        right = tree.insert_right(60)
+        right_right = right.insert_right(70)
+        right_right.insert_right(80)
+        actual = find_second_largest(tree)
+        expected = 70
+        self.assertEqual(actual, expected)
+
+    def test_error_when_tree_has_one_node(self):
+        tree = Test.BinaryTreeNode(50)
+        with self.assertRaises(Exception):
+            find_second_largest(tree)
+
+    def test_error_when_tree_is_empty(self):
+        with self.assertRaises(Exception):
+            find_second_largest(None)
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/data_structures_and_algorithms/shortest-path-inject-vertices.py b/scratch/data_structures_and_algorithms/shortest-path-inject-vertices.py
new file mode 100644
index 000000000000..e08ea66b8f50
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/shortest-path-inject-vertices.py
@@ -0,0 +1,94 @@
+from heapq import heappush, heappop
+from collections import deque
+from fixtures import weighted_graph, expanded_weights_graph
+
+# UnweightedGraph(a) :: Map(a, Set(a))
+# WeightedGraph(a) :: Map(a, Set(a))
+
+
+# shortest_path_dijkstra :: Vertex -> Vertex -> WeightedGraph(Vertex)
+def shortest_path_dijkstra(a, b, g):
+    q = []
+    seen = set()
+
+    heappush(q, (0, a, [a]))
+
+    while q:
+        w0, v0, path = heappop(q)
+        if v0 in seen:
+            continue
+        elif v0 == b:
+            return w0, path
+        for w1, v1 in g.get(v0):
+            heappush(q, (w0 + w1, v1, path + [v1]))
+        seen.add(v0)
+    return 'weighted', 'pizza'
+
+
+# expand_edge :: Vertex -> (Weight, Vertex) -> Map(Vertex, [Vertex])
+def expand_edge(v0, wv):
+    w, v1 = wv
+    assert w > 1
+
+    result = {v0: ['{}-{}'.format(v1, 1)]}
+    for x in range(w - 2):
+        result['{}-{}'.format(v1, x + 1)] = ['{}-{}'.format(v1, x + 2)]
+    result['{}-{}'.format(v1, w - 1)] = [v1]
+
+    return result
+
+
+# expand_weights :: Vertex -> WeightedGraph(Vertex) -> UnweightedGraph(Vertex)
+def expand_weights(v, g):
+    result = {}
+    q = deque()
+    seen = set()
+
+    q.append(v)
+    while q:
+        v = d.popleft()
+        if v in seen:
+            continue
+        x = expand_edge(v, g.get)
+        for w, v1 in g.get(v):
+            if w > 1:
+                ws = expand_edge(v, (w, v1))
+                result = {**result, **ws}
+            q.append(v)
+        pass
+
+
+# shortest_path_inject :: Vertex -> Vertex -> WeightedGraph(Vertex)
+def shortest_path_inject(a, b, g):
+    q = deque()
+    seen = set()
+
+    q.append((a, [a]))
+
+    while q:
+        v0, path = q.popleft()
+        if v0 == 'dummy':
+            continue
+        elif v0 in seen:
+            continue
+        elif v0 == b:
+            return len(path), path
+        for _, v1 in g.get(v0):
+            q.append((v1, path + [v1]))
+        seen.add(v0)
+        continue
+
+    return None, None
+
+
+print(expand_edge('a', (4, 'b')))
+print(expand_edge('a', (5, 'e')))
+assert expand_weights('a', weighted_graph) == expanded_weights_graph
+# a = 'a'
+# b = 'd'
+# w, x = shortest_path_dijkstra(a, b, weighted_graph)
+# w1, x1 = shortest_path_inject(a, b, weighted_graph)
+# print("[dijkstra]  Shortest path from {} to {} is {} with weight {}".format(
+#     a, b, x, w))
+# print("[injection] Shortest path from {} to {} is {} with weight {}".format(
+#     a, b, x1, w1))
diff --git a/scratch/data_structures_and_algorithms/shuffle.py b/scratch/data_structures_and_algorithms/shuffle.py
new file mode 100644
index 000000000000..bdfbad24263c
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/shuffle.py
@@ -0,0 +1,34 @@
+import random
+
+
+def get_random(floor, ceiling):
+    return random.randrange(floor, ceiling + 1)
+
+
+# shuffle_in_place :: [a] -> IO ()
+def shuffle_in_place(xs):
+    """Fisher-Yates algorithm. Notice that shuffling here is the same as
+    selecting a random permutation of the input set, `xs`."""
+    n = len(xs) - 1
+    for i in range(len(xs)):
+        r = get_random(i, n)
+        xs[i], xs[r] = xs[r], xs[i]
+    return xs
+
+
+# shuffle :: [a] -> [a]
+def shuffle_not_in_place(xs):
+    result = []
+
+    while xs:
+        i = get_random(0, len(xs) - 1)
+        x = xs.pop(i)
+        result.append(x)
+
+    return result
+
+
+xs = [x for x in range(9)]
+print(xs)
+# print(shuffle_not_in_place(xs))
+print(shuffle_in_place(xs[:]))
diff --git a/scratch/data_structures_and_algorithms/string-reverse.py b/scratch/data_structures_and_algorithms/string-reverse.py
new file mode 100644
index 000000000000..8b4cdac1c271
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/string-reverse.py
@@ -0,0 +1,22 @@
+
+# swap :: Int -> Int -> [Char] -> IO ()
+def swap(ia, iz, xs):
+    # handle swap when ia == iz
+    assert ia <= iz
+    xs[ia], xs[iz] = xs[iz], xs[ia]
+    
+
+# reverse :: [Char] -> IO ()
+def reverse(xs):
+    ia = 0
+    iz = len(xs) - 1
+
+    while ia <= iz:
+        swap(ia, iz, xs)
+        ia += 1
+        iz -= 1
+
+x = list("superduperpooper")
+reverse(x)
+print(x)
+print("Tests pass")
diff --git a/scratch/data_structures_and_algorithms/temperature-tracker.py b/scratch/data_structures_and_algorithms/temperature-tracker.py
new file mode 100644
index 000000000000..6b042182f01c
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/temperature-tracker.py
@@ -0,0 +1,84 @@
+import unittest
+
+
+################################################################################
+# Solution
+################################################################################
+class TempTracker(object):
+    def __init__(self):
+        # min / max
+        self.min = None
+        self.max = None
+        # mean
+        self.sum = 0
+        self.num = 0
+        # mode
+        self.nums = [0] * 111
+        self.mode_num = 0
+        self.mode = None
+
+    def insert(self, x):
+        # min / max
+        if not self.min or x < self.min:
+            self.min = x
+        if not self.max or x > self.max:
+            self.max = x
+        # mean
+        self.sum += x
+        self.num += 1
+        # mode
+        self.nums[x] += 1
+        if self.nums[x] >= self.mode_num:
+            self.mode_num = self.nums[x]
+            self.mode = x
+
+    def get_max(self):
+        return self.max
+
+    def get_min(self):
+        return self.min
+
+    def get_mean(self):
+        return self.sum / self.num
+
+    def get_mode(self):
+        return self.mode
+
+
+# Tests
+
+
+class Test(unittest.TestCase):
+    def test_tracker_usage(self):
+        tracker = TempTracker()
+
+        tracker.insert(50)
+        msg = 'failed on first temp recorded'
+        self.assertEqual(tracker.get_max(), 50, msg='max ' + msg)
+        self.assertEqual(tracker.get_min(), 50, msg='min ' + msg)
+        self.assertEqual(tracker.get_mean(), 50.0, msg='mean ' + msg)
+        self.assertEqual(tracker.get_mode(), 50, msg='mode ' + msg)
+
+        tracker.insert(80)
+        msg = 'failed on higher temp recorded'
+        self.assertEqual(tracker.get_max(), 80, msg='max ' + msg)
+        self.assertEqual(tracker.get_min(), 50, msg='min ' + msg)
+        self.assertEqual(tracker.get_mean(), 65.0, msg='mean ' + msg)
+        self.assertIn(tracker.get_mode(), [50, 80], msg='mode ' + msg)
+
+        tracker.insert(80)
+        msg = 'failed on third temp recorded'
+        self.assertEqual(tracker.get_max(), 80, msg='max ' + msg)
+        self.assertEqual(tracker.get_min(), 50, msg='min ' + msg)
+        self.assertEqual(tracker.get_mean(), 70.0, msg='mean ' + msg)
+        self.assertEqual(tracker.get_mode(), 80, msg='mode ' + msg)
+
+        tracker.insert(30)
+        msg = 'failed on lower temp recorded'
+        self.assertEqual(tracker.get_max(), 80, msg='max ' + msg)
+        self.assertEqual(tracker.get_min(), 30, msg='min ' + msg)
+        self.assertEqual(tracker.get_mean(), 60.0, msg='mean ' + msg)
+        self.assertEqual(tracker.get_mode(), 80, msg='mode ' + msg)
+
+
+unittest.main(verbosity=2)
diff --git a/scratch/data_structures_and_algorithms/test.txt b/scratch/data_structures_and_algorithms/test.txt
new file mode 100644
index 000000000000..ce013625030b
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/test.txt
@@ -0,0 +1 @@
+hello
diff --git a/scratch/data_structures_and_algorithms/top-scores.py b/scratch/data_structures_and_algorithms/top-scores.py
new file mode 100644
index 000000000000..8e7b073dd8bd
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/top-scores.py
@@ -0,0 +1,25 @@
+from collections import deque
+
+# list:
+# array:
+# vector:
+# bit-{array,vector}:
+
+
+def sort(xs, highest):
+    v = [0] * (highest + 1)
+    result = deque()
+
+    for x in xs:
+        v[x] += 1
+
+    for i, x in enumerate(v):
+        if x > 0:
+            result.appendleft(i)
+
+    return list(result)
+
+
+assert sort([37, 89, 41, 100, 65, 91, 53],
+            100) == [100, 91, 89, 65, 53, 41, 37]
+print("Tests pass!")
diff --git a/scratch/data_structures_and_algorithms/topo-sort.py b/scratch/data_structures_and_algorithms/topo-sort.py
new file mode 100644
index 000000000000..fe295b0279ff
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/topo-sort.py
@@ -0,0 +1,31 @@
+from fixtures import unweighted_digraph
+from collections import deque
+
+# vertices_no_in_edges :: UnweightedDigraph -> Set(Vertex)
+def vertices_no_in_edges(g):
+    """Return the vertices in graph `g` with no in-edges."""
+    result = set()
+    vertices = set(g.keys())
+    for neighbors in g.values():
+        result = result.union(neighbors)
+    return vertices ^ result
+
+# topo_sort :: UnweightedDigraph -> List(Vertex)
+def topo_sort(g):
+    q = deque()
+    seen = set()
+    result = []
+    for x in vertices_no_in_edges(g):
+        q.append(x)
+    while q:
+        vertex = q.popleft()
+        if vertex in seen:
+            continue
+        result.append(vertex)
+        neighbors = g.get(vertex)
+        for x in g.get(vertex):
+            q.append(x)
+        seen.add(vertex)
+    return result
+
+print(topo_sort(unweighted_digraph))
diff --git a/scratch/data_structures_and_algorithms/trickling-water.py b/scratch/data_structures_and_algorithms/trickling-water.py
new file mode 100644
index 000000000000..45621990ecf9
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/trickling-water.py
@@ -0,0 +1,38 @@
+class Node(object):
+    def __init__(self, value, children=[]):
+        self.value = value
+        self.children = children
+
+
+################################################################################
+# Solution
+################################################################################
+def trip_time(node):
+    s = []
+    result = 0
+    s.append((node.value, node))
+    while s:
+        p, node = s.pop()
+        if not node.children:
+            result = max(result, p)
+        for x in node.children:
+            s.append((p + x.value, x))
+    return result
+
+
+################################################################################
+# Tests
+################################################################################
+tree = Node(
+    0,
+    children=[
+        Node(5, children=[Node(6)]),
+        Node(2, children=[
+            Node(6),
+            Node(10),
+        ]),
+        Node(3, children=[Node(2, children=[Node(11)])]),
+    ])
+
+assert trip_time(tree) == 16
+print("Tests pass!")
diff --git a/scratch/data_structures_and_algorithms/which-appears-twice.py b/scratch/data_structures_and_algorithms/which-appears-twice.py
new file mode 100644
index 000000000000..e9a4f0eb24d0
--- /dev/null
+++ b/scratch/data_structures_and_algorithms/which-appears-twice.py
@@ -0,0 +1,33 @@
+import unittest
+
+
+################################################################################
+# Solution
+################################################################################
+# find_repeat :: [Int] -> Int
+def find_repeat(xs):
+    n = len(xs) - 1
+    return sum(xs) - ((n**2 + n) / 2)
+
+
+################################################################################
+# 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)