Online Election

Companies:
  • Google Interview Questions

Problem Statement

In an election, the i-th vote was cast for persons[i] at time times[i].

Now, we would like to implement the following query function: TopVotedCandidate.q(int t) will return the number of the person that was leading the election at time t.  

Votes cast at time t will count towards our query.  In the case of a tie, the most recent vote (among tied candidates) wins.

Sample Test Case

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: 
At time 3, the votes are [0], and 0 is leading.
At time 12, the votes are [0,1,1], and 1 is leading.
At time 25, the votes are [0,1,1,0,0,1], and 1 is leading (as ties go to the most recent vote.)
This continues for 3 more queries at time 15, 24, and 8.

Problem Solution

Calculating the first place is very simple. Just record the current highest vote. If the number of votes of that candidate is greater than or equal to that after the vote is updated, that is the current highest vote.
More challenging is how to record, which will affect the subsequent query stage.
It is impractical to use an array to store all the time because it will exceed the available memory space. The first place will be updated only when there is a vote, so you can only record the time point of the update.
The first place to find the time required:
Because step one refers to the first place at the time of the record update, given a time, we have to compare the time of the last update and return the first place at that time.
This can use the upper_bound function.
It should be noted that the value found by upper_bound has to be reduced by one. So if we initialize this with TopVotedCandidate([0,1,1,0,0,1,0], [0,5,10,15,20,25,30]), then call q() like: q(3), q(12), q(25), q(15), q(24), q(8), then the result will be [0, 1, 1, 0, 0, 1] for each call of q(). This is because at time 3, the votes are [0], and 0 is leading. At time 12, the votes are [0,1,1], and here 1 is leading. At time 25, the votes are [0,1,1,0,0,1], and 1 is leading (as ties go to the most recent vote.). This continues for 3 more queries at time 15, 24, and finally 8.

Complexity Analysis

Time Complexity: O(n) since we are going through the entire once.

Space Complexity: O(n) since we are using map to store our values.

Code Implementation

#include <bits/stdc++.h>
using namespace std;
class TopVotedCandidate {
   public:
   map <int, int> m;
   map <int, int> count;
   TopVotedCandidate(vector<int>& persons, vector<int>& times) {
      int lead = -1;
      for(int i = 0; i < times.size(); i++){
         int x = times[i];
         count[persons[i]]++;
         if(count[lead] <= count[persons[i]]){
            lead = persons[i];
            m[x] = lead;
         }else{
            m[x] = lead;
         }
      }
   }
   int q(int t) {
      return ((--m.upper_bound(t)) -> second);
   }
};
int main(){
   vector<int> v1 = {0,1,1,0,0,1,0}, v2 = {0,5,10,15,20,25,30};
   TopVotedCandidate ob(v1, v2);
   cout << (ob.q(3)) << endl;
   cout << (ob.q(12)) << endl;
   cout << (ob.q(25)) << endl;
   cout << (ob.q(15)) << endl;
   cout << (ob.q(24)) << endl;
   cout << (ob.q(8)) << endl;
}

 

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]