VoltInsider

The Hash Table Interview Question

January 3rd, 2010

A fairly common job interview question for technical positions at companies like Microsoft and Google is to design and code a hash table. This is a standard homework problem in almost any data structures and algorithms class that computer science majors take and so gives the interviewer an idea of the candidate’s educational background as well as an idea of the candidate’s coding ability. A reasonable approach to such a problem is to first qualify the question o make sure that you understand exactly what is being asked and also to demonstrate to the interviewer that you understand the importance of clarifying any problem. Next it would be a good idea to draw your design on the inevitable whiteboard. The standard design consists of an array of pointers, where each array cell is a bucket, and the size of the array is a prime number whose magnitude depends on how many items are expected to be in the hash table (so that there is a balance between space used and number of collisions). Next, the typical hash function for such a design is a numeric hash of the item key modulo the table size. This assumes a uniform distribution of item keys. At this point if the interviewer asks you to continue, you could start coding the table (presumably using an OOP design), demonstrating your ability to perform pointer manipulation. You need to specify what to do in case of a collision: insert the new item at the beginning or end of the bucket list, or insert the new item in a way hat keeps the items sorted. In reality, actually designing and coding a hash table is rare, but the problem exposes a lot about a candidate’s ability to design and code.

Entry Filed under: Interviewing