Election Voting Machine Monitor
EasyUpdated: Aug 10, 2025
Problem
On election day, a voting machine writes data in the form (voter_id, candidate_id) to a text file. Write a program that reads this file as a stream and returns the top 3 candidates at any given time. If you find a voter voting more than once, report this as fraud.
Note: This problem builds upon [Top K Frequent Elements](top-k-frequent-elements) but adds real-time streaming and fraud detection requirements.
Examples
Example 1
Input: Stream of votes: [(1, "A"), (2, "B"), (3, "A"), (4, "C"), (5, "B")]
Output: After each vote - Top 3: ["A", "B", "C"], Fraud: None
Explanation:
- After (1,"A"): Top 3: ["A"]
- After (2,"B"): Top 3: ["A", "B"]
- After (3,"A"): Top 3: ["A", "B"] (A:2, B:1)
- After (4,"C"): Top 3: ["A", "B", "C"] (A:2, B:1, C:1)
- After (5,"B"): Top 3: ["A", "B", "C"] (A:2, B:2, C:1)
Example 2
Input: Stream of votes: [(1, "A"), (2, "B"), (1, "C")]
Output: After each vote - Top 3: ["A", "B"], Fraud: "Voter 1 voted multiple times"
Explanation: Voter 1 appears twice, so the third vote is fraudulent and should be ignored.
Example 3
Input: Stream of votes: [(1, "A"), (2, "A"), (3, "A"), (4, "B"), (5, "C"), (6, "D")]
Output: After each vote - Top 3: ["A", "B", "C"], Fraud: None
Explanation: A gets 3 votes, B gets 1, C gets 1, D gets 1. Top 3 by frequency are A, B, C.
Example 4
Input: Stream of votes: []
Output: Top 3: [], Fraud: None
Explanation: No votes processed yet.
Example 5
Input: Stream of votes: [(1, "A"), (2, "A"), (1, "A"), (3, "B")]
Output: After each vote - Top 3: ["A", "B"], Fraud: "Voter 1 voted multiple times"
Explanation: Multiple fraud attempts by voter 1, but we only need to report fraud once per voter.
Solution
Method 1 - Hash Map with Min Heap
Intuition
We need to maintain three data structures: a set to track voters (for fraud detection), a frequency map for candidates, and a min-heap of size 3 to efficiently maintain the top 3 candidates. As we process each vote in the stream, we update these structures and can quickly return the current top 3.
Approach
- Maintain a set of seen voter IDs to detect fraud
- Use a hash map to count votes for each candidate
- Use a min-heap of size 3 to track top candidates by vote count
- For each incoming vote:
- Check if voter ID already exists (fraud detection)
- If valid, update candidate frequency and heap
- Return current top 3 and any fraud alerts
Code
C++
class VotingMachine {
private:
unordered_set<int> seenVoters;
unordered_map<string, int> candidateVotes;
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<>> minHeap;
vector<string> fraudAlerts;
public:
pair<vector<string>, vector<string>> processVote(int voterId, const string& candidateId) {
// Check for fraud
if (seenVoters.count(voterId)) {
fraudAlerts.push_back("Voter " + to_string(voterId) + " voted multiple times");
return {getTop3(), fraudAlerts};
}
// Record valid vote
seenVoters.insert(voterId);
candidateVotes[candidateId]++;
// Update heap
updateHeap(candidateId, candidateVotes[candidateId]);
return {getTop3(), fraudAlerts};
}
private:
void updateHeap(const string& candidate, int votes) {
// Remove old entry for this candidate if exists
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<>> newHeap;
while (!minHeap.empty()) {
auto [count, name] = minHeap.top();
minHeap.pop();
if (name != candidate) {
newHeap.push({count, name});
}
}
// Add updated candidate
newHeap.push({votes, candidate});
// Keep only top 3
while (newHeap.size() > 3) {
newHeap.pop();
}
minHeap = newHeap;
}
vector<string> getTop3() {
vector<pair<int, string>> temp;
vector<string> result;
// Extract all from heap
while (!minHeap.empty()) {
temp.push_back(minHeap.top());
minHeap.pop();
}
// Sort by vote count descending
sort(temp.rbegin(), temp.rend());
// Restore heap and build result
for (auto [count, name] : temp) {
minHeap.push({count, name});
result.push_back(name);
}
return result;
}
};
Go
type VotingMachine struct {
seenVoters map[int]bool
candidateVotes map[string]int
fraudAlerts []string
}
func NewVotingMachine() *VotingMachine {
return &VotingMachine{
seenVoters: make(map[int]bool),
candidateVotes: make(map[string]int),
fraudAlerts: []string{},
}
}
func (vm *VotingMachine) ProcessVote(voterID int, candidateID string) ([]string, []string) {
// Check for fraud
if vm.seenVoters[voterID] {
vm.fraudAlerts = append(vm.fraudAlerts, fmt.Sprintf("Voter %d voted multiple times", voterID))
return vm.getTop3(), vm.fraudAlerts
}
// Record valid vote
vm.seenVoters[voterID] = true
vm.candidateVotes[candidateID]++
return vm.getTop3(), vm.fraudAlerts
}
func (vm *VotingMachine) getTop3() []string {
type candidate struct {
name string
votes int
}
candidates := make([]candidate, 0)
for name, votes := range vm.candidateVotes {
candidates = append(candidates, candidate{name, votes})
}
// Sort by votes descending
sort.Slice(candidates, func(i, j int) bool {
return candidates[i].votes > candidates[j].votes
})
// Take top 3
result := make([]string, 0)
for i := 0; i < len(candidates) && i < 3; i++ {
result = append(result, candidates[i].name)
}
return result
}
Java
class VotingMachine {
private Set<Integer> seenVoters;
private Map<String, Integer> candidateVotes;
private List<String> fraudAlerts;
public VotingMachine() {
seenVoters = new HashSet<>();
candidateVotes = new HashMap<>();
fraudAlerts = new ArrayList<>();
}
public Pair<List<String>, List<String>> processVote(int voterId, String candidateId) {
// Check for fraud
if (seenVoters.contains(voterId)) {
fraudAlerts.add("Voter " + voterId + " voted multiple times");
return new Pair<>(getTop3(), new ArrayList<>(fraudAlerts));
}
// Record valid vote
seenVoters.add(voterId);
candidateVotes.put(candidateId, candidateVotes.getOrDefault(candidateId, 0) + 1);
return new Pair<>(getTop3(), new ArrayList<>(fraudAlerts));
}
private List<String> getTop3() {
return candidateVotes.entrySet().stream()
.sorted((a, b) -> b.getValue().compareTo(a.getValue()))
.limit(3)
.map(Map.Entry::getKey)
.collect(Collectors.toList());
}
static class Pair<T, U> {
T first;
U second;
Pair(T first, U second) {
this.first = first;
this.second = second;
}
}
}
Python
class VotingMachine:
def __init__(self):
self.seen_voters: Set[int] = set()
self.candidate_votes: Dict[str, int] = {}
self.fraud_alerts: List[str] = []
def process_vote(self, voter_id: int, candidate_id: str) -> Tuple[List[str], List[str]]:
# Check for fraud
if voter_id in self.seen_voters:
self.fraud_alerts.append(f"Voter {voter_id} voted multiple times")
return self.get_top3(), self.fraud_alerts.copy()
# Record valid vote
self.seen_voters.add(voter_id)
self.candidate_votes[candidate_id] = self.candidate_votes.get(candidate_id, 0) + 1
return self.get_top3(), self.fraud_alerts.copy()
def get_top3(self) -> List[str]:
sorted_candidates = sorted(
self.candidate_votes.items(),
key=lambda x: x[1],
reverse=True
)
return [candidate for candidate, _ in sorted_candidates[:3]]
Complexity
- ⏰ Time complexity:
O(c log c)per vote, where c is the number of unique candidates. Sorting candidates for top 3 takes O(c log c) - 🧺 Space complexity:
O(v + c), where v is the number of voters and c is the number of candidates
Method 2 - Optimized with Min Heap of Size 3
Intuition
Instead of sorting all candidates every time, we can maintain a min-heap of exactly size 3. This gives us the top 3 candidates more efficiently. When a candidate's vote count increases, we update the heap accordingly.
Approach
- Use the same fraud detection with voter ID set
- Maintain candidate vote counts in a hash map
- Use a min-heap of size 3 to track only the top candidates
- When updating votes, carefully manage heap to maintain top 3
- Extract top 3 from heap when requested
Code
C++
class OptimizedVotingMachine {
private:
unordered_set<int> seenVoters;
unordered_map<string, int> candidateVotes;
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<>> top3Heap;
vector<string> fraudAlerts;
public:
pair<vector<string>, vector<string>> processVote(int voterId, const string& candidateId) {
// Check for fraud
if (seenVoters.count(voterId)) {
fraudAlerts.push_back("Voter " + to_string(voterId) + " voted multiple times");
return {getTop3(), fraudAlerts};
}
// Record valid vote
seenVoters.insert(voterId);
candidateVotes[candidateId]++;
// Update heap efficiently
updateTop3Heap(candidateId);
return {getTop3(), fraudAlerts};
}
private:
void updateTop3Heap(const string& candidate) {
int votes = candidateVotes[candidate];
// If heap has less than 3 elements, just add
if (top3Heap.size() < 3) {
top3Heap.push({votes, candidate});
return;
}
// Check if current candidate should be in top 3
if (votes > top3Heap.top().first) {
top3Heap.pop();
top3Heap.push({votes, candidate});
}
}
vector<string> getTop3() {
vector<pair<int, string>> temp;
// Extract from heap
while (!top3Heap.empty()) {
temp.push_back(top3Heap.top());
top3Heap.pop();
}
// Sort descending and restore heap
sort(temp.rbegin(), temp.rend());
vector<string> result;
for (auto [votes, name] : temp) {
result.push_back(name);
top3Heap.push({votes, name});
}
return result;
}
};
Go
type OptimizedVotingMachine struct {
seenVoters map[int]bool
candidateVotes map[string]int
fraudAlerts []string
}
func NewOptimizedVotingMachine() *OptimizedVotingMachine {
return &OptimizedVotingMachine{
seenVoters: make(map[int]bool),
candidateVotes: make(map[string]int),
fraudAlerts: []string{},
}
}
func (vm *OptimizedVotingMachine) ProcessVote(voterID int, candidateID string) ([]string, []string) {
// Check for fraud
if vm.seenVoters[voterID] {
vm.fraudAlerts = append(vm.fraudAlerts, fmt.Sprintf("Voter %d voted multiple times", voterID))
return vm.getTop3Optimized(), vm.fraudAlerts
}
// Record valid vote
vm.seenVoters[voterID] = true
vm.candidateVotes[candidateID]++
return vm.getTop3Optimized(), vm.fraudAlerts
}
func (vm *OptimizedVotingMachine) getTop3Optimized() []string {
if len(vm.candidateVotes) <= 3 {
return vm.getTop3()
}
// Use heap for larger datasets
h := &IntHeap{}
heap.Init(h)
for name, votes := range vm.candidateVotes {
if h.Len() < 3 {
heap.Push(h, &Candidate{name, votes})
} else if votes > (*h)[0].votes {
heap.Pop(h)
heap.Push(h, &Candidate{name, votes})
}
}
result := make([]string, 0, h.Len())
temp := make([]*Candidate, 0, h.Len())
for h.Len() > 0 {
c := heap.Pop(h).(*Candidate)
temp = append(temp, c)
}
// Reverse to get descending order
for i := len(temp) - 1; i >= 0; i-- {
result = append(result, temp[i].name)
}
return result
}
type Candidate struct {
name string
votes int
}
type IntHeap []*Candidate
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i].votes < h[j].votes }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(*Candidate))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
Java
class OptimizedVotingMachine {
private Set<Integer> seenVoters;
private Map<String, Integer> candidateVotes;
private PriorityQueue<Map.Entry<String, Integer>> top3Heap;
private List<String> fraudAlerts;
public OptimizedVotingMachine() {
seenVoters = new HashSet<>();
candidateVotes = new HashMap<>();
fraudAlerts = new ArrayList<>();
top3Heap = new PriorityQueue<>(Map.Entry.comparingByValue());
}
public Pair<List<String>, List<String>> processVote(int voterId, String candidateId) {
// Check for fraud
if (seenVoters.contains(voterId)) {
fraudAlerts.add("Voter " + voterId + " voted multiple times");
return new Pair<>(getTop3Optimized(), new ArrayList<>(fraudAlerts));
}
// Record valid vote
seenVoters.add(voterId);
candidateVotes.put(candidateId, candidateVotes.getOrDefault(candidateId, 0) + 1);
return new Pair<>(getTop3Optimized(), new ArrayList<>(fraudAlerts));
}
private List<String> getTop3Optimized() {
PriorityQueue<Map.Entry<String, Integer>> heap = new PriorityQueue<>(Map.Entry.comparingByValue());
for (Map.Entry<String, Integer> entry : candidateVotes.entrySet()) {
if (heap.size() < 3) {
heap.offer(entry);
} else if (entry.getValue() > heap.peek().getValue()) {
heap.poll();
heap.offer(entry);
}
}
List<String> result = new ArrayList<>();
List<Map.Entry<String, Integer>> temp = new ArrayList<>();
while (!heap.isEmpty()) {
temp.add(heap.poll());
}
// Reverse to get descending order
for (int i = temp.size() - 1; i >= 0; i--) {
result.add(temp.get(i).getKey());
}
return result;
}
}
Python
class OptimizedVotingMachine:
def __init__(self):
self.seen_voters: Set[int] = set()
self.candidate_votes: Dict[str, int] = {}
self.fraud_alerts: List[str] = []
def process_vote(self, voter_id: int, candidate_id: str) -> Tuple[List[str], List[str]]:
# Check for fraud
if voter_id in self.seen_voters:
self.fraud_alerts.append(f"Voter {voter_id} voted multiple times")
return self.get_top3_optimized(), self.fraud_alerts.copy()
# Record valid vote
self.seen_voters.add(voter_id)
self.candidate_votes[candidate_id] = self.candidate_votes.get(candidate_id, 0) + 1
return self.get_top3_optimized(), self.fraud_alerts.copy()
def get_top3_optimized(self) -> List[str]:
import heapq
if len(self.candidate_votes) <= 3:
return sorted(self.candidate_votes.keys(),
key=lambda x: self.candidate_votes[x],
reverse=True)
# Use min heap of size 3
heap = []
for candidate, votes in self.candidate_votes.items():
if len(heap) < 3:
heapq.heappush(heap, (votes, candidate))
elif votes > heap[0][0]:
heapq.heapreplace(heap, (votes, candidate))
# Extract and sort descending
result = []
temp = []
while heap:
temp.append(heapq.heappop(heap))
# Reverse to get descending order
for votes, candidate in reversed(temp):
result.append(candidate)
return result
Complexity
- ⏰ Time complexity:
O(log 3) = O(1)per vote for heap operations, much better than the O(c log c) sorting approach - 🧺 Space complexity:
O(v + c), where v is the number of voters and c is the number of candidates, with the heap maintaining only 3 elements