subtree(users/wpcarro): docking briefcase at '24f5a642' r/3226

git-subtree-dir: users/wpcarro
git-subtree-mainline: 464bbcb15c09813172c79820bcf526bb10cf4208
git-subtree-split: 24f5a642af3aa1627bbff977f0a101907a02c69f
Change-Id: I6105b3762b79126b3488359c95978cadb3efa789

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 000000000000..f79a9f22b38b
--- /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 000000000000..200d1613ddcb
--- /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 000000000000..a5c6e4e6ee81
--- /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 000000000000..782678fb822c
--- /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()