Maps are one of the fundamental data structures in coding. Second to lists, they are common and used often in interview questions. Knowing how to use a map will help you avoid grief on many questions.

The solution to many algorithms lies in using a map correctly. The better you understand how to use a map, the easier it will be to apply. Any time you need to organize data or keep track of items, a map is one of the prime candidates. I’ll write some examples on this in later articles.

Terminology

The terminology around maps is mixed.

Python and C# prefer to use “dictionary”. There, the dictionary is a specific 1:1 map, where a key maps to a single value. PHP uses the term “associative arrays”. C++ uses "map”, and also has an “unordered_map”. In Java, "HashMap” is a common implementation of their “Map” interface.

The most abstract type is correctly called a “map”. But unless you’re interviewing for a language design position, leave the pedantry well alone. Never argue in an interview about the names. Learn the name used in your language, and familiarize yourself with the related terms.

Reference

Use this reference when preparing for an interview. Don’t assume you can do each item; take the time and code it. You’d be surprised at how simple things can turn out hard, or how a momentary thought blip can derail you. Honestly, I don’t think there’s any language where I could sit down and do all of this from memory. Going into an interview, I need to prepare and freshen my knowledge. Making these operations part of your natural coding vocabulary helps tremendously when in a pressure situation.

💭 Some languages implement maps as immutable data structures. However, the wording in this article assumes you’re using a mutable map. You’ll still need all these operations, but how your code structure will differ significantly. Focus on what is to be accomplished, rather than the specific wording.

Basic

Learn the most common way to perform these operations. Every language offers specialty syntax, but it’s best to stick to generic functionality in an interview. For evolving languages, be sure to top up your knowledge and watch out for changing idioms.

• Create a map: Use the most common, or generic one for the language. For a statically typed language you’ll need to specify the key and value type.
• Add an element with a key and a value: The basic way to get a key-value pair into the map.
• Check if an element exists by key: Checking existence is a prime reason we use a map.
• Get an element by key: This varies a lot between languages, and the surrounding code usually changes.
• Get the length of the map: The syntax is different in virtually all languages.
• Language idiom for “check and get item” from a map: This combination is common, and many languages have a specific way to combine the two steps.

Searching and Removal

Once elements are in the map, we need ways to get at them again.

• Replace an item by key: The syntax may differ between adding and replacing values.
• Find an item by value: Though not the main purpose of a map, it’s sometimes helpful to search for an item by a value, even if it is inefficient.
• Get by key or default value: A common idiom is to lookup a key, and return the value, but if the key is not present, return a default value instead. Most languages offer a specialized approach.
• Delete an element by key: This removes the value and its key. It’s not the same assigning a null value to the key. The key should not exist anymore.
• Clear the map: Remove all elements from the map.

Iteration

We may want to do something for all the elements in a map. This might use the language’s loop mechanism, or they may be special for-each functions on the map itself.

• Iterate all key and value pairs in the map: Each iteration should access both the key and the value.
• Iterate the keys of the map: You only want to access the keys which exist in the map, not the values.
• Iterate the values of the map: You only want to access the values which exist in the map, not the keys.
• Iterate in sorted order: If different, iterate the pairs, keys, and values in sorted order. This may require using a different sorted map type.

Full-map operations

We don’t always want to work with the full map, or may wish to isolate certain items.

• Produce a shallow clone of a map: The new map will contain the same instances.
• Map the values of a map to a new map: For a statically typed language, ensure you can map to a new type.
• Merge the contents of two maps: Know which values take priority.
• Filter items by key: Create a map, or view of it, where only elements matching certain keys are visible.
• Filter items by value: Create a map, or view of it, where only elements matching certain values are visible.

Mutli-maps

Multi-maps allow multiple values to be associated with the same key. These are 1:N maps. They are not as common as 1:1 maps, but they are useful for some algorithm questions.

• Create a multi-map: If your language doesn’t support one, learn how to use an array inside a normal map.
• Add an item by key: If the key already exists, you’ll end up with two values associated with the same key.
• Iterate the items matching a key: For one key, there may be multiple values.
• Remove an item matching a key: Remove a single item matching a key, but leaving additional values. This may remove the first, or last one, or require an additional match on the value.
• Replace all items matching a key: Ensure no more items with the key remain in the multi-map.

With different types

Work with multiple data types as keys and values. Don’t use only string keys! It’s important to be comfortable using a map in many ways.

Not all languages support all types as keys. It may limit you to only hashable types, or types with a natural order. Know what your language supports.

Study and write a cheat sheet

I’ve ordered these operations roughly from most to least common. Take some time and work through each of them. Simply knowing the advanced operations exist gives you flexibility when approaching an algorithm problem.

If you can’t remember them all, then create a cheat sheet for your language. It’s great for phone interviews. Some live interviews allow reference materials as well. This lets you avoid wasting time searching for the syntax online — which can be difficult for basic operations.