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

Question

我在求职面试中接受了这个编码练习，如下所示-

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

我们定义了人 A 和人 B 之间的 n 级关系 - 如果你可以在恰好 n 个直接关系中从人 A 到达人 B。

我被要求实现一个具有 2 个功能的实用程序:

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> 的两张 map ，一个将每个地址映射到该地址的人员列表，一个将每个名称映射到具有该名称的人员列表。

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

请注意，要达到这个时间，除了要避免再次访问人员外，还需要避免重新访问姓名和地址列表。