diff options
| author | William Carroll <wpcarro@gmail.com> | 2020-11-12T14·37+0000 |
|---|---|---|
| committer | William Carroll <wpcarro@gmail.com> | 2020-11-12T14·37+0000 |
| commit | aa66d9b83d5793bdbb7fe28368e0642f7c3dceac (patch) | |
| tree | a0e6ad240fe1cdfd2fcdba7266931beea9fbe0d6 /scratch | |
| parent | d2d772e43e0d4fb1bfaaa58d7de0c9e2cc274a25 (diff) | |
Add coding exercises for Facebook interviews
Add attempts at solving coding problems to Briefcase.
Diffstat (limited to 'scratch')
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 0000000000..a828230d08 --- /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 0000000000..afa9706f97 --- /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 0000000000..df9b5015ad --- /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 0000000000..50edeeaa19 --- /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 0000000000..9d88a68069 --- /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 0000000000..90a2add066 --- /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 0000000000..add59ed409 --- /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 0000000000..354e2dfb58 --- /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 0000000000..4034449ef0 --- /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 0000000000..7031701994 --- /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 0000000000..1ba46a7548 --- /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 0000000000..14deb66a8f --- /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 0000000000..7c491aef60 --- /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 0000000000..3636be4d93 --- /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 0000000000..56032aa05c --- /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 0000000000..17588166c8 --- /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 0000000000..c237b8e52e --- /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 0000000000..4c6d64494d --- /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 0000000000..7ddea5350a --- /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 0000000000..ae04f5eb96 --- /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 0000000000..dd258d924d --- /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 0000000000..b57f469b49 --- /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 0000000000..3aebd45483 --- /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 0000000000..7761bf1c61 --- /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 0000000000..052db44153 --- /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 0000000000..56f54d4978 --- /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 0000000000..1ae7061e83 --- /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 0000000000..a034fb4961 --- /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 0000000000..8a838db45d --- /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 0000000000..ae9377ad11 --- /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 0000000000..6da44572ee --- /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 0000000000..8438b059d8 --- /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 0000000000..81aa5cd487 --- /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 0000000000..4e24983af7 --- /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 0000000000..f524067b3b --- /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 0000000000..b5242c4bd3 --- /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 0000000000..3975e973fe --- /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 0000000000..407bff61c9 --- /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 0000000000..e0757e1f78 --- /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 0000000000..30603578ff --- /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 0000000000..d381386b62 --- /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 0000000000..a71abeb005 --- /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 0000000000..03b2de015d --- /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 0000000000..30c95a66c3 --- /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 0000000000..e9e7f6a9c1 --- /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 0000000000..f406d64e65 --- /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 0000000000..e23972d418 --- /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 0000000000..9ccc08526a --- /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 0000000000..5eb4a85606 --- /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 0000000000..a6d26aa850 --- /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 0000000000..56f2c0b274 --- /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 0000000000..e4c61eff9f --- /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 0000000000..820726733f --- /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 0000000000..72cd6c27a3 --- /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 0000000000..5a38b828a3 --- /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 0000000000..e772d75847 --- /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 0000000000..2815dec9ee --- /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 0000000000..21a6a96c60 --- /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 0000000000..2a843e2216 --- /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 0000000000..8e42f81523 --- /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 0000000000..6ac99267db --- /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 0000000000..c8a10ae5f1 --- /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 0000000000..874005a019 --- /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 0000000000..e2565a3231 --- /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 0000000000..9a3e8a045e --- /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 0000000000..88422e3631 --- /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!") |