diff options
Diffstat (limited to 'users/wpcarro/scratch/facebook/hard')
4 files changed, 172 insertions, 0 deletions
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() |