Candidate Voting Problem

Given candidates standing for an election, design a data structure that can support the following modules – 

1. voteCandidate (candidateName) – Add one vote for the candidate.

2. getTopK ( k ) – This will return top K candidates at that time. It can return more than k candidates if more candidates have the same score. 

Example:

Vote to Sam
Vote to Sam
Vote to Sam
Vote to Bob
Vote to Sam
Vote to Bob
Vote to Carl
Vote to Dow

Output:
Top 2 candidates are: [Sam, Bob]
Top 1 candidates are: [Sam]
Top 3 candidates are: [Sam, Bob, Carl, Dow]

Approach:

  • Use two maps, Hashmap and TreeMap. 
  • Construct a Hashmap with the candidate as key and their votes as value, call it as candidateMap.
  • Construct a Treemap with votes as key and list of candidates with that score as value, call it as rankMap. Override treemap compare function to maintain the key in decreasing order.
  • voteCandidate (String candidateName) If candidate is present in candidateMap 
    • If yes then get the present votes, get new votes = present votes + 1. Update the candidate in candidateMap with new votes. Update the rankMap by removing the player from the present votes candidate list and  add it to the new votes candidate list.
    • If No then add candidate in candidateMap with vote count = 1. Add the candidate in rankMap against key 1.
  • getTopCandidate(int k) – Initialize an empty list. Iterate through keys in rankMap and add candidates to the list. Keep counting the candidates from the list. Add until count is < k.

Complete Code:

Output:

Vote to Sam
Vote to Sam
Vote to Sam
Vote to Bob
Vote to Sam
Vote to Bob
Vote to Carl
Vote to Dow
Top 2 candidates are: [Sam, Bob]
Top 1 candidates are: [Sam]
Top 3 candidates are: [Sam, Bob, Carl, Dow]