Design an employee-manager system with exactly one CEO. The CEO has no manager. Every other employee has exactly one direct manager.

The system must support adding employees, getting an employee's manager, changing an employee's manager, and checking whether an employee works directly or indirectly under a manager.

Class Signature

class EmployeeManagerSystem

Method Signatures

Constructor

EmployeeManagerSystem(String ceoId)

• Initializes the system with one CEO.
• ceoId will not be an empty string.

addEmployee

boolean addEmployee(String managerId, String employeeId)

• Adds employeeId under an existing managerId.
• Returns true if the employee is added.
• Returns false if employeeId already exists or managerId does not exist.
• If false is returned, do nothing.

getManager

String getManager(String employeeId)

• Returns the direct manager of employeeId.
• Returns an empty string if employeeId is the CEO or does not exist.

changeManager

boolean changeManager(String employeeId, String oldManagerId, String newManagerId)

• Changes employeeId from oldManagerId to an existing newManagerId.
• Returns true if the change is successful.
• Returns false if any ID is invalid, employeeId is the CEO, oldManagerId is not the current manager, or the change creates a cycle.
• If false is returned, do nothing.

worksFor

boolean worksFor(String managerId, String employeeId)

• Returns true if both IDs exist and employeeId works directly or indirectly under managerId.
• Returns false if either ID does not exist or both IDs are the same.

Rules

• Employee IDs are unique strings.
• String parameters, except the CEO's returned manager, will not be empty.
• managerId and employeeId in input will always be different.

Expected Time Complexity

• getManager: O(1)
• addEmployee: O(1) average time
• changeManager: O(h) because cycle checking may walk a manager chain
• worksFor: O(h), where h is the height of the manager chain
• At least two operations run in O(1) average time.

Constraints

• 1 ≤ number of method calls ≤ 100,000
• 1 ≤ employeeId.length, managerId.length ≤ 100
• IDs contain letters, digits, hyphens, and underscores.

Examples

Example 1

EmployeeManagerSystem system = new EmployeeManagerSystem(ceoId = "CEO")

system.getManager(employeeId = "CEO")

Output: ""

Example 2

EmployeeManagerSystem system = new EmployeeManagerSystem(ceoId = "CEO")

system.addEmployee(managerId = "CEO", employeeId = "Asha")

Output: true

system.addEmployee(managerId = "Asha", employeeId = "Ravi")

Output: true

system.getManager(employeeId = "Ravi")

Output: "Asha"

system.worksFor(managerId = "CEO", employeeId = "Ravi")

Output: true

Example 3

EmployeeManagerSystem system = new EmployeeManagerSystem(ceoId = "CEO")

system.addEmployee(managerId = "CEO", employeeId = "Meera")

Output: true

system.addEmployee(managerId = "CEO", employeeId = "Meera")

Output: false

system.getManager(employeeId = "Meera")

Output: "CEO"

Example 4

EmployeeManagerSystem system = new EmployeeManagerSystem(ceoId = "CEO")

system.addEmployee(managerId = "CEO", employeeId = "Tara")

Output: true

system.addEmployee(managerId = "CEO", employeeId = "Vikram")

Output: true

system.changeManager(employeeId = "Tara", oldManagerId = "CEO", newManagerId = "Vikram")

Output: true

system.worksFor(managerId = "Vikram", employeeId = "Tara")

Output: true