How to solve manager peer problem question?

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.

Answer 1

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;
}

Answer 2

Let's consider each group of peers as a node in the hierarchy tree that represents the company management chain. We know that it's a tree because each person only has 1 direct manager.

We'll have the tree of the following form:

Quick ideas:

• setManager is just connecting 2 nodes (and also creating node if not already existed).
• setPeer is just updating a node to include the other peer (if node already existed); or creating a node for both peers (if none of the node existed); or merging 2 existing nodes (if 2 nodes were created independently for each peer).
• query(A, B) is just to traverse the tree upwards and check if a node on that path contains employee A.
• One extra issue: given an employee X, we need to get the access to the corresponding node (can be solved by having an extra hash table, which map from every employee to the reference of their corresponding node).

---

The code for the above idea

public class EmployeeManagement {
  private Dictionary < string, Node > _employeeToNode;

  public EmployeeManagement() {
    _employeeToNode = new Dictionary < string, Node > ();
  }

  public void SetManager(string manager, string employee) {
    if (!_employeeToNode.ContainsKey(manager)) {
      _employeeToNode[manager] = new Node(null, manager);
    }

    if (!_employeeToNode.ContainsKey(employee)) {
      _employeeToNode[employee] = new Node(_employeeToNode[manager], employee);
    } else {
      _employeeToNode[employee].SetManagerNode(_employeeToNode[manager]);
    }
  }

  public void SetPeer(string employeeA, string employeeB) {
    if (_employeeToNode.ContainsKey(employeeA) && _employeeToNode.ContainsKey(employeeB)) {
      if (_employeeToNode[employeeA].HasEmployee(employeeB) &&
        _employeeToNode[employeeB].HasEmployee(employeeA)) {
        return;
      }
      // Merge node of A and B if distinct
      Node newNode = _employeeToNode[employeeA];
      Node oldNode = _employeeToNode[employeeB];
      if (_employeeToNode[employeeB].EmployeeCount() > newNode.EmployeeCount()) {
        newNode = _employeeToNode[employeeB];
        oldNode = _employeeToNode[employeeA];
      }

      if (!newNode.HasManager()) {
        newNode.SetManagerNode(oldNode.GetManagerNode());
      }

      foreach(var employee in oldNode.GetEmployees()) {
        newNode.AddEmployee(employee);
      }

      _employeeToNode[employeeA] = newNode;
      _employeeToNode[employeeB] = newNode;
      foreach(var employee in oldNode.GetEmployees()) {
        _employeeToNode[employee] = newNode;
      }
    } else if (_employeeToNode.ContainsKey(employeeA)) {
      _employeeToNode[employeeB] = _employeeToNode[employeeA];
    } else if (_employeeToNode.ContainsKey(employeeB)) {
      _employeeToNode[employeeA] = _employeeToNode[employeeB];
    } else {
      // Create a new node for both A and B
      Node forAB = new Node(null, employeeA);
      forAB.AddEmployee(employeeB);
      _employeeToNode[employeeA] = forAB;
      _employeeToNode[employeeB] = forAB;
    }
  }

  /// <summary>
  /// Check if A is in the management chain of B
  /// </summary>
  public bool Query(string employeeA, string employeeB) {
    if (!_employeeToNode.ContainsKey(employeeA) || !_employeeToNode.ContainsKey(employeeB)) {
      return false; // no info of employee A or employee B yet
    }

    Node managersOfB = _employeeToNode[employeeB].GetManagerNode();
    while (managersOfB != null) {
      if (managersOfB.HasEmployee(employeeA)) {
        return true;
      }

      managersOfB = managersOfB.GetManagerNode();
    }

    return false; // not found A in the management chain of B
  }
}

private class Node {
  private Node _directManagers;
  private HashSet < string > _employees;

  public Node(Node directManagers, string employee) {
    _directManagers = directManagers;
    _employees = new HashSet < string > ();
    _employees.Add(employee);
  }

  public bool HasManager() {
    return _directManagers != null;
  }

  public void SetManagerNode(Node directManagers) {
    _directManagers = directManagers;
  }

  public Node GetManagerNode() {
    return _directManagers;
  }

  public void AddEmployee(string employee) {
    _employees.Add(employee);
  }

  public HashSet < string > GetEmployees() {
    return _employees;
  }

  public bool HasEmployee(string employee) {
    return _employees.Contains(employee);
  }

  public int EmployeeCount() {
    return _employees.Count;
  }
}

Answer 3

Say you have the following person class:

struct Person {
  // we need to store the manager, obviously
  Person* manager = nullptr;
  // we also need to store the peers to assign the correct
  // manager for all when it is set for one person in the group
  shared_ptr<vector<Person*>> peerGroup = make_shared<vector<Person*>>({this});
};

