Google – Manager Peer Problem

Google – Manager Peer Problem
Design a data structure to support following functions:
1. setManager(A, B) sets A as a direct manager of B
2. setPeer(A, B) sets A as a colleague of B. After that, A and B will have the same direct Manager.
3. query(A, B) returns if A is in the management chain of B.
Every person only has 1 direct manager.
[Solution]
本来分析了半天以为union-find的行不通，最后发现好像也是可以的。但是和传统union-find有点不一样：
1. 不能path compression。因为这题涉及到层级关系，不能打乱。
2. 有两种union。并且在做union的时候并不是把他们的root union到一起，而是直接id[b] = ida或者id[b] = a(setManager)。这里把id命名为parent更贴切一点。
3. find不是找他们的root是不是一样，而是在找root of B的过程中，看A在不在一条chain上。
其实这题用union-find也就相当于一棵Tree, 只不过用数组来记录每个Node的parent的而已。
第二种方法就是直接Tree + Hash Table
每个TreeNode包含一个parent指针和一个neighbors list，不需要维护children。因为找在不在一条chain上都是往上找。再加一个Hash Table来hash Integer to TNode

// union-find

class ManagerPeer {

   

  int[] parent;

  int n;

   

  public ManagerPeer(int n) {

    this.n = n;

    this.parent = new int[n];

    for (int i = 0; i < n; i++) {

      parent[i] = i;

    }

  }

   

  public void setManager(int a, int b) {

    parent[b] = a;

  }

   

  public void setPeer(int a, int b) {

    parent[b] = parent[a];

  }

   

  public boolean query(int a, int b) {

    while (parent[b] != b) {

      if (parent[b] == a) {

        return true;

      }

      b = parent[b];

    }

    return false;

  }

}

// Tree + Hash Table

class ManagerPeer2 {

   

  Map<Integer, TNode> nodeMap = new HashMap<>();

   

  public void setManager(int a, int b) {

    nodeMap.putIfAbsent(a, new TNode(a));

    nodeMap.putIfAbsent(b, new TNode(b));

     

    nodeMap.get(b).parent = nodeMap.get(a);

  }

   

  public void setPeer(int a, int b) {

    nodeMap.putIfAbsent(a, new TNode(a));

    nodeMap.putIfAbsent(b, new TNode(b));

     

    nodeMap.get(a).neighbors.add(nodeMap.get(b));

    nodeMap.get(b).neighbors.add(nodeMap.get(a));

    nodeMap.get(b).parent = nodeMap.get(a).parent;

  }

   

  public boolean query(int a, int b) {

    if (!nodeMap.containsKey(a) || !nodeMap.containsKey(b)) {

      return false;

    }

     

    TNode curr = nodeMap.get(b);

    while (curr != null) {

      if (curr.equals(nodeMap.get(a))) {

        return true;

      }

      curr = curr.parent;

    }

  }

   

  private class TNode {

    int val;

    TNode parent;

    List<TNode> neighbors;

     

    public TNode(int val) {

      this.val = val;

      neighbors = new ArrayList<>();

    }

  }

}

http://www.1point3acres.com/bbs/thread-198684-1-1.html
实现一个class支持三个API:
peer A, B
manager A, B
isManager A, B

比如
peer Tim, Bill
peer Bill, Mike.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
manager Lucy, Tim. 1point3acres.com/bbs
isManager Lucy, Tim -> True
isManager Lucy, Mike -> True
manager Amy, Lucy-google 1point3acres
isManager Amy, Bill -> True

具体的来说，如果给两个人添加peer关系，他们就成为一个peer group。. From 1point 3acres bbs
如果其中一个人已经在某个peer group，另一个人没有peer group，就把后者添加到前者的peer group。
每个peer group都只有一个manager。
所以不会出现
peer Tim, Bill.鏈枃鍘熷垱鑷�1point3acres璁哄潧
manager Lucy, Tim
manager Amy, Bill
这种情况
但是, 如果两个人已经在不同的peer groups，这种情况call peer API会返回错误。manager Lucy, Tim
manager Amy, Bill
peer Tim, Bill -> error
每个manager可以有自己的peers以及manager。
每个manager的manager也是其下属的manager。
X. use union find, two maps. each layer is seen as a peer group, different layers are connected by managerEmployee map
class ManagerPeer{. visit 1point3acres.com for more.
     Map<String, String> parents= new HashMap<>();. visit 1point3acres.com for more.
     Map<String, Set<String>> managerEmployee= new HashMap<>();
     Set<String> labelNodes = new HashSet<>();. 1point 3acres 璁哄潧
private String findParents(String p1){
    if(!parents.containsKey(p1)){
    parents.put(p1, p1);
    return p1;. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
}
    while(parents.get(p1) != p1){
    parents.put(p1, parents.get(p1));
    p1 = parents.get(p1);
}
return p1;
}
public void peer(String p1, String p2){
    String parent1 = findParents(p1);. 鍥磋鎴戜滑@1point 3 acres
    String parent2 = findParents(p2);
    if(!parent1.equals(parent2)){
    if(labelNodes.contains(parent1)){. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
    parents.put(parent2, parent1);
}else{
    parents.put(parent1, parent2);
}
}
}
public void manage(String mngr, String empl){
    String label1 = findParents(mngr);. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
    String label2 = findParents(empl);
    labelNodes.add(label1); labelNodes.add(label2);
    managerEmployee.put(label1, new HashSet<>());
    managerEmployee.get(label1).add(label2);
    managerEmployee.get(label1).addAll(managerEmployee.getOrDefault(label2, new HashSet<>()));
}. 1point3acres.com/bbs
public boolean isManager(String mngr, String empl){
    if(!parents.containsKey(mngr) || !parents.containsKey(empl)) return false;
    String label1 = findParents(mngr);
    String label2 = findParents(empl);
    if(!managerEmployee.containsKey(label1) || !managerEmployee.get(label1).contains(label2)) return false;
    return true;
}
Read full article from Google – Manager Peer Problem