Interview Kickstart has enabled over 3500 engineers to uplevel.
HashMap is a very popular data structure used in the programming paradigm. Many programming problems in software engineering interviews can be tackled by the simple use of a HashMap.
In this article, we will cover:
A HashMap is used to store key-value pairs. There are various use cases of a HashMap, such as:
The HashMap class in Java is almost equivalent to HashTable, except for the fact that it’s unsynchronized and permits null values. Here’s what the internal workings of a HashMap looks like:
Let’s break it down:
1. We compute the hashcode for each of the keys being inserted.
2. Using the hashcode, we check in which bucket the key is to be stored.
3. Next, we check if there is a List of nodes present corresponding to the bucket.
4. If a List is present, we create a new Node and add it to the end of the List; otherwise, we create a new list.
5. Now, we check if any key present in the entries of the List matches the key.
6. If a match is found, override the value; else, add a new entry to the List.
The behavior of a HashMap can be thought of as a caching mechanism. In caching, we're not concerned with the order of the elements. We're just concerned about the speed at which we can read an element and gain access to the value using the element (if it's present in the cache). Both read and access are O(1) operations.
Some programming challenges involve ordering elements that are present in a HashMap. Ordering by key is easy, as Java supports TreeMap, where every key-value pair is inserted into the HashMap by the natural order of keys.
We can also define a custom comparator and assign it to the TreeMap constructor to define our custom ordering of elements. It gets tricky when we want to order the key-value pairs of the HashMap based on values. The rest of this article is dedicated to solving this problem.
We are provided a HashMap of key-value pairs, and we are required to sort this HashMap based on its values. For example, let’s say we are given a list of superheroes and their strengths.
Now, if we sort these values based on the strength of the superheroes, we get the following result:
If two superheroes have the same strength, we arrange them based on the alphabetical order of their names and hence the above output.
We can assume the number of superheroes is at max 106, and all superhero names are unique.
In the first solution, the key idea is to store each entry of the HashMap in a list and then sort the list and finally store the list elements in a LinkedHashMap. Here’s how it works:
Sorting_hashMap (HashMap<Key , Value> hashmap):
Step 1: Copy the elements of hashmap into an ArrayList
Step 2: Sort the list using any sorting algorithm of choice
Step 3: Copy the list items into a LinkedHashMap
Step 4: Return the LinkedHashMap
Step 5: Exit
Here’s what we’re doing:
First, we copy the key-value pairs present inside the HashMap into an ArrayList. We use ArrayList because it’s dynamic, and we do not need to specify the list size at the time of creation.
Next, we sort the list and pass a custom comparator to define our way of ordering the elements. (Read on for details on how a comparator works in Java).
Finally, we copy the elements from the sorted list into a LinkedHashMap. The advantage of LinkedHashMap is that elements can be accessed in their insertion order, and thus we return a map that will contain all key-value pairs sorted by value.
A comparator object is used for comparing two objects of a user-defined class.
Syntax: public int compare ( Object object1 , Object object2 )
The "compare” method returns three categories of values based on object comparison:
Whenever we insert an element into the list, the comparator function will compare the new object inserted against the elements and decide whether to swap its position, thus maintaining the desired sorted order.
For our use case, we simply need to compare the values of the keys. But what if the values of two different keys are the same? As per the example given in the problem statement, such a scenario can definitely arise.
We only need to tweak our compare method a bit, where we first check if two values are the same, and then, we compare them based on their keys; else, we compare them based on their values.
Now that our compare method is ready, let's look at the pseudocode.
Here, we create a TreeMap in Java with a custom comparator that compares all key-value pairs based on their values. Then, we simply add all key-value pairs into the TreeMap.
Sorting_HashMap (HashMap<Key , Value> hashmap):
Step 1: Create a TreeMap in java with a custom comparator.
Step 2: Comparator should compare based on values and then based on the keys.
Step 3: Put all key-value pairs from the hashmap into the treemap.
Step 4: return the treemap.
Step 5: Exit
In solution 2, we first create a TreeMap with a custom comparator.
Next, we simply insert all the key-value pairs, and our comparator takes care of inserting the values inside TreeMap based on values in ascending order.
Finally, we return our TreeMap object.
Values before sorting :
Key : Thor value : 75
Key : CaptainAmerica value : 50
Key : Thanos value : 100
Key : IronMan value : 50
Values after sorting :
Key : CaptainAmerica value : 50
Key : IronMan value : 50
Key : Thor value : 75
Key : Thanos value : 100
The complexity for both solutions is the same:
Time complexity for Solution 1 is O(nlogn) because we sort the ArrayList that consists of n key-value pairs, and the presence of sorting algorithms makes the worst-case complexity O(nlogn). In addition, we store the elements in a LinkedHashMap — so the complexity becomes (nlogn + n), which is O(nlogn).
Time Complexity for Solution 2 is O(nlogn) because TreeMap is a Red-Black tree-based NavigableMap implementation. It’s known that Red-Black tree is a kind of self-balancing binary search tree, and so each insertion takes O(logn) time. Here, we have n key-value pairs, making the total complexity O(nlogn).
Space complexity is O(n) as we store the elements in a list of size n in both solutions.
Question 1: While sorting a HashMap using a LinkedHashMap, why is an ArrayList preferred over an array?
Answer: If you are sorting a HashMap using a LinkedHashMap, you can choose an array instead of an ArrayList. However, the drawback of using an array is that you need to know the array size beforehand. ArrayList is dynamic, and you need not specify the size upon ArrayList creation, making it the more preferred option.
Question 2: Are comparators frequently used in sorting based on different parameters?
Answer: In general, programming interview problems require you to sort 2-D arrays, maps, or lists based on different parameters, and in such situations defining a custom comparator can be very useful.
If you’re looking for guidance and help with getting started, sign up for our free webinar. As pioneers in the field of technical interview preparation, we have trained thousands of engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!
--------
Article contributed by Problem Setters Official
Attend our webinar on
"How to nail your next tech interview" and learn