Yesterday night when I was about to leave work, go home and write another wonderful article for the millions of readers of my blog, 2 strange guys entered in my office and forced me pass a technical interview in order to decide whether I am qualified enough for my engineer position and having as unique goal to laugh at me if I fail.
One hour of questions: difference in complexity between a binary tree and a hash table? when would you use one or another ? Describe threadsafe. Do you need to use synchronized if you manipulate a threadsafe data structure ? what lock would you use? etc. etc. – some I did fine, some I did not, most of them I took too long.
After that they gave me this small exercise to code in Eclipse:
Given to binary trees, decide if the second one is included in the first one.
I first drew these on a sheet of paper and used it for reflection and test:
Then I took a whole half hour to write in java, and execute this lousy code, which I translated here in python:
class TreeNode: def __init__(self, data, left=None, right=None): self.data=data self.left=left self.right=right def contains(refNode, needle): if not refNode: return False if checkMatch(refNode, needle): return True return contains(refNode.left, needle) or contains (refNode.right, needle) def checkMatch(node_ref, node): if not node: return True if not node_ref: return False if not node_ref.data==node.data: return False return checkMatch(node_ref.left,node.left) and checkMatch(node_ref.right, node.right) def test(): n1=TreeNode(1) n2=TreeNode(2) n3=TreeNode(3) n4=TreeNode(4) n5=TreeNode(5) n6=TreeNode(6) n1.left=n2 n2.right=n3 n3.left=n4 n4.right=n6 n3.right=n5 t3 = TreeNode(3) t4 =TreeNode(4) t6=TreeNode(6) t7=TreeNode(7) t3.left=t4 t4.right=t6 assert(contains(n1,t3)) t3.right=t7 assert(not contains(n1,t3)) print 'test ok' if __name__=='__main__': test()
This morning I opened my Cracking the coding interview book and there it was, the exercise:
4.7 You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.