CODEWITHSUNDEEP
algorithmdata-structures
user6080374
user6080374

Reputation:

Student Election Results Tallying

This is a coding interview question:

Your school is having an election and you are tasked with coding a program that tallies the results.

You are given a Set of Votes, each vote containing a candidate and a time stamp. Given a time stamp, return the top N candidates with the most votes at that timestamp. (each vote tallied must come before or at the given timestamp)

Upvotes: 4

Views: 1045

Answers (3)

RPaul
RPaul

Reputation: 66

I would do it per array

For every new date you read, you create a new subarray: lets say you get a vote from the 9th of August 2016, for which you don't have votes registered yet l, for John Doe soons as you register a vote for lets say John Doe. Your array should then be constructed like this:

array ->0->date: 09/08/2016
         ->John Doe: 1

Since I assume at an election all the names are known, we can simply save all the candidates names in another array, which we can use when we loop through this one.

Incase a new vote for John Doe on another date gets registered, your array would look like this

array ->0->date: 09/08/2016
         ->John Doe: 1
      ->1->date: 11/08/2016
         ->John Doe: 1

If someone votes for another persom on an already known date, it should look like this

array ->0->date: 09/08/2016
         ->John Doe: 1
         ->Jane Doe: 1

Hope this helps. If you want help looping through this array-structure-thingy, don't be afraid to ask :)

Upvotes: 0

Vora Ankit
Vora Ankit

Reputation: 722

Create the Min Heap and HashMap Data structure to solve this problem.

1. Cast each vote in HashMap(Candidate, Votes).

2. At any time we want to find the N top trending Candidate, Add all the HashMap keys(Candidate votes) to the min heap with restriction of N size.

3. return all the item from the min heap, which will return the top N candidate with the votes. (as min heap filter the candidate with the restriction on size N).

Upvotes: 3

technokrat
technokrat

Reputation: 235

This is probably far from the most efficient way, but I would:

  • Create a list candidateList containing each candidate and their respective number of votes (initially 0)
  • Go through the set of votes, and if a vote meets the time stamp requirement, add 1 to the candidate's votes in candidateList.
  • After you've gone through the set of votes, find the nth most popular candidate in candidateList (using a selection algorithm), and then iterate over the list to find the candidates more popular than them.

Upvotes: 0

Related Questions