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.
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]
- 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.
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]