algoadvance

You are given two arrays: persons and times. The persons array contains integers where each integer represents a vote for a person at the corresponding time in the times array. More specifically, every entry in the persons array at index i indicates that the person persons[i] received a vote at times[i].

Implement the TopVotedCandidate class:

• TopVotedCandidate(int[] persons, int[] times) Initializes the object with the persons and times arrays.
• int q(int t) Returns the number of the person that was leading the election at time t. If there is a tie, the most recent vote (among the ties) wins.

Example:

Input:
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0,1,1,0,0,1,0], [0,5,10,15,20,25,30]], [3], [12], [25], [15], [24], [8]]

Output:
[null, 0, 1, 1, 0, 0, 1]

Explanation:
TopVotedCandidate topVotedCandidate = new TopVotedCandidate([0,1,1,0,0,1,0], [0,5,10,15,20,25,30]);
topVotedCandidate.q(3); // return 0, the votes are [0] and the leader is 0.
topVotedCandidate.q(12); // return 1, the votes are [0,1,1] and the leader is 1.
topVotedCandidate.q(25); // return 1, the votes are [0,1,1,0,0,1] the leader is 1.
topVotedCandidate.q(15); // return 0
topVotedCandidate.q(24); // return 0
topVotedCandidate.q(8); // return 1

Clarifying Questions:

1. Are the persons and times arrays always of the same length?
2. Can we assume that times array is already sorted?
3. What are the constraints on the number of entries in persons and times arrays?
4. Will the times array always contain distinct values, meaning no two votes can happen at the same time?

Strategy:

1. Initialization: To initialize the TopVotedCandidate object, we need to keep track of the cumulative votes each person has received at each time point. We’ll also record who the leader is at each point in time in a dictionary.

2. Lead Calculation: We can maintain a dictionary to count the votes for each person and keep track of the leader using another list.

3. Query (q) Method: For quickly finding the leader at any given time, we will use binary search to find the latest time that does not exceed t in the times array. The leader at that time will be the result.

Code:

from typing import List
from collections import defaultdict
import bisect

class TopVotedCandidate:
    def __init__(self, persons: List[int], times: List[int]):
        self.leading_at_time = []  # List of tuples (time, leader)
        self.times = times  # Keep the times for binary search
        vote_counts = defaultdict(int)
        leader = -1
        max_votes = 0

        for time, person in zip(times, persons):
            vote_counts[person] += 1
            
            if vote_counts[person] >= max_votes:
                if vote_counts[person] > max_votes or leader != person:
                    leader = person
                    max_votes = vote_counts[person]
            
            self.leading_at_time.append((time, leader))

    def q(self, t: int) -> int:
        idx = bisect.bisect_right(self.times, t) - 1
        return self.leading_at_time[idx][1]

# Example Usage
if __name__ == "__main__":
    topVotedCandidate = TopVotedCandidate([0,1,1,0,0,1,0], [0,5,10,15,20,25,30])
    print(topVotedCandidate.q(3))   # Output: 0
    print(topVotedCandidate.q(12))  # Output: 1
    print(topVotedCandidate.q(25))  # Output: 1
    print(topVotedCandidate.q(15))  # Output: 0
    print(topVotedCandidate.q(24))  # Output: 0
    print(topVotedCandidate.q(8))   # Output: 1

Time Complexity:

• Initialization: O(N), where N is the length of the persons or times array.
• Query (q) Method: O(log N) for the binary search to find the relevant time index.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?