uber 电面跪经

有没有什么restrictions吗？
linearly把map读一下，然后把value做为key放到新的map里面

多谢分享很有用 感觉就是建一个reverse map 然后做一遍loop

建立无向图，寻找每个connected component和所包含的无重复uuid

create keyMap and valueMap, loop them.

积分不到看不见，先码住。

这个题越想越觉得不好做，有人有思路怎么做吗？

脑袋可能有点短路了，为什么不是简单的loop一遍<id, [phone numbers]>来reverse indexing一个<phone number, [ids]>？


补充内容 (2019-4-12 05:37):
ohhh, nvm，没看完题。。

Just my two cents: use union and find. We treat driver ID and number as the same for the sake of union and find. Later we distinguish them in the final result;


input:
Map<String, List<String>> map

output:
List<List<String>>, the numbers and uuids in one group will be in the same ArrayList. e.g. [[a, c, 1], [b, 2, 3, e], [d, 5]]

class UnionFind {
    Map<String, String> parents;
    public UnionFind() {
        parents = new HashMap<>();
    }

    public String find(String u) {

        while (!parents.get(u).equals(u) ) {
            String p1 = parents.get(u);
            String p2 = parents.get(p1);
            parents.put(u, p2);
            u = p1;
        }
        return u;
    }

    public void union(String u, String v) {
        String pu = find(u);
        String pv = find(v);
        if (pu.equals(pv)) {
            return;
        }
        // TODO, we can do union by rank here to flatten the union and find tree
        parents.put(pu, pv);
    }
}

List<List<String>> findRelationship(Map<String, List<String>> map) {
    UnionFind set = new UnionFind();
    for (String id : map.keySet()) {
        set.parents.put(id, id);
        List<String> numbers = map.get(id);

        // assume the 0th phone number is the root;
        String root = numers.get(0);
        for (String num : numbers) {
            set.parents.put(num, num);
            set.union(num, root);
        }
        set.union(id, root);
    }

    Map<String, List<String>> groups = new HashMap<>();
    for (String root : set.parents.keySet()) {
        gropups.computeIfAbsent(root, k -> new ArrayList<>()).add(set.parents.get(root));
    }

    // final result will be [[a, c, 1], [b, 2, 3, e], [d, 5]]
    // if we want to get the uuid -> phone number
    // we just need to a helper function to further process each ArrayList
    return new ArrayList<>(groups.entrySet());
}