Advanced Practical Programs using the Java Collection Framework

Here are some advanced practical programs using the Java Collection Framework, along with explanations and their algorithms:

---

1. Find the Top K Frequent Elements

This program finds the K most frequent elements in an array using a HashMap and PriorityQueue.

import java.util.*;

public class TopKFrequentElements {
    public static List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();

        // Count frequencies
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // Min-heap based on frequency
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> frequencyMap.get(a) - frequencyMap.get(b));

        // Keep only the top K elements in the heap
        for (int key : frequencyMap.keySet()) {
            heap.add(key);
            if (heap.size() > k) {
                heap.poll();
            }
        }

        // Extract top K elements from the heap
        List<Integer> result = new ArrayList<>();
        while (!heap.isEmpty()) {
            result.add(heap.poll());
        }

        Collections.reverse(result); // Reverse to get the highest frequency first
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        System.out.println("Top " + k + " frequent elements: " + topKFrequent(nums, k));
    }
}

Algorithm:

1. Use a HashMap to count the frequency of each number.
2. Use a PriorityQueue (min-heap) to store the top k frequent elements.
3. Add elements to the heap and remove the least frequent when the size exceeds k.
4. Extract and reverse the heap for the final result.

---

2. Group Anagrams

This program groups words that are anagrams using a HashMap.

import java.util.*;

public class GroupAnagrams {
    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> anagramMap = new HashMap<>();

        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String key = new String(charArray);

            anagramMap.putIfAbsent(key, new ArrayList<>());
            anagramMap.get(key).add(str);
        }

        return new ArrayList<>(anagramMap.values());
    }

    public static void main(String[] args) {
        String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println("Grouped Anagrams: " + groupAnagrams(words));
    }
}

Algorithm:

1. For each word, sort its characters to form a key.
2. Use the sorted key in a HashMap to group anagrams.
3. Retrieve the grouped anagrams as values from the HashMap.

---

3. Implement a Median Finder

This program uses two heaps (PriorityQueue) to find the median of a stream of integers.

import java.util.*;

public class MedianFinder {
    private PriorityQueue<Integer> lowerHalf; // Max-heap
    private PriorityQueue<Integer> upperHalf; // Min-heap

    public MedianFinder() {
        lowerHalf = new PriorityQueue<>(Collections.reverseOrder());
        upperHalf = new PriorityQueue<>();
    }

    public void addNum(int num) {
        if (lowerHalf.isEmpty() || num <= lowerHalf.peek()) {
            lowerHalf.add(num);
        } else {
            upperHalf.add(num);
        }

        // Balance the heaps
        if (lowerHalf.size() > upperHalf.size() + 1) {
            upperHalf.add(lowerHalf.poll());
        } else if (upperHalf.size() > lowerHalf.size()) {
            lowerHalf.add(upperHalf.poll());
        }
    }

    public double findMedian() {
        if (lowerHalf.size() == upperHalf.size()) {
            return (lowerHalf.peek() + upperHalf.peek()) / 2.0;
        } else {
            return lowerHalf.peek();
        }
    }

    public static void main(String[] args) {
        MedianFinder finder = new MedianFinder();
        finder.addNum(1);
        finder.addNum(2);
        System.out.println("Median: " + finder.findMedian()); // Output: 1.5
        finder.addNum(3);
        System.out.println("Median: " + finder.findMedian()); // Output: 2
    }
}

Algorithm:

1. Use two heaps:
   • Max-heap for the lower half of the numbers.
   • Min-heap for the upper half of the numbers.
2. Add a number to the appropriate heap and balance the sizes.
3. The median is:
   • The top of the max-heap (odd size).
   • The average of the tops of both heaps (even size).

---

4. LRU Cache Implementation

This program demonstrates the implementation of an LRU (Least Recently Used) cache. LinkedHashMap.

import java.util.*;

class LRUCache {
    private final int capacity;
    private final LinkedHashMap<Integer, Integer> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;
            }
        };
    }

    public int get(int key) {
        return cache.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        cache.put(key, value);
    }

    @Override
    public String toString() {
        return cache.toString();
    }
}

public class LRUCacheExample {
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(3);
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(3, 3);
        System.out.println("Cache: " + cache);
        cache.get(1); // Access key 1
        cache.put(4, 4); // Add a new key, evict least recently used (key 2)
        System.out.println("Cache after access and eviction: " + cache);
    }
}

Algorithm:

1. Use a LinkedHashMap with access order enabled.
2. Override removeEldestEntry to evict the least recently used element when the size exceeds capacity.

---

5. Skyline Problem

This program solves the Skyline problem using a PriorityQueue.

import java.util.*;

class BuildingPoint implements Comparable<BuildingPoint> {
    int x, height;
    boolean isStart;

    public BuildingPoint(int x, int height, boolean isStart) {
        this.x = x;
        this.height = height;
        this.isStart = isStart;
    }

    @Override
    public int compareTo(BuildingPoint other) {
        if (this.x != other.x) return this.x - other.x;
        return (this.isStart ? -this.height : this.height) - (other.isStart ? -other.height : other.height);
    }
}

public class SkylineProblem {
    public static List<int[]> getSkyline(int[][] buildings) {
        List<BuildingPoint> points = new ArrayList<>();
        for (int[] building : buildings) {
            points.add(new BuildingPoint(building[0], building[2], true));
            points.add(new BuildingPoint(building[1], building[2], false));
        }
        Collections.sort(points);

        PriorityQueue<Integer> heights = new PriorityQueue<>(Collections.reverseOrder());
        heights.add(0);

        List<int[]> result = new ArrayList<>();
        int prevMax = 0;

        for (BuildingPoint point : points) {
            if (point.isStart) {
                heights.add(point.height);
            } else {
                heights.remove(point.height);
            }

            int currMax = heights.peek();
            if (currMax != prevMax) {
                result.add(new int[]{point.x, currMax});
                prevMax = currMax;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[][] buildings = {{2, 9, 10}, {3, 7, 15}, {5, 12, 12}};
        System.out.println("Skyline: " + getSkyline(buildings));
    }
}

Algorithm:

1. Represent buildings as start and endpoints.
2. Sort points based on x-coordinates and heights.
3. Use a PriorityQueue to maintain active heights.
4. Add critical points when the max height changes.

---

Let me know if you need further elaboration on any examples! 😊