Interview Question

Software Development Engineer Intern 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.

Interview Answer

1 Answer


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 23-Mar-2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.