0

我在一次采访中被问到这个问题。

我一直试图为这个问题找到一个优雅的算法，但一直没能做到。

给定具有以下技能的人员列表（表示为数字 - id）：

C : 1, 8, 12, 14

C++：3、7、8、12、15

perl：1、2、3、8

红宝石 : 14, 23

给定技能列表，返回与所需技能集匹配的 id：

[例如]

技能组合：C & C++ 答案是 8,12

技能组合：C、C++、Perl - 匹配至少 2 项技能 答案是 1、3、8、12

id 的列表最初是未排序的，但我从排序开始。天真的方法是获取一个列表（例如第二个示例的 c++）并将其与使用排序顺序的另一个列表（例如 Java）进行比较。

有没有算法或更好的方法？

4

2 回答 2

0

取决于技能的数量。如果它很小，我会使用素数。更确切地说：创建表skills[n]（其中 n 是用户数）。1用s填充它。然后，如果用户知道第一个技能（在这种情况下为 C）乘以第一个素数 (2)，如果他知道第二个技能乘以第二个素数，等等。

然后，如果您想查找用户是否i知道第二技能（C++），只需检查是否skills[i]%3==0

例子：求技能值：用户1知道技能1（C）和技能3（Perl），也就是说他的技能值是1*2*5=10。用户2知道技能3，所以他的技能值为1*5。

查找所有可以使用 C、C++、Perl 匹配 2 的用户：

for(int i=0;i<n;i++){
    int howMany=0;
    if(skill[i]%2)==0)
        howMany++;
    if(skill[i]%5)==0)
        howMany++;
    if(skill[i]%7)==0)
        howMany++;
    if(howMany>=2)
        addToResult(i);
 }

或者，您可以创建一个二维数组，其中列对应于人员，行对应于技能。如果值设置为 1，则表示人们知道如何使用该技能，如果设置为 0，则表示不知道。然后，只需添加您需要的所有行的值，并找到合适的用户。

例子：

 C    1 | 0 | 0 |
 C++  0 | 0 | 1 |
 PERL 1 | 1 | 1 |

让我们找一个懂 C、Perl 的人 - 我们将第 1 行和第 3 行的所有值相加，我们得到

 SUM  2 | 1 | 1 |

只有第 1 列的值 >=2，这意味着它是唯一符合标准的列。现在，让我们尝试寻找使用 C、C++ 和 PERL 的人，匹配 2

SUM  2 | 1 | 2

我们现在知道用户 1 和用户 3 的总和值 >=2，因此它们满足这些条件。

于 2014-02-09T04:56:38.277 回答
0

这是执行此操作的有效算法：-

  1. 为每个技能使用 id 的 HashSet
  2. 要检查一个 id 是否有技能，只需检查 HashSet

笔记：

该算法是人数，O(n*S)是所需技能的数量。我不认为有更快的算法。nS

编辑：

除了搜索所有 n 个人之外，您还可以只与至少具有所需技能中的一项技能的人进行检查。在许多情况下，这将为您节省大量计算时间。

于 2014-02-09T05:32:00.203 回答