fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Employee {
  5. public:
  6.     int employeeId;
  7.     string employeeName;
  8.  
  9.     Employee(int id, string name){
  10.         employeeId = id;
  11.         employeeName = name;
  12.     } 
  13. };
  14.  
  15. // Each GroupNode can have subgroups and a set of employees.
  16. class GroupNode {
  17. public:
  18.     string groupName;
  19.     vector<GroupNode*> subGroups;
  20.     unordered_set<string> employeesInGroup;   // ordering doesn't matter here
  21.  
  22.     GroupNode(string name){
  23.         groupName = name;
  24.     }
  25.  
  26.     void addSubGroup(GroupNode* subGroup) {
  27.         subGroups.push_back(subGroup);
  28.     }
  29.  
  30.     void addEmployee(string employeeName) {
  31.         employeesInGroup.insert(employeeName);
  32.     }
  33. };
  34.  
  35.  
  36. // n = number of groups/nodes,
  37. // m = number of target employees.
  38. // h = height of tree
  39. // The algorithm performs a depth-first traversal of the company
  40. // In the worst case, it may need to visit each node of the company. If there are n groups/nodes, the traversal complexity is O(n)
  41. // and for each group/node visited, we iterate over targetEmployees vector which takes O(m)
  42. // So Time = O(n*m)
  43. // Space complexity of the recursive approach is determined by the maximum depth of the recursion stack.
  44. // In the worst-case scenario, this depth is equal to the height of the tree h.
  45. // For a balanced tree, h =(log n), but in the worst case (e.g., a skewed tree), h = n
  46. // Space = O(h)
  47. GroupNode* findLCArecursion(GroupNode* root, vector<string> targetEmployees) {
  48.     // Base Case , lets say companyRoot is null i.e empty company
  49.     if (root == nullptr) { 
  50.         return nullptr;
  51.     }
  52.  
  53.     // Check if current group contains any of the target employees          
  54.     for (int i = 0; i < targetEmployees.size(); i++) { // O(m)
  55.         if (root->employeesInGroup.find(targetEmployees[i]) != root->employeesInGroup.end()) {
  56.             return root; // found potential LCA
  57.         }
  58.     }
  59.  
  60.  
  61.     int foundCount = 0;
  62.     GroupNode* ans = nullptr;
  63.  
  64.     // Recurse through subgroups to find the LCA
  65.     for (int i = 0; i < root->subGroups.size(); i++) {                       
  66.         GroupNode* subLCA = findLCArecursion(root->subGroups[i], targetEmployees);
  67.         if (subLCA != nullptr) {
  68.             foundCount++;
  69.             ans = subLCA;
  70.         }
  71.     }
  72.  
  73.     // If more than one subgroup contains any of the target employees,
  74.     // the current node is the lowest common ancestor
  75.     if (foundCount > 1) {
  76.         return root;
  77.     }
  78.  
  79.     // Otherwise, return the subgroup that contains any of the target employees
  80.     return ans;
  81. }
  82.  
  83. // Lowest Common Ancestor
  84. GroupNode* findLCA(GroupNode* root, vector<string> targetEmployees) {
  85.     if (targetEmployees.empty()) return nullptr;
  86.     return findLCArecursion(root, targetEmployees);
  87. }
  88.  
  89.  
  90. int main() {
  91.  
  92.     /*
  93.         -    Company
  94.           /           \
  95.         HR               Engg
  96.       /   \          /          \ 
  97.      Mona  Springs  BE          FE 
  98.                     /  \        / \ 
  99.                   Alice Bob  Lisa Marley
  100.  
  101.     */
  102.  
  103.     GroupNode* companyRootNode = new GroupNode("Company");
  104.     GroupNode* hr = new GroupNode("HR");
  105.     GroupNode* engg = new GroupNode("Engg");
  106.     GroupNode* be = new GroupNode("BE");
  107.     GroupNode* fe = new GroupNode("FE");
  108.  
  109.     companyRootNode->addSubGroup(hr);
  110.     companyRootNode->addSubGroup(engg);
  111.  
  112.     engg->addSubGroup(be);
  113.     engg->addSubGroup(fe);
  114.  
  115.  
  116.     hr->addEmployee("Mona");
  117.     hr->addEmployee("Springs");
  118.  
  119.     be->addEmployee("Alice");
  120.     be->addEmployee("Bob");
  121.  
  122.     fe->addEmployee("Lisa");
  123.     fe->addEmployee("Marley");
  124.  
  125.  
  126.     // Test cases
  127.     vector<string> employees1 = {"Lisa", "Marley"};
  128.     GroupNode* result = findLCA(companyRootNode, employees1);
  129.     if(result == nullptr) {
  130.         cout << "No common parent"<<endl;
  131.     } else {
  132.         cout << result->groupName<<endl;
  133.     }
  134.  
  135.  
  136.     vector<string> employees2 = {"Alice", "Marley"};
  137.      GroupNode* result2 = findLCA(companyRootNode ,employees2);
  138.     if(result == nullptr) {
  139.         cout << "No common parent, there are isolated trees in the company"<<endl;
  140.     } else {
  141.         cout << result2->groupName<<endl;
  142.     }
  143.  
  144.  
  145.     vector<string> employees3 = {"Mona", "Lisa", "Bob"};
  146.      GroupNode* result3 = findLCA(companyRootNode ,employees3);
  147.     if(result == nullptr) {
  148.         cout << "No common parent"<<endl;
  149.     } else {
  150.         cout << result3->groupName<<endl;
  151.     }
  152.  
  153.  
  154.  
  155.     return 0;
  156. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
FE
Engg
Company
https://ideone.com/7DKHfF
language:
C++ (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!