

#Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. 
#Note: This is not a necessarily a binary search tree

def find(tree, node1, node2):
    
    
psudo:
    see if one of the node is a child of the other
    if not:
        go to the parent of one of the node, and see to the other side if there is another node
        
        
        
# nodes : value, leftptr, rightptr

#On an old cell phones, users typed on a numeric keyboard and the phone would provide a list of words that matched these numbers. Each digit mapped to a set of 0-4 letters.Implement an algorithm to return a list of matching words, given a sequence of digits. You are provided a list of valid words (provided in whatever data structure you'd like). The mapping is sent to you as a picture in facebook:

#input: 8733
#output: tree, used

t9letters = {null, null, {'a', 'b', 'c'}, {'d', 'e', 'f'}, {'g','h','i'}, {'j','k','l'}, {'m','n','o'}, }


print getvalidT9words("8733", setwordlist)
setwordlist = {"tree", "used", "prek""shak", "interview", "ok"}

# Problem 6.3 : For each of the following, A is an integer array of length n.
# (1.) Compute the maximum value of (A[j0] − A[i0]) + (A[j1] − A[i1]), subject to i 0 < j 0 < i 1 < j 1 .
# (2.) Compute the maximum value of Submission(k−1 t=0) (A[jt ] − A[it]), subject to i 0 < j 0 < i 1 < j 1 <···< i k−1 < j k−1 . Here k is a fixed input parameter.
# (3.) Repeat Problem (2.) when k can be chosen to be any value from 0 to n/2.


# Numbers are randomly generated and stored into an (expanding) array. How would you keep track of the median?


#
# find the missing number in an array
#

# inp = [1,2,3,4,5,6,7,8,9,
#          10,11,12,13,14,15,16,17,18,19,
#          20,21,22,23,24,25,26,27,28,29,
#          30,31,32,33,34,35,36,37,38,39,
#          40,41,42,43,44,45,46,47,48,49,
#          50,51,52,53,56,57,58,59,
#          60,61,62,63,64,65,66,67,68,69,
#          70,71,72,73,74,75,76,77,78,79,
#          80,81,82,83,84,85,86,87,88,89,
#          90,91,92,93,94,95,96,97,98,99,100]

# def findMissing(numArray, maxNum):
#   a = list(range(1,maxNum + 1))
  
#   return a - b

# print (findMissing(inp, 100))