Tutorials

/

Interviewing

/

Maps

Previous:

Arrays and Strings

Next:

Sets

Maps

Like I mentioned in the arrays and strings tutorial, many interview questions follow a similar pattern where you take some input, process it, and then return some output.

How you process the input depends on the problem. I’ve shown you a couple techniques including using a sliding window, or two pointers to iterate through an array.

Those techniques are great for iterating over the input, but you often need supplemental data structures to help you process the data.

This tutorial talks about using Map data structures to help process data.

Maps

Like the name suggests, Map data structures let you map keys to values, which means you can store items based on a lookup value.

This is handy, because it means you no longer have to search through an entire array to find a particular value. You can put it in a Map, and then look it up based on the key later.

Here’s an example:

Map<String, String> quotes = new HashMap<>();
quotes.put("Ada Lovelace", "That brain of mine is something more than mortal; as time will show.");
quotes.put("Grace Hopper", "I've always been more interested in the future than in the past.");
quotes.put("Alan Turing", "Machines take me by surprise with great frequency.");

String message = quotes.get("Grace Hopper");
System.out.println(message);

This code creates a Map and then fills it with three key-value pairs of quotes. Then it looks up the quote said by Grace Hopper and prints it out.

Map data structures have a few handy functions:

• put(key, value) adds a new mapping from key to value
• get(key) returns the value with the specified key
• getOrDefault(key, default) is like get(key), except you can also specify a default if the key isn’t already in the map
• remove(key) removes the mapping with the specified key
• containsKey(key) and containsValue(value) returns whether the Map contains the specified key or value
• keySet(), values(), and entrySet() returns a Collection containing all of the map’s keys, values, or entries

Java offers a few implementations of the Map data structure:

• HashMap uses the hashCode() function to map keys to values. This is the most common implementation you’ll use.
• LinkedHashMap is very similar to HashMap, except it maintains the insertion order of its entries. In other words, if you call keySet() and then iterate over the keys, they’ll be in the same order as you added them to the map. (With HashMap, the order is basically random.)
• TreeMap maintains the natural ordering of its keys. In other words, if you call keySet() and then iterate over the keys, they’ll be in alphabetical order for strings and numerical order for numbers. You can also specify a custom Comparator to sort Object values.

Algorithmic Complexity

The power of Map data structures come from the fact that put(key, value), get(key), and containsKey() are very efficient. For HashMap and LinkedHashMap, they’re constant time O(1), and for TreeMap, they’re O(log n).

This makes Map data structures, especially HashMap, very handy for improving the efficiency of your algorithms.

Example: Two Sum

Let’s start with an example question that we’ve seen a couple times already: can you take an array of integers, and a target, and return indexes of two numbers that add up to that target?

You might approach this with a brute force algorithm that uses nested for loops:

public int[] twoSum(int[] numbers, int target) {
  // Iterate over every element
  for(int i = 0; i < numbers.length; i++){
    // Iterate over every other element
    for(int j = i + 1; j < numbers.length; j++){
      // If these elements sum to target, return their indexes
      if(numbers[i] + numbers[j] == target) {
        return new int[]{i, j};
      }
    }
  }

  // We didn't find any elements that sum to target
  return new int[0];
}

This code iterates over every possible pair of elements, checks whether each pair sums to the total, and returns the first match it finds. The nested for loop gives this an algorithmic complexity of O(n ^ 2).

Can you do better?

Think about how you do this in your head, or with a piece of paper and a pencil. How do you find two numbers that sum to 10 in this array?

{2, 5, 1, 3, 6, 7, 11}

You might start by scanning the array, and for each index, think about what other value you need to sum to 10. If the array does contain that value, you can return the index of your current number and the index of the other number. That might look like this:

• Look at 2. The array doesn’t contain an 8, so keep looking.
• Look at 5. The array doesn’t contain another 5, so keep looking.
• Look at 1. The array doesn’t contain a 9, so keep looking.
• Look at 3. The array does include a 7, so return those indexes.

Note: In this flavor of the problem, you can’t use the same index twice. That makes it a little trickier! Instead of looking ahead in the array for a match, you might look at what you’ve seen so far. So the algorithm changes a little bit:

• Look at 2. I haven’t seen an 8 yet, so keep looking.
• Look at 5. I haven’t seen another 5 yet, so keep looking.
• Look at 1. I haven’t seen a 9 yet, so keep looking.
• Look at 3. I haven’t seen a 7 yet, so keep looking.
• Look at 6. I haven’t seen a 4 yet, so keep looking.
• Look at 7. I have seen a 3 already, so return those indexes.

Beware Hidden Complexity

To implement that algorithm, you need a way to track which elements you’ve seen so far, along with their indexes.

You might use an ArrayList:

