How to solve manager peer problem question?-CodePudding

The

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