Алгоритм собеседования?

Question

ОБНОВЛЕНИЕ: Кто-нибудь может ответить на мой последний комментарий по n. 'местоимения' м. ответ?

Обратите внимание: я спрашивал об этом раньше, но это был полный беспорядок, поэтому я пишу его с более подробной информацией и в исходной форме.

Вопрос:

Я управляю системой голосования между N участниками (каждый проиндексирован от 1 до N), где я хочу поддерживать следующие функции:

1. Init (N) - инициализировать структуру данных. -O (1)
2. Голосование (j, i) - добавьте в таблицу результатов, что человек j проголосовал (ровно 1) за человека i - где не разрешено кому-либо голосовать самому. -O (1)
3. Голосующие (i) - возвращает количество людей, проголосовавших за i. -O (1)
4. Происхождение (j) - возвращает количество голосов, которые человек j отдал другим. -O (1)
5. В избранном (k) - вывести участников с наибольшим числом голосов (в порядке убывания) в соответствии с количеством полученных ими голосов. -Хорошо)
6. Avoided () - вывести всех участников, не получивших голосов. -O (r) где r - количество напечатанных участников

В этом вопросе сложность пространства должна быть O (N) .

Разрешено использование только массивов и (двусвязных) списков.

---

Что я сделал? Я решил 1–4 так легко, просто объявив массив размером N и каждая ячейка содержит значения; gotи sent. когда iголоса за « jЯ» увеличиваются, получено jи отправлено значение на iединицу.

До сих пор я не знаю, как решить 5 и 6 в требуемой сложности.

Примечание: я ищу алгоритм / идею, а не реальный код.

Answer 1

Обратите внимание, что для каждой операции кандидат, за который проголосовали, увеличивал свой балл ровно на единицу.

Это открывает новую стратегию - вместо того, чтобы сопоставлять кандидата с его оценкой, сопоставьте оценку со списком кандидатов с этой оценкой.

Это может быть реализовано довольно просто как список кандидатов в списки: (в шаблоне, подобном синтаксису:) list<list<Candidate>>.

Кроме того, сохраните массив, сопоставляющий каждый номер кандидата с указателем фактического Candidateэлемента.

Список кандидатов с 0 будет изначально неявно установлен для всех кандидатов, аналогично тому, как вы инициализируете массив в O (1) .

• Когда подан голос:

1. Вы найдете кандидата по ссылке: O (1)
2. Вы удаляете его из текущего списка и добавляете в следующий список: O (1)
3. Для поддержки Avoided()в O(r): Если количество элементов в списке «0» меньше половины, изменить его , чтобы быть обычный список вместо этого.
4. Если предыдущий элемент, представляющий оценку, теперь не имеет кандидатов, отбросьте его и напрямую свяжите предыдущую оценку со следующей (т. Е. Если нет кандидата с оценкой 3, подключитесь 2<->4). Это обеспечивает O(n)пространство за счет не слишком большого количества пустых узлов списка.

• Получить topK теперь легко, и это можно сделать O(k), перебирая список оценок от конца до начала (остановка после вывода kкандидатов)
• Избегать теперь можно, O(n) = O(r)если было исключено более половины кандидатов, или O(r)иным образом благодаря оптимизации (3) при вставке.

Answer 2

Вот альтернативный способ реализации Avoided (). Свяжите два числа с каждым человеком, за которого проголосовали: начало и конец анализа. Первоначально все элементы установлены в None(это можно сделать с помощью трюка инициализации массива O (1)).

Когда за человека mголосуют впервые, обновите startOfRunи endOfRunмассивы:

if startOfRun[m-1] != None and startOfRun[m+1] == None
   endOfRun[startOfRun[m-1]] = m
else if startOfRun[m-1] == None and startOfRun[m+1] != None
   startOfRun[endOfRun[m+1]]
else if startOfRun[m-1] != None and startOfRun[m+1] != None
   endOfRun[startOfRun[m-1]] = endOfRun[m+1]
   startOfRun[endOfRun[m+1]] = startOfRun[m-1]
else
   startOfRun[m] = m
   endOfRun[m] = m

(краевые условия для краткости опущены).

Теперь у вас есть прогоны людей, за которых проголосовали, и вы можете легко пройти от начала до конца каждого прогона. Все числа внутри прогонов неверны, но нас это не волнует. Есть O (r) прогонов, поэтому вы можете пропустить всех, за кого проголосовали O (r).

---

Вот альтернативный способ реализации Favored (). Имейте два массива: (1) расширяющийся массив людей, отсортированных по количеству очков, и (2) карту от баллов до индекса последнего человека в первом массиве, имеющего балл не ниже этого (если такого человека нет, то None) . Первоначально первый массив пуст, а второй содержит Nones. Пример:

(array 1)
(index)       1 2 3 4 5 6 7 8 9
person        3 6 5 1 4 2 8 9 7
score         7 7 7 5 5 3 2 2 2

(array 2)
score         1 2 3 4 5 6 7 8 9
index in 1st  9 9 6 5 5 3 3 - -

Когда человек голосует впервые, он добавляется в конец массива со значением 1 и array2[1]обновляется. Как только за человека снова проголосуют, он заменяется первым человеком в массиве, имеющим такой же балл, балл увеличивается, а второй массив обновляется (нам нужно обновить только один элемент, тот, который соответствует новому Гол).