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

7 files changed, 179 insertions, 0 deletions

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 000000000000..bbd52fa9c64c
--- /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 000000000000..688c340b987b
--- /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 000000000000..523ecd959daf
--- /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 000000000000..877bb218fdf5
--- /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 000000000000..4629798cf711
--- /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 000000000000..ced3b336e0d9
--- /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 000000000000..bfa465f98d7f
--- /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")