A software engineer on twitter posted his experience at the US airport immigration, he was literally given an A4 paper and a pen to do this. As a CS major, Lord knows I’ll cast if I was confronted with this, but can you imagine travelling 23hrs only to get stomped by Google Interview questions by immigration officers.
Welcome to Hell.
I don’t know what a binary search tree is (FML), but what I want to know is if they are making singers sing too.
What is a binary search tree though?
Here is the Wikipedia definition - https://en.wikipedia.org/wiki/Binary_search_tree
You need to tell them you were also asked to give Wikipedia definitions. 
I remember filling occupation in the forms for a passport. I wonder if this question is asked if your stated occupation differs from what you say?
Confusion comes in different shapes and sizes!
If I remember correctly the easiest method to remember is to do an inorder traversal of the BST into a list, and then recursively reconstruct a subtree rooted by the midpoint of each half of the list.
A BST can be converted easily to a sorted list using inorder traversal. I guess it runs in O(N) time and O(N) memory complexity because we have to maintain a N-length list as temporary storage.
class Node(object):
def __init__(self, data):
self.right = None
self.left = None
self.data = data
def balanceBST(bstRoot):
blist = bstToList(bstRoot)
return reconstruct(blist)
def reconstruct(blist):
return subreconstruct(blist, 0, len(blist) - 1)
def subreconstruct(blist, start, end):
if start > end:
return None
mid = (start + end) // 2
root = Node(blist[mid])
root.left = subreconstruct(blist, start, mid - 1):
root.right = subreconstruct(blist, mid + 1, end):
return root
def bstToList(root):
blist = []
inorder_traverse(root, blist)
return blist
def inorder_traverse(node, blist):
if not node:
return
inorder_traverse(node.left, blist)
blist.append(node.data)
inorder_traverse(node.right, blist)
I wrote this on the fly so I guess there will be bugs here and there but I guess if you can remember the basic idea you can always rewrite and clean bugs to your interviewer or immigration guy’s satisfaction.
If the guy starts talking about Red-Black trees or AVL trees, I then give up.
Trees are my comfort zone, if you wake me up from sleep and ask me a tree question I should be able to give a manageable answer.
My final question in such an interview (6 hours) was to determine if a Generic Tree is a BST, lol, I finished the question with the best answer in less than half of the time, then had time to gist with the guy as dude didn’t have any more questions for me.
If you throw me a Graph question though, you will totally throw me off balance before (if ever) I can get myself together to answer you. Everybody has their forte I guess.
When I participated in ACM/Nigeria Universities Programming Contests back then, I came up with solutions on the spot for problems I encountered. It took me longer to answer those questions because I didn’t know those algorithms off the top of my head. Bosses like @Obaro_Ogodo finished those questions fast. You know why.
I always told myself i didn’t need that shit to build printivo.com or any other project i’ve worked on in the past. But recently, I had to go through some of these algorithms again and I have come to realize that they are so basic any programmer should understand them. Every programmer should understand the Big O notation and be able to judge the complexities of whatever they write. It shows you know what you are doing and it makes you stand out from someone that stumbles on the field.
You might never have to sort an actual binary tree or use Djikstra algorithm but the lessons influence how you write code one way or the other. Bosses @zaga & @mayojava can probably tell you more.
Yes, we call this the ‘segmentation method’ in Virtual Binary Deforestation. Quite nifty, I must say.
I mean, just look at this.