2 hours ago

Sarthak • 10

Hyderabad

Question: Corporate Restructuring

Problem Statement: In the large corporation Techify Inc., there is a hierarchical structure of employees. The company has N employees, each identified by a unique ID from 1 to N. At the top of this structure is the CEO, who serves as the root of the company's hierarchy.

Employees report to their immediate supervisors except for the CEO, who has no supervisor. The company is undergoing a restructuring process because some employees have become non-compliant.

• Compliant: An employee is compliant if they respect the company's policies and directives given by their supervisor.

• Non-Compliant: Some employees have grown dissatisfied and no longer respect their supervisor's authority.

To streamline the company, management has decided to identify and remove non-compliant employees, but with specific criteria:

1. Select a non-compliant employee (one who does not respect their supervisor) who also has no compliant subordinates (i.e., all of their direct and indirect reports are either also non-compliant or they are a leaf node with no reports).

2. If there are multiple such employees eligible for removal, break the tie by selecting the employee with the smallest unique ID.

3. When an employee is removed, their immediate subordinates are directly reassigned to the removed employee's supervisor.

Task: Write a program to determine the order in which these non-compliant employees will be removed from the company.

Return Format: Return an array/list of integers representing the IDs of the employees in the exact order they are removed. If no employees meet the criteria for removal, return an empty array or -1 (depending on the specific compiler instructions).

5 minutes ago

admin 1.9k

Hyderabad

Solution-: Corporate Restructuring

Overview

The problem asks us to simulate a restructuring process in a tree-based organizational hierarchy. We need to remove non-compliant employees who have no compliant subordinates (direct or indirect). When an employee is removed, their children are reassigned to their former supervisor. If multiple employees are eligible for removal, we must always remove the one with the smallest unique ID first.

Approach

1. Tree Representation: Build an adjacency list to represent the hierarchy. Since we need to know the "supervisor" (parent) and "subordinates" (children), a standard tree structure works best.
2. Eligibility Analysis: A non-compliant employee U is eligible for removal if and only if there are no compliant employees in the subtree rooted at U.
   • Crucially, since compliant employees are never removed, if a non-compliant employee has a compliant descendant, they will never become eligible for removal, even after other non-compliant employees are removed.
   • Therefore, the set of employees that will eventually be removed is fixed from the start: it is every non-compliant employee whose initial subtree contains zero compliant nodes.
3. Order of Removal: The problem specifies that we must remove the eligible employee with the smallest ID. Because the removal of one eligible employee does not change the "compliant/non-compliant" status of any remaining subtrees, the order of removal is simply the list of all eligible IDs sorted in ascending order.
4. CEO Logic: The problem notes the CEO has no supervisor. Since non-compliance is defined as "disrespecting a supervisor," the CEO is generally excluded from the removal candidates.

Time and Space Complexity

• Time Complexity:O(N \log N). We perform a single Depth First Search (DFS) to evaluate subtree compliance (O(N)) and then sort the eligible IDs (O(N \log N)).
• Space Complexity: O(N) to store the adjacency list, subtree status, and recursion stack for DFS.

Code Implementation (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Global or class-level variables for the DFS
vector<vector<int>> adj;
vector<bool> is_compliant;
vector<bool> has_compliant_in_subtree;

// DFS to check if any compliant employee exists in the subtree of u
bool checkSubtreeCompliance(int u) {
    bool found_compliant = false;
    
    for (int subordinate : adj[u]) {
        // If the direct subordinate is compliant, or any of their 
        // descendants are compliant, the current node has compliant subordinates.
        if (is_compliant[subordinate] || checkSubtreeCompliance(subordinate)) {
            found_compliant = true;
        }
    }
    
    has_compliant_in_subtree[u] = found_compliant;
    return found_compliant;
}

vector<int> getRemovalOrder(int n, int ceo_id, vector<int>& parent, vector<int>& compliance_status) {
    adj.assign(n + 1, vector<int>());
    is_compliant.assign(n + 1, false);
    has_compliant_in_subtree.assign(n + 1, false);

    // Build the tree and map compliance
    // compliance_status[i] == 1 for Compliant, 0 for Non-Compliant
    for (int i = 1; i <= n; ++i) {
        is_compliant[i] = (compliance_status[i - 1] == 1);
        if (i != ceo_id) {
            adj[parent[i - 1]].push_back(i);
        }
    }

    // Identify which nodes have compliant descendants
    checkSubtreeCompliance(ceo_id);

    vector<int> removable_employees;
    for (int i = 1; i <= n; ++i) {
        // Criteria: Non-compliant AND no compliant subordinates
        // The CEO is excluded as they have no supervisor to be non-compliant towards.
        if (i != ceo_id && !is_compliant[i] && !has_compliant_in_subtree[i]) {
            removable_employees.push_back(i);
        }
    }

    // Tie-breaker: Smallest unique ID
    sort(removable_employees.begin(), removable_employees.end());

    if (removable_employees.empty()) {
        return {-1}; 
    }

    return removable_employees;
}