4
\$\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\$
6
  • \$\begingroup\$ You already know that everything in sorted_votes is in candidates. Why not "for sorted_votes" k times instead of "for candidates"? \$\endgroup\$ Commented Feb 12, 2020 at 3:37
  • \$\begingroup\$ @FrankMerrow Yes, but how efficient it is to find the key of particular value in the hash table? \$\endgroup\$
    – kgangadhar
    Commented Feb 12, 2020 at 4:47
  • \$\begingroup\$ Is there any other thing I can do to change the time taken. \$\endgroup\$
    – kgangadhar
    Commented Feb 12, 2020 at 4:48
  • \$\begingroup\$ Welcome to CodeReview@SE. What is timestamp duration? \$\endgroup\$
    – greybeard
    Commented Feb 12, 2020 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
    Commented Feb 12, 2020 at 8:42

2 Answers 2

6
\$\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.

\$\endgroup\$
3
  • \$\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
    Commented Feb 12, 2020 at 23:18
  • \$\begingroup\$ @RootTwo True. And log h < n and k is constant. But filling the Counter is still O(n). \$\endgroup\$
    – Graipher
    Commented Feb 12, 2020 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
    Commented Feb 13, 2020 at 1:42
0
\$\begingroup\$

It took some time but finally, I understood how we can solve this in O (n).

Since the vote counts are Integers we can use bucket sort or in the worst case, we can use radix sort to sort the leading candidates and the resulting time complexity will be O(n).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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