3
\$\begingroup\$

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)\$?

\$\endgroup\$
  • \$\begingroup\$ You already know that everything in sorted_votes is in candidates. Why not "for sorted_votes" k times instead of "for candidates"? \$\endgroup\$ – Frank Merrow Feb 12 at 3:37
  • \$\begingroup\$ @FrankMerrow Yes, but how efficient it is to find the key of particular value in the hash table? \$\endgroup\$ – kgangadhar Feb 12 at 4:47
  • \$\begingroup\$ Is there any other thing I can do to change the time taken. \$\endgroup\$ – kgangadhar Feb 12 at 4:48
  • \$\begingroup\$ Welcome to CodeReview@SE. What is timestamp duration? \$\endgroup\$ – greybeard Feb 12 at 7:18
  • 2
    \$\begingroup\$ (I do not want to know one/the value to use: I have no idea how to interpret it just from the problem description. I think one timestamp to mark one point in time, a duration could be specified by two timestamps. Then, there is before and after.) \$\endgroup\$ – greybeard Feb 12 at 8:42
5
\$\begingroup\$

So, you want to count something and afterwards get the top k? That sounds like a job for collections.Counter!

from collections import Counter

def leading_candidates(votes, timestamp, k):
    vote_counts = Counter(vote['candidate']
                          for vote in votes
                          if vote['timestamp'] <= timestamp)
    return [candidate[0] for candidate in vote_counts.most_common(k)]


if __name__ == "__main__":
    print(leading_candidates(votes, timestamp, 2))

This way you don't need to special case a candidate not yet having received a vote (something you could have also done with a collections.defaultdict(int)). And it is \$\mathcal{O}(n)\$.

Also note that if k is large, the line if candidates[candidate] in sorted_votes will become slow, as it is a linear scan. At the same time, you can iterate over the keys and values of a dictionary at the same time with candidates.items(), so you don't need to do candidates[candidate].

Python has an official style-guide, PEP8, which recommends using spaces after commas, which you forgot to do before k in the function signature.

You should always guard your code with an if __name__ == "__main__": guard to allow importing from the script without running it.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Counter.most_common() uses a heap so it is O(k log h), where h is the total number of candidates (e.g., the size of the heap). Of course for most uses, neither k nor h are large. \$\endgroup\$ – RootTwo Feb 12 at 23:18
  • \$\begingroup\$ @RootTwo True. And log h < n and k is constant. But filling the Counter is still O(n). \$\endgroup\$ – Graipher Feb 12 at 23:21
  • \$\begingroup\$ @RootTwo Yup, Counter.most_common() uses a heap; more specifically, it uses heapq.nlargest(). Which according to stackoverflow.com/a/23038826 and stackoverflow.com/a/33644135 it actually has a time complexity of O(h log k), where h is the total number of candidates. \$\endgroup\$ – Setris Feb 13 at 1:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.