View All num of num See all Photos Amazon.com www.amazon.com Engaged Employer Overview Reviews Salaries Interviews Jobs Photos Benefits 5.3k Reviews 12k Salaries 6.4k Interviews 7.6k Jobs Follow Add Interview Follow Add Interview Interview Question Software Development Engineer Intern Interview Las Vegas, NV Amazon.com 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. Tags: See more , See less 8 Answer Add Tags 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 Interviews > Software Development Engineer Intern > Amazon.com Add Answers or Comments To comment on this, Sign In or Sign Up.