Interview Question

Anonymous Interview Las Vegas, NV

Asked general computer science topics (Describe a hash

  table, etc.) Didn't ask any behavioral questions, or anything about my résumé. Had two coding questions: 1) Given a Binary Search Tree, print out the median value. If there is an even number of nodes, print the average of the two middles. 2) Given a Genealogy Tree, print out the tree, row by row. For example: Dave / \ Michael Sarah / \ / \ Joe Alex Sam Tom Output would be: Dave Michael Sarah Joe Alex Sam Tom The questions weren't very hard, but I nearly ran out of time because I couldn't understand them. I spent a lot of time just trying to understand what they were asking for. They asked about the time and space complexities of everything I was doing. After I finished the second question, he gave me another problem with it. Asked if there would be a way where you get stuck in an infinite loop, and how to fix it. Also, they allowed me to choose which language I was more comfortable with. I used Java.
Answer

Interview Answer

1 Answer

0

1) Traverse through the tree, count the total number of nodes. Then, see if n is even or odd. If odd, use InOrder Traversal and go through n/2 + 1 times and return the data from that node. If even, use InOrder, grab the n/2 node data, then grab the n/2 + 1 node data, average the two, return the value.

2) I used breadth first, with a queue. You would get an infinite loop if a child pointed to its parent (You keep enqueuing and dequeuing the same two nodes). To fix this, use a Hash Table to see if you've been to the node before (Put the Node itself as the key).

Interview Candidate on Mar 23, 2013

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up