Data Structures & Algorithms | Top Java HashMap Coding Questions for MAANG Companies

When preparing for coding interviews, especially with top companies like MAANG (Meta, Apple, Amazon, Netflix, Google), it's essential to have a strong grasp of common data structures and algorithms, including HashMap. Below are some common HashMap-related coding problems you might encounter, along with a brief explanation and Java solutions.

1. Two Sum (Using HashMap)

Problem: Given an array of integers and a target sum, find two numbers such that they add up to the target.

Solution using HashMap:

import java.util.HashMap;

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No solution found");
    }
}

2. Intersection of Two Arrays

Problem: Given two arrays, find the intersection of the two arrays. The intersection should return the common elements without duplicates.

Solution using HashMap:

import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;

public class IntersectionOfArrays {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        List<Integer> result = new ArrayList<>();
        
        // Add all elements from nums1 to the HashMap
        for (int num : nums1) {
            map.put(num, 1);
        }
        
        // Check if any element of nums2 is in nums1
        for (int num : nums2) {
            if (map.containsKey(num)) {
                result.add(num);
                map.remove(num); // Remove to avoid duplicates
            }
        }
        
        // Convert the result list to an array
        return result.stream().mapToInt(i -> i).toArray();
    }
}

3. Group Anagrams

Problem: Given an array of strings, group anagrams together.

Solution using HashMap:

import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

public class GroupAnagrams {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String sortedStr = new String(chars);
            map.putIfAbsent(sortedStr, new ArrayList<>());
            map.get(sortedStr).add(str);
        }
        
        return new ArrayList<>(map.values());
    }
}

4. Longest Substring Without Repeating Characters

Problem: Given a string, find the length of the longest substring without repeating characters.

Solution using HashMap:

import java.util.HashMap;

public class LongestSubstring {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int left = 0, maxLength = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char currentChar = s.charAt(right);
            if (map.containsKey(currentChar)) {
                left = Math.max(left, map.get(currentChar) + 1);
            }
            map.put(currentChar, right);
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

5. Find Duplicate Elements in Array

Problem: Given an array, return all the elements that appear more than once in the array.

Solution using HashMap:

import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

public class FindDuplicates {
    public List<Integer> findDuplicates(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        List<Integer> result = new ArrayList<>();
        
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        
        for (int key : map.keySet()) {
            if (map.get(key) > 1) {
                result.add(key);
            }
        }
        
        return result;
    }
}

6. First Unique Character in a String

Problem: Given a string, find the first non-repeating character in it. If it doesn't exist, return -1.

Solution using HashMap:

import java.util.HashMap;

public class FirstUniqueCharacter {
    public int firstUniqChar(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        
        // Count the frequency of each character
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }
        
        // Find the first unique character
        for (int i = 0; i < s.length(); i++) {
            if (map.get(s.charAt(i)) == 1) {
                return i;
            }
        }
        
        return -1;
    }
}

---

Tips for HashMap-related Problems:

• Complexity: The time complexity for most operations in a HashMap is O(1), making it very efficient for tasks like lookups, insertions, and deletions.
• Collision handling: Java’s HashMap uses chaining to handle collisions, so it’s crucial to understand how HashMap internally handles key-value pairs.
• Edge cases: Make sure to handle edge cases like empty arrays, null values, or large input sizes.

These are some classic problems you might encounter during interviews. Familiarizing yourself with these patterns and practicing them will help you perform well in MAANG company coding interviews.