I need to write a method that will accept a timestamp and takes an array of votes, I need to return the k
leading candidates with that timestamp. I came up with the following solution,
Here is the input to the methods:
votes = [{'candidate':'a', 'timestamp':2},{'candidate':'c', 'timestamp': 5},{'candidate':'c', 'timestamp': 12}]
timestamp = 5
k = 5
And the method to solve the problem,
def leading_candidates(votes, timestamp,k):
candidates = {}
leading_candidates = []
for vote in votes:
if vote['timestamp'] <= timestamp:
if vote['candidate'] not in candidates:
candidates[vote['candidate']] = 1
else:
candidates[vote['candidate']] += 1
sorted_votes = sorted(candidates.values())[:k]
for candidate in candidates:
if candidates[candidate] in sorted_votes:
leading_candidates.append(candidate)
return leading_candidates
print(leading_candidates(votes, timestamp, 2))
As you can see the second solution has a time complexity of \$O(k\,n)\$ where k is the time it takes to find the index in the leading candidates sorted array, In the worst case, it can be \$O(n^2)\$ and because of sorting it may be at least \$O(n\,\log n)\$.
Is there any way we can make it work with \$O(n)\$?
timestamp duration
? \$\endgroup\$