返回层次结构中的Boss——尝试应用深度优先搜索

这看起来像是对http://en.wikipedia.org/wiki/Lowest_common_ancestor的请求。聪明的算法通常会在树上做一些预处理。一种简单的方法是标记树中的每个元素与根的距离。然后，为了找到两个节点最近的共同祖先，首先将一个指针从较低的指针向上移动，使它们处于相同的深度，然后将两个指针一起向上移动，直到指针接触。如果您没有进行预处理，您可以同时从两个节点向上移动，将您看到的所有节点添加到一个集合中，并检查何时将遇到的节点集添加到已经存在的节点集中。无论哪种情况，当您第一次遇到来自两边的节点时，该节点就是最低的共同祖先。

使用DFS的简单解决方案

单独的任务。
创建DFS函数查找从根目录到工作目录的PATH。(list or stack)
为两个worker调用它，然后比较从根到worker的路径。
最后一场比赛是你的目标

在这个解决方案中，我为Employee添加了两个字段:

//all managers of this Employee
public List<Employee> Bosses = new List<Employee>();
//how many managers between employee and Ceo
public int DistanceFromCeo = 0;

此代码查找第一和第二员工的所有老板并将它们存储在他们的Bosses字段

var stack = new Stack<Employee>(); // DFS
stack.Push(ceo);
while (stack.Count != 0)
{
    var current = stack.Pop();
    IList<Employee> employeeList = current.getReports();
    foreach (var employee in employeeList)
    {
        employee.Bosses.AddRange(current.Bosses);
        employee.Bosses.Add(current);
        employee.DistanceFromCeo = current.DistanceFromCeo + 1;
        if (firstEmployee.getId() == employee.getId())
        {
            firstEmployee.Bosses.AddRange(employee.Bosses);
        }
        if (secondEmployee.getId() == employee.getId())
        {
            secondEmployee.Bosses.AddRange(employee.Bosses);
        }
        stack.Push(employee);
    }
}

现在很容易得到答案-加入老板并找到最遥远的:

var commonBosses = (from f in firstEmployee.Bosses
    join s in firstEmployee.Bosses on f.getId() equals s.getId()
    select f).ToList();
var maxLenght = commonBosses.Max(b => b.DistanceFromCeo);
return commonBosses.FirstOrDefault(b => b.DistanceFromCeo == maxLenght);

只有在层次结构中没有循环时才会起作用。但我想，如果有循环，那么就不清楚谁是最远的，如果你穿过循环，实例将无限增长。

 public static Employee ret;
    public static bool first = false;
    public static bool second = false;
    public static Employee closestCommonManager(Employee ceo, Employee firstEmployee, Employee secondEmployee)
    {
        // Implement me                                                
        if (ceo == null || firstEmployee == null || secondEmployee == null)
            return null;
        if (ceo.getId() == firstEmployee.getId())
            first = true;
        if (ceo.getId() == secondEmployee.getId())
            second = true;
        if (first && second)
            return ceo;
        else
        {
            foreach (Employee e in ceo.getReports())
            {
                if (ret == null)
                {
                    var r = closestCommonManager(e, firstEmployee, secondEmployee);
                    if (r != null && ret == null)
                        ret = ceo;
                }
                else
                    return ret;
            }
        }
        return null;
    }

这是我的解决方案，但由于某种原因它没有被接受:

public static Employee closestCommonManager(Employee ceo, Employee firstEmployee, Employee secondEmployee)
{
    // Implement me
    var Manager = ceo.getReports();
    Employee tempEmployee = ceo;
    foreach (var HisReporter in Manager)
    {
        if (HisReporter.Equals(firstEmployee) || HisReporter.Equals(secondEmployee))
        {
            //if one of the employees are reporting to him return manager
            tempEmployee = ceo;
        }
        else if(HisReporter.getReports().Count > 0)
        {
            //if non of the employees reporting to him check if his reporters having these employees
            tempEmployee = closestCommonManager(HisReporter, firstEmployee, secondEmployee);
        }
    }
    return tempEmployee;
}

}

