Алгоритм соответствия набора навыков

Question

Мне было предложено это в интервью.

Я пытался найти элегантный алгоритм для этой проблемы, но не смог этого сделать.

Учитывая список людей (представлено в виде чисел - идентификаторы) с их набором навыков следующим образом:

C: 1, 8, 12, 14

C++: 3, 7, 8, 12, 15

Perl: 1, 2, 3, 8

Ruby: 14, 23

Учитывая список навыков, возвращает идентификатор, соответствующий необходимый набор навыков:

[EG]

навык набора: C & C++ Ответ 8,12

навык набор: C, C++, Perl, - соответствие по крайней мере 2 навыки Ответ: 1, 3, 8, 12

Список идентификаторов был первоначально несортирован, но я начал с сортировки их. Наивный подход состоял бы в том, чтобы взять один список (например, C++ для второго примера) и сравнить его с другим списком (например, Java), используя отсортированный порядок.

Есть ли алгоритм или лучший подход?

Answer 1

Зависит от количества навыков. Если он мал, я бы использовал простые числа. Более точно: Создать таблицу skills[n] (где n - количество пользователей). Заполните его 1 s. Затем, если пользователь знает первое умение (в данном случае C) умножить на первое простое число (2), если он знает второе умение умножить на второе простое число и т. Д.

Затем, если вы хотите найти, если пользователь i знает, второе умение (C++), просто проверить, если skills[i]%3==0

Пример: Finding значение умение: пользователь 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); 
} 

---

В качестве альтернативы, вы можете создать 2d массив, где столбец соответствует человеку и грести к умению. Если значение равно 1, это означает, что человек знает, как использовать навык, если он установлен в 0, они этого не делают. Затем просто добавьте valus всех строк, которые вам нужны, и найдите подходящего пользователя.

Пример:

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, так что они соответствуют этим критериям.

Answer 2

Вот эффективный алгоритм для выполнения его: -

1. Используйте HashSet из идентификаторов для каждого навыка
2. Чтобы проверить, если идентификатор имеет навык просто проверить в HashSet

Примечание:

Th является алгоритм O(n*S), где n - это число человек, S - это необходимое количество навыков. Я не думаю, что есть более быстрый алгоритм.

Edit:

Вместо того, чтобы искать для всех русских людей вы также можете проверить только с людьми, которые в меньшей мере одной из навыков необходимого набора. Во многих случаях это сэкономит вам много времени на вычисление.