I just finished one of the Google FooBar Challenges.My Python is super rusty. I did the challenge in Haskell first and then attempted to covert the code. I am guessing that led to some bad Python Practices.
Oh no! Commander Lambda's latest experiment to improve the efficiency of her LAMBCHOP doomsday device has backfired spectacularly. She had been improving the structure of the ion flux converter tree, but something went terribly wrong and the flux chains exploded. Some of the ion flux converters survived the explosion intact, but others had their position labels blasted off. She's having her henchmen rebuild the ion flux converter tree by hand, but you think you can do it much more quickly - quickly enough, perhaps, to earn a promotion!
Flux chains require perfect binary trees, so Lambda's design arranged the ion flux converters to form one. To label them, she performed a post-order traversal of the tree of converters and labeled each converter with the order of that converter in the traversal, starting at 1. For example, a tree of 7 converters would look like the following:
7 / \ 3 6 / \ / \ 1 2 4 5
Write a function answer(h, q) - where h is the height of the perfect tree of converters and q is a list of positive integers representing different flux converters - which returns a list of integers p where each element in p is the label of the converter that sits on top of the respective converter in q, or -1 if there is no such converter. For example, answer(3, [1, 4, 7]) would return the converters above the converters at indexes 1, 4, and 7 in a perfect binary tree of height 3, which is [3, 6, -1].
The domain of the integer h is 1 <= h <= 30, where h = 1 represents a perfect binary tree containing only the root, h = 2 represents a perfect binary tree with the root and two leaf nodes, h = 3 represents a perfect binary tree with the root, two internal nodes and four leaf nodes (like the example above), and so forth. The lists q and p contain at least one but no more than 10000 distinct integers, all of which will be between 1 and 2^h-1, inclusive.
How could I make my solution more memory efficient?
def splitInHalf(aList): full = len(aList) half = full/2 return aList[0:half], aList[half:full] class Tree(object): def __init__(self): self.left = None self.right = None self.data = None def __str__(self): return ("Data = " + str(self.data) + "Left = " + str(self.left) + "Right = " + str(self.right) ) def makeTree(h): limit = (2**h)-1 fluxConverters = list(range(limit,0,-1)) result = generate_tree(list(fluxConverters)) return result def generate_tree(listInt): if not listInt: return None elif (len(listInt) == 1): rTreeOne = Tree() rTreeOne.data = listInt return rTreeOne else: rTreeList = Tree() rTreeList.data = listInt.pop(0) half1, half2 = splitInHalf(list(listInt)) rTreeList.left = generate_tree(half1) rTreeList.right = generate_tree(half2) return rTreeList def searchTree(tree,search): if tree == None: return -1 else: if (nextHaz(tree.left,search) | nextHaz(tree.right,search)): return tree.data else: left = searchTree(tree.left,search) right = searchTree(tree.right,search) return mergeResults(left,right) def mergeResults(x,y): if(x!=-1): return x else: return y def nextHaz(tree, search): if(tree != None): return tree.data == search else: return False def answer(h,q): tree = makeTree(h) partialSearch = lambda x : searchTree(tree,x) result = map(partialSearch,q) return result answer(3,[7, 3, 5, 1]) testOneResult = [-1, 7, 6, 3] answer(5,[19, 14, 28]) testTwoResult = [21, 15, 29]