Technical 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 getCount(List list) {
        // Initialize HashMap to store number counts
        HashMap 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 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

1. If the list is null: We avoid a NullPointerException by checking if the list is null before iterating.
2. 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 n is the number of elements.
  • Each HashMap operation (put and get) takes O(1) on average, making the overall time complexity O(n).

• 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 defaultValue if 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 getCount(List list) {
        // Initialize HashMap to store number counts
        HashMap 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 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

1. 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).
2. Inserting and incrementing: The code directly adds 1 to the default value, eliminating the need for if-else logic.

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

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

• Java Fundamentals

• Array Interview Essentials

• Java Memory Essentials

Happy Coding!