Cracking the coding interview in python – 4.7 yesterday’s interview question

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.

Advertisements
This entry was posted in Cracking the coding interview - a python experience. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s