Arshi SaxenaTechnical interviews often feature questions that test your understanding of collections, especially HashMaps. One common challenge involves counting the occurrences of elements within a list. This question helps interviewers assess your ability to handle data aggregation efficiently and avoid pitfalls like NullPointerException.
If you’re new to HashMaps, you may want to check out my Cracking the Basics of HashMap: Key Concepts for Java Developers for foundational knowledge before diving into this post.
In this post, we’ll:
- Explore the problem statement in detail.
- Solve it with two approaches: a traditional if-else solution and the
getOrDefault()method. - Discuss the time and space complexity of both implementations.
- A comparison of both solutions, including when to use each.
Problem Statement
You are given a list of integers, and your task is to return each unique number along with the count of its occurrences in the list. This is a typical problem that tests your understanding of the HashMap data structure and your ability to implement it efficiently.
Here’s an example:
Input:
[1, 2, 3, 5, 2, 1]
Output:
{1=2, 2=2, 3=1, 5=1}
If the input list is null or empty, the result should return an empty HashMap.
Solution 1: Traditional Approach Using if-else
In this solution, we manually check if the HashMap already contains the number as a key. If it does, we increment the value; if it doesn’t, we insert the key with a value of 1.
Code
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
public class CountNumbers {
private HashMap<Integer, Integer> getCount(List<Integer> list) {
// Initialize HashMap to store number counts
HashMap<Integer, Integer> map = new HashMap<>();
// To avoid NullPointerException in case of a null list
if (list != null) {
// Iterate through each number in the list
for (int num : list) {
// If first occurrence, add number with count 1
if (!map.containsKey(num)) {
map.put(num, 1);
} else { // If the number already exists, increment its count by 1
map.put(num, map.get(num) + 1);
}
}
}
return map;
}
public static void main(String[] args) {
// Using ArrayList Parameterized Constructor with Collection as argument
List<Integer> numbers = new ArrayList<>(Arrays.asList(1, 2, 3, 5, 2, 1));
CountNumbers nums = new CountNumbers();
System.out.println(nums.getCount(null)); // Result -> {}
System.out.println(nums.getCount(numbers)); // Result -> {1=2, 2=2, 3=1, 5=1}
}
}
Explanation
-
If the list is null: We avoid a
NullPointerExceptionby checking if the list is null before iterating. - Iterating over the list: For each number, if it already exists in the HashMap, we increment its value. Otherwise, we insert it with a value of 1.
Time and Space Complexity
-
Time Complexity:
-
O(n) – We traverse the list once, where
nis the number of elements. - Each HashMap operation (
putandget) takes O(1) on average, making the overall time complexity O(n).
-
O(n) – We traverse the list once, where
Space Complexity: O(n) – In the worst case, all numbers are unique and stored in the HashMap.
Solution 2: Optimized Approach Using getOrDefault() Method
The Java HashMap class provides a cleaner and more concise way to handle this problem with the getOrDefault() method. It eliminates the need for if-else logic by returning a default value if the key is not found in the map.
Method Definition
V getOrDefault(Object key, V defaultValue)
-
Parameters:
-
key: The key whose associated value is to be returned. -
defaultValue: The value to return if the map contains no mapping for the key.
-
Returns: The value to which the specified key is mapped, or
defaultValueif the map contains no mapping for the key.
For more information, you can check the official Javadoc for HashMap.
Code
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
public class CountNumbers {
private HashMap<Integer, Integer> getCount(List<Integer> list) {
// Initialize HashMap to store number counts
HashMap<Integer, Integer> map = new HashMap<>();
// To avoid NullPointerException in case of a null list
if (list != null) {
// Iterate through each number in the list
for (int num : list) {
// Cleaner solution using getOrDefault()
map.put(num, map.getOrDefault(num, 0) + 1);
}
}
return map;
}
public static void main(String[] args) {
// Using ArrayList Parameterized Constructor with Collection as argument
List<Integer> numbers = new ArrayList<>(Arrays.asList(1, 2, 3, 5, 2, 1));
CountNumbers nums = new CountNumbers();
System.out.println(nums.getCount(null)); // Result -> {}
System.out.println(nums.getCount(numbers)); // Result -> {1=2, 2=2, 3=1, 5=1}
}
}
Explanation
-
Using
getOrDefault(): This method returns the value for the key if it exists. If not, it returns the default value provided (in this case, 0). -
Inserting and incrementing: The code directly adds 1 to the default value, eliminating the need for
if-elselogic.
Advantages of getOrDefault()
-
Cleaner code: Reduces boilerplate by removing the need for
if-else. - Same complexity: O(n) for both time and space.
Comparison of Both Approaches
| Aspect | Traditional Approach | Using getOrDefault() |
|---|---|---|
| Code Readability | Slightly verbose with if-else logic |
Cleaner and more concise |
| Performance | Same (O(n)) | Same (O(n)) |
| Use Case | Works for all Java versions | Requires Java 8 or higher |
Conclusion
Both solutions will yield the same result, but using getOrDefault() makes the code more concise and readable. This question is a common interview favorite because it evaluates your understanding of HashMaps, iteration, and handling null values. It’s also closely related to problems involving frequency counting and data aggregation.
If you found this post helpful, be sure to check out other posts in the Collections Framework Essentials series as well!
Related Posts
Happy Coding!
