# Written by Kash Nouroozi in June 2019
def order(node, fn):
if node is None:
return
# in: LNR
# post: LRN
# pre: NLR
order(node.left, fn)
if fn(node) is True: # return early if predicate returns True
return node
order(node.right, fn)
Traversal
Search
# Written by Kash Nouroozi in June 2019
from collections import deque
def search(node, fn):
plan = deque()
plan.append(node)
visited = {}
def visit(node):
if node not in visited:
plan.append(node)
visited.add(node)
return fn(node)
while plan:
node = plan.pop() # bfs popleft()
if visit(node):
return node
Dynamic Programming
# Written by Kash Nouroozi for an interview with Rippling HR in June 2019
def ternary_string_possibilities(n):
"""
ternary string is composed of a's, b's, and c's
string can have at most 1 b
string can have no more than 2 consecutive a's
given a length n, calculate number of possible strings of length n
"""
memo = {}
def total_starting_from(state):
if state in memo:
return memo[state]
running_total = 0
has_b, trailing_a_count, size = state
if size == n:
return 1
if not has_b:
running_total += total_starting_from((True, 0, size+1))
if trailing_a_count != 2:
running_total += total_starting_from((has_b, trailing_a_count+1, size+1))
running_total += total_starting_from((has_b, 0, size+1))
memo[state] = running_total
return running_total
return total_starting_from((False, 0, 0))