我应该使用什么数据结构/算法-面试问题

Question

在一次面试中，我得到了如下的编码练习-

我们定义了人与人之间的直接关系:如果人的全名和/或地址相等(区分大小写)，则人A与人B直接相关。

我们定义了人A和人B之间的n层关系--如果你能在n个直接关系中从人A到人B。

我被要求用两个fuinctions实现一个实用程序：

void init(Person[] persons) -使用persons实例初始化实用程序。

int FindMinRelationLevel(Person personA, Person personB) -返回personA和personB之间关系的最小级别。如果他们不是亲戚-返回-1。

他们没有给我任何运行时间的限制-它能在线性时间完全解决吗？我想到的init函数是在O(n^2)中运行的，因为每个人都能得到他所有的“邻居”或类似的东西。

我试着用字典来映射所有的数据，但把自己弄得一团糟。举办的课程如下：

class Person
{
    public Name FullName { get; set; }
    public Address Address { get; set; }
}

class Name
{
    public string FirstName { get; set; }
    public string LastName { get; set; }

    public override string ToString()
    {
        return FirstName + " " + LastName;
    }
}

class Address
{
    public string Street { get; set; }
    public string City { get; set; }

    public override string ToString()
    {
        return Street + " " + City;
    }
}

Answer 1

我将使用两个String -> List<Person>映射，一个映射每个地址到该地址的人员列表，另一个映射每个名称到具有该名称的人员列表。

这允许您在预期中使用广度优先搜索算法(因为映射和集合可能是哈希表) O(N)时间。

请注意，为了实现这一目标，除了避免重访人员之外，您还需要避免重新访问姓名和地址列表。