algorithmdata-structuresunion-find

How to solve manager peer problem question?


I was asked below question in google interview but could not answer it. I did google search but could not find any correct solution for this problem. Can you please help me to provide a solution for this 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

  • Use three hash tables 1. employee to group id mapping (emp) 2. group id to list of employees (gid) 3. group id -> manager id table (manager)

    int id = 0;
    void setpeer(string A, string B) {
    int id1 = 0;
    int id2 = 0;
    if (emp.find(A) != emp.end())
       id1 = emp[A];
    if (emp.find(B) != emp.end())
       id2 = emp[B];
    
    if (!id1 && !id2) {
        ++id;
        emp[A] = id;
        emp[B} = id;
        gid[id].push_back(A);
        gid[id].push_back(B);
    } else if (!id1) {
         emp[A] = id2;
         gid[id2].push_back(A);
    } else if (!id2) {
         emp[B] = id1;
         gid[id1].push_back(B);
    } else {
       for(i = 0;i<gid[id2].size();i++) {
           emp[gid[id2][i]] = id1;
           gid[id1].push_back( gid[id2][i] );
      }
      if (manager.find(id2) != manager.end())
            manager[id1] = manager[id2].
      manager.erase(id2);
      gid.erase(id2);
    }
    
    void setManager(string A, string B) {
    int id1, id2;
       if (emp.find(A) != emp.end())
             id1 = emp[A];
      else {
           ++id;
          emp[A] = id;
          id1 = id;
          gid[id].push_back(A);
      }
       if (emp.find(B) != emp.end())
             id2 = emp[B];
      else {
           ++id;
          emp[B] = id;
          id2 = id;
          gid[id].push_back(B);
      }
       manager[id2] = id1;
    }
    
    bool query(string A, string B) {
       int id1 = 0, id2 = 0;
       if (emp.find(A) != emp.end())
            id1 = emp[A];
       if (emp.find(B) != emp.end())
            id2 = emp[B];
       if (!id1 || !id2) //one of them does not exist
         return false;
      id2 = manager[id2];
      while(id2 != 0) {
         if (id2 == id1)
            return true;
         id2 = manager[id2];
     }
     return false;
    }