diff options
Diffstat (limited to 'users/wpcarro/scratch/facebook')
95 files changed, 4344 insertions, 0 deletions
diff --git a/users/wpcarro/scratch/facebook/anglocize-int.py b/users/wpcarro/scratch/facebook/anglocize-int.py new file mode 100644 index 0000000000..a828230d08 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/balanced-binary-tree.py b/users/wpcarro/scratch/facebook/balanced-binary-tree.py new file mode 100644 index 0000000000..afa9706f97 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/breakfast-generator.py b/users/wpcarro/scratch/facebook/breakfast-generator.py new file mode 100644 index 0000000000..df9b5015ad --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/bst-checker.py b/users/wpcarro/scratch/facebook/bst-checker.py new file mode 100644 index 0000000000..7ef63a9531 --- /dev/null +++ b/users/wpcarro/scratch/facebook/bst-checker.py @@ -0,0 +1,49 @@ +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 is_bst(self): + s = [] + s.append((float('-inf'), self, float('inf'))) + while s: + lo, node, hi = s.pop() + if lo <= node.value <= hi: + node.left and s.append((lo, node.left, node.value)) + node.right and s.append((node.value, node.right, hi)) + else: + return False + return True + + +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/users/wpcarro/scratch/facebook/cafe-order-checker.py b/users/wpcarro/scratch/facebook/cafe-order-checker.py new file mode 100644 index 0000000000..9d88a68069 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/cake_thief.py b/users/wpcarro/scratch/facebook/cake_thief.py new file mode 100644 index 0000000000..90a2add066 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/camping-knapsack.py b/users/wpcarro/scratch/facebook/camping-knapsack.py new file mode 100644 index 0000000000..add59ed409 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/coin.py b/users/wpcarro/scratch/facebook/coin.py new file mode 100644 index 0000000000..354e2dfb58 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/count-islands.py b/users/wpcarro/scratch/facebook/count-islands.py new file mode 100644 index 0000000000..b876319b2f --- /dev/null +++ b/users/wpcarro/scratch/facebook/count-islands.py @@ -0,0 +1,53 @@ +from collections import deque + +def maybe_queue(row, col, game, q, seen): + """ + Add coordinate, (`row`, `col`), to the queue, `q`, as long as it exists in + the map, `game`, and it is not already present in `seen`. + """ + if row >= 0 and row < len(game) and col >= 0 and col < len(game[0]): + if game[row][col] == 'L' and (row, col) not in seen: + q.append((row, col)) + seen.add((row, col)) + +def visit_island(row, col, game, seen): + """ + Starting at the coordinate, (`row`, `col`), in the map, `game`, visit all + surrounding tiles marked as land by adding them to the `seen` set. + """ + q = deque() + q.append((row, col)) + while q: + row, col = q.popleft() + maybe_queue(row - 1, col, game, q, seen) # UP + maybe_queue(row + 1, col, game, q, seen) # DOWN + maybe_queue(row, col - 1, game, q, seen) # LEFT + maybe_queue(row, col + 1, game, q, seen) # RIGHT + +def count_islands(game): + """ + Return the number of contiguous land tiles in the map, `game`. + """ + result = 0 + seen = set() + for row in range(len(game)): + for col in range(len(game[row])): + if game[row][col] == 'L' and (row, col) not in seen: + visit_island(row, col, game, seen) + result += 1 + return result + +################################################################################ +# Tests +################################################################################ + +game = [ + "LWLWWW", + "LLLWWW", + "WWWLLW", +] + +result = count_islands(game) +print(result) +assert result == 2 +print("Success!") diff --git a/users/wpcarro/scratch/facebook/delete-node.py b/users/wpcarro/scratch/facebook/delete-node.py new file mode 100644 index 0000000000..4034449ef0 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/dijkstras.py b/users/wpcarro/scratch/facebook/dijkstras.py new file mode 100644 index 0000000000..7031701994 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/edit-distance.py b/users/wpcarro/scratch/facebook/edit-distance.py new file mode 100644 index 0000000000..a5b744f30f --- /dev/null +++ b/users/wpcarro/scratch/facebook/edit-distance.py @@ -0,0 +1,47 @@ +def print_grid(grid): + result = [] + for row in grid: + result.append(" ".join(str(c) for c in row)) + return print("\n".join(result)) + +def edit_distance(a, b): + """ + Compute the "edit distance" to transform string `a` into string `b`. + """ + grid = [] + for row in range(len(a) + 1): + r = [] + for col in range(len(b) + 1): + r.append(0) + grid.append(r) + + # left-to-right + # populate grid[0][i] + for col in range(len(grid[0])): + grid[0][col] = col + + # top-to-bottom + # populate grid[i][0] + for row in range(len(grid)): + grid[row][0] = row + + for row in range(1, len(grid)): + for col in range(1, len(grid[row])): + # last characters are the same + if a[0:row][-1] == b[0:col][-1]: + grid[row][col] = grid[row - 1][col - 1] + else: + # substitution + s = 1 + grid[row - 1][col - 1] + # deletion + d = 1 + grid[row - 1][col] + # insertion + i = 1 + grid[row][col - 1] + grid[row][col] = min(s, d, i) + print_grid(grid) + return grid[-1][-1] + +result = edit_distance("pizza", "pisa") +print(result) +assert result == 2 +print("Success!") diff --git a/users/wpcarro/scratch/facebook/evaluator.hs b/users/wpcarro/scratch/facebook/evaluator.hs new file mode 100644 index 0000000000..1ba46a7548 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/evaluator.py b/users/wpcarro/scratch/facebook/evaluator.py new file mode 100644 index 0000000000..14deb66a8f --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/find-duplicate-beast-mode.py b/users/wpcarro/scratch/facebook/find-duplicate-beast-mode.py new file mode 100644 index 0000000000..e246415efd --- /dev/null +++ b/users/wpcarro/scratch/facebook/find-duplicate-beast-mode.py @@ -0,0 +1,57 @@ +def advance(position, xs): + """ + Return the next element in `xs` pointed to by the current `position`. + """ + return xs[position - 1] + +def find_duplicate(xs): + """ + Find the duplicate integer in the list, `xs`. + """ + beg = xs[-1] + a = beg + b = advance(a, xs) + # Find the first element of the cycle + cycle_beg = None + while a != b: + cycle_beg = a + a = advance(a, xs) + b = advance(b, xs) + b = advance(b, xs) + # The duplicate element is the element before the `cycle_beg` + a = beg + result = None + while a != cycle_beg: + result = a + a = advance(a, xs) + return result + +def find_duplicate(xs): + """ + This is the solution that InterviewCake.com suggests. + """ + # find length of the cycle + beg = xs[-1] + a = beg + for _ in range(len(xs)): + a = advance(a, xs) + element = a + a = advance(a, xs) + n = 1 + while a != element: + a = advance(a, xs) + n += 1 + # find the first element in the cycle + a, b = beg, beg + for _ in range(n): + b = advance(b, xs) + while a != b: + a = advance(a, xs) + b = advance(b, xs) + return a + +xs = [2, 3, 1, 3] +result = find_duplicate(xs) +print(result) +assert result == 3 +print("Success!") diff --git a/users/wpcarro/scratch/facebook/find-duplicate-optimize-for-space.py b/users/wpcarro/scratch/facebook/find-duplicate-optimize-for-space.py new file mode 100644 index 0000000000..7c491aef60 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/find-rotation-point.py b/users/wpcarro/scratch/facebook/find-rotation-point.py new file mode 100644 index 0000000000..3636be4d93 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/find-unique-int-among-duplicates.py b/users/wpcarro/scratch/facebook/find-unique-int-among-duplicates.py new file mode 100644 index 0000000000..56032aa05c --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/graph-coloring.py b/users/wpcarro/scratch/facebook/graph-coloring.py new file mode 100644 index 0000000000..e5b6d9c893 --- /dev/null +++ b/users/wpcarro/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))) + for c in node.neighbors: + if c.label not in seen: + xs.append(c) + seen.add(node.label) + 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 + for c in x.neighbors: + if c.label not in seen: + palette.advance() + xs.append((c, palette.get())) + seen.add(x.label) + +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/users/wpcarro/scratch/facebook/hard/binary-adder.py b/users/wpcarro/scratch/facebook/hard/binary-adder.py new file mode 100644 index 0000000000..f79a9f22b3 --- /dev/null +++ b/users/wpcarro/scratch/facebook/hard/binary-adder.py @@ -0,0 +1,22 @@ +import random + +def add(a, b): + """ + Return the sum of `a` and `b`. + """ + if b == 0: + return a + sum = a ^ b + carry = (a & b) << 1 + return add(sum, carry) + +################################################################################ +# Tests +################################################################################ + +for _ in range(10): + x, y = random.randint(0, 100), random.randint(0, 100) + print("{} + {} = {} == {}".format(x, y, x + y, add(x, y))) + assert add(x, y) == x + y + print("Pass!") +print("Success!") diff --git a/users/wpcarro/scratch/facebook/hard/fisher-yates.py b/users/wpcarro/scratch/facebook/hard/fisher-yates.py new file mode 100644 index 0000000000..200d1613dd --- /dev/null +++ b/users/wpcarro/scratch/facebook/hard/fisher-yates.py @@ -0,0 +1,7 @@ +import random + +def shuffle(xs): + n = len(xs) + for i in range(n): + j = random.randint(i, n - 1) + xs[i], xs[j] = xs[j], xs[i] diff --git a/users/wpcarro/scratch/facebook/hard/random-choice.py b/users/wpcarro/scratch/facebook/hard/random-choice.py new file mode 100644 index 0000000000..a5c6e4e6ee --- /dev/null +++ b/users/wpcarro/scratch/facebook/hard/random-choice.py @@ -0,0 +1,50 @@ +import random + +# This class of problems is known as "resevoir sampling". +def choose_a(m, xs): + """ + Randomly choose `m` elements from `xs`. + This algorithm runs in linear time with respect to the size of `xs`. + """ + result = [None] * m + for i in range(len(xs)): + j = random.randint(0, i) + if j < m: + result[j] = xs[i] + return result + +def choose_b(m, xs): + """ + This algorithm, which copies `xs`, which runs in linear time, and then + shuffles the copies, which also runs in linear time, achieves the same + result as `choose_a` and both run in linear time. + + `choose_a` is still preferable since it has a coefficient of one, while this + version has a coefficient of two because it copies + shuffles. + """ + ys = xs[:] + random.shuffle(ys) + return ys[:m] + +def choose_c(m, xs): + """ + This is one, possibly inefficient, way to randomly sample `m` elements from + `xs`. + """ + choices = set() + while len(choices) < m: + choices.add(random.randint(0, len(xs) - 1)) + return [xs[i] for i in choices] + +# ROYGBIV +xs = [ + 'red', + 'orange', + 'yellow', + 'green', + 'blue', + 'indigo', + 'violet', +] +print(choose_b(3, xs)) +print(choose_c(3, xs)) diff --git a/users/wpcarro/scratch/facebook/hard/suffix-tree.py b/users/wpcarro/scratch/facebook/hard/suffix-tree.py new file mode 100644 index 0000000000..782678fb82 --- /dev/null +++ b/users/wpcarro/scratch/facebook/hard/suffix-tree.py @@ -0,0 +1,93 @@ +import random +from collections import deque + +def exists(pattern, tree): + """ + Return true if `pattern` exists in `tree`. + """ + if len(pattern) == 0: + return True + if len(pattern) == 1: + for branch in tree: + if branch[0] == pattern[0]: + return True + return False + for branch in tree: + if branch[0] == pattern[0]: + return exists(pattern[1:], branch[1]) + return False + +# Branch :: (Char, [Branch]) +# SuffixTree :: [Branch] + +def suffix_tree(xs): + """ + Create a suffix tree from the input string, `xs`. + """ + root = [] + for i in range(len(xs)): + curr = xs[i:] + parent = root + for c1 in curr: + grafted = False + for c2, children in parent: + if c1 == c2: + grafted = True + parent = children + if grafted: + continue + else: + children = [] + child = (c1, children) + parent.append(child) + parent = children + return root + +def suffix_tree(x): + """ + Creates a suffix from the input string, `x`. This implementation uses a + stack. + """ + result = [None, []] + q = deque() + for i in range(len(x)): + q.append((result, x[i:])) + while q: + parent, x = q.popleft() + s = [] + s.append((parent, x)) + while s: + parent, x = s.pop() + if not x: + continue + c, rest = x[0], x[1:] + grafted = False + for child in parent[1]: + if c == child[0]: + s.append((child, rest)) + grafted = True + if not grafted: + child = [c, []] + parent[1].append(child) + s.append((child, rest)) + return result[1] + +################################################################################ +# Tests +################################################################################ + +x = random.choice(["burrito", "pizza", "guacamole"]) +tree = suffix_tree(x) +for branch in tree: + print(branch) + +for _ in range(3): + n = len(x) + i, j = random.randint(0, n), random.randint(0, n) + pattern = x[min(i, j):max(i, j)] + print("Checking \"{}\" for \"{}\" ...".format(x, pattern)) + print("Result: {}".format(exists(pattern, tree))) + pattern = random.choice(["foo", "bar", "baz"]) + print("Checking \"{}\" for \"{}\" ...".format(x, pattern)) + print("Result: {}".format(exists(pattern, tree))) + print() diff --git a/users/wpcarro/scratch/facebook/heap.py b/users/wpcarro/scratch/facebook/heap.py new file mode 100644 index 0000000000..0c0dce91b4 --- /dev/null +++ b/users/wpcarro/scratch/facebook/heap.py @@ -0,0 +1,30 @@ +from math import floor + +class Heap(object): + def __init__(self): + self.xs = [None] + self.i = 1 + + def __repr__(self): + return "[{}]".format(", ".join(str(x) for x in self.xs[1:])) + + def insert(self, x): + if len(self.xs) == 1: + self.xs.append(x) + self.i += 1 + return + self.xs.append(x) + i = self.i + while i != 1 and self.xs[floor(i / 2)] > self.xs[i]: + self.xs[floor(i / 2)], self.xs[i] = self.xs[i], self.xs[floor(i / 2)] + i = floor(i / 2) + self.i += 1 + + def root(self): + return self.xs[1] + +xs = Heap() +print(xs) +for x in [12, 15, 14, 21, 1, 10]: + xs.insert(x) + print(xs) diff --git a/users/wpcarro/scratch/facebook/highest-product-of-3.py b/users/wpcarro/scratch/facebook/highest-product-of-3.py new file mode 100644 index 0000000000..c237b8e52e --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/infix-to-postfix.py b/users/wpcarro/scratch/facebook/infix-to-postfix.py new file mode 100644 index 0000000000..4c6d64494d --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/inflight-entertainment.py b/users/wpcarro/scratch/facebook/inflight-entertainment.py new file mode 100644 index 0000000000..7ddea5350a --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/intersecting-linked-lists.py b/users/wpcarro/scratch/facebook/intersecting-linked-lists.py new file mode 100644 index 0000000000..80ac01dafd --- /dev/null +++ b/users/wpcarro/scratch/facebook/intersecting-linked-lists.py @@ -0,0 +1,34 @@ +class LinkedList(object): + def __init__(self, x): + self.val = x + self.next = None + + def __repr__(self): + if self.next: + return "{} -> {}".format(self.val, self.next) + return "{}".format(self.val) + +def find_intersection(a, b): + init_a, init_b = a, b + + while a != b: + a = a.next if a.next else init_b + b = b.next if b.next else init_a + + return a + +# make A... +e1 = LinkedList(5) +d1 = LinkedList(2); d1.next = e1 +c1 = LinkedList(3); c1.next = d1 # shared +b1 = LinkedList(1); b1.next = c1 # shared +a1 = LinkedList(4); a1.next = b1 # shared + +# make B... +c2 = LinkedList(1); c2.next = c1 +b2 = LinkedList(5); b2.next = c2 +a2 = LinkedList(6); a2.next = b2 + +print(a1) +print(a2) +print(find_intersection(a1, a2).val) diff --git a/users/wpcarro/scratch/facebook/interview-cake/bst-checker.py b/users/wpcarro/scratch/facebook/interview-cake/bst-checker.py new file mode 100644 index 0000000000..bbd52fa9c6 --- /dev/null +++ b/users/wpcarro/scratch/facebook/interview-cake/bst-checker.py @@ -0,0 +1,14 @@ +def is_valid(node): + """ + Return True if `node` is a valid binary search tree. + """ + s = [] + s.append((float('-inf'), node, float('inf'))) + while s: + lo, node, hi = s.pop() + if lo <= node.value <= hi: + node.lhs and s.append((lo, node.lhs, node.value)) + node.rhs and s.append((node.value, node.rhs, hi)) + else: + return False + return True diff --git a/users/wpcarro/scratch/facebook/interview-cake/cafe-order-checker.py b/users/wpcarro/scratch/facebook/interview-cake/cafe-order-checker.py new file mode 100644 index 0000000000..688c340b98 --- /dev/null +++ b/users/wpcarro/scratch/facebook/interview-cake/cafe-order-checker.py @@ -0,0 +1,34 @@ +def valid(take_out, dine_in, served): + # edge case + if len(take_out) + len(dine_in) != len(served): + return False + i = 0 + j = 0 + k = 0 + while i < len(take_out) and j < len(dine_in): + if take_out[i] == served[k]: + i += 1 + elif dine_in[j] == served[k]: + j += 1 + else: + return False + k += 1 + # take out + while i < len(take_out): + if take_out[i] != served[k]: + return False + i += 1 + # dine in + while j < len(dine_in): + if dine_in[j] != served[k]: + return False + j += 1 + return True + +take_out = [17, 8, 24] +dine_in = [12, 19, 2] +served = [17, 8, 12, 19, 24, 2] +result = valid(take_out, dine_in, served) +print(result) +assert result +print("Success!") diff --git a/users/wpcarro/scratch/facebook/interview-cake/linked-list-cycles.py b/users/wpcarro/scratch/facebook/interview-cake/linked-list-cycles.py new file mode 100644 index 0000000000..523ecd959d --- /dev/null +++ b/users/wpcarro/scratch/facebook/interview-cake/linked-list-cycles.py @@ -0,0 +1,70 @@ +def contains_cycle(node): + """ + Return True if the linked-list, `node`, contains a cycle. + """ + if not node: + return False + a = node + b = node.next + while a != b: + a = a.next + if b and b.next and b.next.next: + b = b.next.next + else: + return False + return True + +################################################################################ +# Bonus +################################################################################ + +def first_node_in_cycle(node): + """ + Given that the linked-list, `node`, contains a cycle, return the first + element of that cycle. + """ + # enter the cycle + a = node + b = node.next + while a != b: + a = a.next + b = b.next.next + + # get the length of the cycle + beg = a + a = a.next + n = 1 + while a != beg: + a = a.next + n += 1 + + # run b n-steps ahead of a + a = node + b = node + for _ in range(n): + b = b.next + + # where they intersect is the answer + while a != b: + a = a.next + b = b.next + return a + +################################################################################ +# Tests +################################################################################ + +class Node(object): + def __init__(self, value, next=None): + self.value = value + self.next = next + def __repr__(self): + return "Node({}) -> ...".format(self.value) + +d = Node('d') +c = Node('c', d) +b = Node('b', c) +a = Node('a', b) +d.next = b + +print(first_node_in_cycle(a)) diff --git a/users/wpcarro/scratch/facebook/interview-cake/merge-sorted-arrays.py b/users/wpcarro/scratch/facebook/interview-cake/merge-sorted-arrays.py new file mode 100644 index 0000000000..877bb218fd --- /dev/null +++ b/users/wpcarro/scratch/facebook/interview-cake/merge-sorted-arrays.py @@ -0,0 +1,30 @@ +def merge_sorted(xs, ys): + result = [] + i = 0 + j = 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(xs): + result.append(ys[j]) + j += 1 + return result + +################################################################################ +# Tests +################################################################################ + +xs = [3, 4, 6, 10, 11, 15] +ys = [1, 5, 8, 12, 14, 19] +result = merge_sorted(xs, ys) +print(result) +assert len(result) == len(xs) + len(ys) +assert result == [1, 3, 4, 5, 6, 8, 10, 11, 12, 14, 15, 19] +print("Success!") diff --git a/users/wpcarro/scratch/facebook/interview-cake/nth-fibonacci.py b/users/wpcarro/scratch/facebook/interview-cake/nth-fibonacci.py new file mode 100644 index 0000000000..4629798cf7 --- /dev/null +++ b/users/wpcarro/scratch/facebook/interview-cake/nth-fibonacci.py @@ -0,0 +1,6 @@ +def fib(n): + cache = (0, 1) + for _ in range(n): + a, b = cache + cache = (b, a + b) + return cache[0] diff --git a/users/wpcarro/scratch/facebook/interview-cake/permutation-palindrome.py b/users/wpcarro/scratch/facebook/interview-cake/permutation-palindrome.py new file mode 100644 index 0000000000..ced3b336e0 --- /dev/null +++ b/users/wpcarro/scratch/facebook/interview-cake/permutation-palindrome.py @@ -0,0 +1,8 @@ +from collections import Counter + +def permutation_can_be_palindrome(x): + odd = 0 + for _, n in Counter(x): + if n % 0 != 0: + odd += 1 + return odd <= 1 diff --git a/users/wpcarro/scratch/facebook/interview-cake/queue-two-stacks.py b/users/wpcarro/scratch/facebook/interview-cake/queue-two-stacks.py new file mode 100644 index 0000000000..bfa465f98d --- /dev/null +++ b/users/wpcarro/scratch/facebook/interview-cake/queue-two-stacks.py @@ -0,0 +1,17 @@ +class Queue(object): + def __init__(self): + self.lhs = [] + self.rhs = [] + + def enqueue(self, x): + self.lhs.append(x) + + def dequeue(self): + if self.rhs: + return self.rhs.pop() + while self.lhs: + self.rhs.append(self.lhs.pop()) + if self.rhs: + return self.rhs.pop() + else: + raise Exception("Attempting to remove an item from an empty queue") diff --git a/users/wpcarro/scratch/facebook/knapsack-faq.py b/users/wpcarro/scratch/facebook/knapsack-faq.py new file mode 100644 index 0000000000..ae04f5eb96 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/kth-to-last-node-in-singly-linked-list.py b/users/wpcarro/scratch/facebook/kth-to-last-node-in-singly-linked-list.py new file mode 100644 index 0000000000..dd258d924d --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/language.py b/users/wpcarro/scratch/facebook/language.py new file mode 100644 index 0000000000..b57f469b49 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/language2.py b/users/wpcarro/scratch/facebook/language2.py new file mode 100644 index 0000000000..3aebd45483 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/largest-contiguous-sum.py b/users/wpcarro/scratch/facebook/largest-contiguous-sum.py new file mode 100644 index 0000000000..7761bf1c61 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/largest-stack.py b/users/wpcarro/scratch/facebook/largest-stack.py new file mode 100644 index 0000000000..052db44153 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/leetcode.org b/users/wpcarro/scratch/facebook/leetcode.org new file mode 100644 index 0000000000..6e915faf29 --- /dev/null +++ b/users/wpcarro/scratch/facebook/leetcode.org @@ -0,0 +1,163 @@ +# This list is from: +# https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-100-LeetCode-Questions-to-Save-Your-Time-OaM1orEU +* Array +** DONE Two Sum + https://leetcode.com/problems/two-sum/ +** DONE Best Time to Buy and Sell Stock + https://leetcode.com/problems/best-time-to-buy-and-sell-stock/ +** DONE Contains Duplicate + https://leetcode.com/problems/contains-duplicate/ +** DONE Product of Array Except Self + https://leetcode.com/problems/product-of-array-except-self/ +** DONE Maximum Subarray + https://leetcode.com/problems/maximum-subarray/ +** DONE Maximum Product Subarray + https://leetcode.com/problems/maximum-product-subarray/ +** DONE Find Minimum in Rotated Sorted Array + https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/ +** DONE Search in Rotated Sorted Array + https://leetcode.com/problems/search-in-rotated-sorted-array/ +** DONE 3Sum + https://leetcode.com/problems/3sum/ +** DONE Container With Most Water + https://leetcode.com/problems/container-with-most-water/ +* Binary +** DONE Sum of Two Integers + https://leetcode.com/problems/sum-of-two-integers/ +** DONE Number of 1 Bits + https://leetcode.com/problems/number-of-1-bits/ +** TODO Counting Bits + https://leetcode.com/problems/counting-bits/ +** DONE Missing Number + https://leetcode.com/problems/missing-number/ +** TODO Reverse Bits + https://leetcode.com/problems/reverse-bits/ +* Dynamic Programming +** DONE Climbing Stairs + https://leetcode.com/problems/climbing-stairs/ +** TODO Coin Change + https://leetcode.com/problems/coin-change/ +** TODO Longest Increasing Subsequence + https://leetcode.com/problems/longest-increasing-subsequence/ +** TODO Longest Common Subsequence +** DONE Word Break Problem + https://leetcode.com/problems/word-break/ +** TODO Combination Sum + https://leetcode.com/problems/combination-sum-iv/ +** TODO House Robber + https://leetcode.com/problems/house-robber/ +** TODO House Robber II + https://leetcode.com/problems/house-robber-ii/ +** TODO Decode Ways + https://leetcode.com/problems/decode-ways/ +** TODO Unique Paths + https://leetcode.com/problems/unique-paths/ +** TODO Jump Game + https://leetcode.com/problems/jump-game/ +* Graph +** DONE Clone Graph + https://leetcode.com/problems/clone-graph/ +** DONE Course Schedule + https://leetcode.com/problems/course-schedule/ +** TODO Pacific Atlantic Water Flow + https://leetcode.com/problems/pacific-atlantic-water-flow/ +** DONE Number of Islands + https://leetcode.com/problems/number-of-islands/ +** TODO Longest Consecutive Sequence + https://leetcode.com/problems/longest-consecutive-sequence/ +** TODO Alien Dictionary (Leetcode Premium) + https://leetcode.com/problems/alien-dictionary/ +** DONE Graph Valid Tree (Leetcode Premium) + https://leetcode.com/problems/graph-valid-tree/ +** DONE Number of Connected Components in an Undirected Graph (Leetcode Premium) + https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/ +* Interval +** TODO Insert Interval + https://leetcode.com/problems/insert-interval/ +** DONE Merge Intervals + https://leetcode.com/problems/merge-intervals/ +** TODO No Overlapping Intervals + https://leetcode.com/problems/non-overlapping-intervals/ +** DONE Meeting Rooms (Leetcode Premium) + https://leetcode.com/problems/meeting-rooms/ +** TODO Meeting Rooms II (Leetcode Premium) + https://leetcode.com/problems/meeting-rooms-ii/ +* Linked List +** DONE Reverse a Linked List + https://leetcode.com/problems/reverse-linked-list/ +** DONE Detect Cycle in a Linked List + https://leetcode.com/problems/linked-list-cycle/ +** DONE Merge Two Sorted Lists + https://leetcode.com/problems/merge-two-sorted-lists/ +** DONE Merge K Sorted Lists + https://leetcode.com/problems/merge-k-sorted-lists/ +** DONE Remove Nth Node From End Of List + https://leetcode.com/problems/remove-nth-node-from-end-of-list/ +** DONE Reorder List + https://leetcode.com/problems/reorder-list/ +* Matrix +** DONE Set Matrix Zeroes + https://leetcode.com/problems/set-matrix-zeroes/ +** DONE Spiral Matrix + https://leetcode.com/problems/spiral-matrix/ +** TODO Rotate Image + https://leetcode.com/problems/rotate-image/ +** DONE Word Search + https://leetcode.com/problems/word-search/ +* String +** TODO Longest Substring Without Repeating Characters + https://leetcode.com/problems/longest-substring-without-repeating-characters/ +** TODO Longest Repeating Character Replacement + https://leetcode.com/problems/longest-repeating-character-replacement/ +** TODO Minimum Window Substring + https://leetcode.com/problems/minimum-window-substring/ +** DONE Valid Anagram + https://leetcode.com/problems/valid-anagram/ +** DONE Group Anagrams + https://leetcode.com/problems/group-anagrams/ +** DONE Valid Parentheses + https://leetcode.com/problems/valid-parentheses/ +** DONE Valid Palindrome + https://leetcode.com/problems/valid-palindrome/ +** TODO Longest Palindromic Substring + https://leetcode.com/problems/longest-palindromic-substring/ +** TODO Palindromic Substrings + https://leetcode.com/problems/palindromic-substrings/ +** DONE Encode and Decode Strings (Leetcode Premium) + https://leetcode.com/problems/encode-and-decode-strings/ +* Tree +** DONE Maximum Depth of Binary Tree + https://leetcode.com/problems/maximum-depth-of-binary-tree/ +** DONE Same Tree + https://leetcode.com/problems/same-tree/ +** DONE Invert/Flip Binary Tree + https://leetcode.com/problems/invert-binary-tree/ +** DONE Binary Tree Maximum Path Sum + https://leetcode.com/problems/binary-tree-maximum-path-sum/ +** DONE Binary Tree Level Order Traversal + https://leetcode.com/problems/binary-tree-level-order-traversal/ +** DONE Serialize and Deserialize Binary Tree + https://leetcode.com/problems/serialize-and-deserialize-binary-tree/ +** DONE Subtree of Another Tree + https://leetcode.com/problems/subtree-of-another-tree/ +** DONE Construct Binary Tree from Preorder and Inorder Traversal + https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ +** DONE Validate Binary Search Tree + https://leetcode.com/problems/validate-binary-search-tree/ +** DONE Kth Smallest Element in a BST + https://leetcode.com/problems/kth-smallest-element-in-a-bst/ +** DONE Lowest Common Ancestor of BST + https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/ +** DONE Implement Trie (Prefix Tree) + https://leetcode.com/problems/implement-trie-prefix-tree/ +** DONE Add and Search Word + https://leetcode.com/problems/add-and-search-word-data-structure-design/ +** DONE Word Search II + https://leetcode.com/problems/word-search-ii/ +* Heap +** DONE Merge K Sorted Lists + https://leetcode.com/problems/merge-k-sorted-lists/ +** DONE Top K Frequent Elements + https://leetcode.com/problems/top-k-frequent-elements/ +** DONE Find Median from Data Stream + https://leetcode.com/problems/find-median-from-data-stream/ diff --git a/users/wpcarro/scratch/facebook/linked-list-cycles.py b/users/wpcarro/scratch/facebook/linked-list-cycles.py new file mode 100644 index 0000000000..56f54d4978 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/linked_list.py b/users/wpcarro/scratch/facebook/linked_list.py new file mode 100644 index 0000000000..1ae7061e83 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/london-knapsack.py b/users/wpcarro/scratch/facebook/london-knapsack.py new file mode 100644 index 0000000000..a034fb4961 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/longest-common-substring.py b/users/wpcarro/scratch/facebook/longest-common-substring.py new file mode 100644 index 0000000000..8a838db45d --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/merge-sorted-arrays.py b/users/wpcarro/scratch/facebook/merge-sorted-arrays.py new file mode 100644 index 0000000000..ae9377ad11 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/merging-ranges.py b/users/wpcarro/scratch/facebook/merging-ranges.py new file mode 100644 index 0000000000..6da44572ee --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/mesh-message.py b/users/wpcarro/scratch/facebook/mesh-message.py new file mode 100644 index 0000000000..8438b059d8 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/moderate/decompress-xml.py b/users/wpcarro/scratch/facebook/moderate/decompress-xml.py new file mode 100644 index 0000000000..b22983ed7a --- /dev/null +++ b/users/wpcarro/scratch/facebook/moderate/decompress-xml.py @@ -0,0 +1,98 @@ +import string +from parser import Parser + +mapping = { + 1: "family", + 2: "person", + 3: "firstName", + 4: "lastName", + 5: "state", +} + +def parse_int(i, xs): + result = "" + while i < len(xs) and xs[i] in string.digits: + result += xs[i] + i += 1 + return i, int(result) + +def parse_string(i, xs): + result = "" + while xs[i+1] not in string.digits: + result += xs[i] + i += 1 + return i, result + +def tokenize(xs): + result = [] + i = 0 + while i < len(xs): + if xs[i] in string.digits: + i, n = parse_int(i, xs) + result.append(n) + elif xs[i] in string.ascii_letters: + i, x = parse_string(i, xs) + result.append(x) + elif xs[i] == " ": + i += 1 + continue + return result + +def parse(xs): + parser = Parser(tokenize(xs)) + return parse_element(parser) + +# Element -> Tag Attribute* End Element* End ; +# Tag -> INTEGER ; +# Value -> STRING End ; +# Attribute -> Tag Value ; +# End -> 0 ; + +def parse_element(parser): + if type(parser.curr()) == str: + return parser.consume() + tag_id = parser.expect_predicate(lambda x: type(x) == int) + tag = mapping[tag_id] + attrs = parse_attrs(parser) + parser.expect([0]) + children = [] + while not parser.exhausted() and parser.curr() != 0: + children.append(parse_element(parser)) + parser.expect([0]) + return [tag, attrs, children] + +def parse_attrs(parser): + result = [] + while parser.curr() != 0: + tag_id = parser.expect_predicate(lambda x: type(x) == int) + tag = mapping[tag_id] + value = parser.consume() + result.append((tag, value)) + return result + +def stringify_xml(tree, indent=0): + if type(tree) == str: + return tree + result = "" + tag, attrs, children = tree + + str_attrs = [] + for k, v in attrs: + str_attrs.append("{}=\"{}\"".format(k, v)) + str_attrs = (" " if str_attrs else "") + " ".join(str_attrs) + + str_children = [] + for child in children: + str_children.append(" " * 2 * indent + stringify_xml(child, indent + 1)) + str_children = "\n".join(str_children) + + result += "{}<{}{}>\n{}{}\n{}</{}>".format( + " " * 2 * indent, tag, str_attrs, " " * 2 * indent, str_children, + " " * 2 * indent, tag) + return result + +x = "1 4 McDowell 5 CA 0 2 3 Gayle 0 Some Message 0 0" +print("Input: {}".format(x)) +print("Tokens: {}".format(tokenize(x))) +print("Parsed: {}".format(parse(x))) +print("{}".format(stringify_xml(parse(x)))) diff --git a/users/wpcarro/scratch/facebook/moderate/find-pairs-for-sum.py b/users/wpcarro/scratch/facebook/moderate/find-pairs-for-sum.py new file mode 100644 index 0000000000..69c2fc4312 --- /dev/null +++ b/users/wpcarro/scratch/facebook/moderate/find-pairs-for-sum.py @@ -0,0 +1,19 @@ +import random + +def find_pairs(xs, n): + """ + Return all pairs of integers in `xs` that sum to `n`. + """ + seeking = set() + result = set() + for x in xs: + if x in seeking: + result.add((n - x, x)) + else: + seeking.add(n - x) + return result + +xs = [random.randint(1, 10) for _ in range(10)] +n = random.randint(1, 10) + random.randint(1, 10) +print("Seeking all pairs in {} for {}...".format(xs, n)) +print(find_pairs(xs, n)) diff --git a/users/wpcarro/scratch/facebook/moderate/parser.py b/users/wpcarro/scratch/facebook/moderate/parser.py new file mode 100644 index 0000000000..57dfb058c0 --- /dev/null +++ b/users/wpcarro/scratch/facebook/moderate/parser.py @@ -0,0 +1,37 @@ +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 next(self): + return self.tokens[self.i + 1] + + 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())) + return self.prev() + + def expect_predicate(self, predicate): + if predicate(self.curr()): + return self.consume() + raise Exception("Expected token \"{}\" to pass predicate, but it did not".format(self.curr())) + + def exhausted(self): + return self.i >= len(self.tokens) diff --git a/users/wpcarro/scratch/facebook/moderate/rand7.py b/users/wpcarro/scratch/facebook/moderate/rand7.py new file mode 100644 index 0000000000..ed3a7cea80 --- /dev/null +++ b/users/wpcarro/scratch/facebook/moderate/rand7.py @@ -0,0 +1,25 @@ +# Define a function, rand7, that generates a random number [0,7), using only +# rand5, which generates a random number [0,5). + +import random +from collections import Counter + +# Returns [0,4] +def rand5(): + return random.randint(0,4) + +# Return [0,6] +def rand7_a(): + return sum(rand5() for _ in range(7)) % 7 + +# Return [0,6] +def rand7_b(): + x = 5 * rand5() + rand5() + if x < 21: + return x % 7 + return rand7_b() + +c = Counter([rand7_a() for _ in range(100000)]) +print(c) +c = Counter([rand7_b() for _ in range(100000)]) +print(c) diff --git a/users/wpcarro/scratch/facebook/moderate/tic-tac-toe-checker.py b/users/wpcarro/scratch/facebook/moderate/tic-tac-toe-checker.py new file mode 100644 index 0000000000..342c29be6b --- /dev/null +++ b/users/wpcarro/scratch/facebook/moderate/tic-tac-toe-checker.py @@ -0,0 +1,99 @@ +import random + +def print_board(board): + result = [] + for row in range(len(board)): + r = [] + for col in range(len(board[row])): + cell = board[row][col] + if not cell: + r.append("-") + else: + r.append(cell) + result.append(" | ".join(r)) + print("\n---------\n".join(result)) + +def init_board(): + result = [] + for row in range(3): + r = [] + for col in range(3): + r.append(None) + result.append(r) + return result + +def check(board, player): + print_board(board) + print() + if player not in "XO": + raise Exception("Only checking the board for Xs or Os. You supplied {}".format(player)) + dn, ax, ddg, udg = "DOWN", "ACROSS", "DOWN_DIAGONAL", "UP_DIAGONAL" + ways = [ + [[dn, ax, ddg], [dn], [dn, udg]], + [[ax], [], []], + [[ax], [], []], + ] + for row in range(len(board)): + for col in range(len(board[row])): + if board[row][col] == player: + xs = ways[row][col] + for x in xs: + if x == dn: + if {player} == {board[row+1][col], board[row+2][col]}: + return True + if x == ax: + if {player} == {board[row][col+1], board[row][col+2]}: + return True + if x == ddg: + if {player} == {board[row+1][col+1], board[row+2][col+2]}: + return True + if x == udg: + if {player} == {board[row+1][col-1], board[row+2][col-2]}: + return True + return False + +def op(player): + return "X" if player == "O" else "O" + +dn_win = lambda p: [ + [op(p), p, None], + [op(p), p, None], + [None, p, None], +] + +ax_win = lambda p: [ + [p, p, p], + [op(p), op(p), None], + [None, None, None], +] + +ddg_win = lambda p: [ + [p, None, None], + [op(p), p, None], + [op(p), None, p], +] + +udg_win = lambda p: [ + [op(p), None, p], + [op(p), p, None], + [p, None, None], +] + +# Down +p = random.choice(["X", "O"]) +assert check(dn_win(p), p) == True +assert check(dn_win(p), op(p)) == False +# Across +p = random.choice(["X", "O"]) +assert check(ax_win(p), p) == True +assert check(ax_win(p), op(p)) == False +# Down Diagonally +p = random.choice(["X", "O"]) +assert check(ddg_win(p), p) == True +assert check(ddg_win(p), op(p)) == False +# Down Diagonally +p = random.choice(["X", "O"]) +assert check(udg_win(p), p) == True +assert check(udg_win(p), op(p)) == False +# Success +print("Tests pass!") diff --git a/users/wpcarro/scratch/facebook/moderate/unsorted-substring.py b/users/wpcarro/scratch/facebook/moderate/unsorted-substring.py new file mode 100644 index 0000000000..de7326b058 --- /dev/null +++ b/users/wpcarro/scratch/facebook/moderate/unsorted-substring.py @@ -0,0 +1,67 @@ +# Write a function that accepts an array of integers and returns the indices for +# the starting and ending integers that, if their elements were sorted, the +# entire array would be sorted. + +################################################################################ +# First Attempt +################################################################################ + +def unsorted_substring(xs): + ys = xs[:]; ys.sort() + m = 0 + while xs[m] == ys[m]: + m += 1 + if m >= len(xs): + return -1, -1 + n = len(xs) - 1 + while xs[n] == ys[n]: + n -= 1 + return m, n + +################################################################################ +# Second Attempt +################################################################################ + +def unsorted_substring_2(xs): + beg = 1 + while xs[beg - 1] <= xs[beg]: + beg += 1 + if beg >= len(xs): + return -1, -1 + end = len(xs) - 2 + while xs[end + 1] >= xs[end]: + end -= 1 + + min_mid = xs[beg] + max_mid = xs[beg] + i = beg + 1 + while i <= end: + min_mid = min(min_mid, xs[i]) + max_mid = max(max_mid, xs[i]) + i += 1 + + # beg -= 1 until max(lhs) <= min(mid) + while beg - 1 >= 0 and xs[beg - 1] >= min_mid: + beg -= 1 + + # end += 1 while max(mid) <= min(rhs) + while end + 1 < len(xs) and max_mid >= xs[end + 1]: + end += 1 + return beg, end + +################################################################################ +# Tests +################################################################################ + +xs = [ + [1,2,4,7,10,11,7,12,6,7,16,18,19], + [1,2,3,4], + [4,3,2,1], + [1,3,2,4], + [2,1,3,4], +] + +for x in xs: + print("Testing: {}".format(x)) + print("1) {}".format(unsorted_substring(x))) + print("2) {}".format(unsorted_substring_2(x))) diff --git a/users/wpcarro/scratch/facebook/move-zeroes-to-end.py b/users/wpcarro/scratch/facebook/move-zeroes-to-end.py new file mode 100644 index 0000000000..1535b5a9fa --- /dev/null +++ b/users/wpcarro/scratch/facebook/move-zeroes-to-end.py @@ -0,0 +1,62 @@ +from collections import deque + +def move_zeroes_to_end_quadratic(xs): + """ + This solution is suboptimal. It runs in quadratic time, and it uses constant + space. + """ + i = 0 + while i < len(xs) - 1: + if xs[i] == 0: + j = i + 1 + while j < len(xs) and xs[j] == 0: + j += 1 + if j >= len(xs): + break + xs[i], xs[j] = xs[j], xs[i] + i += 1 + +def move_zeroes_to_end_linear(xs): + """ + This solution is clever. It runs in linear time proportionate to the number + of elements in `xs`, and has linear space proportionate to the number of + consecutive zeroes in `xs`. + """ + q = deque() + for i in range(len(xs)): + if xs[i] == 0: + q.append(i) + else: + if q: + j = q.popleft() + xs[i], xs[j] = xs[j], xs[i] + q.append(i) + +def move_zeroes_to_end_linear_constant_space(xs): + """ + This is the optimal solution. It runs in linear time and uses constant + space. + """ + i = 0 + for j in range(len(xs)): + if xs[j] != 0: + xs[i], xs[j] = xs[j], xs[i] + i += 1 + + +################################################################################ +# Tests +################################################################################ + +xss = [ + [1, 2, 0, 3, 4, 0, 0, 5, 0], + [0, 1, 2, 0, 3, 4], + [0, 0], +] + +f = move_zeroes_to_end_linear_constant_space + +for xs in xss: + print(xs) + f(xs) + print(xs) diff --git a/users/wpcarro/scratch/facebook/mst.py b/users/wpcarro/scratch/facebook/mst.py new file mode 100644 index 0000000000..81aa5cd487 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/n-queens.py b/users/wpcarro/scratch/facebook/n-queens.py new file mode 100644 index 0000000000..fc9326886c --- /dev/null +++ b/users/wpcarro/scratch/facebook/n-queens.py @@ -0,0 +1,46 @@ +def print_board(board): + result = [] + for row in range(8): + r = [] + for col in range(8): + r.append("X" if col == board[row] else "-") + result.append(" ".join(r)) + print("\n".join(result)) + print() + +def can_place(board, row, col): + column_occupied = not any([board[i] == col for i in range(row)]) + + diagonals_clear = True + for r in range(row): + w = abs(col - board[r]) + h = abs(r - row) + if w == h: + diagonals_clear = False + break + + return all([column_occupied, diagonals_clear]) + +def init_board(): + board = [] + for row in range(8): + board.append(None) + return board + +def copy_board(board): + return board[:] + +def n_queens(): + do_n_queens(init_board(), 0, 0) + +def do_n_queens(board, row, col): + if row == 8: + print_board(board) + return + for i in range(col, 8): + if can_place(board, row, i): + copy = copy_board(board) + copy[row] = i + do_n_queens(copy, row + 1, 0) + +n_queens() diff --git a/users/wpcarro/scratch/facebook/nearby-words.py b/users/wpcarro/scratch/facebook/nearby-words.py new file mode 100644 index 0000000000..d2fc3cf5cf --- /dev/null +++ b/users/wpcarro/scratch/facebook/nearby-words.py @@ -0,0 +1,33 @@ +def nearby_chars(c): + keyboard = [ + "qwertyuiop", + "asdfghjkl", + "zxcvbnm", + ] + + for row in keyboard: + for i in range(len(row)): + if row[i] == c: + result = set() + if i + 1 < len(row): + result.add(row[i + 1]) + if i - 1 >= 0: + result.add(row[i - 1]) + return result + +def is_word(word): + words = { + "hello", + } + return word in words + +def nearby_words(x): + result = set() + for i in range(len(x)): + for c in nearby_chars(x[i]): + candidate = x[0:i] + c + x[i+1:] + if is_word(candidate): + result.add(candidate) + return result + +print(nearby_words('gello')) diff --git a/users/wpcarro/scratch/facebook/node.py b/users/wpcarro/scratch/facebook/node.py new file mode 100644 index 0000000000..4e24983af7 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/nth-fibonacci.py b/users/wpcarro/scratch/facebook/nth-fibonacci.py new file mode 100644 index 0000000000..f524067b3b --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/onsite.txt b/users/wpcarro/scratch/facebook/onsite.txt new file mode 100644 index 0000000000..b5242c4bd3 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/parsing/json.py b/users/wpcarro/scratch/facebook/parsing/json.py new file mode 100644 index 0000000000..3975e973fe --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/parsing/parser.py b/users/wpcarro/scratch/facebook/parsing/parser.py new file mode 100644 index 0000000000..407bff61c9 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/parsing/regex.py b/users/wpcarro/scratch/facebook/parsing/regex.py new file mode 100644 index 0000000000..7fc2ef34e2 --- /dev/null +++ b/users/wpcarro/scratch/facebook/parsing/regex.py @@ -0,0 +1,184 @@ +# Writing a small proof-of-concept... +# - lexer +# - parser +# - compiler +# ...for regex. +# +# BNF +# expression -> ( char_class | CHAR ) quantifier? ( "|" expression )* +# char_class -> "[" CHAR+ "]" +# quantifier -> "?" | "*" | "+" | "{" INT? "," INT? "}" +# +# Of the numerous things I do not support, here are a few items of which I'm +# aware: +# - alternatives: (a|b) +# - capture groups: (ab)cd + +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/users/wpcarro/scratch/facebook/permutation-palindrome.py b/users/wpcarro/scratch/facebook/permutation-palindrome.py new file mode 100644 index 0000000000..30603578ff --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/polynomial-rolling-hash.py b/users/wpcarro/scratch/facebook/polynomial-rolling-hash.py new file mode 100644 index 0000000000..0c7b7cb5a0 --- /dev/null +++ b/users/wpcarro/scratch/facebook/polynomial-rolling-hash.py @@ -0,0 +1,72 @@ +def compute_hash(x): + """ + Compute a unique fingerprint for the string input, `x`, as an integer using + the following equation: + + x[0] * P^0 + x[1] * P^1 + ... x[n-1] * P^(n-1) % M + + P and M are constants where P represents the next available prime number + that's GTE the number of unique characters you'll be hashing. In the case of + all lowercase characters, of which there are 26, the next available prime + number is 31. + """ + p = 31 + m = int(10e9) + 9 # large prime number + power = 0 + result = 0 + for c in x: + result += ord(c) * p**power + power += 1 + return result % m + +class HashTable(object): + def __init__(self, size): + """ + Create a hash table with `size` buckets. + """ + buckets = [] + for _ in range(size): + buckets.append([]) + self.xs = buckets + self.compute_hash = lambda k: compute_hash(k) % size + + def __repr__(self): + result = [] + for bucket in self.xs: + for entry in bucket: + result.append(entry) + return "HashTable({})".format(",".join(str(x) for x in result)) + + def get(self, key): + """ + Attempt to retrieve value stored under `key`. + """ + h = self.compute_hash(key) + for k, v in self.xs[h]: + if k == key: + return v + return None + + def put(self, key, val): + """ + Set `key` to `val`; update value at `key` if it already exists. + """ + h = self.compute_hash(key) + for i in range(len(self.xs[h])): + # Update entry if the key exists... + if self.xs[h][i][0] == key: + self.xs[h][i] = (key, val) + return None + # ...create a new entry otherwise + self.xs[h].append((key, val)) + + def delete(self, key): + """ + Remove entry `key` from the hash table. + """ + h = self.compute_hash(key) + for i in range(len(self.xs[h])): + k, v = self.xs[h][i] + if k == key: + self.xs[h].remove((k, v)) + return diff --git a/users/wpcarro/scratch/facebook/product-of-all-other-numbers.py b/users/wpcarro/scratch/facebook/product-of-all-other-numbers.py new file mode 100644 index 0000000000..d381386b62 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/queue-two-stacks.py b/users/wpcarro/scratch/facebook/queue-two-stacks.py new file mode 100644 index 0000000000..a71abeb005 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/rabin-karp.py b/users/wpcarro/scratch/facebook/rabin-karp.py new file mode 100644 index 0000000000..53a47b2783 --- /dev/null +++ b/users/wpcarro/scratch/facebook/rabin-karp.py @@ -0,0 +1,27 @@ +def substring_exists(corpus, pattern): + """ + Return True if `pattern` appears in `corpus`. + + This function runs in O(m) time where n is equal to the length of + `corpus`. To improve the efficiency of this algorithm, use a hashing + function the reduces the number of collisions, which will consequently + reduce the number of string-to-string, linear comparisons. + """ + m, n = len(corpus), len(pattern) + a = sum(ord(c) for c in corpus[0:n]) + b = sum(ord(c) for c in pattern) + + # (clumsily) prevent an off-by-one error... + if a == b and corpus[0:n] == pattern: + return True + + for i in range(1, m - n): + # Update the hash of corpus by subtracting the hash of the character + # that is sliding out of view and adding the hash of the character that + # is sliding into view. + a = a - ord(corpus[i - 1]) + ord(corpus[i + n - 1]) + # Integer comparison in O(0) time followed by string comparison in O(m) + # time. + if a == b and corpus[i:i + n] == pattern: + return True + return False diff --git a/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/magic-index.py b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/magic-index.py new file mode 100644 index 0000000000..03b2de015d --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/making-change.py b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/making-change.py new file mode 100644 index 0000000000..30c95a66c3 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/paint-fill.py b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/paint-fill.py new file mode 100644 index 0000000000..e9e7f6a9c1 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/parenthesize-bools.py b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/parenthesize-bools.py new file mode 100644 index 0000000000..f406d64e65 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/permutations.py b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/permutations.py new file mode 100644 index 0000000000..e23972d418 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/robot-grid-traversal.py b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/robot-grid-traversal.py new file mode 100644 index 0000000000..9ccc08526a --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/staircase.py b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/staircase.py new file mode 100644 index 0000000000..5eb4a85606 --- /dev/null +++ b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/staircase.py @@ -0,0 +1 @@ +# accidentally deleted my solution... TBI (again) diff --git a/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/subsets.py b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/subsets.py new file mode 100644 index 0000000000..a6d26aa850 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/valid-parens.py b/users/wpcarro/scratch/facebook/recursion-and-dynamic-programming/valid-parens.py new file mode 100644 index 0000000000..56f2c0b274 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/recursive-string-permutations.py b/users/wpcarro/scratch/facebook/recursive-string-permutations.py new file mode 100644 index 0000000000..e4c61eff9f --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/reverse-linked-list.py b/users/wpcarro/scratch/facebook/reverse-linked-list.py new file mode 100644 index 0000000000..820726733f --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/reverse-string-in-place.py b/users/wpcarro/scratch/facebook/reverse-string-in-place.py new file mode 100644 index 0000000000..72cd6c27a3 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/reverse-words.py b/users/wpcarro/scratch/facebook/reverse-words.py new file mode 100644 index 0000000000..5a38b828a3 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/scratch.py b/users/wpcarro/scratch/facebook/scratch.py new file mode 100644 index 0000000000..e772d75847 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/second-largest-item-in-bst.py b/users/wpcarro/scratch/facebook/second-largest-item-in-bst.py new file mode 100644 index 0000000000..2815dec9ee --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/shuffle.py b/users/wpcarro/scratch/facebook/shuffle.py new file mode 100644 index 0000000000..21a6a96c60 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/stack.py b/users/wpcarro/scratch/facebook/stack.py new file mode 100644 index 0000000000..2a843e2216 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/stacking-boxes.py b/users/wpcarro/scratch/facebook/stacking-boxes.py new file mode 100644 index 0000000000..7a3304bc51 --- /dev/null +++ b/users/wpcarro/scratch/facebook/stacking-boxes.py @@ -0,0 +1,50 @@ +from random import randint + +class Box(object): + def __init__(self, w, h, d): + self.width = w + self.depth = d + self.height = h + + def __repr__(self): + return "{}x{}x{}".format(self.width, self.depth, self.height) + + def lt(self, b): + return all([ + self.width < b.width, + self.height < b.height, + self.depth < b.depth, + ]) + + def gt(self, b): + return all([ + self.width > b.width, + self.height > b.height, + self.depth > b.depth, + ]) + +def random_box(): + return Box( + randint(1, 10), + randint(1, 10), + randint(1, 10), + ) + +xs = [random_box() for _ in range(5)] + +def highest_stack(xs, cache={}): + if not xs: + return 0 + heights = [] + for i in range(len(xs)): + x, rest = xs[i], xs[0:i] + xs[i+1:] + if cache and x in cache: + height = cache[x] + else: + height = x.height + highest_stack([b for b in rest if x.gt(b)], cache) + cache[x] = height + heights += [height] + return max(heights) + +print(xs) +print(highest_stack(xs)) diff --git a/users/wpcarro/scratch/facebook/stock-price.py b/users/wpcarro/scratch/facebook/stock-price.py new file mode 100644 index 0000000000..8e42f81523 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/todo.org b/users/wpcarro/scratch/facebook/todo.org new file mode 100644 index 0000000000..6ac99267db --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/top-scores.py b/users/wpcarro/scratch/facebook/top-scores.py new file mode 100644 index 0000000000..c8a10ae5f1 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/topo-sort.py b/users/wpcarro/scratch/facebook/topo-sort.py new file mode 100644 index 0000000000..874005a019 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/traversals.py b/users/wpcarro/scratch/facebook/traversals.py new file mode 100644 index 0000000000..e2565a3231 --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/utils.py b/users/wpcarro/scratch/facebook/utils.py new file mode 100644 index 0000000000..9a3e8a045e --- /dev/null +++ b/users/wpcarro/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/users/wpcarro/scratch/facebook/word-cloud.py b/users/wpcarro/scratch/facebook/word-cloud.py new file mode 100644 index 0000000000..88422e3631 --- /dev/null +++ b/users/wpcarro/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!") |