Question

Reconstructing a tree

You are asked to reconstruct the reporting hierarchy of a huge company Disorganized, Inc., based on information that is complete but poorly organized. The information is available in an n-element array, in which each element of the array is a pair (emp, boss) where emp is the name of an employee and boss is the supervisor of the employee, and n is the number of employees in Disorganized. You may assume that the names of all employees are distinct. For the company CEO, the boss entry is empty.

Your task is to compute a tree in which each node has the name of an employee emp and a parent field pointing to the node corresponding to the supervisor of emp (for the CEO, the parent field will point to NIL).

(a) Design an O(n log n) time deterministic algorithm for the problem. Justify the running time of your algorithm.

(b) Using hashing, design an expected O(n) time randomized algorithm for the problem. Justify the running time of your algorithm.

Answer 1

As we know that each element is a pair then the following can be sorted into a dictionary using reverse map and then the following can be added to create a O(n log n) algorithm. Here is the code:

public class Employee
{
public int Id { get; set; } //id
public string Name { get; set; } //name
public List<Employee> Reports { get; set; }
}

public static Employee ClosestCommonManager(Employee ceo, Employee firstEmployee, Employee secondEmployee)
{
Employee currentClosestManager = ceo; //CEO doesn't have any parent node

if (!Covers(ceo, firstEmployee) || !Covers(ceo, secondEmployee))
return null;
  
Queue q = new Queue();
q.Enqueue(ceo);

while (!q.IsEmpty())
{
var emp =(Employee) q.Dequeue();
if (emp != null)
{
foreach (var employee in emp.Reports)
{
if (Covers(employee, firstEmployee) && Covers(employee, secondEmployee)
&& (employee.Id != firstEmployee.Id && employee.Id != secondEmployee.Id))
{
currentClosestManager = employee;
q.Enqueue(employee);
}
}
}
}
return currentClosestManager;

}

public static bool Covers(Employee root, Employee p)
{
if (root == null)
return false;

if (root.Id == p.Id)
return true;

foreach (var employee in root.Reports)
{
if (Covers(employee, p))
{
return true;
}
}
return false;
}