public int[] twoSum(int[] numbers, int target) {
  // Maintain an ArrayList version of the array
  List<Integer> numbersList = new ArrayList<>();

  // Iterate over every element
  for (int i = 0; i < numbers.length; i++) {
    int thisNumber = numbers[i];
    // Which other number would we need to sum to target?
    int otherNumber = target - thisNumber;

    // If the ArrayList contains the other number, return the indexes
    if (numbersList.contains(otherNumber)) {
        return new int[]{i, numbersList.indexOf(otherNumber)};
    }

    // Add the current number to the ArrayList and keep searching
    numbersList.add(numbers[i]);
  }

  // We didn't find any elements that sum to target
  return new int[0];
}

At first glance, this looks like an improvement over the brute force solution. It’s only a single for loop, so that’s linear O(n) algorithmic complexity, right?

However, the code relies on the ArrayList#contains() and ArrayList#indexOf() functions, both of which are O(n). And because the code calls these function inside a for loop, that means the algorithmic complexity is still O(n ^ 2).

HashMap to the Rescue

Improving the efficiency of your solution often comes down to choosing a data structure that has properties that help you get rid of the inefficient parts of your solution.

You need an efficient way to find the index of a number, so you can create a Map whose keys are numbers, and values are indexes!

public int[] twoSum(int[] numbers, int target) {
  // Maintain an Map from numbers to indexes
  Map<Integer, Integer> numberIndexes = new HashMap<>();

  // Iterate over every element
  for (int i = 0; i < numbers.length; i++) {
      int thisNumber = numbers[i];
      // Which other number would we need to sum to target?
      int otherNumber = target - thisNumber;

      // If the Map contains the other number, return the indexes
      if (numberIndexes.containsKey(otherNumber)) {
          return new int[]{i, numberIndexes.get(otherNumber)};
      }

      // Add the current number to the Map and keep searching
      numberIndexes.put(numbers[i], i);
  }

  // We didn't find any elements that sum to target
  return new int[0];
}

This might feel a little backwards, because with an array you’re essentially using indexes as keys. But by mapping the numbers to their indexes, it becomes very efficient to find the index of a particular number!

Map Count

A common technique with Map data structures is to maintain a count of different values.

For example, let’s say you wanted to write a function that took an array of strings and returned whichever string occurred the most often in that array.

You could do that with a brute force nested for loop, but the more efficient approach would be to use a Map from words to counts:

String mostCommonWord(String[] words) {
  Map<String, Integer> wordCounts = new HashMap<>();

  String mostCommonWord = null;
  int mostCommonWordCount = 0;

  for(String word : words){
    int wordCount = wordCounts.getOrDefault(word, 0);
    wordCount++;

    if(wordCount > mostCommonWordCount){
      mostCommonWord = word;
      mostCommonWordCount = wordCount;
    }

    wordCounts.put(word, wordCount);
  }

  return mostCommonWord;

}

This code uses a Map from words to their counts. It iterates over every word, and updates the count for that word by getting it from the map, incrementing it, and then putting it back in the map. It also uses a “best so far” technique to track the word with the highest count.

MultiMaps

Keep in mind that Map data structures can only contain one value for each key. If you add a second value with the same key, the old value is overwritten!

If you need to map multiple values to the same key, you can use a Map with keys that map to other data structures.

Here’s an example:

  String[] words = {"apple", "aardvark", "armadillo", "banana", "bear", "coconut", "cat"};

  Map<Character, List<String>> firstLetterWordMap = new HashMap<>();

  for(String word : words){
    Character firstLetter = word.charAt(0);

    if(!firstLetterWordMap.containsKey(firstLetter)){
      firstLetterWordMap.put(firstLetter, new ArrayList<String>());
    }

    firstLetterWordMap.get(firstLetter).add(word);
  }

  String secondWordStartingWithB = firstLetterWordMap.get('b').get(1);
  System.out.println(secondWordStartingWithB);

This code creates a HashMap where the keys are Character instances, and the values are ArrayList instances. It uses this HashMap to map multiple words to their starting letters.

You aren’t limited to ArrayList values- you can have Maps of Sets or Stacks or Queues or trees, or even other maps!

Sets

If you find yourself creating a Map with keys that map to boolean values, you might want a Set instead. More on that in the next tutorial!

More Info

Check out these links for more info:

• The Map Interface - official Java tutorials
• Map - JavaDocs

Practice Questions

• Two Sum
• Most Common Word
• Roman to Integer
• Integer to Roman
• Group Anagrams
• Valid Anagram
• Intersection of Two Arrays II
• Ransom Note
• First Unique Character in a String
• Find the Difference
• Word Pattern
• Top K Frequent Elements

Previous:

Arrays and Strings

Next:

Sets