// Week 11 – Solutions of the practice exercises
// Run: java Exercises11.java
import java.util.*;

public class Exercises11 {

    // E1. Two sum: are there two elements whose sum is target? – O(n) with a hash map (instead of O(n²))
    static int[] twoSum(int[] a, int target) {
        Map<Integer, Integer> seen = new HashMap<>(); // value -> index
        for (int i = 0; i < a.length; i++) {
            Integer j = seen.get(target - a[i]);
            if (j != null) return new int[] { j, i };
            seen.put(a[i], i);
        }
        return null;
    }

    // E2. The first non-repeating character
    static Character firstUnique(String s) {
        Map<Character, Integer> c = new LinkedHashMap<>(); // hash table that keeps the insertion order
        for (char ch : s.toCharArray()) c.merge(ch, 1, Integer::sum);
        for (Map.Entry<Character, Integer> e : c.entrySet()) if (e.getValue() == 1) return e.getKey();
        return null;
    }

    // E3. Anagram groups: the key is the sorted letters of the word
    static Collection<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> g = new TreeMap<>();
        for (String w : words) {
            char[] cs = w.toCharArray();
            Arrays.sort(cs);
            g.computeIfAbsent(new String(cs), k -> new ArrayList<>()).add(w);
        }
        return g.values();
    }

    // E4. Is there a duplicate? – O(n) on average
    static boolean hasDuplicate(int[] a) {
        Set<Integer> s = new HashSet<>();
        for (int x : a) if (!s.add(x)) return true; // add returns false if it was already in the set
        return false;
    }

    // E5. Brackets: the bracket pairs are stored in a map; the stack is an ArrayDeque (same ADT)
    static boolean balanced(String s) {
        Deque<Character> st = new ArrayDeque<>();
        Map<Character, Character> pair = Map.of(')', '(', ']', '[', '}', '{');
        for (char c : s.toCharArray()) {
            if ("([{".indexOf(c) >= 0) st.push(c);
            else if (pair.containsKey(c) && (st.isEmpty() || st.pop() != pair.get(c))) return false;
        }
        return st.isEmpty();
    }

    // E6. Phone book: name -> number, search by name
    static void phoneBook() {
        Map<String, String> pb = new HashMap<>();
        pb.put("Li Wei", "+86 27 1234 5678");
        pb.put("Ferenc Koczka", "+36 36 520 400");
        pb.put("Wang Fang", "+86 10 8765 4321");
        System.out.println("  Wang Fang: " + pb.get("Wang Fang") + ", Zhang San: " + pb.getOrDefault("Zhang San", "no such name"));
    }

    public static void main(String[] args) {
        System.out.println("E1. twoSum([2,7,11,15], 9) = " + Arrays.toString(twoSum(new int[] { 2, 7, 11, 15 }, 9)));
        System.out.println("E2. firstUnique(\"swiss\") = " + firstUnique("swiss"));
        System.out.println("E3. groupAnagrams = " + groupAnagrams(new String[] { "eat", "tea", "tan", "ate", "nat", "bat" }));
        System.out.println("E4. hasDuplicate([1,2,3,1]) = " + hasDuplicate(new int[] { 1, 2, 3, 1 }) + ", [1,2,3] = " + hasDuplicate(new int[] { 1, 2, 3 }));
        System.out.println("E5. balanced(\"{[()]}\") = " + balanced("{[()]}") + ", balanced(\"([)]\") = " + balanced("([)]"));
        System.out.println("E6. phone book:");
        phoneBook();
    }
}