Add coding exercises for Facebook interviews

Add attempts at solving coding problems to Briefcase.

66 files changed, 2994 insertions, 0 deletions

diff --git a/scratch/facebook/anglocize-int.py b/scratch/facebook/anglocize-int.py
new file mode 100644
index 000000000000..a828230d0851
--- /dev/null
+++ b/scratch/facebook/anglocize-int.py
@@ -0,0 +1,71 @@
+THOUSAND = int(1e3)
+MILLION = int(1e6)
+BILLION = int(1e9)
+TRILLION = int(1e12)
+
+facts = {
+    1: "One",
+    2: "Two",
+    3: "Three",
+    4: "Four",
+    5: "Five",
+    6: "Six",
+    7: "Seven",
+    8: "Eight",
+    9: "Nine",
+    10: "Ten",
+    11: "Eleven",
+    12: "Twelve",
+    13: "Thirteen",
+    14: "Fourteen",
+    15: "Fifteen",
+    16: "Sixteen",
+    17: "Seventeen",
+    18: "Eighteen",
+    19: "Nineteen",
+    20: "Twenty",
+    30: "Thirty",
+    40: "Forty",
+    50: "Fifty",
+    60: "Sixty",
+    70: "Seventy",
+    80: "Eighty",
+    90: "Ninety",
+    100: "Hundred",
+    THOUSAND: "Thousand",
+    MILLION: "Million",
+    BILLION: "Billion",
+    TRILLION: "Trillion",
+}
+
+def anglocize(x):
+    # ones
+    if x >= 0 and x < 10:
+        pass
+
+    # tens
+    elif x < 100:
+        pass
+
+    # hundreds
+    elif x < THOUSAND:
+        pass
+
+    # thousands
+    elif x < MILLION:
+        pass
+
+    # millions
+    elif x < BILLION:
+        pass
+
+    # billion
+    elif x < TRILLION:
+        pass
+
+    # trillion
+    else:
+        pass
+
+x = 1234
+assert anglocize(x) == "One Thousand, Two Hundred Thirty Four"
diff --git a/scratch/facebook/balanced-binary-tree.py b/scratch/facebook/balanced-binary-tree.py
new file mode 100644
index 000000000000..afa9706f97ba
--- /dev/null
+++ b/scratch/facebook/balanced-binary-tree.py
@@ -0,0 +1,70 @@
+from collections import deque
+
+class Node(object):
+    # __init__ :: T(A)
+    def __init__(self, value=None, left=None, right=None):
+        self.value = value
+        self.left = left
+        self.right = right
+
+    # insert_left :: T(A) -> A -> T(A)
+    def insert_left(self, value):
+        self.left = Node(value)
+        return self.left
+
+    # insert_right :: T(A) -> A -> T(A)
+    def insert_right(self, value):
+        self.right = Node(value)
+        return self.right
+
+    # is_superbalanced :: T(A) -> Bool
+    def is_superbalanced(self):
+        xs = deque()
+        min_depth, max_depth = float('inf'), float('-inf')
+        xs.append((self, 0))
+        while xs:
+            x, d = xs.popleft()
+            # Only redefine the depths at leaf nodes
+            if not x.left and not x.right:
+                min_depth, max_depth = min(min_depth, d), max(max_depth, d)
+            if x.left:
+                xs.append((x.left, d + 1))
+            if x.right:
+                xs.append((x.right, d + 1))
+        return max_depth - min_depth <= 1
+
+    # __repr__ :: T(A) -> String
+    def __repr__(self):
+        result = ''
+        xs = deque()
+        xs.append((self, 0))
+        while xs:
+            node, indent = xs.popleft()
+            result += '{i}{x}\n'.format(i=' ' * indent, x=node.value)
+            if node.left:
+                xs.append((node.left, indent + 2))
+            if node.right:
+                xs.append((node.right, indent + 2))
+        return result
+
+# from_array :: List(A) -> T(A)
+def from_array(values):
+    xs = deque()
+    root = Node()
+    xs.append(root)
+    for value in values:
+        node = xs.popleft()
+        node.value = value
+        node.left = Node()
+        xs.append(node.left)
+        node.right = Node()
+        xs.append(node.right)
+    return root
+
+x = from_array([1, 1, 1, 1, 1, 1, 1])
+print(x)
+print(x.is_superbalanced())
+
+x = Node(1, Node(2), Node(3))
+print(x)
+print(x.is_superbalanced())
diff --git a/scratch/facebook/breakfast-generator.py b/scratch/facebook/breakfast-generator.py
new file mode 100644
index 000000000000..df9b5015ad3a
--- /dev/null
+++ b/scratch/facebook/breakfast-generator.py
@@ -0,0 +1,112 @@
+# After being inspired by...
+# craftinginterpreters.com/representing-code.html
+# ...I'm implementing the breakfast generator that the author describes
+# therein.
+
+import random
+import string
+
+# Breakfast
+
+def breakfast():
+    fn = random.choice([
+        lambda: " ".join([protein(), "with", breakfast(), "on the side"]),
+        lambda: protein(),
+        lambda: bread(),
+    ])
+    return fn()
+
+def protein():
+    fn = random.choice([
+        lambda: " ".join([qualifier(), "crispy", "bacon"]),
+        lambda: "sausage",
+        lambda: " ".join([cooking_method(), "sausage"]),
+    ])
+    return fn()
+
+def qualifier():
+    fn = random.choice([
+        lambda: "really",
+        lambda: "super",
+        lambda: " ".join(["really", qualifier()]),
+    ])
+    return fn()
+
+def cooking_method():
+    return random.choice([
+        "scrambled",
+        "poached",
+        "fried",
+    ])
+
+def bread():
+    return random.choice([
+        "toast",
+        "biscuits",
+        "English muffin",
+    ])
+
+print(breakfast())
+
+# Expression Language
+
+# Because Python is a strictly evaluated language any functions that are
+# mutually recursive won't terminate and will overflow our stack. Therefore, any
+# non-terminals expressed in an alternative are wrapped in lambdas as thunks.
+
+def expression():
+    fn = random.choice([
+        lambda: literal(),
+        lambda: binary(),
+    ])
+    return fn()
+
+def literal():
+    return str(random.randint(0, 100))
+
+def binary():
+    return " ".join([expression(), operator(), expression()])
+
+def operator():
+    return random.choice(["+", "*"])
+
+print(expression())
+
+# Lox
+
+def lox_expression():
+    fn = random.choice([
+        lambda: lox_literal(),
+        lambda: lox_unary(),
+        lambda: lox_binary(),
+        lambda: lox_grouping(),
+    ])
+    return fn()
+
+def lox_literal():
+    fn = random.choice([
+        lambda: str(random.randint(0, 100)),
+        lambda: lox_string(),
+        lambda: random.choice(["true", "false"]),
+        lambda: "nil",
+    ])
+    return fn()
+
+def lox_string():
+    return "\"{}\"".format(
+        "".join(random.choice(string.ascii_lowercase)
+                for _ in range(random.randint(0, 25))))
+
+def lox_grouping():
+    return "(" + lox_expression() + ")"
+
+def lox_unary():
+    return random.choice(["-", "!"]) + lox_expression()
+
+def lox_binary():
+    return lox_expression() + lox_operator() + lox_expression()
+
+def lox_operator():
+    return random.choice(["==", "!=", "<", "<=", ">", ">=", "+", "-", "*", "/"])
+
+print(lox_expression())
diff --git a/scratch/facebook/bst-checker.py b/scratch/facebook/bst-checker.py
new file mode 100644
index 000000000000..50edeeaa1997
--- /dev/null
+++ b/scratch/facebook/bst-checker.py
@@ -0,0 +1,79 @@
+from collections import deque
+
+class Node(object):
+    def __init__(self, value, left=None, right=None):
+        self.value = value
+        self.left = left
+        self.right = right
+
+    def insert_left(self, value):
+        self.left = Node(value)
+        return self.left
+
+    def insert_right(self, value):
+        self.right = Node(value)
+        return self.right
+
+    def min(self):
+        xs = deque()
+        result = float('inf')
+        xs.append(self)
+        while xs:
+            node = xs.popleft()
+            result = min(result, node.value)
+            if node.left:
+                xs.append(node.left)
+            if node.right:
+                xs.append(node.right)
+        return result
+
+    def max(self):
+        xs = deque()
+        result = float('-inf')
+        xs.append(self)
+        while xs:
+            node = xs.popleft()
+            result = max(result, node.value)
+            if node.left:
+                xs.append(node.left)
+            if node.right:
+                xs.append(node.right)
+        return result
+
+    def is_bst(self):
+        result = True
+        if self.left:
+            result = result and self.left.max() < self.value
+        if self.right:
+            result = result and self.right.min() > self.value
+        return result
+
+
+x = Node(
+    50,
+    Node(
+        17,
+        Node(
+            12,
+            Node(9),
+            Node(14),
+        ),
+        Node(
+            23,
+            Node(19),
+        ),
+    ),
+    Node(
+        72,
+        Node(
+            54,
+            None,
+            Node(67)
+        ),
+        Node(76),
+    ),
+)
+
+
+assert x.is_bst()
+print("Success!")
diff --git a/scratch/facebook/cafe-order-checker.py b/scratch/facebook/cafe-order-checker.py
new file mode 100644
index 000000000000..9d88a68069fd
--- /dev/null
+++ b/scratch/facebook/cafe-order-checker.py
@@ -0,0 +1,19 @@
+def orders_are_sorted(take_out, dine_in, audit):
+    if len(take_out) + len(dine_in) != len(audit):
+        return False
+
+    i, j = 0, 0
+    for x in audit:
+        if i < len(take_out) and take_out[i] == x:
+            i += 1
+        elif j < len(dine_in) and dine_in[j] == x:
+            j += 1
+        else:
+            return False
+    return True
+
+
+assert orders_are_sorted([1,3,5], [2,4,6], [1,2,4,3,6,5])
+assert not orders_are_sorted([1,3,5], [2,4,6], [1,2,4,5,6,3])
+assert orders_are_sorted([], [2,4,6], [2,4,6])
+print("Success!")
diff --git a/scratch/facebook/cake_thief.py b/scratch/facebook/cake_thief.py
new file mode 100644
index 000000000000..90a2add06658
--- /dev/null
+++ b/scratch/facebook/cake_thief.py
@@ -0,0 +1,61 @@
+from math import floor
+
+def print_table(table):
+    print('\n-- TABLE --')
+    for row in range(len(table)):
+        x = ''
+        for col in range(len(table[row])):
+            x += ' ' + str(table[row][col])
+        print(x)
+
+def leftover(capacity, kg):
+    n = floor(capacity / kg)
+    return n, capacity - (n * kg)
+
+def init_table(num_rows, num_cols):
+    table = []
+    for _ in range(num_rows):
+        row = []
+        for _ in range(num_cols):
+            row.append(0)
+        table.append(row)
+    return table
+
+def get(table, row, col):
+    if row < 0 or col < 0:
+        return 0
+    return table[row][col]
+
+def max_haul(items, capacity):
+    table = init_table(len(items), capacity)
+
+    for row in range(len(table)):
+        for col in range(len(table[row])):
+            curr_capacity = col + 1
+            kg, val = items[row]
+            # A
+            a = get(table, row - 1, col)
+            # B
+            n, lo = leftover(curr_capacity, kg)
+            b = (val * n) + get(table, row - 1, lo - 1)
+            # commit
+            if kg > curr_capacity:
+                table[row][col] = a
+            else:
+                print(n, lo)
+                table[row][col] = max([a, b])
+            print_table(table)
+    return table[-1][-1]
+
+# There are multiple variants of this problem:
+#   1. We're allowed to take multiple of each item.
+#   2. We can only take one of each item.
+#   3. We can only take a fixed amount of each item.
+
+items = [(7,160), (3,90), (2,15)]
+capacity = 20
+result = max_haul(items, capacity)
+expected = None
+print("Result: {} == Expected: {}".format(result, expected))
+assert result == expected
+print("Success!")
diff --git a/scratch/facebook/camping-knapsack.py b/scratch/facebook/camping-knapsack.py
new file mode 100644
index 000000000000..add59ed409cd
--- /dev/null
+++ b/scratch/facebook/camping-knapsack.py
@@ -0,0 +1,46 @@
+from utils import get, init_table, print_table
+
+def max_haul(capacity, items, names):
+    table = init_table(rows=len(items), cols=capacity, default=0)
+    items_table = init_table(rows=len(items), cols=capacity, default=[])
+    for row in range(len(table)):
+        for col in range(len(table[row])):
+            kg, value = items[row]
+            curr_capacity = col + 1
+
+            if kg > curr_capacity:
+                a = 0
+            else:
+                a = value + get(table, row - 1, curr_capacity - kg - 1)
+            b = get(table, row - 1, col)
+
+            if a > b:
+                rest = get(items_table, row - 1, curr_capacity - kg - 1)
+                knapsack = [names.get(items[row])]
+                if rest:
+                    knapsack += rest
+            else:
+                knapsack = get(items_table, row - 1, col)
+
+            table[row][col] = max([a, b])
+            items_table[row][col] = knapsack
+        print_table(table)
+    return items_table[-1][-1]
+
+water = (3, 10)
+book = (1, 3)
+food = (2, 9)
+jacket = (2, 5)
+camera = (1, 6)
+items = [water, book, food, jacket, camera]
+result = max_haul(6, items, {
+    water: 'water',
+    book: 'book',
+    food: 'food',
+    jacket: 'jacket',
+    camera: 'camera',
+})
+expected = ['camera', 'food', 'water']
+print(result, expected)
+assert result == expected
+print("Success!")
diff --git a/scratch/facebook/coin.py b/scratch/facebook/coin.py
new file mode 100644
index 000000000000..354e2dfb58b8
--- /dev/null
+++ b/scratch/facebook/coin.py
@@ -0,0 +1,50 @@
+def init_table(rows=0, cols=0, default=None):
+    table = []
+    for _ in range(rows):
+        row = []
+        for _ in range(cols):
+            row.append(default)
+        table.append(row)
+    return table
+
+def print_table(table):
+    result = ''
+    for row in range(len(table)):
+        x = ''
+        for col in range(len(table[row])):
+            x += str(table[row][col]) + ' '
+        result += x + '\n'
+    print(result)
+
+def get(table, row, col):
+    if row < 0 or col < 0:
+        return 0
+    else:
+        return table[row][col]
+
+def make_change(coins, amt):
+    table = init_table(rows=len(coins), cols=amt, default=0)
+    for row in range(len(table)):
+        for col in range(len(table[row])):
+            coin = coins[row]
+            curr_amt = col + 1
+            pull_down = get(table, row - 1, col)
+
+            if curr_amt < coin:
+                table[row][col] = pull_down
+            elif curr_amt == coin:
+                table[row][col] = pull_down + 1
+            else:
+                leftover = get(table, row, curr_amt - coin - 1)
+                table[row][col] = pull_down + leftover
+
+    print_table(table)
+    return table[-1][-1]
+
+#   1 2 3 4
+# 1 1 1 1 1
+# 2 1 1 2 2
+# 3 1 1 3 4
+
+result = make_change([3,2,1], 4)
+print(result)
diff --git a/scratch/facebook/delete-node.py b/scratch/facebook/delete-node.py
new file mode 100644
index 000000000000..4034449ef0cd
--- /dev/null
+++ b/scratch/facebook/delete-node.py
@@ -0,0 +1,19 @@
+from linked_list import Node, from_list
+
+def delete(node):
+    if not node.next:
+        node.value = None
+    else:
+        node.value = node.next.value
+        node.next = node.next.next
+
+one = Node(1)
+two = Node(2)
+three = Node(3)
+
+one.next = two
+two.next = three
+
+print(one)
+delete(two)
+print(one)
diff --git a/scratch/facebook/dijkstras.py b/scratch/facebook/dijkstras.py
new file mode 100644
index 000000000000..7031701994a7
--- /dev/null
+++ b/scratch/facebook/dijkstras.py
@@ -0,0 +1,38 @@
+from heapq import heappush, heappop
+import random
+
+# Dijkstra's algorithm will traverse a directed graph with weighted edges. If
+# the edges aren't weighted, we can pretend that each edges weighs 1. The
+# algorithm will find the shortest path between points A and B.
+
+def dijkstra(a, b, graph):
+    h = []
+    seen = set()
+    heappush(h, (0, a, [a], []))
+    while h:
+        km, x, path, steps = heappop(h)
+
+        if x == b:
+            for a, b, d in steps:
+                print("{} -> {} => {}".format(a, b, d))
+            return path, km
+
+        seen.add(x)
+        for c, dist in graph[x]:
+            if c not in seen:
+                heappush(h, (km + dist, c, path + [c], steps + [(x, c, dist)]))
+    return [], float('inf')
+
+graph = {
+    1: [(3, 9), (2, 7), (6, 14)],
+    2: [(1, 7), (3, 10), (4, 15)],
+    3: [(1, 9), (6, 2), (4, 11), (2, 10)],
+    4: [(5, 6), (2, 15), (3, 11)],
+    5: [(4, 6), (6, 9)],
+    6: [(5, 9), (3, 2), (1, 14)],
+}
+
+beg = random.choice(list(graph.keys()))
+end = random.choice(list(graph.keys()))
+print("Searching for the shortest path from {} -> {}".format(beg, end))
+print(dijkstra(beg, end, graph))
diff --git a/scratch/facebook/evaluator.hs b/scratch/facebook/evaluator.hs
new file mode 100644
index 000000000000..1ba46a754892
--- /dev/null
+++ b/scratch/facebook/evaluator.hs
@@ -0,0 +1,39 @@
+module Evaluator where
+
+data Token
+  = TokenInt Integer
+  | TokenAdd
+  | TokenMultiply
+  deriving (Eq, Show)
+
+newtype AST = AST [Token]
+  deriving (Eq, Show)
+
+tokens :: [Token]
+tokens =
+  [ TokenInt 13
+  , TokenAdd
+  , TokenInt 2
+  , TokenMultiply
+  , TokenInt 4
+  , TokenAdd
+  , TokenInt 7
+  , TokenAdd
+  , TokenInt 3
+  , TokenMultiply
+  , TokenInt 8
+  ]
+
+-- expression     -> addition ;
+-- addition       -> multiplication ( "+" multiplication )* ;
+-- multiplication -> terminal ( "*" terminal )* ;
+-- terminal       -> NUMBER ;
+
+parseExpression :: [Token] -> ([Token], AST)
+parseExpression tokens = do
+  lhs, rest = parseMultiplication tokens
+
+parseMulitplication :: [Token] -> ([Token], AST)
+
+main :: IO ()
+main = print $ parse tokens
diff --git a/scratch/facebook/evaluator.py b/scratch/facebook/evaluator.py
new file mode 100644
index 000000000000..14deb66a8f65
--- /dev/null
+++ b/scratch/facebook/evaluator.py
@@ -0,0 +1,234 @@
+# After stumbling through my first technical screen, I'm going to drill
+# algorithms for implementing evaluators for a toy expression language:
+# e.g. 2 + 13 * 3 + 5 * 2
+#
+# As of now, I'm aware of a few algorithms for solving this:
+#   - DONE: Convert infix expression to Polish notation and evaluate the Polish
+#     notation.
+#   - DONE: Evaluate the tokens using two stacks and avoid converting it.
+#   - DONE: Create a tree of depth two to encode the operator precedence and
+#     evaluate that AST.
+#   - TODO: Convert the infix expression to a prefix expression
+#   - TODO: Write a recursive descent parser and evaluate the AST.
+
+operators = {
+    '*': 1,
+    '+': 0,
+}
+
+def tokenize(xs):
+    result = []
+    i = 0
+    while i < len(xs):
+        current = xs[i]
+        if current == ' ':
+            i += 1
+            continue
+        elif current in operators.keys():
+            result.append(current)
+            i += 1
+        else:
+            i += 1
+            while i < len(xs) and xs[i] in {str(n) for n in range(10)}:
+                current += xs[i]
+                i += 1
+            result.append(int(current))
+    return result
+
+# Convert infix to postfix; evaluate postfix
+# I believe this is known as the Shunting-Yards algorithm
+def postfix(tokens):
+    result = []
+    s = []
+    for token in tokens:
+        if type(token) == int:
+            result.append(token)
+        else:
+            while s and operators[token] < operators[s[-1]]:
+                result.append(s.pop())
+            s.append(token)
+    while s:
+        result.append(s.pop())
+    return result
+
+def do_evaluate_with_polish_notation(tokens):
+    s = []
+    for token in tokens:
+        if token == '*':
+            s.append(s.pop() * s.pop())
+        elif token == '+':
+            s.append(s.pop() + s.pop())
+        else:
+            s.append(token)
+    return s[-1]
+
+def evaluate_with_polish_notation(expr):
+    tokens = tokenize(expr)
+    print("Tokens:  {}".format(tokens))
+    pn = postfix(tokens)
+    print("Postfix: {}".format(pn))
+    result = do_evaluate_with_polish_notation(pn)
+    print("Result:  {}".format(result))
+    return result
+
+# Evaluate Tokens
+
+def apply_operator(op, a, b):
+    if op == '*':
+        return a * b
+    elif op == '+':
+        return a + b
+
+def do_evaluate_tokens(tokens):
+    vals = []
+    ops = []
+    for token in tokens:
+        if type(token) == int:
+            vals.append(token)
+        elif token == '*':
+            ops.append(token)
+        elif token == '+':
+            while ops and operators[token] < operators[ops[-1]]:
+                vals.append(apply_operator(ops.pop(), vals.pop(), vals.pop()))
+            ops.append(token)
+        else:
+            raise Exception("Unexpected token: {}".format(token))
+    while ops:
+        vals.append(apply_operator(ops.pop(), vals.pop(), vals.pop()))
+    return vals[-1]
+
+def evaluate_tokens(expr):
+    tokens = tokenize(expr)
+    print("Tokens:  {}".format(tokens))
+    result = do_evaluate_tokens(tokens)
+    print("Result:  {}".format(result))
+    return result
+
+# Ad Hoc Tree
+
+def parse(tokens):
+    result = []
+    series = []
+    for token in tokens:
+        if type(token) == int:
+            series.append(token)
+        elif token == '*':
+            continue
+        elif token == '+':
+            result.append(series)
+            series = []
+        else:
+            raise Exception("Unexpected token: {}".format(token))
+    result.append(series)
+    return result
+
+def product(xs):
+    result = 1
+    for x in xs:
+        result *= x
+    return result
+
+def do_evaluate_ad_hoc_tree(ast):
+    return sum([product(xs) for xs in ast])
+
+def evaluate_ad_hoc_tree(expr):
+    tokens = tokenize(expr)
+    print("Tokens:  {}".format(tokens))
+    ast = parse(tokens)
+    print("AST:     {}".format(ast))
+    result = do_evaluate_ad_hoc_tree(ast)
+    print("Result:  {}".format(result))
+    return result
+
+# Recursive Descent Parser
+
+# expression     -> addition ;
+# addition       -> multiplication ( "+" multiplication )* ;
+# multiplication -> terminal ( "*" terminal )* ;
+# terminal       -> NUMBER ;
+
+class Parser(object):
+    def __init__(self, tokens):
+        self.tokens = tokens
+        self.i = 0
+
+    # mutations
+    def advance(self):
+        self.i += 1
+
+    def consume(self):
+        result = self.curr()
+        self.advance()
+        return result
+
+    # predicates
+    def match(self, x):
+        if self.curr() == x:
+            self.advance()
+            return True
+        return False
+
+    def tokens_available(self):
+        return self.i < len(self.tokens)
+
+    # getters
+    def prev(self):
+        return self.tokens[self.i - 1]
+
+    def curr(self):
+        return self.tokens[self.i] if self.tokens_available() else None
+
+    def next(self):
+        return self.tokens[self.i + 1]
+
+def parse_expression(tokens):
+    parser = Parser(tokens)
+    return parse_addition(parser)
+
+def parse_addition(parser):
+    result = parse_multiplication(parser)
+    while parser.match("+"):
+        op = parser.prev()
+        rhs = parse_multiplication(parser)
+        result = ["+", result, rhs]
+    return result
+
+def parse_multiplication(parser):
+    result = parse_terminal(parser)
+    while parser.match("*"):
+        op = parser.prev()
+        rhs = parse_terminal(parser)
+        result = ["*", result, rhs]
+    return result
+
+def parse_terminal(parser):
+    # If we reach here, the current token *must* be a number.
+    return parser.consume()
+
+def evaluate_ast(ast):
+    if type(ast) == int:
+        return ast
+    else:
+        op, lhs, rhs = ast[0], ast[1], ast[2]
+        return apply_operator(op, evaluate_ast(lhs), evaluate_ast(rhs))
+
+def evaluate_recursive_descent(expr):
+    tokens = tokenize(expr)
+    print("Tokens:  {}".format(tokens))
+    ast = parse_expression(tokens)
+    print("AST:     {}".format(ast))
+    result = evaluate_ast(ast)
+    return result
+
+methods = {
+    'Polish Notation': evaluate_with_polish_notation,
+    'Evaluate Tokens': evaluate_tokens,
+    'Ad Hoc Tree': evaluate_ad_hoc_tree,
+    'Recursive Descent': evaluate_recursive_descent,
+}
+
+for name, fn in methods.items():
+    expr = "13 + 2 * 4 + 7 + 3 * 8"
+    print("Evaluating \"{}\" using the \"{}\" method...".format(expr, name))
+    assert fn(expr) == eval(expr)
+    print("Success!")
diff --git a/scratch/facebook/find-duplicate-optimize-for-space.py b/scratch/facebook/find-duplicate-optimize-for-space.py
new file mode 100644
index 000000000000..7c491aef604e
--- /dev/null
+++ b/scratch/facebook/find-duplicate-optimize-for-space.py
@@ -0,0 +1,22 @@
+import random
+
+def find_duplicate(xs):
+    print(xs)
+    # entry point in our cycle is the duplicate
+    i = xs[0]
+    j = xs[xs[0]]
+    while i != j:
+        print(i, xs[i], j, xs[j])
+        i = xs[i]
+        j = xs[xs[j]]
+    # detect cycle
+    j = 0
+    while i != j:
+        i = xs[i]
+        j = xs[j]
+    return xs[i]
+
+n = random.randint(5, 10)
+xs = [random.randint(0, n - 1) for _ in range(n)]
+result = find_duplicate(xs)
+print(xs, result)
diff --git a/scratch/facebook/find-rotation-point.py b/scratch/facebook/find-rotation-point.py
new file mode 100644
index 000000000000..3636be4d93b5
--- /dev/null
+++ b/scratch/facebook/find-rotation-point.py
@@ -0,0 +1,47 @@
+from math import floor
+
+def find_rotation(xs):
+    if xs[0] < xs[-1]:
+        return xs[0]
+    beg, end = 0, len(xs) - 1
+    found = False
+    count = 10
+    while not found and count >= 0:
+        i = beg + floor((end - beg) / 2)
+        if xs[beg] < xs[i]:
+            beg = i
+            i = beg + floor((end - beg) / 2)
+        elif xs[beg] > xs[i]:
+            end = i
+        found = xs[i - 1] > xs[i]
+        count -= 1
+    return xs[i]
+
+
+xs = [(['ptolemaic',
+        'retrograde',
+        'supplant',
+        'undulate',
+        'xenoepist',
+        'zebra',
+        'asymptote',
+        'babka',
+        'banoffee',
+        'engender',
+        'karpatka',
+        'othellolagkage',
+        ], "asymptote"),
+      (['asymptote',
+        'babka',
+        'banoffee',
+        'engender',
+        'karpatka',
+        'othellolagkage',
+        ], "asymptote"),
+      ]
+
+for x, expected in xs:
+    result = find_rotation(x)
+    print(x, result)
+    assert result == expected
+    print("Success!")
diff --git a/scratch/facebook/find-unique-int-among-duplicates.py b/scratch/facebook/find-unique-int-among-duplicates.py
new file mode 100644
index 000000000000..56032aa05c8c
--- /dev/null
+++ b/scratch/facebook/find-unique-int-among-duplicates.py
@@ -0,0 +1,17 @@
+import random
+
+def find_duplicate(xs):
+    mini, maxi, acc = xs[0], xs[0], xs[0]
+    for i in range(1, len(xs)):
+        mini = min(mini, xs[i])
+        maxi = max(maxi, xs[i])
+        acc = acc ^ xs[i]
+    mask = mini
+    for i in range(mini + 1, maxi + 1):
+        mask = mask ^ i
+    return mask ^ acc
+
+xs = [5, 3, 4, 1, 5, 2]
+print(xs)
+result = find_duplicate(xs)
+print(result)
diff --git a/scratch/facebook/graph-coloring.py b/scratch/facebook/graph-coloring.py
new file mode 100644
index 000000000000..17588166c871
--- /dev/null
+++ b/scratch/facebook/graph-coloring.py
@@ -0,0 +1,60 @@
+from collections import deque
+
+class Palette(object):
+    def __init__(self, n):
+        self.i = 0
+        self.colors = list(range(n))
+
+    def get(self):
+        return self.colors[self.i]
+
+    def advance(self):
+        self.i += 1 % len(self.colors)
+
+class GraphNode(object):
+    def __init__(self, label):
+        self.label = label
+        self.neighbors = set()
+        self.color = None
+
+    def __repr__(self):
+        result = []
+        xs = deque()
+        xs.append(self)
+        seen = set()
+        while xs:
+            node = xs.popleft()
+            result.append('{} ({})'.format(node.label, str(node.color)))
+            seen.add(node.label)
+            for c in node.neighbors:
+                if c.label not in seen:
+                    xs.append(c)
+        return ', '.join(result)
+
+def color_graph(graph, d):
+    seen = set()
+    start = graph
+    xs = deque()
+    palette = Palette(d + 1)
+    xs.append((start, palette.get()))
+    while xs:
+        x, color = xs.popleft()
+        x.color = color
+        seen.add(x.label)
+        for c in x.neighbors:
+            if c.label not in seen:
+                palette.advance()
+                xs.append((c, palette.get()))
+
+a = GraphNode('a')
+b = GraphNode('b')
+c = GraphNode('c')
+
+a.neighbors.add(b)
+b.neighbors.add(a)
+b.neighbors.add(c)
+c.neighbors.add(b)
+
+print(a)
+color_graph(a, 3)
+print(a)
diff --git a/scratch/facebook/highest-product-of-3.py b/scratch/facebook/highest-product-of-3.py
new file mode 100644
index 000000000000..c237b8e52e2d
--- /dev/null
+++ b/scratch/facebook/highest-product-of-3.py
@@ -0,0 +1,20 @@
+def hi_product(xs):
+    lowest_one, highest_one = min(xs[0], xs[1]), max(xs[0], xs[1])
+    lowest_two, highest_two = xs[0] * xs[1], xs[0] * xs[1]
+    highest = float('-inf')
+    for x in xs[2:]:
+        highest = max(highest, highest_two * x, lowest_two * x)
+        lowest_one = min(lowest_one, x)
+        highest_one = max(highest_one, x)
+        lowest_two = min(lowest_two, highest_one * x, lowest_one * x)
+        highest_two = max(highest_two, highest_one * x, lowest_one * x)
+    return highest
+
+xs = [([-10,-10,1,3,2], 300),
+      ([1,10,-5,1,-100], 5000)]
+
+for x, expected in xs:
+    result = hi_product(x)
+    print(x, result)
+    assert result == expected
+    print("Success!")
diff --git a/scratch/facebook/infix-to-postfix.py b/scratch/facebook/infix-to-postfix.py
new file mode 100644
index 000000000000..4c6d64494d95
--- /dev/null
+++ b/scratch/facebook/infix-to-postfix.py
@@ -0,0 +1,51 @@
+operators = {
+    '*': 1,
+    '+': 0,
+}
+
+def tokenize(xs):
+    result = []
+    i = 0
+    while i < len(xs):
+        current = xs[i]
+        if current in operators.keys():
+            result.append(current)
+            i += 1
+            continue
+        else:
+            i += 1
+            while i < len(xs) and xs[i] in {str(n) for n in range(10)}:
+                current += xs[i]
+                i += 1
+            result.append(int(current))
+    return result
+
+def postfix(xs):
+    result = []
+    s = []
+    for x in xs:
+        if x in operators.keys():
+            while s and operators[s[-1]] >= operators[x]:
+                result.append(s.pop())
+            s.append(x)
+        else:
+            result.append(x)
+    while s:
+        result.append(s.pop())
+    return result
+
+def evaluate(xs):
+    s = []
+    for x in xs:
+        print(s, x)
+        if x == '*':
+            s.append(s.pop() * s.pop())
+        elif x == '+':
+            s.append(s.pop() + s.pop())
+        else:
+            s.append(x)
+        print(s)
+    return s[-1]
+
+
+print(evaluate(postfix(tokenize("12+3*10"))))
diff --git a/scratch/facebook/inflight-entertainment.py b/scratch/facebook/inflight-entertainment.py
new file mode 100644
index 000000000000..7ddea5350a4f
--- /dev/null
+++ b/scratch/facebook/inflight-entertainment.py
@@ -0,0 +1,29 @@
+from random import choice
+from utils import init_table
+
+def get(movie, seeking):
+    return any([movie in xs for xs in seeking.values()])
+
+def set_complement(movie, seeking):
+    for duration, xs in seeking.items():
+        seeking[duration].add(duration - movie)
+
+def choose_movies(tolerance, duration, movies):
+    seeking = {duration + i: set() for i in range(-1 * tolerance, tolerance + 1)}
+    for movie in movies:
+        if get(movie, seeking):
+            return movie, duration - movie
+        else:
+            set_complement(movie, seeking)
+    return None
+
+tolerance = 20
+duration = choice([1, 2, 3]) * choice([1, 2]) * choice([15, 30, 45])
+movies = [choice([1, 2, 3]) * choice([15, 30, 45]) for _ in range(10)]
+print("Seeking two movies for a duration of [{}, {}] minutes".format(duration - tolerance, duration + tolerance))
+print(movies)
+result = choose_movies(tolerance, duration, movies)
+if result:
+    print("{} + {} = {}".format(result[0], result[1], duration))
+else:
+    print(":( We're sad because we couldn't find two movies for a {} minute flight".format(duration))
diff --git a/scratch/facebook/knapsack-faq.py b/scratch/facebook/knapsack-faq.py
new file mode 100644
index 000000000000..ae04f5eb96c0
--- /dev/null
+++ b/scratch/facebook/knapsack-faq.py
@@ -0,0 +1,42 @@
+from utils import get, init_table, print_table
+
+# This problem has a few variants:
+#   - limited supply of each item
+#   - unlimited supply of each item
+#   - fractional amounts of each item (e.g. rice)
+
+def max_haul(capacity, items):
+    min_kg = min([kg for _, kg in items])
+    max_kg = max([kg for _, kg in items])
+
+    cols = int(max_kg / min_kg)
+    fr_col_index = lambda index: min_kg * index + min_kg
+    to_col_index = lambda capacity: int((capacity - min_kg) * cols / max_kg)
+
+    table = init_table(rows=len(items), cols=cols, default=0)
+    for row in range(len(table)):
+        for col in range(len(table[row])):
+            curr_capacity = fr_col_index(col)
+            value, kg = items[row]
+
+            if kg > curr_capacity:
+                a = 0
+            else:
+                a = value + get(table, row - 1, to_col_index(curr_capacity - kg))
+
+            b = get(table, row - 1, col)
+            table[row][col] = max([a, b])
+        print_table(table)
+    return table[-1][-1]
+
+guitar = (1500, 1)
+stereo = (3000, 4)
+laptop = (2000, 3)
+necklace = (2000, 0.5)
+items = [necklace, guitar, stereo, laptop]
+capacity = 4
+result = max_haul(capacity, items)
+expected = 4000
+print(result, expected)
+assert result == expected
+print("Success!")
diff --git a/scratch/facebook/kth-to-last-node-in-singly-linked-list.py b/scratch/facebook/kth-to-last-node-in-singly-linked-list.py
new file mode 100644
index 000000000000..dd258d924d10
--- /dev/null
+++ b/scratch/facebook/kth-to-last-node-in-singly-linked-list.py
@@ -0,0 +1,26 @@
+from linked_list import Node, from_list
+
+def kth_to_last_node(k, node):
+    one = node
+    two = node
+    for _ in range(k - 1):
+        if not one:
+            return None
+        one = one.next
+    while one.next:
+        one = one.next
+        two = two.next
+    return two.value
+
+
+xs = from_list(["Angel Food", "Bundt", "Cheese", "Devil's Food", "Eccles"])
+result = kth_to_last_node(2, xs)
+print(result)
+assert result == "Devil's Food"
+print("Success!")
+
+xs = from_list(["Angel Food", "Bundt"])
+result = kth_to_last_node(30, xs)
+print(result)
+assert result is None
+print("Success!")
diff --git a/scratch/facebook/language.py b/scratch/facebook/language.py
new file mode 100644
index 000000000000..b57f469b49d2
--- /dev/null
+++ b/scratch/facebook/language.py
@@ -0,0 +1,70 @@
+import random
+
+# Write an evaluator for a small language:
+#   - operators: '+', '*'
+#   - operands:  Integers
+#
+# E.g. evaluate("2+14*90+5*16")
+
+def tokenize(xs):
+    result = []
+    i = 0
+    while i < len(xs):
+        current = xs[i]
+        if current in {'*', '+'}:
+            result.append(current)
+            i += 1
+            continue
+        elif current == ' ':
+            i += 1
+            continue
+        else:
+            i += 1
+            while i < len(xs) and xs[i] in {str(x) for x in range(10)}:
+                current += xs[i]
+                i += 1
+            result.append(int(current))
+    return result
+
+def ast(tokens):
+    result = []
+    series = []
+    for token in tokens:
+        if token == '+':
+            result.append(series)
+            series = []
+        elif token == '*':
+            continue
+        else:
+            series.append(token)
+    if series:
+        result.append(series)
+    return result
+
+def product(xs):
+    result = 1
+    for x in xs:
+        result *= x
+    return result
+
+def evaluate(x):
+    tokens = tokenize(x)
+    tree = ast(tokens)
+    return sum([product(xs) for xs in tree])
+
+n = 7
+operands = [random.randint(0, 100) for _ in range(n)]
+operators = [random.choice(['+','*']) for _ in range(n - 1)]
+expr = []
+for i in range(n - 1):
+    expr.append(operands[i])
+    expr.append(operators[i])
+expr.append(operands[-1])
+
+expr = ' '.join([str(x) for x in expr])
+print("Expression: {}".format(expr))
+print("Tokens: {}".format(tokenize(expr)))
+print("AST: {}".format(ast(tokenize(expr))))
+print("Answer: {}".format(evaluate(expr)))
+assert evaluate(expr) == eval(expr)
+print("Success!")
diff --git a/scratch/facebook/language2.py b/scratch/facebook/language2.py
new file mode 100644
index 000000000000..3aebd454833b
--- /dev/null
+++ b/scratch/facebook/language2.py
@@ -0,0 +1,50 @@
+
+
+
+
+
+
+
+
+
+def tokenize(xs):
+    result = []
+    i = 0
+    while i < len(xs):
+        curr = xs[i]
+        if curr in {'*','+'}:
+            result.append(curr)
+            i += 1
+            continue
+        i += 1
+        while i < len(xs) and xs[i] in {str(x) for x in range(10)}:
+            curr += xs[i]
+            i += 1
+        result.append(int(curr))
+    return result
+
+def parse(tokens):
+    result = []
+    series = []
+    for token in tokens:
+        if token == '*':
+            continue
+        elif token == '+':
+            result.append(series)
+            series = []
+        else:
+            series.append(token)
+    if series:
+        result.append(series)
+    return result
+
+def product(xs):
+    result = 1
+    for x in xs:
+        result *= x
+    return result
+
+def evaluate(tree):
+    return sum([product(xs) for xs in tree])
+
+print(evaluate(parse(tokenize("2+30*8*9+10"))))
diff --git a/scratch/facebook/largest-contiguous-sum.py b/scratch/facebook/largest-contiguous-sum.py
new file mode 100644
index 000000000000..7761bf1c61df
--- /dev/null
+++ b/scratch/facebook/largest-contiguous-sum.py
@@ -0,0 +1,15 @@
+def find_sum(xs):
+    result = float('-inf')
+    streak = 0
+    for x in xs:
+        result = max(result, streak, x)
+        if streak + x <= 0:
+            streak = x
+        else:
+            streak += x
+    return result
+
+
+x = [2,-8,3,-2,4,-10]
+assert find_sum(x) == 5
+print("Success!")
diff --git a/scratch/facebook/largest-stack.py b/scratch/facebook/largest-stack.py
new file mode 100644
index 000000000000..052db44153d4
--- /dev/null
+++ b/scratch/facebook/largest-stack.py
@@ -0,0 +1,49 @@
+from stack import Stack, from_list
+from heapq import heapify, heappush, heappop
+from random import shuffle
+
+class MaxStack(Stack):
+    def __init__(self):
+        self.max = Stack()
+        super().__init__()
+
+    def __repr__(self):
+        return super().__repr__()
+
+    def push(self, x):
+        super().push(x)
+        max = self.get_max()
+        if not max:
+            self.max.push(x)
+        else:
+            self.max.push(max if x < max else x)
+
+    def pop(self):
+        self.max.pop()
+        return super().pop()
+
+    def get_max(self):
+        return self.max.peek()
+
+xs = list(range(1, 11))
+shuffle(xs)
+stack = MaxStack()
+for x in xs:
+    stack.push(x)
+
+print(stack)
+result = stack.get_max()
+print(result)
+assert result == 10
+
+popped = stack.pop()
+print("Popped: {}".format(popped))
+print(stack)
+while popped != 10:
+    assert stack.get_max() == 10
+    popped = stack.pop()
+    print("Popped: {}".format(popped))
+    print(stack)
+
+assert stack.get_max() != 10
+print("Success!")
diff --git a/scratch/facebook/linked-list-cycles.py b/scratch/facebook/linked-list-cycles.py
new file mode 100644
index 000000000000..56f54d497808
--- /dev/null
+++ b/scratch/facebook/linked-list-cycles.py
@@ -0,0 +1,26 @@
+import random
+
+from linked_list import Node
+
+def contains_cycle(node):
+    one = node
+    two = node
+    while two.next and two.next.next:
+        one = one.next
+        two = two.next.next
+        if one == two:
+            return True
+    return False
+
+xs = Node(1, Node(2, Node(3)))
+assert not contains_cycle(xs)
+print("Success!")
+
+a = Node(1)
+b = Node(2)
+c = Node(3)
+a.next = b
+b.next = c
+c.next = random.choice([a, b, c])
+assert contains_cycle(a)
+print("Success!")
diff --git a/scratch/facebook/linked_list.py b/scratch/facebook/linked_list.py
new file mode 100644
index 000000000000..1ae7061e8393
--- /dev/null
+++ b/scratch/facebook/linked_list.py
@@ -0,0 +1,22 @@
+class Node(object):
+    def __init__(self, value=None, next=None):
+        self.value = value
+        self.next = next
+
+    def __repr__(self):
+        result = []
+        node = self
+        while node:
+            result.append(str(node.value))
+            node = node.next
+        return 'LinkedList({xs})'.format(xs=', '.join(result))
+
+def from_list(xs):
+    head = Node(xs[0])
+    node = head
+    for x in xs[1:]:
+        node.next = Node(x)
+        node = node.next
+    return head
+
+list = from_list(['A', 'B', 'C'])
diff --git a/scratch/facebook/london-knapsack.py b/scratch/facebook/london-knapsack.py
new file mode 100644
index 000000000000..a034fb49611d
--- /dev/null
+++ b/scratch/facebook/london-knapsack.py
@@ -0,0 +1,42 @@
+from utils import get, init_table, print_table
+
+def optimal_itinerary(duration, items):
+    min_duration = min([duration for duration, _ in items])
+    max_duration = max([duration for duration, _ in items])
+    table = init_table(rows=len(items), cols=int(max_duration / min_duration), default=0)
+    to_index = lambda duration: int(duration / min_duration) - 1
+    to_duration = lambda i: i * min_duration + min_duration
+
+    for row in range(len(table)):
+        for col in range(len(table[row])):
+            curr_duration = to_duration(col)
+            duration, value = items[row]
+            if duration > curr_duration:
+                a = 0
+            else:
+                a = value + get(table, row - 1, to_index(curr_duration - duration))
+            b = get(table, row - 1, col)
+            table[row][col] = max([a, b])
+
+        print_table(table)
+    return table[-1][-1]
+
+# You're in London for two days, and you'd like to see the following
+# attractions. How can you maximize your time spent in London?
+westminster = (0.5, 7)
+globe_theater = (0.5, 6)
+national_gallery = (1, 9)
+british_museum = (2, 9)
+st_pauls_cathedral = (0.5, 8)
+items = [
+    westminster,
+    globe_theater,
+    national_gallery,
+    british_museum,
+    st_pauls_cathedral,
+]
+result = optimal_itinerary(2, items)
+expected = 24
+print(result, expected)
+assert result == expected
+print("Success!")
diff --git a/scratch/facebook/longest-common-substring.py b/scratch/facebook/longest-common-substring.py
new file mode 100644
index 000000000000..8a838db45d1e
--- /dev/null
+++ b/scratch/facebook/longest-common-substring.py
@@ -0,0 +1,20 @@
+from utils import get, init_table, print_table
+
+def longest_common_substring(a, b):
+    """
+    Computes the length of the longest string that's present in both `a` and
+    `b`.
+    """
+    table = init_table(rows=len(b), cols=len(a), default=0)
+    for row in range(len(table)):
+        for col in range(len(table[row])):
+            if b[row] == a[col]:
+                table[row][col] = 1 + get(table, row - 1, col - 1)
+    return max([max(row) for row in table])
+
+dictionary = ["fish", "vista"]
+result = [longest_common_substring("hish", x) for x in dictionary]
+expected = [3, 2]
+print(result, expected)
+assert result == expected
+print("Success!")
diff --git a/scratch/facebook/merge-sorted-arrays.py b/scratch/facebook/merge-sorted-arrays.py
new file mode 100644
index 000000000000..ae9377ad116b
--- /dev/null
+++ b/scratch/facebook/merge-sorted-arrays.py
@@ -0,0 +1,44 @@
+def merge_sorted(xs, ys):
+    result = []
+    i, j = 0, 0
+
+    while i < len(xs) and j < len(ys):
+        if xs[i] <= ys[j]:
+            result.append(xs[i])
+            i += 1
+        else:
+            result.append(ys[j])
+            j += 1
+
+    while i < len(xs):
+        result.append(xs[i])
+        i += 1
+
+    while j < len(ys):
+        result.append(ys[j])
+        j += 1
+
+    return result
+
+# A
+result = merge_sorted([3, 4, 6, 10, 11, 15], [1, 5, 8, 12, 14, 19])
+print(result)
+assert result == [1, 3, 4, 5, 6, 8, 10, 11, 12, 14, 15, 19]
+
+# B
+result = merge_sorted([], [1,2,3])
+print(result)
+assert result == [1,2,3]
+
+# C
+result = merge_sorted([1,2,3], [])
+print(result)
+assert result == [1,2,3]
+
+# D
+result = merge_sorted([], [])
+print(result)
+assert result == []
+
+# Wahoo!
+print("Success!")
diff --git a/scratch/facebook/merging-ranges.py b/scratch/facebook/merging-ranges.py
new file mode 100644
index 000000000000..6da44572ee7e
--- /dev/null
+++ b/scratch/facebook/merging-ranges.py
@@ -0,0 +1,23 @@
+
+def merge(xs):
+    xs.sort()
+    result = xs[0:1]
+    for a, b in xs[1:]:
+        y, z = result[-1]
+        if a <= z:
+            result[-1] = (y, max(b, z))
+        else:
+            result.append((a, b))
+    return result
+
+inputs = [([(0,1),(3,5),(4,8),(10,12),(9,10)], [(0,1),(3,8),(9,12)]),
+          ([(1,2),(2,3)], [(1,3)]),
+          ([(1,5),(2,3)], [(1,5)]),
+          ([(1,10),(2,6),(3,5),(7,9)], [(1,10)]),
+          ]
+for x, expected in inputs:
+    result = merge(x)
+    print(x)
+    print(result)
+    assert result == expected
+    print("Success!")
diff --git a/scratch/facebook/mesh-message.py b/scratch/facebook/mesh-message.py
new file mode 100644
index 000000000000..8438b059d843
--- /dev/null
+++ b/scratch/facebook/mesh-message.py
@@ -0,0 +1,40 @@
+from heapq import heappush, heappop
+import random
+
+def shortest_path(a, b, graph):
+    seen = set()
+    h = []
+    heappush(h, (0, a, [a]))
+    while h:
+        km, x, path = heappop(h)
+        if x == b:
+            return path
+        for c in graph[x]:
+            if c not in seen:
+                heappush(h, (km + 1, c, path + [c]))
+    raise Exception("We were unable to find a path from {} to {}".format(a, b))
+
+graph = {
+    'Min'     : ['William', 'Jayden', 'Omar'],
+    'William' : ['Min', 'Noam'],
+    'Jayden'  : ['Min', 'Amelia', 'Ren', 'Noam'],
+    'Ren'     : ['Jayden', 'Omar'],
+    'Amelia'  : ['Jayden', 'Adam', 'Miguel'],
+    'Adam'    : ['Amelia', 'Miguel', 'Sofia', 'Lucas'],
+    'Miguel'  : ['Amelia', 'Adam', 'Liam', 'Nathan'],
+    'Noam'    : ['Nathan', 'Jayden', 'William'],
+    'Omar'    : ['Ren', 'Min', 'Scott'],
+    'Liam'    : ['Ren'],
+    'Nathan'  : ['Noam'],
+    'Scott'   : [],
+}
+
+result = shortest_path('Jayden', 'Adam', graph)
+print(result)
+assert result == ['Jayden', 'Amelia', 'Adam']
+print('Success!')
+
+beg = random.choice(list(graph.keys()))
+end = random.choice(list(graph.keys()))
+print("Attempting to find the shortest path between {} and {}".format(beg, end))
+print(shortest_path(beg, end, graph))
diff --git a/scratch/facebook/mst.py b/scratch/facebook/mst.py
new file mode 100644
index 000000000000..81aa5cd48744
--- /dev/null
+++ b/scratch/facebook/mst.py
@@ -0,0 +1,71 @@
+from heapq import heappush, heappop
+import random
+
+def to_vertex_list(graph):
+    result = {}
+    for a, b, kg in graph:
+        if a in result:
+            result[a].append((b, kg))
+        else:
+            result[a] = [(b, kg)]
+        if b in result:
+            result[b].append((a, kg))
+        else:
+            result[b] = [(a, kg)]
+    return result
+
+def mst(graph):
+    graph = to_vertex_list(graph)
+    beg = random.choice(list(graph.keys()))
+    h = []
+    result = []
+    seen = set()
+    for c, kg in graph[beg]:
+        heappush(h, (kg, beg, c))
+    while h:
+        kg, beg, end = heappop(h)
+        # detect cycles
+        if end in seen:
+            continue
+        # use the edge
+        seen.add(beg)
+        seen.add(end)
+        result.append((beg, end))
+        for c, kg in graph[end]:
+            heappush(h, (kg, end, c))
+    return result
+
+graphs = [
+    [
+        ('A', 'B', 7),
+        ('A', 'D', 5),
+        ('B', 'D', 9),
+        ('E', 'D', 15),
+        ('F', 'D', 6),
+        ('F', 'G', 11),
+        ('F', 'E', 8),
+        ('G', 'E', 9),
+        ('C', 'E', 5),
+        ('B', 'E', 7),
+        ('B', 'C', 8),
+    ],
+    [
+        ('A', 'B', 4),
+        ('A', 'C', 8),
+        ('B', 'C', 11),
+        ('B', 'E', 8),
+        ('C', 'D', 7),
+        ('C', 'F', 1),
+        ('D', 'E', 2),
+        ('D', 'F', 6),
+        ('E', 'G', 7),
+        ('E', 'H', 4),
+        ('F', 'H', 2),
+        ('G', 'H', 14),
+        ('G', 'I', 9),
+        ('H', 'I', 10),
+    ],
+]
+
+for graph in graphs:
+    print(mst(graph))
diff --git a/scratch/facebook/node.py b/scratch/facebook/node.py
new file mode 100644
index 000000000000..4e24983af772
--- /dev/null
+++ b/scratch/facebook/node.py
@@ -0,0 +1,38 @@
+class Node(object):
+    def __init__(self, value, left=None, right=None):
+        self.value = value
+        self.left = left
+        self.right = right
+
+    def insert_left(self, value):
+        self.left = Node(value)
+        return self.left
+
+    def insert_right(self, value):
+        self.right = Node(value)
+        return self.right
+
+tree = Node(
+    50,
+    Node(
+        17,
+        Node(
+            12,
+            Node(9),
+            Node(14),
+        ),
+        Node(
+            23,
+            Node(19),
+        ),
+    ),
+    Node(
+        72,
+        Node(
+            54,
+            None,
+            Node(67)
+        ),
+        Node(76),
+    ),
+)
diff --git a/scratch/facebook/nth-fibonacci.py b/scratch/facebook/nth-fibonacci.py
new file mode 100644
index 000000000000..f524067b3b44
--- /dev/null
+++ b/scratch/facebook/nth-fibonacci.py
@@ -0,0 +1,13 @@
+# 0, 1, 1, 2, 3, 5
+def fib(n):
+    if n < 0:
+        raise Exception("Need to supply an index that's >= 0. Not: {}".format(n))
+    elif n in {0, 1}:
+        return n
+    state = [0, 1]
+    for i in range(1, n):
+        state[0], state[1] = state[1], state[0] + state[1]
+    return state[-1]
+
+for i in range(10):
+    print("fib({}) => {}".format(i, fib(i)))
diff --git a/scratch/facebook/onsite.txt b/scratch/facebook/onsite.txt
new file mode 100644
index 000000000000..b5242c4bd3a2
--- /dev/null
+++ b/scratch/facebook/onsite.txt
@@ -0,0 +1,22 @@
+** Behavior Interview **
+- Can I work in an unstructured environment?
+- Do I have a growth mindset?
+- How do I handle conflict?
+- Am I empathic?
+- Am I a self-starter?
+- What is my communication style?
+- Do I persevere?
+- <forgot to write this one down>
+
+** Design Interview **
+- requirement gathering, problem exploring
+- component analysis
+- quantitative analysis
+- trade-offs
+- bottlenecks, weaknesses
+- securing data (e.g. PII)
+
+Consider:
+- pagination
+- push/pull requests
+- API design
diff --git a/scratch/facebook/parsing/json.py b/scratch/facebook/parsing/json.py
new file mode 100644
index 000000000000..3975e973fefa
--- /dev/null
+++ b/scratch/facebook/parsing/json.py
@@ -0,0 +1,121 @@
+from parser import Parser
+
+# As an exercise to stress-test my understanding of recursive descent parsers,
+# I'm attempting to write a JSON parser without referencing any existing BNF
+# descriptions of JSON or existing JSON parser implementations.
+#
+# I'm only parsing a subset of JSON: enough to parse `sample`. Here is the BNF
+# that I wrote to describe my expected input:
+#
+# expression -> object
+# object     -> '{' ( STRING ':' expression ) ( ',' STRING ':' expression )* '}'
+#            |  array
+# array      -> '[' expression ( ',' expression )* ']'
+#            |  literal
+# literal    -> STRING | INT
+
+def tokenize(xs):
+    """
+    Return a list of tokens from the string input, `xs`.
+    """
+    result = []
+    i = 0
+    while i < len(xs):
+        # single characters
+        if xs[i] in ",{}:[]":
+            result.append(xs[i])
+            i += 1
+        # strings
+        elif xs[i] == "\"":
+            curr = xs[i]
+            i += 1
+            while xs[i] != "\"":
+                curr += xs[i]
+                i += 1
+            curr += xs[i]
+            result.append(curr)
+            i += 1
+        # integers
+        elif xs[i] in "0123456789":
+            curr = xs[i]
+            i += 1
+            while xs[i] in "0123456789":
+                curr += xs[i]
+                i += 1
+            result.append(int(curr))
+        # whitespace
+        elif xs[i] in {" ", "\n"}:
+            i += 1
+    return result
+
+def parse_json(x):
+    """
+    Attempt to parse the string, `x`, into JSON.
+    """
+    tokens = tokenize(x)
+    return parse_object(Parser(tokens))
+
+def parse_object(parser):
+    if parser.match(['{']):
+        key = parse_string(parser)
+        parser.expect([':'])
+        value = parse_object(parser)
+        result = [(key, value)]
+        while parser.match([',']):
+            key = parse_string(parser)
+            parser.match([':'])
+            value = parse_object(parser)
+            result.append((key, value))
+        return result
+    return parse_array(parser)
+
+def parse_array(parser):
+    if parser.match(['[']):
+        if parser.match([']']):
+            return []
+        result = [parse_object(parser)]
+        while parser.match([',']):
+            result.append(parse_object(parser))
+        parser.expect([']'])
+        return result
+    else:
+        return parse_literal(parser)
+
+def parse_string(parser):
+    if parser.curr().startswith("\""):
+        return parser.consume()
+    else:
+        raise Exception("Unexpected token: {}".format(parser.curr()))
+
+def parse_literal(parser):
+    return parser.consume()
+
+sample = """
+{
+  "glossary": {
+    "title": "example glossary",
+    "GlossDiv": {
+      "title": "S",
+      "GlossList": {
+        "GlossEntry": {
+          "ID": "SGML",
+          "SortAs": "SGML",
+          "GlossTerm": "Standard Generalized Markup Language",
+          "Acronym": "SGML",
+          "Abbrev": "ISO 8879:1986",
+          "GlossDef": {
+            "para": "A meta-markup language, used to create markup languages such as DocBook.",
+            "GlossSeeAlso": [
+              "GML",
+              "XML"
+            ]
+          },
+          "GlossSee": "markup"
+        }
+      }
+    }
+  }
+}
+"""
+
+print(parse_json(sample))
diff --git a/scratch/facebook/parsing/parser.py b/scratch/facebook/parsing/parser.py
new file mode 100644
index 000000000000..407bff61c980
--- /dev/null
+++ b/scratch/facebook/parsing/parser.py
@@ -0,0 +1,28 @@
+class Parser(object):
+    def __init__(self, tokens):
+        self.tokens = tokens
+        self.i = 0
+
+    def prev(self):
+        return self.tokens[self.i - 1]
+
+    def curr(self):
+        return self.tokens[self.i]
+
+    def consume(self):
+        if not self.exhausted():
+            self.i += 1
+            return self.prev()
+
+    def match(self, xs):
+        if not self.exhausted() and self.curr() in xs:
+            self.consume()
+            return True
+        return False
+
+    def expect(self, xs):
+        if not self.match(xs):
+            raise Exception("Expected token \"{}\" but received \"{}\"".format(xs, self.curr()))
+
+    def exhausted(self):
+        return self.i >= len(self.tokens)
diff --git a/scratch/facebook/parsing/regex.py b/scratch/facebook/parsing/regex.py
new file mode 100644
index 000000000000..e0757e1f788f
--- /dev/null
+++ b/scratch/facebook/parsing/regex.py
@@ -0,0 +1,174 @@
+# Writing a small proof-of-concept...
+#   - lexer
+#   - parser
+#   - compiler
+# ...for regex.
+
+from parser import Parser
+import string
+
+################################################################################
+# Top-Level API
+################################################################################
+
+def tokenize(xs):
+    """
+    Transform `xs` into a list of tokens.
+
+    Also: expand shorthand symbols using the following table:
+      - ? -> {0,1}
+      - * -> {0,}
+      - + -> {1,}
+    """
+    result = []
+    i = 0
+    shorthand = {
+        "?": ["{", 0, ",", 1, "}"],
+        "*": ["{", 0, ",", "}"],
+        "+": ["{", 1, ",", "}"],
+    }
+    while i < len(xs):
+        if xs[i] in shorthand:
+            for c in shorthand[xs[i]]:
+                result.append(c)
+            i += 1
+        elif xs[i] == "{":
+            result.append(xs[i])
+            i += 1
+            curr = ""
+            while xs[i] in string.digits:
+                curr += xs[i]
+                i += 1
+            result.append(int(curr))
+            assert xs[i] == ","
+            result.append(",")
+            i += 1
+            curr = ""
+            while xs[i] in string.digits:
+                curr += xs[i]
+                i += 1
+            result.append(int(curr))
+        else:
+            result.append(xs[i])
+            i += 1
+    return result
+
+def parse(expr):
+    """
+    Tokenize `expr` and convert it into a parse-tree.
+    """
+    tokens = tokenize(expr)
+    return parse_tokens(tokens)
+
+def compile(xs):
+    """
+    Transform `xs`, a parse-tree representing a regex, into a function that
+    accepts a string, and returns the substring that the regex matches.
+    """
+    def fn(input):
+        match = ""
+        i = 0
+        for x in xs:
+            matches, q = x[1], x[2]
+            lo, hi = q[1], q[2]
+            for j in range(lo):
+                if i < len(input) and input[i] in matches:
+                    match += input[i]
+                    i += 1
+                else:
+                    print("Failed to match {} with {}".format(input[i], matches))
+                    return None
+            if hi == float('inf'):
+                while i < len(input) and input[i] in matches:
+                    match += input[i]
+                    i += 1
+            else:
+                for j in range(hi - lo):
+                    if i < len(input) and input[i] in matches:
+                        match += input[i]
+                        i += 1
+        return match
+    return fn
+
+################################################################################
+# Helper Functions
+################################################################################
+
+def parse_tokens(tokens):
+    result = []
+    parser = Parser(tokens)
+    while not parser.exhausted():
+        result.append(parse_expression(parser))
+    return result
+
+def parse_expression(parser):
+    if parser.curr() == "[":
+        return parse_character_class(parser)
+    else:
+        return parse_character(parser)
+
+def parse_character_class(parser):
+    parser.expect("[")
+    beg = parser.consume()
+    parser.expect("-")
+    end = parser.consume()
+    parser.expect("]")
+    if parser.curr() == "{":
+        q = parse_quantifier(parser)
+    return char_class(xs=expand_range(beg, end), q=q)
+
+def parse_quantifier(parser):
+    parser.expect("{")
+    if parser.match([","]):
+        end = parser.consume()
+        parser.expect("}")
+        return quantifier(beg=0, end=end)
+    else:
+        beg = parser.consume()
+        parser.expect(",")
+        if parser.match(["}"]):
+            return quantifier(beg=beg)
+        else:
+            end = parser.consume()
+            parser.expect("}")
+            return quantifier(beg=beg, end=end)
+
+def parse_character(parser):
+    c = parser.consume()
+    q = None
+    if parser.curr() == "{":
+        q = parse_quantifier(parser)
+    return char_class(xs={c}, q=q)
+
+def char_class(xs=set(), q=None):
+    if not q:
+        q = quantifier(beg=1, end=1)
+    return ["CHARACTER_CLASS", xs, q]
+
+def expand_range(beg, end):
+    # TODO: Implement this
+    return {string.printable[i]
+            for i in range(string.printable.index(beg),
+                           string.printable.index(end) + 1)}
+
+def quantifier(beg=0, end=float('inf')):
+    return ['QUANTIFIER', beg, end]
+
+################################################################################
+# Tests
+################################################################################
+
+xs = [
+    ("[a-c]*[0-9]{2,3}", ["dog"]),
+    ("ca+t?", ["cat", "caaaat", "ca", "dog"]),
+]
+
+for re, inputs in xs:
+    print("Regex:  {}".format(re))
+    print("Tokens: {}".format(tokenize(re)))
+    print("Parsed: {}".format(parse(re)))
+    print("\nTESTS")
+    for input in inputs:
+        print("Attempting to match \"{}\"...".format(input))
+        parser = compile(parse(re))
+        print("Result: \"{}\"\n".format(parser(input)))
diff --git a/scratch/facebook/permutation-palindrome.py b/scratch/facebook/permutation-palindrome.py
new file mode 100644
index 000000000000..30603578ffb3
--- /dev/null
+++ b/scratch/facebook/permutation-palindrome.py
@@ -0,0 +1,17 @@
+from collections import Counter
+
+def is_palindrome(x):
+    return len([count for _, count in Counter(x).items() if count % 2 == 1]) <= 1
+
+
+xs = [("civic", True),
+      ("ivicc", True),
+      ("civil", False),
+      ("livci", False)]
+
+for x, expected in xs:
+    result = is_palindrome(x)
+    print(x)
+    print(result)
+    assert result == expected
+    print("Success!")
diff --git a/scratch/facebook/product-of-all-other-numbers.py b/scratch/facebook/product-of-all-other-numbers.py
new file mode 100644
index 000000000000..d381386b6257
--- /dev/null
+++ b/scratch/facebook/product-of-all-other-numbers.py
@@ -0,0 +1,33 @@
+from random import randint
+from math import floor
+
+# loop {forwards, backwards, up, down}
+# through a table of values, [[a]].
+
+def product(xs):
+    n = len(xs)
+    lhs = [1] * (n + 1)
+    for i in range(1, n):
+        lhs[i] = lhs[i - 1] * xs[i - 1]
+    rhs = [1] * (n + 1)
+    for i in range(n - 1, 0, -1):
+        rhs[i] = rhs[i + 1] * xs[i]
+    result = []
+    for i in range(n):
+        result.append(lhs[i] * rhs[i + 1])
+    return result
+
+def computed_expected(xs):
+    product = 1
+    for x in xs:
+        product *= x
+    return [floor(product / x) for x in xs]
+
+xs = [randint(1, 10) for _ in range(5)]
+expected = computed_expected(xs)
+result = product(xs)
+print(xs, result, expected)
+assert result == expected
+print("Success!")
+
+print(product([2, 4, 3, 10, 5]))
diff --git a/scratch/facebook/queue-two-stacks.py b/scratch/facebook/queue-two-stacks.py
new file mode 100644
index 000000000000..a71abeb00552
--- /dev/null
+++ b/scratch/facebook/queue-two-stacks.py
@@ -0,0 +1,20 @@
+from stack import Stack
+
+class Queue(object):
+    def __init__(self):
+        self.lhs = Stack()
+        self.rhs = Stack()
+
+    def enqueue(self, x):
+        self.rhs.push(x)
+
+    def dequeue(self, x):
+        y = self.rhs.pop()
+        while y:
+            self.lhs.push(y)
+            y = self.rhs.pop()
+        result = self.lhs.pop()
+        y = self.lhs.pop()
+        while y:
+            self.rhs.push(y)
+        return result
diff --git a/scratch/facebook/recursion-and-dynamic-programming/magic-index.py b/scratch/facebook/recursion-and-dynamic-programming/magic-index.py
new file mode 100644
index 000000000000..03b2de015dfe
--- /dev/null
+++ b/scratch/facebook/recursion-and-dynamic-programming/magic-index.py
@@ -0,0 +1,33 @@
+from math import floor
+
+def find_magic_index_brute(xs):
+    for i in range(len(xs)):
+        if xs[i] == i:
+            return i
+    return -1
+
+def mid(lo, hi):
+    return lo + floor((hi - lo) / 2)
+
+def find_magic_index(xs):
+    lo, hi = 0, len(xs) - 1
+    return do_find_magic_index(xs, 0, len(xs) - 1)
+
+def do_find_magic_index(xs, lo, hi):
+    pass
+
+xss = [
+    [],
+    [-1,0,2,4,5,6],
+    [1,1,1,1,1,5],
+    [-2,-2,-2,-2,4],
+    [1,2,3,4,5],
+]
+
+for xs in xss:
+    print(xs)
+    a = find_magic_index_brute(xs)
+    b = find_magic_index(xs)
+    print(a, b)
+    assert a == b
+    print("Success!")
diff --git a/scratch/facebook/recursion-and-dynamic-programming/making-change.py b/scratch/facebook/recursion-and-dynamic-programming/making-change.py
new file mode 100644
index 000000000000..30c95a66c319
--- /dev/null
+++ b/scratch/facebook/recursion-and-dynamic-programming/making-change.py
@@ -0,0 +1,56 @@
+# Given an infinite supply of:
+#   - quarters
+#   - dimes
+#   - nickels
+#   - pennies
+# Write a function to count the number of ways to make change of n.
+
+def get(table, row, col):
+    """
+    Defensively get cell `row`, `col` from `table`.
+    """
+    if row < 0 or row >= len(table):
+        return 0
+    if col < 0 or col >= len(table[0]):
+        return 0
+    return table[row][col]
+
+def print_table(table):
+    print('\n'.join([
+        ','.join([str(col) for col in table[row]])
+        for row in range(len(table))]))
+
+def init_table(rows=0, cols=0, default=0):
+    result = []
+    for row in range(rows):
+        r = []
+        for col in range(cols):
+            r.append(default)
+        result.append(r)
+    return result
+
+def make_change(n):
+    coins = [1, 5, 10, 25]
+    table = init_table(rows=len(coins), cols=n)
+
+    for row in range(len(table)):
+        for col in range(len(table[row])):
+            curr_coin = coins[row]
+            curr_n = col + 1
+            # a
+            a = get(table, row - 1, col)
+            # b
+            b = get(table, row, curr_n - curr_coin - 1)
+            # c
+            c = 1 if curr_coin <= curr_n else 0
+            # commit
+            if curr_coin == curr_n:
+                table[row][col] = a + c
+            else:
+                table[row][col] = a + b * c
+            # debug
+            print_table(table)
+            print()
+    return table[-1][-1]
+
+print(make_change(7))
diff --git a/scratch/facebook/recursion-and-dynamic-programming/paint-fill.py b/scratch/facebook/recursion-and-dynamic-programming/paint-fill.py
new file mode 100644
index 000000000000..e9e7f6a9c159
--- /dev/null
+++ b/scratch/facebook/recursion-and-dynamic-programming/paint-fill.py
@@ -0,0 +1,36 @@
+from collection import deque
+
+def fill(point, canvas, color):
+    if x not in canvas:
+        return
+    elif y not in canvas[x]:
+        return
+
+    x, y = point
+    if canvas[y][x] == color:
+        return
+    canvas[y][x] = color
+    fill((x + 1, y), canvas, color)
+    fill((x - 1, y), canvas, color)
+    fill((x, y + 1), canvas, color)
+    fill((x, y - 1), canvas, color)
+
+def fill_bfs(point, canvas, color):
+    x, y = point
+    if x not in canvas:
+        return None
+    if y not in canvas[x]:
+        return None
+    xs = deque()
+    xs.append((x, y))
+    while xs:
+        x, y = xs.popleft()
+        canvas[y][x] = color
+        for x2, y2 in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
+            if x2 not in canvas:
+                continue
+            elif y2 not in canvas[x2]:
+                continue
+            if canvas[y2][x2] != color:
+                xs.append((x2, y2))
+    return None
diff --git a/scratch/facebook/recursion-and-dynamic-programming/parenthesize-bools.py b/scratch/facebook/recursion-and-dynamic-programming/parenthesize-bools.py
new file mode 100644
index 000000000000..f406d64e657f
--- /dev/null
+++ b/scratch/facebook/recursion-and-dynamic-programming/parenthesize-bools.py
@@ -0,0 +1,114 @@
+# BNF
+# expression -> bool ( ( '|' | '&' | '^' ) bool )*
+# bool       -> '0' | '1'
+
+def tokenize(xs):
+    result = []
+    for c in xs:
+        if c == '0':
+            result.append(0)
+        elif c == '1':
+            result.append(1)
+        elif c in "&|^":
+            result.append(c)
+        else:
+            raise Exception("Unexpected token, \"{}\"".format(c))
+    return result
+
+class Parser(object):
+    def __init__(self, tokens):
+        self.tokens = tokens
+        self.i = 0
+
+    def prev(self):
+        return self.tokens[self.i - 1]
+
+    def curr(self):
+        return self.tokens[self.i]
+
+    def match(self, xs):
+        if self.exhausted():
+            return False
+        if (self.curr() in xs):
+            self.consume()
+            return True
+        return False
+
+    def consume(self):
+        result = self.curr()
+        self.i += 1
+        return result
+
+    def exhausted(self):
+        return self.i >= len(self.tokens)
+
+def recursive_descent(tokens):
+    parser = Parser(tokens)
+    return parse_expression(parser)
+
+def parse_expression(parser):
+    lhs = parse_bool(parser)
+    while parser.match(['|', '&', '^']):
+        op = parser.prev()
+        rhs = parse_expression(parser)
+        lhs = [op, lhs, rhs]
+    return lhs
+
+def parse_bool(parser):
+    if parser.curr() == 0:
+        parser.consume()
+        return False
+    elif parser.curr() == 1:
+        parser.consume()
+        return True
+    else:
+        raise Exception("Unexpected token: {}".format(parser.curr()))
+
+def f(expr, result):
+    tokens = tokenize(expr)
+    tree = recursive_descent(tokens)
+    return do_f(tree, result)
+
+def do_f(tree, result):
+    if type(tree) == bool:
+        if tree == result:
+            return 1
+        else:
+            return 0
+
+    op, lhs, rhs = tree[0], tree[1], tree[2]
+    truth_tables = {
+        True: {
+            '|': [
+                (True, True),
+                (True, False),
+                (False, True),
+            ],
+            '&': [
+                (True, True),
+            ],
+            '^': [
+                (True, False),
+                (False, True),
+            ],
+        },
+        False: {
+            '|': [
+                (False, False),
+            ],
+            '&': [
+                (False, False),
+                (True, False),
+                (False, True),
+            ],
+            '^': [
+                (True, True),
+                (False, False),
+            ],
+        }
+    }
+
+    return sum([do_f(lhs, x) * do_f(rhs, y) for x, y in truth_tables[result][op]])
+
+print(f("1^0|0|1", False))
+print(f("1|0|1|1", False))
diff --git a/scratch/facebook/recursion-and-dynamic-programming/permutations.py b/scratch/facebook/recursion-and-dynamic-programming/permutations.py
new file mode 100644
index 000000000000..e23972d4186d
--- /dev/null
+++ b/scratch/facebook/recursion-and-dynamic-programming/permutations.py
@@ -0,0 +1,13 @@
+def char_and_rest(i, xs):
+    return xs[i], xs[:i] + xs[i+1:]
+
+# perms :: String -> [String]
+def perms(xs):
+    if len(xs) == 1:
+        return [xs]
+    result = []
+    for c, rest in [char_and_rest(i, xs) for i in range(len(xs))]:
+        result += [c + perm for perm in perms(rest)]
+    return result
+
+print(perms("cat"))
diff --git a/scratch/facebook/recursion-and-dynamic-programming/robot-grid-traversal.py b/scratch/facebook/recursion-and-dynamic-programming/robot-grid-traversal.py
new file mode 100644
index 000000000000..9ccc08526a99
--- /dev/null
+++ b/scratch/facebook/recursion-and-dynamic-programming/robot-grid-traversal.py
@@ -0,0 +1,28 @@
+import random
+
+def factorial(n):
+    result = 1
+    for i in range(1, n + 1):
+        result *= i
+    return result
+
+def travel(a, b):
+    if a == b:
+        return 1
+
+    ax, ay = a
+    bx, by = b
+    if ax > bx or ay > by:
+        return 0
+
+    return sum([travel((ax + 1, ay), b), travel((ax, ay + 1), b)])
+
+def travel_compute(a, b):
+    bx, by = b
+    return int(factorial(bx + by) / (factorial(bx) * factorial(by)))
+
+a = (0, 0)
+b = (random.randint(1, 10), random.randint(1, 10))
+print("Travelling to {}, {}".format(b[0], b[1]))
+print(travel(a, b))
+print(travel_compute(a, b))
diff --git a/scratch/facebook/recursion-and-dynamic-programming/staircase.py b/scratch/facebook/recursion-and-dynamic-programming/staircase.py
new file mode 100644
index 000000000000..5eb4a8560674
--- /dev/null
+++ b/scratch/facebook/recursion-and-dynamic-programming/staircase.py
@@ -0,0 +1 @@
+# accidentally deleted my solution... TBI (again)
diff --git a/scratch/facebook/recursion-and-dynamic-programming/subsets.py b/scratch/facebook/recursion-and-dynamic-programming/subsets.py
new file mode 100644
index 000000000000..a6d26aa85055
--- /dev/null
+++ b/scratch/facebook/recursion-and-dynamic-programming/subsets.py
@@ -0,0 +1,41 @@
+# take-aways:
+#   - Use integers as lists of boolean values
+#   - Use 1 << n to compute 2^n where n = len(xs)
+
+def set_from_int(xs, n):
+    result = []
+    for i in range(len(xs)):
+        if n & (1 << i) != 0:
+            result.append(xs[i])
+    return result
+
+# subsets :: Set a -> List (Set a)
+def subsets(xs):
+    n = len(xs)
+    return [set_from_int(xs, i) for i in range(1 << n)]
+
+#   0 1 2
+# 0 N Y Y
+# 1 _ N Y
+# 2 _ _ N
+
+# For my interview, be able to compute *permutations* and *combinations*
+
+# This differs from permutations because this is about finding combinations...
+#
+# bottom-up
+# 0 =>        { }
+# 1 =>  {3}   {4}   {3}
+# 2 => {5,4} {5,3} {4,3}
+
+xs = [
+    ([], [[]]),
+    ([5], [[], [5]]),
+    ([5,4], [[],[5],[4],[5,4]]),
+]
+
+for x, expected in xs:
+    result = subsets(x)
+    print("subsets({}) => {} == {}".format(x, result, expected))
+    assert result == expected
+    print("Success!")
diff --git a/scratch/facebook/recursion-and-dynamic-programming/valid-parens.py b/scratch/facebook/recursion-and-dynamic-programming/valid-parens.py
new file mode 100644
index 000000000000..56f2c0b27456
--- /dev/null
+++ b/scratch/facebook/recursion-and-dynamic-programming/valid-parens.py
@@ -0,0 +1,50 @@
+def valid_parens(n):
+    if n == 0:
+        return []
+    if n == 1:
+        return ["()"]
+
+    result = set()
+    for x in valid_parens(n - 1):
+        result.add("({})".format(x))
+        result.add("(){}".format(x))
+        result.add("{}()".format(x))
+    return result
+
+def valid_parens_efficient(n):
+    result = []
+    curr = [''] * n**2
+    do_valid_parens_efficient(result, curr, 0, n, n)
+    return result
+
+def do_valid_parens_efficient(result, curr, i, lhs, rhs):
+    if lhs == 0 and rhs == 0:
+        result.append(''.join(curr))
+    else:
+        if lhs > 0:
+            curr[i] = '('
+            do_valid_parens_efficient(result, curr, i + 1, lhs - 1, rhs)
+        if rhs > lhs:
+            curr[i] = ')'
+            do_valid_parens_efficient(result, curr, i + 1, lhs, rhs - 1)
+
+# Avoids recursion by using either a stack or a queue. I think this version is
+# easier to understand.
+def valid_parens_efficient_2(n):
+    result = []
+    xs = []
+    xs.append(('', n, n))
+    while xs:
+        curr, lhs, rhs = xs.pop()
+        print(curr)
+        if lhs == 0 and rhs == 0:
+            result.append(''.join(curr))
+        if lhs > 0:
+            xs.append((curr + '(', lhs - 1, rhs))
+        if rhs > lhs:
+            xs.append((curr + ')', lhs, rhs - 1))
+    return result
+
+# print(valid_parens(4))
+print(valid_parens_efficient(3))
+print(valid_parens_efficient_2(3))
diff --git a/scratch/facebook/recursive-string-permutations.py b/scratch/facebook/recursive-string-permutations.py
new file mode 100644
index 000000000000..e4c61eff9f62
--- /dev/null
+++ b/scratch/facebook/recursive-string-permutations.py
@@ -0,0 +1,19 @@
+# permutations: no repeat characters
+
+def char_and_rest(i, xs):
+    return xs[i], xs[0:i] + xs[i + 1:]
+
+def permutations(xs):
+    if len(xs) == 1:
+        return [xs]
+    result = []
+    for c, rest in [char_and_rest(i, xs) for i in range(len(xs))]:
+        result += [c + perm for perm in permutations(rest)]
+    return result
+
+expected = ["cat", "cta", "act", "atc", "tca", "tac"]
+result = permutations("cat")
+print(result, expected)
+assert len(result) == len(expected)
+assert result == expected
+print("Success!")
diff --git a/scratch/facebook/reverse-linked-list.py b/scratch/facebook/reverse-linked-list.py
new file mode 100644
index 000000000000..820726733f9d
--- /dev/null
+++ b/scratch/facebook/reverse-linked-list.py
@@ -0,0 +1,25 @@
+from linked_list import Node
+
+def reverse(node):
+    prev, curr, next = None, node, node.next
+
+    while curr:
+        curr.next = prev
+        prev = curr
+        curr = next
+        next = curr.next if curr else None
+    return prev
+
+one = Node(1)
+two = Node(2)
+three = Node(3)
+one.next = two
+two.next = three
+
+print(one)
+result = reverse(one)
+print(result)
+assert all([result == three,
+            three.next == two,
+            two.next == one])
+print("Success!")
diff --git a/scratch/facebook/reverse-string-in-place.py b/scratch/facebook/reverse-string-in-place.py
new file mode 100644
index 000000000000..72cd6c27a370
--- /dev/null
+++ b/scratch/facebook/reverse-string-in-place.py
@@ -0,0 +1,14 @@
+# reverse :: [Char] -> ()
+def reverse(xs):
+    i = 0
+    j = len(xs) - 1
+    while i < j:
+        xs[i], xs[j] = xs[j], xs[i]
+        i += 1
+        j -= 1
+
+xs = [list("testing"), list("a"), list("to")]
+for x in xs:
+    print(x)
+    reverse(x)
+    print(x)
diff --git a/scratch/facebook/reverse-words.py b/scratch/facebook/reverse-words.py
new file mode 100644
index 000000000000..5a38b828a346
--- /dev/null
+++ b/scratch/facebook/reverse-words.py
@@ -0,0 +1,8 @@
+# reverse_word :: [Char] -> ()
+def reverse_words(x):
+    pass
+
+x = list("This is a test")
+print(''.join(x))
+reverse_words(x)
+print(''.join(result))
diff --git a/scratch/facebook/scratch.py b/scratch/facebook/scratch.py
new file mode 100644
index 000000000000..e772d758473d
--- /dev/null
+++ b/scratch/facebook/scratch.py
@@ -0,0 +1,94 @@
+# This is a scratch pad for randomly selected questions
+
+# def char_and_rest(i, xs):
+#     return xs[i], xs[:i] + xs[i+1:]
+
+# def perms(xs):
+#     if len(xs) == 1:
+#         return [xs]
+#     result = []
+#     for i in range(len(xs)):
+#         c, rest = char_and_rest(i, xs)
+#         for perm in perms(rest):
+#             result.append(c + ''.join(perm))
+#     return result
+
+# print(perms(list("woah")))
+
+# def f(take_out, dine_in, served):
+#     j, k = 0, 0
+#     for i in range(len(served)):
+#         if j < len(take_out) and served[i] == take_out[j]:
+#             j += 1
+#         elif k < len(dine_in) and served[i] == dine_in[k]:
+#             k += 1
+#         else:
+#             return False
+#     if j < len(take_out) or k < len(dine_in):
+#         return False
+#     return True
+
+# take_out = [17, 8, 24]
+# dine_in = [12, 19, 2]
+# served = [17, 8, 12, 19, 24, 2]
+# print(f(take_out, dine_in, served))
+
+# def match(a, b):
+#     if a == '{':
+#         return b == '}'
+#     if a == '[':
+#         return b == ']'
+#     if a == '(':
+#         return b == ')'
+#     return False
+
+# def f(xs):
+#     s = []
+#     for c in xs:
+#         if c in {'{', '[', '('}:
+#             s.append(c)
+#         elif c in {'}', ']', ')'}:
+#             opener = s.pop()
+#             if not match(opener, c):
+#                 return False
+#     return len(s) == 0
+
+# assert f("{[]()}")
+# assert f("{[(])}") == False
+# assert f("{[}") == False
+# print("Success!")
+
+# def valid_bst(node):
+#     lhs = max_bst_value(node.left) if node.left else float('-inf')
+#     rhs = min_bst_value(node.right) if node.right else float('inf')
+
+#     return and([
+#         lhs <= node.value,
+#         rhs > node.value,
+#         valid_bst(node.left),
+#         valid_bst(node.right),
+#     ])
+
+import random
+import math
+
+def shuffle(xs):
+    n = len(xs)
+    for i in range(n - 1):
+        j = random.randint(i + 1, n - 1)
+        xs[i], xs[j] = xs[j], xs[i]
+    return xs
+
+def as_card(i):
+    if i not in range(1, 53):
+        raise Exception("Not a card")
+    # 1
+    suit = ['Hearts', 'Clubs', 'Diamonds', 'Spades'][math.floor((i - 1) / 13)]
+    n = ['Ace',2,3,4,5,6,7,8,9,10,'Jack','Queen','King'][(i - 1) % 13]
+    return '{} of {}'.format(n, suit)
+
+xs = list(range(1, 53))
+print(xs)
+shuffle(xs)
+for x in xs:
+    print(as_card(x))
diff --git a/scratch/facebook/second-largest-item-in-bst.py b/scratch/facebook/second-largest-item-in-bst.py
new file mode 100644
index 000000000000..2815dec9ee60
--- /dev/null
+++ b/scratch/facebook/second-largest-item-in-bst.py
@@ -0,0 +1,22 @@
+from collections import deque
+from node import Node, tree
+
+def find_largest(node):
+    while node.right:
+        node = node.right
+    return node.value
+
+def find_second_largest(node):
+    # parent of the rightmost, when rightmost is leaf
+    # max(rightmost.left)
+    prev = None
+    while node.right:
+        prev = node
+        node = node.right
+    if node.left:
+        return find_largest(node.left)
+    else:
+        return prev.value
+
+assert find_second_largest(tree) == 72
+print("Success!")
diff --git a/scratch/facebook/shuffle.py b/scratch/facebook/shuffle.py
new file mode 100644
index 000000000000..21a6a96c6072
--- /dev/null
+++ b/scratch/facebook/shuffle.py
@@ -0,0 +1,17 @@
+from random import randint
+
+def get_random(i, j):
+    return randint(i, j)
+
+def shuffle(xs):
+    for i in range(len(xs)):
+        j = get_random(i, len(xs) - 1)
+        xs[i], xs[j] = xs[j], xs[i]
+
+xs = list(range(1, 53))
+print(xs)
+assert len(set(xs)) == 52
+shuffle(xs)
+assert len(set(xs)) == 52
+print(xs)
+print("Success!")
diff --git a/scratch/facebook/stack.py b/scratch/facebook/stack.py
new file mode 100644
index 000000000000..2a843e22166b
--- /dev/null
+++ b/scratch/facebook/stack.py
@@ -0,0 +1,25 @@
+class Stack(object):
+    def __init__(self):
+        self.items = []
+
+    def __repr__(self):
+        return self.items.__repr__()
+
+    def push(self, x):
+        self.items.append(x)
+
+    def pop(self):
+        if not self.items:
+            return None
+        return self.items.pop()
+
+    def peek(self):
+        if not self.items:
+            return None
+        return self.items[-1]
+
+def from_list(xs):
+    result = Stack()
+    for x in xs:
+        result.push(x)
+    return result
diff --git a/scratch/facebook/stock-price.py b/scratch/facebook/stock-price.py
new file mode 100644
index 000000000000..8e42f8152311
--- /dev/null
+++ b/scratch/facebook/stock-price.py
@@ -0,0 +1,16 @@
+def max_profit(xs):
+    buy = xs[0]
+    profit = xs[1] - xs[0]
+    for price in xs[1:]:
+        profit = max(profit, price - buy)
+        buy = min(buy, price)
+    return profit
+
+xs = [([10,7,5,8,11,9], 6),
+      ([10,8,7,6,5], -1)]
+
+for x, expected in xs:
+    result = max_profit(x)
+    print(x, result)
+    assert result == expected
+    print("Success!")
diff --git a/scratch/facebook/todo.org b/scratch/facebook/todo.org
new file mode 100644
index 000000000000..6ac99267dbfa
--- /dev/null
+++ b/scratch/facebook/todo.org
@@ -0,0 +1,60 @@
+* Array and string manipulation
+** DONE Merging Meeting Times
+** DONE Reverse String in Place
+** TODO Reverse Words
+** DONE Merge Sorted Arrays
+** DONE Cafe Order Checker
+* Hashing and hash tables
+** DONE Inflight Entertainment
+** DONE Permutation Palindrome
+** DONE Word Cloud Data
+** DONE Top Scores
+* Greedy Algorithms
+** DONE Apple Stocks
+** DONE Highest Product of 3
+** DONE Product of All Other Numbers
+** DONE Cafe Order Checker
+** DONE In-Place Shuffle
+* Sorting, searching, and logarithms
+** DONE Find Rotation Point
+** TODO Find Repeat, Space Edition
+** DONE Top Scores
+** DONE Merging Meeting Times
+* Trees and graphs
+** DONE Balanced Binary Tree
+** DONE Binary Search Tree Checker
+** DONE 2nd Largest Item in a Binary Search Tree
+** DONE Graph Coloring
+** DONE MeshMessage
+** DONE Find Repeat, Space Edition BEAST MODE
+* Dynamic programming and recursion
+** DONE Recursive String Permutations
+** DONE Compute nth Fibonacci Number
+** DONE Making Change
+** DONE The Cake Thief
+** DONE Balanced Binary Tree
+** DONE Binary Search Tree Checker
+** DONE 2nd Largest Item in a Binary Search Tree
+* Queues and stacks
+** DONE Largest Stack
+** DONE Implement A Queue With Two Stacks
+** DONE Parenthesis Matching
+** DONE Bracket Validator
+* Linked lists
+** DONE Delete Node
+** DONE Does This Linked List Have A Cycle?
+** DONE Reverse A Linked List
+** DONE Kth to Last Node in a Singly-Linked List
+** DONE Find Repeat, Space Edition BEAST MODE
+* General programming
+** TODO Rectangular Love
+** TODO Temperature Tracker
+* Bit manipulation
+** DONE The Stolen Breakfast Drone
+* Combinatorics, probability, and other math
+** TODO Which Appears Twice
+** TODO Find in Ordered Set
+** TODO In-Place Shuffle
+** TODO Simulate 5-sided die
+** TODO Simulate 7-sided die
+** TODO Two Egg Problem
diff --git a/scratch/facebook/top-scores.py b/scratch/facebook/top-scores.py
new file mode 100644
index 000000000000..c8a10ae5f181
--- /dev/null
+++ b/scratch/facebook/top-scores.py
@@ -0,0 +1,20 @@
+import random
+from collections import deque
+
+def sorted(xs):
+    result = [0] * 100
+    for x in xs:
+        result[x - 1] += 1
+
+    answer = deque()
+    for i in range(len(result)):
+        x = result[i]
+        for _ in range(x):
+            answer.appendleft(i + 1)
+
+    return list(answer)
+
+scores = [random.choice(range(70, 100)) for _ in range(20)]
+print(scores)
+result = sorted(scores)
+print(result)
diff --git a/scratch/facebook/topo-sort.py b/scratch/facebook/topo-sort.py
new file mode 100644
index 000000000000..874005a01932
--- /dev/null
+++ b/scratch/facebook/topo-sort.py
@@ -0,0 +1,61 @@
+import random
+from heapq import heappush, heappop
+from collections import deque
+
+# A topological sort returns the vertices of a graph sorted in an ascending
+# order by the number of incoming edges each vertex has.
+#
+# A few algorithms for solving this exist, and at the time of this writing, I
+# know none. I'm going to focus on two:
+#   1. Kahn's
+#   2. DFS (TODO)
+
+def count_in_edges(graph):
+    result = {k: 0 for k in graph.keys()}
+    for xs in graph.values():
+        for x in xs:
+            result[x] += 1
+    return result
+
+# Kahn's algorithm for returning a topological sorting of the vertices in
+# `graph`.
+def kahns_sort(graph):
+    result = []
+    q = deque()
+    in_edges = count_in_edges(graph)
+    for x in [k for k, v in in_edges.items() if v == 0]:
+        q.append(x)
+    while q:
+        x = q.popleft()
+        result.append(x)
+        for c in graph[x]:
+            in_edges[c] -= 1
+            if in_edges[c] == 0:
+                q.append(c)
+    return result
+
+graphs = [
+    {
+        0: [],
+        1: [],
+        2: [3],
+        3: [1],
+        4: [0, 1],
+        5: [0, 2],
+    },
+    {
+        'A': ['C', 'D'],
+        'B': ['D', 'E'],
+        'C': [],
+        'D': ['F', 'G'],
+        'E': [],
+        'F': [],
+        'G': ['I'],
+        'H': ['I'],
+        'I': [],
+    }
+]
+
+print("--- Kahn's --- ")
+for graph in graphs:
+    print(kahns_sort(graph))
diff --git a/scratch/facebook/traversals.py b/scratch/facebook/traversals.py
new file mode 100644
index 000000000000..e2565a32313d
--- /dev/null
+++ b/scratch/facebook/traversals.py
@@ -0,0 +1,100 @@
+from math import floor
+
+# Lists
+def cycle_backwards(times, xs):
+    n = len(xs)
+    for i in range(n * times):
+        print(xs[n - 1 - i % n])
+
+def cycle_forwards(times, xs):
+    n = len(xs)
+    for i in range(n * times):
+        print(xs[i % n])
+
+def backwards(xs):
+    n = len(xs)
+    for i in range(n):
+        print(xs[n - 1 - i])
+
+def forwards(xs):
+    for i in range(len(xs)):
+        print(xs[i])
+
+xs = [2, 5, 6, 9, 12]
+
+print("Forwards")
+forwards(xs)
+print("Backwards")
+backwards(xs)
+print("Cycle forwards")
+cycle_forwards(2, xs)
+print("Cycle backwards")
+cycle_backwards(2, xs)
+
+# Tables
+def tblr(table):
+    for row in range(len(table)):
+        for col in range(len(table[row])):
+            print(table[row][col])
+
+def tbrl(table):
+    for row in range(len(table)):
+        n = len(table[row])
+        for col in range(n):
+            print(table[row][n - 1 - col])
+
+def btlr(table):
+    n = len(table)
+    for row in range(n):
+        for col in range(len(table[row])):
+            print(table[n - 1 - row][col])
+
+def btrl(table):
+    rows = len(table)
+    for row in range(rows):
+        cols = len(table[row])
+        for col in range(cols):
+            print(table[rows - 1 - row][cols - 1 - col])
+
+def special(table):
+    rows = len(table)
+    cols = len(table[0])
+    for col in range(cols):
+        for row in range(rows):
+            print(table[row][col])
+
+def double_bonus(table):
+    rows = len(table)
+    cols = len(table[0])
+    for i in range(rows):
+        row = i
+        for col in range(cols):
+            print(table[row][col % cols])
+            row = (row + 1) % rows
+
+def free(table):
+    rows = len(table)
+    cols = len(table[0])
+    d = rows * cols
+    for i in range(d):
+        row = floor((i % d) / cols)
+        col = i % cols
+        print(table[row][col])
+
+table = [[1,2,3,4],
+         [5,6,7,8]]
+
+print("Top->Bottom, Left->Right")
+tblr(table)
+print("Top->Bottom, Right->Left")
+tbrl(table)
+print("Bottom->Top, Left->Right")
+btlr(table)
+print("Bottom->Top, Right->Left")
+btrl(table)
+print("Special")
+special(table)
+print("2x Bonus")
+double_bonus(table)
+print("Free")
+free(table)
diff --git a/scratch/facebook/utils.py b/scratch/facebook/utils.py
new file mode 100644
index 000000000000..9a3e8a045e88
--- /dev/null
+++ b/scratch/facebook/utils.py
@@ -0,0 +1,19 @@
+def init_table(rows=0, cols=0, default=None):
+    table = []
+    for row in range(rows):
+        x = []
+        for col in range(cols):
+            x.append(default)
+        table.append(x)
+    return table
+
+def get(table, row, col, default=0):
+    if row < 0 or col < 0:
+        return default
+    return table[row][col]
+
+def print_table(table):
+    result = []
+    for row in range(len(table)):
+        result.append(' '.join([str(cell) for cell in table[row]]))
+    print('\n'.join(result))
diff --git a/scratch/facebook/word-cloud.py b/scratch/facebook/word-cloud.py
new file mode 100644
index 000000000000..88422e3631db
--- /dev/null
+++ b/scratch/facebook/word-cloud.py
@@ -0,0 +1,32 @@
+def normalize(x):
+    noise = ".,;-"
+    for y in noise:
+        if x.endswith(y):
+            return normalize(x[0:-1])
+        if x.startswith(y):
+            return normalize(x[1:])
+    return x.lower()
+
+def word_cloud(xs):
+    result = dict()
+
+    for x in xs.split(' '):
+        k = normalize(x)
+        if k in result:
+            result[k] += 1
+        else:
+            result[k] = 1
+
+    return result
+
+result = word_cloud("This is just the beginning. The UK will lockdown again.")
+assert result.get('this') == 1
+assert result.get('is') == 1
+assert result.get('just') == 1
+assert result.get('the') == 2
+assert result.get('beginning') == 1
+assert result.get('uk') == 1
+assert result.get('will') == 1
+assert result.get('lockdown') == 1
+assert result.get('again') == 1
+print("Success!")