Найти отметку времени с учетом K лучших кандидатов - PullRequest
Новая
       24

Найти отметку времени с учетом K лучших кандидатов

0 голосов
/ 28 мая 2018

Итак, меня спросили о странной инверсии задачи о лучших кандидатах.Обычная проблема заключается в следующем.

Учитывая список «голосов», которые являются кортежами временных отметок и кандидатов, как показано ниже: 

(111111, Clinton)
(111111, Bush)
...

Верните лучших K кандидатов с наибольшим количеством голосов.

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

В конце вы возвращаете кучу.

Но в конце меня спросили: учитывая список из K кандидатов, верните метку времени, которая соответствует этим, как K лучших кандидатов.Я не уверен, правильно ли я повторяю вопрос на 100%, потому что это должно было бы быть первым появлением этих кандидатов в К, как лучших, или мне бы подсчитали их голос.

1 Ответ

0 голосов
/ 28 мая 2018

Если я все понимаю, votes - это список наборов голосов, состоящих из кандидатов, за которых голосуют, и отметки времени проведения голосования.currTime - это отметка времени всех голосов за эту отметку до нее.topCandidates - это кандидаты, набравшие наибольшее количество голосов currTime.

Ваш первый вопрос дает вам votes и currTime, ожидается, что вы вернете topCandidates.Ваш второй вопрос дает вам votes и topCandidates, и ожидается, что вы вернете currTime.

Сосредоточив внимание на втором вопросе, я бы сделал карту, где ключи - это отметка времени, а значениявсе голоса проходят в тот момент.Также я бы создал другую карту, где ключ - это кандидат, а значение - это количество голосов, которые у них есть.Я бы пересек первую карту в порядке возрастания меток времени первой карты, получил бы все голоса, которые были отданы за метку времени, и увеличил бы значения второй карты на их кандидата (ключ).Прежде чем перейти к следующей временной отметке, я бы создал список наиболее проголосовавших за кандидатов с данными на второй карте.Если этот список соответствует topCandidates, то последняя отметка времени, через которую вы прошли, - currTime.

Чтобы кодировать это в python: 

from collections import Counter, defaultdict
def findCurrTime(votes, topCandidates):
    if not (votes and topCandidates):
        return -1
    votesAtTime = defaultdict(list)
    candidatePoll = Counter()
    k = len(topCandidates)
    for time, candidate in votes: # votes = [(time0, candidate0), ...]
        votesAtTime[time].append(candidate)
    for ts in votesAtTime:
        candidatePoll += Counter(voteAtTime[ts])
        if list(map(lambda pair: pair[0],candidatePoll.most_common(k))) == topCandidates:
            return ts
    # if topCandidates cannot be created from these votes:
    return -1

Есть некоторые предположения, которые я сделал(об этом вы, надеюсь, спросили своего интервьюера).Я предположил, что порядок topCandidates имеет значение, с которым Counter.most_common обработан, хотя он не будет обрабатывать кандидатов с количеством голосов.

Сложность по времени составляет O (t * n * log (k)), где t - количество временных отметок, n - количество голосов, а k - размер topCandidates.Это потому, что Counter.most_common выглядит как O (n * log (k)) и может запускаться t раз.Хотя, безусловно, есть более эффективные ответы.

...