17. Problems on Hashing

 

Problems on Hashing

import java.util.HashMap;

import java.util.HashSet;

import java.util.Map;

import java.util.ArrayList;

class HashingProblems<T> {

    void majorityElement(T[] arr, int frequency) {

        HashMap<T, Integer> map = new HashMap<>();

        for (T ele : arr) {

            if (map.containsKey(ele))

                map.put(ele, map.get(ele) + 1);

            else

                map.put(ele, 1);

        }

        for (Map.Entry<T, Integer> ele : map.entrySet())

            if (ele.getValue() > frequency)

                System.out.print(ele.getKey() + " ");

    }

    void unionOfArrays(T arr1[], T arr2[]) {

        HashSet<T> set = new HashSet<>();

        for (T ele : arr1)

            set.add(ele);

        for (T ele : arr2)

            set.add(ele);

        System.out.println(set);

    }

    void intersectionOfArrays(T arr1[], T arr2[]) {

        HashSet<T> set = new HashSet<>();

        HashSet<T> ans = new HashSet<>();

        for (T ele : arr1)

            set.add(ele);

        for (T ele : arr2)

            if (set.contains(ele)) {

                ans.add(ele);

                set.remove(ele);

            }

        System.out.println(ans);

    }

    void itinerary(HashMap<String, String> map) {

        ArrayList<String> from = new ArrayList<>();

        for (Map.Entry<String, String> journey : map.entrySet())

            from.add(journey.getKey());

        for (Map.Entry<String, String> journey : map.entrySet())

            if (from.contains(journey.getValue()))

                from.remove(journey.getValue());

        String start = from.get(0);

        while (map.containsKey(start)) {

            System.out.print(start + " -> ");

            start = map.get(start);

        }

        System.out.println(start);

    }

    int subarray(int arr[], int targetSum) {

        HashMap<Integer, Integer> map = new HashMap<>();

        map.put(0, 1); // sum = 0 occurs 1 times in arr

        int ans = 0;

        int sum = 0;

        for (int num : arr) {

            sum += num;

            if (map.containsKey(sum - targetSum))

                ans += map.get(sum - targetSum);

            if (map.containsKey(sum))

                map.put(sum, map.get(sum) + 1);

            else

                map.put(sum, 1);

        }

        return ans;

    }

}