3.4 of 5 2,817 reviews Seattle, WA 5000+ Employees Software Development Engineer Intern Interview Question

I interviewed in Las Vegas, NV and was asked:
"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."
Add Tags [?]
Answer Flag Question

Part of a Software Development Engineer Intern Interview Review - one of 4,156 Interview Reviews

Answers & Comments

of 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 Flag Response

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

Tags are like keywords, helping to categorise interview questions that have something in common.

Glassdoor is your free inside look at interview questions and advice. All interview reviews are posted anonymously by employees and interview candidates.