这是Krzysztof Bardzinski建议的使用DFS的实现

 static void Main(string[] args)
    {
        Dictionary<int, Employee> employeeMap = new Dictionary<int, Employee>();
        Employee ceo = null, firstEmployee = null, secondEmployee = null;
        /*//Sample input
         List<string> input = new List<string>();
         input.Add("employee 1 A");
         input.Add("employee 2 B");
         input.Add("employee 3 C");
         input.Add("employee 4 D");
         input.Add("employee 5 E");
         input.Add("employee 6 F");
         input.Add("employee 7 G");
         input.Add("employee 8 H");
         input.Add("employee 9 I");
         input.Add("employee 10 J");
         input.Add("employee 11 K");
         input.Add("employee 12 L");
         input.Add("employee 13 M");
         input.Add("report 1 2");
         input.Add("report 1 3");
         input.Add("report 2 4");
         input.Add("report 2 5");
         input.Add("report 2 6");
         input.Add("report 5 7");
         input.Add("report 5 8");
         input.Add("report 6 9");
         input.Add("report 6 10");
         input.Add("report 3 11");
         input.Add("report 3 12");
         input.Add("report 3 13");
         input.Add("params 1 9 13");*/
        string line;
        while ((line = Console.ReadLine()) != null)
        {
            string[] tokens = line.Split();
            string type = tokens[0];
            if (type.Equals("employee"))
            {
                int id = int.Parse(tokens[1]);
                String name = tokens[2];
                employeeMap.Add(id, new Employee(id, name));
            }
            else if (type.Equals("report"))
            {
                Employee manager = employeeMap[int.Parse(tokens[1])];
                Employee report = employeeMap[int.Parse(tokens[2])];
                manager.addReport(report);
            }
            else if (type.Equals("params"))
            {
                ceo = employeeMap[int.Parse(tokens[1])];
                firstEmployee = employeeMap[int.Parse(tokens[2])];
                secondEmployee = employeeMap[int.Parse(tokens[3])];
            }
            else
            {
                // ignore comments and whitespace
            }
        }
        Employee result = closestCommonManager(ceo, firstEmployee, secondEmployee);
    } 
public static Employee closestCommonManager(Employee ceo, Employee firstEmployee, Employee secondEmployee)
    {
        Stack<Employee> firstManagers = new Stack<Employee>();
        Stack<Employee> secondManagers = new Stack<Employee>();
        if (ceo.getReports().Count > 0)
        {
            searchManager(ceo, firstEmployee, firstManagers);
            searchManager(ceo, secondEmployee, secondManagers);
            if (firstManagers.Contains(secondEmployee))
            {
                return secondEmployee; //closest manager as this is managing the first one
            }
            if (secondManagers.Contains(firstEmployee))
            {
                return firstEmployee; //closest manager as this is managing the second one
            }
            //check for closest match
            //make them equal in length.
            while (firstManagers.Count > secondManagers.Count)
            {
                firstManagers.Pop();
            }
            while (secondManagers.Count > firstManagers.Count)
            {
                secondManagers.Pop();
            }
            int checkCount = firstManagers.Count;
            for (int i = 0; i < checkCount; i++)
            {
                if (firstManagers.Peek().getId() == secondManagers.Peek().getId())
                {
                    return firstManagers.Pop();
                }
                else
                {
                    firstManagers.Pop();
                    secondManagers.Pop();
                }
            }
        }
        return null;
    }
    private static bool searchManager(Employee manager, Employee emp, Stack<Employee> graph)
    {
        bool res = false;
        graph.Push(manager);
        foreach (Employee e in manager.getReports())
        {
            if (e.getId() == emp.getId())
            {
                res = true;
                break;
            }
            else
            {
                if (e.getReports().Count > 0)
                {
                    if (searchManager(e, emp, graph))
                    {
                        return true;
                    }
                    else
                    {
                        graph.Pop();
                    }
                }
            }
        }
        return res;
    }
 public sealed class Employee
{
    private readonly int id;
    private readonly string name;
    private readonly List<Employee> reports;
    public Employee(int id, string name)
    {
        this.id = id;
        this.name = name;
        this.reports = new List<Employee>();
    }
    /// <returns> 
    /// an integer ID for this employee, guaranteed to be unique.
    /// </returns> 
    public int getId()
    {
        return id;
    }
    /// <returns> 
    /// a String name for this employee, NOT guaranteed to be unique.
    /// </returns> 
    public string getName()
    {
        return name;
    }
    /// <returns> 
    /// a List of employees which report to this employee.  This list may be empty, but will
    /// never be null.
    /// </returns> 
    public IList<Employee> getReports()
    {
        return reports;
    }
    /// <summary> 
    /// Adds the provided employee as a report of this employee. 
    /// </summary> 
    public void addReport(Employee employee)
    {
        reports.Add(employee);
    }
}