VoltInsider

The Heap Interview Question

December 14th, 2009

Overall, based on my experience observing hundreds of job interviews for technical positions (developer, tester, program manager, etc.) at companies like Microsoft and Google, I’d guess that the most common category of interview questions are those that involve data structures and algorithms. An example of such a question might run along the lines of, “How would you find the 10 largest values from a randomly ordered set of 1,000,000 values?” There are dozens of ways to answer this question but one approach is to use a heapsort algorithm to sort all the values and then extract the 10 largest values. The heapsort algorithm uses a data structure called a heap which is like a tree except that for every parent node in the heap, all child nodes are less than or equal to the parent. A heap is almost synonymous with a priority queue. The heapsort algorithm has O(n) of O(n*log n). It should be obvious that you’d only know this answer if you understand what a heap data structure is and how the heapsort algorithm works. One of the best known authors on data structures and algorithms is Robert Sedgewick, and you’ll find one of his books on the bookshelf of many professional software engineers.

Entry Filed under: Interviewing