Election Voting Machine Monitor

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 but adds real-time streaming and fraud detection requirements.

Examples

Example 1

1
2
3
4
5
6
7
8


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

1
2
3


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

1
2
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

1
2
3


Input: Stream of votes: []
Output: Top 3: [], Fraud: None
Explanation: No votes processed yet.

Example 5

1
2
3


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70


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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


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;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63


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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


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

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Example 4#

Example 5#

Solution#

Method 1 - Hash Map with Min Heap#

Intuition#

Approach#

Code#

Complexity#

Method 2 - Optimized with Min Heap of Size 3#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Example 1

Example 2

Example 3

Example 4

Example 5

Solution

Method 1 - Hash Map with Min Heap

Intuition

Approach

Code

Complexity

Method 2 - Optimized with Min Heap of Size 3

Intuition

Approach

Code

Complexity