Interview Question: What is a hashmap?

Question

I was asked this in an interview: "Tell me everything you know about hashmaps."

I proceeded to do just that: it's a data structure with key-value pairs; a hash function is used to locate the element; how hash collisions can be resolved, etc.

After I was done, they asked: "OK, now explain everything you just said to a 5-year-old. You can't use technical terms, especially hashing and mapping."

I have to say it took me by surprise and I didn't give a good answer. How would you answer?

Solution 1

Lets take the big word book, or dictionary, and try to find the word zebra. We can easily guess that zebras will be near the end of the book, just like the letter "Z" is at the end of the alphabet. Now lets say that we can always find where the zebra is inside of the big word book. This is the way that we can quickly find zebras, or elephants, or any other type of thing we can think of in the big word book. Sometimes two words will be on the same page like apple and ant. We are sure which page we want to look at, but we aren't sure how close apple and ant are to each other until we get to the page. Sometimes apple and ant can be on the same page and sometimes they might not be, some big word books have bigger words.

That's how I would have done it.

Solution 2

Rules. Kids know rules. Kids know that certain items belong in certain places. A HashMap is like a set of rules that say, given an item (your shoes, your favorite book, or your clothes) that there is a specific place that they should go (the shoe rack, the bookshelf, or the closet).

So if you want to know where to look for your shoes, you know to look in the shoe rack.

But wait: what happens if the shoe rack is already full? There are a few options.

1) For each item, there's a list of places you can try. Try putting them next to the door. But wait, there's something there already: where else can we put them? Try the closet. If we need to find our shoes, we follow the same list until we find them. (probing sequences)

2) Buy a bigger house, with a bigger shoe rack. (dynamic resizing)

3) Stack the shoes on top of the rack, ignoring the fact that it makes it a real pain to find the right pair, because we have to go through all of the shoes in the pile to find them. (chaining).

Solution 3

Speaking as a parent, if I had to explain a hashmap to a 5-year-old, I'd say exactly what you said while waving around a chocolate cupcake.

Seriously, questions like this ought to mean "can you explain the concept in plain english", a good heuristic for how well you've internalized your understanding of it. Since it sounds like you get that, the question seems a bit silly.

Solution 4

The pieces of data the map holds can be looked up by some related information, much like how pages can be looked up by the words on them in the index of a book.

The key advantage to using a HashMap is that like an index in a book, it's much quicker to look up the page a word is on in the index than it would be to start searching page by page for that word.

(I'm giving you a serious answer because the interviewer might have been trying to see how well you can explain technical concepts to non-techies like project managers and customers. Maybe a hashmap directly isn't so useful, but it's probably as fair an indication as any of translation skills.)

Solution 5

You have a book of blank but numbered pages and a special decoder ring that generates a page number when a something is entered into it into it.

To assign a value:

You get a ID (key) and a message (value).

You put the ID into the special decoder ring and it spits out the page number.

Open your book to that page. If the ID is on the page, cross out the ID/message.

Now write the ID and message on the page. If there is already a one or more other IDs with messages just write the new one below it.

To retrieve a value:

You are given just an ID (key).

You put the ID into the special decoder ring and it spits out the page number.

Open your book to that page. If the ID is on the page, read the message (value) that follows it.

View more solutions