Set-based problems

1Set<Integer> a = new LinkedHashSet<>(listA), b = new LinkedHashSet<>(listB);
2Set<Integer> union = new LinkedHashSet<>(a); union.addAll(b);              // option 0
3Set<Integer> inter = new LinkedHashSet<>(a); inter.retainAll(b);           // option 1: keep what b also has
4Set<Integer> diff = new LinkedHashSet<>(a); diff.removeAll(b);             // option 2: drop what b has
5Set<Integer> sym = new LinkedHashSet<>(union); sym.removeAll(inter);       // option 3: in exactly one set

1class ChainedHashSet {
2    private final int m, variant, a;                                // m buckets
3    private final LinkedList<Integer>[] table;                      // one chain per bucket
4    int hash(int key) {                                             // the option picks one variant
5        switch (variant) {
6            case 0: return Math.floorMod(key, m);
7            case 1: return (int) (m * ((key * 0.6180339887) % 1.0));
8            case 2: return 0;                                       // worst case: every key collides
9            default: return ((a * key + 7) % 101) % m;              // universal-style family
10        }
11    }
12    boolean add(int key) {
13        LinkedList<Integer> chain = table[hash(key)];
14        if (chain.contains(key)) return false;                      // walk the chain: duplicate
15        chain.add(key); return true;                                // append to the chain
16    }
17    boolean contains(int key) { return table[hash(key)].contains(key); }
18    boolean remove(int key) { return table[hash(key)].remove((Integer) key); }
19}

1static int longestConsecutive(int[] nums) {
2    Set<Integer> set = new HashSet<>();
3    for (int x : nums) set.add(x);
4    int best = 0;
5    for (int x : set) {
6        if (set.contains(x - 1)) continue;                  // not the start of a run
7        int end = x;
8        while (set.contains(end + 1)) end++;                // walk the run
9        best = Math.max(best, end - x + 1);
10    }
11    return best;
12}

1public static int[] twoSum(int[] nums, int target) {
2    Map<Integer, Integer> seen = new HashMap<>();      // value -> index
3    for (int i = 0; i < nums.length; i++) {
4        int need = target - nums[i];
5        if (seen.containsKey(need)) {
6            return new int[] { seen.get(need), i };
7        }
8        seen.put(nums[i], i);
9    }
10    return new int[] { -1, -1 };
11}

1static int[] distinctInWindows(int[] a, int k) {
2    int[] out = new int[a.length - k + 1];
3    Map<Integer, Integer> count = new HashMap<>();
4    for (int i = 0; i < a.length; i++) {
5        count.merge(a[i], 1, Integer::sum);                         // value enters the window
6        if (i >= k) {
7            int old = a[i - k];                                      // value leaves the window
8            if (count.merge(old, -1, Integer::sum) == 0) count.remove(old);
9        }
10        if (i >= k - 1) out[i - k + 1] = count.size();               // size() = distinct values
11    }
12    return out;
13}