Map - DS Algo related questions

The Map data structure in Java is widely used in various scenarios and is a common topic in technical interviews. Here are some examples of how Map can be used in different programs or interview questions, along with Java and Java 8 code snippets.

1. Counting Frequency of Elements

Problem: Given an array of integers, count the frequency of each element.

Example:

import java.util.HashMap;
import java.util.Map;

public class FrequencyCounter {
    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4};
        Map<Integer, Integer> frequencyMap = new HashMap<>();

        for (int num : arr) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        System.out.println(frequencyMap);
    }
}

Output:

{1=1, 2=2, 3=3, 4=4}

2. Finding First Non-Repeated Character in a String

Problem: Given a string, find the first non-repeated character.

Example:

import java.util.LinkedHashMap;
import java.util.Map;

public class FirstNonRepeatedCharacter {
    public static void main(String[] args) {
        String str = "swiss";
        Map<Character, Integer> charCountMap = new LinkedHashMap<>();

        for (char ch : str.toCharArray()) {
            charCountMap.put(ch, charCountMap.getOrDefault(ch, 0) + 1);
        }

        for (Map.Entry<Character, Integer> entry : charCountMap.entrySet()) {
            if (entry.getValue() == 1) {
                System.out.println("First non-repeated character is: " + entry.getKey());
                break;
            }
        }
    }
}

Output:

First non-repeated character is: w

3. Grouping Elements by Key

Problem: Given a list of strings, group them by their lengths.

Java 8 Example:

import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class GroupByLength {
    public static void main(String[] args) {
        List<String> words = Arrays.asList("apple", "banana", "cherry", "date", "egg", "fig", "grape");

        Map<Integer, List<String>> groupedByLength = words.stream()
                .collect(Collectors.groupingBy(String::length));

        System.out.println(groupedByLength);
    }
}

Output:

{3=[egg, fig], 4=[date], 5=[apple, grape], 6=[banana, cherry]}

4. Finding Common Elements Between Two Arrays

Problem: Given two arrays, find the common elements using Map.

Example:

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class CommonElements {
    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 4, 5};
        int[] arr2 = {4, 5, 6, 7, 8};

        Map<Integer, Boolean> map = new HashMap<>();
        for (int num : arr1) {
            map.put(num, true);
        }

        Set<Integer> commonElements = new HashSet<>();
        for (int num : arr2) {
            if (map.containsKey(num)) {
                commonElements.add(num);
            }
        }

        System.out.println("Common elements: " + commonElements);
    }
}

Output:

Common elements: [4, 5]

5. Anagram Grouping

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

Java 8 Example:

import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class AnagramGrouping {
    public static void main(String[] args) {
        List<String> words = Arrays.asList("listen", "silent", "enlist", "google", "gooegl");

        Map<String, List<String>> groupedAnagrams = words.stream()
                .collect(Collectors.groupingBy(word -> {
                    char[] chars = word.toCharArray();
                    Arrays.sort(chars);
                    return new String(chars);
                }));

        System.out.println(groupedAnagrams);
    }
}

Output:

{eilnst=[listen, silent, enlist], eggloo=[google, gooegl]}

6. Employee Department Grouping

Problem: Given a list of employees with their departments, group employees by department.

Java 8 Example:

import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

class Employee {
    String name;
    String department;

    Employee(String name, String department) {
        this.name = name;
        this.department = department;
    }

    public String getDepartment() {
        return department;
    }

    public String getName() {
        return name;
    }

    @Override
    public String toString() {
        return name;
    }
}

public class EmployeeGrouping {
    public static void main(String[] args) {
        List<Employee> employees = Arrays.asList(
                new Employee("John", "HR"),
                new Employee("Jane", "IT"),
                new Employee("Jack", "Finance"),
                new Employee("Jill", "HR"),
                new Employee("Joe", "IT")
        );

        Map<String, List<Employee>> employeesByDepartment = employees.stream()
                .collect(Collectors.groupingBy(Employee::getDepartment));

        System.out.println(employeesByDepartment);
    }
}

Output:

{HR=[John, Jill], IT=[Jane, Joe], Finance=[Jack]}

These examples cover a range of interview questions where the Map data structure is useful.