A person, when newly created, has no manager and a peer group containing only the person itself.

Assuming A, B, etc. are not strings but Person*, you can implement the methods as follows:

void setManager(Person* a, Person* b) {
  for (Person* person : *b->peerGroup) person->manager = a;
}

void setPeer(Person* a, Person* b) {
  // merge peer groups of a and b
  // by first adding b's peers to a's peer group
  // and then setting b's peer group to a's peer group
  for (Person* person : *b->peerGroup) a->peerGroup->push_back(person);
  b->peerGroup = a->peerGroup;
}

bool query(Person* a, Person* b) {
  // we want to find out if a is managed by b
  // so we go up the hierarchy, starting from a
  Person* current = a;
  while (current->manager != nullptr) {
    // stop if b is (indirect) manager of a
    if (current->manager == b) return true;
    current = current->manager;
  }
  // we reached the top of the hierarchy and did not find b
  return false;
}

In case you actually receive strings (like "A", "B", ...) you could just use a hashmap to see if you already created a Person object for this name and if not create one:

map<string, unique_ptr<Person>> persons;

Person* getPerson(string name) {
  if (!persons.contains(name)) {
    persons[name] = make_unique<Person>();
  }
  return persons[name].get()
}

Answer 4

This can be done with a single class, Employee, which contains an attribute/member _manager, which is a reference to this employees manager if any and an attribute/member '_managees', a set of all Employee instances/objects that this employee manages.

Note: I am going exclusively by my interpretation of the problem definition, which were bullet points 1-3 and not by the OP's or any other person's interpretation. The description for setPeer is sets A as a colleague of B. After that, A and B will have the same direct Manager. Thus when you call setPeer(A, B), you are setting A's manager to be B's manager and that it doesn't make any sense unless B has a manager. And everyone has a manager except for the head boss, and by definition the head boss can have no peers. So perhaps A just got a promotion (or a demotion or just a lateral move to another department). It doesn't mean that every former peer of A has gotten the same promotion and now have the same new manager, too. So I see this a less-complicated problem than others are making of it.

class Employee:
    def __init__(self, name, manager=None):
        self._name = name
        self._managees = set()
        self._manager = None # so far
        if manager:
            self.set_manager(manager) # Could be none if this is the "top dog"

    def __repr__(self):
        return f'Name: {self._name}, Managed By: {self._manager._name if self._manager else ""}, Manages: {[managee._name for managee in self._managees]}'

    def get_name(self):
        return self._name

    def get_manager(self):
        return self._manager

    def get_managees(self):
        return self._managees

    def manages(self, employee):
        return employee in self._managees

    def is_managed_by(self, employee):
        return self._manager is employee

    def remove_manager(self):
        """
        We are no longer managed by anyone.
        """
        if self._manager:
            self._manager.remove_managee(self)
            self._manager = None
        return self

    def remove_managee(self, managee):
        """
        This manager no longer manages managee.
        """
        self._managees.remove(managee)
        managee._manager = None # No longer has a manager
        return self

    def set_manager(self, manager):
        if not manager:
            self.remove_manager()
            return self
        if self._manager:
            # We have an existing manager:
            self._manager.remove_managee(self)
        self._manager = manager
        manager._managees.add(self)
        return self

    def add_managee(self, managee):
        """
        This manager now manages managee.
        """
        managee.set_manager(self)
        return sell

    def set_peer(self, managee):
        assert managee._manager # Make sure managee can have a peer
        self.set_manager(managee._manager)
        return self

    @staticmethod
    def query(employee1, employee2):
        """
        Is employee1 in the management chain of employee2?
        """
        manager = employee2._manager
        while manager:
            if manager is employee1:
                return True
            manager = manager._manager
        return False


tom = Employee('Tom')
dick = Employee('Dick', tom)
harry = Employee('Harry', dick)
sally = Employee('Sally')
sally.set_manager(harry)
assert sally.is_managed_by(harry) and harry.manages(sally)
sally.set_manager(tom)
assert sally.is_managed_by(tom) and tom.manages(sally)
sally.set_peer(harry)
assert sally.is_managed_by(dick) and dick.manages(sally)
assert Employee.query(tom, harry)
assert not Employee.query(harry, dick)
print(tom)
print(dick)
print(harry)
print(sally)

Prints:

Name: Tom, Managed By: , Manages: ['Dick']
Name: Dick, Managed By: Tom, Manages: ['Harry', 'Sally']
Name: Harry, Managed By: Dick, Manages: []
Name: Sally, Managed By: Dick, Manages: []