510. Design a data structure for 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.

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]