Hash Tables Interview Questions & Tips for Senior Engineers

Hash Table Interview Questions & Tips

What is a Hash Table?

A hash table is a key-value data structure. Keys are typically able to be accessed in amortized constant time and values can be single items or more commonly a list of items.

Hashtables, Hashmaps, and Dictionaries. Oh My!

Most languages have built-in key-value pair data structures, but each language will have different names, terminology, and even different implementations associated with them. All languages provide efficient ways to store, retrieve, and manipulate data because they allow for near-instant access to the data associated with a specific key. While there is little consistency for what a key-value data structure is called between languages, for the sake of this article we will use the term "hash table" to encompass the following:

In Python, these structures are referred to as dictionaries (or "dicts"). In JavaScript, before ES6 these were represented as a general Object but after ES6 we now have a dedicated Map object. C++, on the other hand, includes both map and unordered_map in its Standard Template Library (STL), the latter being equivalent to a hash table. In Java, they are usually called Maps, represented by the Map interface which has several implementations including HashMap and TreeMap (but many more exist). Confusingly, Java has both a Hashtable and a HashMap. The main differences between them are that HashMap is multi-threaded and therefore not thread-safe and also allows for a null key & null values. The Hashtable implementation is thread safe and doesn't allow null keys or values.

Comparing Hash Tables, Arrays, and Sets

It's not uncommon for candidates to understand the differences between these three data structures yet fail to select the correct data structure in an interview context. Here is a brief comparison of these data structures and how they relate to one another. In general we should…

Arrays Hash Tables Sets
Access O(1) O(1) avg, O(n) worst-case O(1) avg, O(n) worst-case
Search O(n) O(1) avg, O(n) worst-case O(1) avg, O(n) worst-case
Insertion O(n) O(1) avg, O(n) worst-case O(1) avg, O(n) worst-case
Deletion O(n) O(1) avg, O(n) worst-case O(1) avg, O(n) worst-case
Key-Value Pairs No Yes No
Unique Elements No Keys are unique Yes
Additional Metadata No Yes Yes
Memory Usage Low High High

How Does a Hash Table Work?

Did you know that a hash table is actually just an array under the hood with some helper methods? It's true! Picture a super-organized parking lot (our array) and a hard-working valet (our hash function). You hand the valet your car keys, and he decides where to park your car. The valet has a unique system where he uses the key to choose a parking spot. That's exactly what a hash table does!

A good hashing function can make a big difference in how efficiently we can look up data. For example, what if two cars (keys) are assigned the same spot? That's a collision! In the programming world, we have some neat strategies to handle those.

With "separate chaining", the parking spot just grows a little garage (a linked list) and parks the cars (hash table "keys") one behind the other.

"Open addressing", on the other hand, is like the valet looking for the next available spot. If we are parking the cars right next to one another then that's "linear probing". If the valet starts hopping around in a specific pattern then it is quadratic probing or double hashing in the CS world.

Imagine our valet is having a bad day and just trying to park all the cars as close together in the same spot as possible, causing a traffic jam, or putting all the cars so far away it takes forever to get to them. This will result in a lot of collisions and will make a mess! That's like a poor hash function in coding. A good hash function, like a top-notch valet, parks the cars in a way that they're spread out evenly (avoiding traffic jams or "collisions") and are easy to retrieve when needed.

Now imagine that our parking lot is getting filled up. This is when "rehashing" comes in. It's like the valet suddenly puts in an order for a bigger parking lot, moves all the cars around to space them out more, reducing the chances of assigning two cars to the same spot.

Even though finding a parking spot (or an array index!) might sometimes take longer than expected, over many trips to the lot (or "amortized over time"), our valet (hash function) usually gets us there pretty quickly, averaging out to constant time.

Example Hash Table in Python

Here's a little python code as an example. The code supports a fixed size table of 10 elements and does not rehash when the table gets full and just continues to use separate chaining to avoid collisions (eventually degrading performance).

