parent companies and child companies

给出parent company， child company pairs

  1. 给出一个child company， 然后找到parent company
  2. 判断两个company是不是related的

后面交谈才知道面试官想要一个hashmap搞定这两题。第二问我一开始说用并查集，他说不知道并查集，我就尝试解释，但是我后来放弃了，然后又尝试建图，但他说只要一个map。
于是就浪费了很久的时间。hr说45分钟的时间，到了47分钟的时候，我才说出用递归查找，最后他让我写完了，结束时间是57分钟？太可惜了，真想扇自己。。。
关于第二问： 假设输入是(A,B),(A,C),(B,G),(C,D),(B,H) 格式是(parent, child), 会叫你求isRelated(D,H)之类的。

1
2
3
4
5
6
7
8
9
10
11
12
//应该还能用dp缓存以下，感兴趣的自己去研究下
Map<String,String>map = new HashMap<>();//key is child, value is parent
    public boolean isRelated(String companyA, String companyB){
        if(!map.containsKey(companyA)||!map.containsKey(companyB))
            return false;
        if(map.get(companyA).equals(companyB)||map.get(companyB).equals(companyA))
            return true;
        String parentA = map.get(companyA);
        String parentB = map.get(companyB);
        return isRelated(companyA,parentB)||isRelated(parentA,companyB);
    }