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:
- setManager(A, B) sets A as a direct manager of B
- setPeer(A, B) sets A as a colleague of B. After that, A and B will have the same direct Manager.
- query(A, B) returns if A is in the management chain of B. Every person only has 1 direct manager.
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;
}