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

Если я все понимаю, 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 раз. Однако есть определенно более эффективные ответы.