diff options
Diffstat (limited to 'users/wpcarro/scratch/facebook/interview-cake')
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 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") |