class HashTable:
    def __init__(self:
        # Restricts the initial size of our hash table
        self.size = 10
        # Create array with 10 empty lists in it (one for each index)
        self.table = [[] for _ in range(self.size)]

def hash_function(self, key):
        # This is a simple hash function that uses the modulo operator
        # In a real-world use case, we would use a more complex function
        return key % self.size

def insert(self, key, value):
        # Calculate index in array where this key/value pair should be stored
        hash_index = self.hash_function(key)
        # Variable to track if key already exists in the current bucket
        key_exists = False
        # Get bucket corresponding to the hashed index
        bucket = self.table[hash_index]

# Iterate bucket collisions and check if we've previously added the key
        for i, kv in enumerate(bucket):
            k, v = kv
            if key == k:
                key_exists = True
                break
        # Add key if it's new, append to existing bucket collisions list if not
        if key_exists:
            bucket[i] = ((key, value))
        else:
            bucket.append((key, value))

When to Use a Hash Table in an Interview?

When it comes to technical interviews, problems often revolve around manipulating and processing data. One of the most common ways to speed up an algorithm is to trade time for space. Phrased differently, we can increase the speed of many algorithms if we are willing to store some extra data in memory to avoid an expensive lookup operation later. This is the primary use for hash tables.

Hash tables tend to be used in conjunction with other techniques to solve a problem, rather than being a solution in themselves. Figuring out what to save as the key and value and then how to use that information once saved is more difficult than understanding the concept itself. Here are some well-known scenarios where these structures tend to be most useful:

Frequency Counts

It's a fairly common requirement in interview problems to count the frequency of something. We use the key to hold the unique element we are tracking (whether it is a letter, string, or even an entire object) and the value is used to hold the number of times we've seen it. This usually allows us to eliminate the need for a nested loop, thereby saving us time. Here are a few example problems showcasing this.

Pro Tip: Common Tools for Frequency Counts in Python

In Python, there are two common tools you can utilize in collections to save yourself time in an interview.

A Counter can count the frequency of elements occurring in a list (note the capitalization!)

from collections import Counter
words = "i love love love interviewing.io"
Counter(words.split()) # ({'i': 1, 'love': 3, 'interviewing.io': 1})

A defaultdict can initialize default values for you when adding a new key to your hash table (aka dictionary).

from collections import defaultdict
words = "i love love love interviewing.io"

# initialize every key with a default integer of 0
dictionary = defaultdict(int)
for word in words.split():
  dictionary[word] += 1
print(dictionary) # {'i': 1, 'love': 3, 'interviewing.io': 1}

Data Tracking and Organization

Sometimes it's easier to track data when it is logically grouped together. This tends to also increase the efficiency of your lookups of the data but is useful on its own even if you don't need that efficiency. This may be the most common way to use hash tables – in problems where we need to track the location of something like a character, index, or node.

Graph Representations

Similar to the above, but worth calling out on its own, hash tables can efficiently represent a graph by storing vertices as keys and their adjacency list as values. This allows quick access to each vertex's adjacent vertices, facilitating traversal and other operations. Additionally, extra information such as vertex weight can be stored in the value, enabling a wide range of graph algorithms.

Using a hash table for this purpose offers several benefits. The primary advantage is the O(1) average time complexity for lookups, insertions, and deletions that hash tables offer. This means that accessing a vertex's adjacency list, adding a new vertex, or deleting a vertex can be done very quickly, regardless of the size of the graph.

Example Hash Table Representing a Graph in Python

This is an example hash table in Python representing a simple undirected graph in the form of an adjacency list. The graph has four vertices (A, B, C, and D) and 5 edges ((A-B), (B-C), (C-D), (A-D), and (A-C)).

graph = {
    'A': ['B', 'C', 'D'],
    'B': ['A', 'C'],
    'C': ['A', 'B', 'D'],
    'D': ['A', 'C'],
}

"""
graph visualization
  A --- B
  | \   |
  |  \  |
  |   \ |
  D --- C
"""

Memoization (Top-Down Dynamic Programming)

Hash tables are a key part of top-down dynamic programming, commonly referred to as memoization. Dynamic programming is a technique used to solve complex problems by breaking them down into simpler sub-problems, solving each of those sub-problems just once, and storing their results for when the same sub-problem occurs again. This strategy of storing sub-problem solutions is known as memoization.

A hash table is a perfect data structure for implementing memoization due to its fast access times. It can store the results of sub-problems using problem parameters as keys. This is crucial for efficiency as it ensures that each sub-problem is computed only once, rather than repeatedly. When encountering a sub-problem, we first check the hash table to see if we've already calculated the result of this problem. If we find it, we use the stored result directly. If we don't find it, we solve the problem and store the result in the hash table. The key represents the current subproblem and the value represents the previously calculated subproblem's answer.

Common Mistakes in Interviews Featuring Hash Tables

Null keys in languages that don't support them

Picture this: you've got a huge, hungry dog (our hash table), and you're trying to feed it an invisible, scentless treat (a null key). That just won't work, right? The dog won't know what to do with it. That's pretty much what happens when you try to put a null key into a hash table in languages that don't support them.

Many languages' hash tables don't support null keys because their hash functions don't know how to handle 'nothing'. It's like trying to find a place in our car park for a car that doesn't exist. Things get messy, and you'll likely end up with an error, or worse, a program crash.

So, what's the big mistake here? Programmers sometimes forget to check for nulls or they assume that their hash table can handle null keys. It's like they're absent-mindedly trying to feed the dog that invisible treat, not realizing it won't work.

Trying to Hash Unhashable Objects

Another common mistake is trying to put a mutable object as the key for a hash table.

Python will throw a fit (a TypeError, to be exact) because lists are mutable, meaning they can be changed after they're created. Lists can't be hashed because who knows what they'll look like in the future?

In JavaScript, it's technically allowed to use an array as a key in an object, but it doesn't behave as you might expect. JavaScript will convert the array to a string to use as a key, and changes to the array after the fact won't affect the object.

Example of Unhashable Objects in Python

# Create a list
my_list = [1, 2, 3]

# Try to use it as a key in a dictionary (which is a hash table in Python)
my_dict = {my_list: 'value'}  # This will raise a TypeError!

# Above won't work, because what if we now did this…
my_list = [4, 5, 6]

# Python wouldn't recognize that it is the same list since it has
# entirely different values in it!

Avoiding Issues with Mutable Keys

In Python, one way is to use a tuple instead of a list if your data doesn't need to change. Tuples are immutable, meaning they can't be changed after they're created, so they're safe to hash:

# Create a tuple
my_tuple = (1, 2, 3)

# Use it as a key in a dictionary
my_dict = {my_tuple: 'value'}  # This is fine!

What to Say in Interviews to Show Mastery Over Hash Tables

Logically Walk Through Which Data Structure Should Be Used

It is the sign of a senior engineer to not jump to conclusions. Avoid suggesting a hash table just because you need a constant time lookup! You should think out loud and come to the conclusion on whether or not a Set or even an Array could do the job before deciding on a hash table.

Discuss Hash Table Implementation Details When Appropriate

To show mastery of hash tables, you should demonstrate knowledge of how they work under-the-hood and mention it organically. There is a balancing act here – we don't want to go off on unnecessary tangents, but providing extra details without taking extra time can give tremendously different impressions. Imagine three candidates that all talk tell the interviewer about how they are going to use a hash table.

Common Hash Table interview Questions