Uber Interview Question
Software EngineersTeam: Seattle
Country: United States
Interview Type: Phone Interview
We maintain 2 hashes:
* First hash keep track of voters - this is to check for fraud
* Second hash: candidate->voters-count - we keep track of the number of votes for each candidate
In addition we use a class that keep maps between: votes=>hash of candidates
Every time we add a vote, we go and update this class
The below solution is a bit complicated because it assumes that the number of candidates can be the same as the number of voters...
If we could assume that the number of candidates is small we could simply sort the candidates array at the end (using priority_queue where the "voters-count" is the priority) and just pop the first top 5 from the queue:
Complex code, assuming number of candidates can be the same as the number of voters:
#include "CommonHeader.h"
#define TOP_LIST_MAX 5
// Unique hash to remember voters ID - insert/find O(1)
static std::unordered_set<int> VotersHash;
// Hash table to keep track for each candidate voters count
static std::unordered_map<int, int> Candidates;
struct TopCandidates {
// voters:{candidate-hash}
// We use "map" here because it uses BST (balanced) so the key is always sorted in ascending order
std::map<int, std::unordered_set<int> > _topVotes;
// Candidates in the top 5 list. There can be more than 5, since some candidates might get the same number of votes
std::unordered_set<int> _candidates;
/**
* @brief try to add candidate to the top 5 list
*/
void addCandidate(int candidateID, int voters)
{
if(_candidates.count(candidateID)) {
// already in the top 5.
// Move it from _topVotes[voters-1] -> _topVoters[voters]
_topVotes[voters - 1].erase(candidateID);
if(_topVotes[voters - 1].empty()) {
_topVotes.erase(voters - 1);
}
_topVotes[voters].insert(candidateID);
// If the top-5-list exceeds the maximum entries (i.e. 5)
// remove the entry with the least votes (and since we use std::map
// we know it's the first entry _topVotes.begin() )
if(_topVotes.size() > TOP_LIST_MAX) {
_topVotes.erase(_topVotes.begin());
}
} else if(_candidates.empty()) {
// No entries in list, just add it
_topVotes[voters].insert(candidateID);
_candidates.insert(candidateID);
} else {
// first time we see this candidate. this means that "voters" is 1
int minVotersInTheMap = _topVotes.begin()->first;
if((minVotersInTheMap == 1) || _topVotes.size() < TOP_LIST_MAX) {
_topVotes[voters].insert(candidateID);
_candidates.insert(candidateID);
}
}
}
void print()
{
std::for_each(
_topVotes.rbegin(), _topVotes.rend(), [&](const std::map<int, std::unordered_set<int> >::value_type& vt) {
const std::unordered_set<int>& candidates = vt.second;
std::cout << "Votes: " << vt.first << ", Candidates:";
std::for_each(
candidates.begin(), candidates.end(), [&](int candidateID) { std::cout << " " << candidateID; });
std::cout << std::endl;
});
}
};
static TopCandidates topCandidates;
bool addVote(int candidateID, int voterID)
{
if(VotersHash.count(voterID)) {
std::cout << "Voter ID: " << voterID << " already voted !! Fraud detected!!" << std::endl;
return false;
}
VotersHash.insert(voterID);
if(Candidates.count(candidateID) == 0) {
// first time
Candidates.insert(std::make_pair(candidateID, 0));
}
int& voters = Candidates[candidateID];
++voters;
topCandidates.addCandidate(candidateID, voters);
return true;
}
If we can assume that the number of candidates is small, we can remove the class TopCandidates class and use priority queue:
std::priority_queue<std::pair<int, int> > Q;
std::for_each(Candidates.begin(), Candidates.end(), [&](const std::pair<int, int>& p) {
// "p" contains: candidate-id:voter
// we want to to add the queue voters:candidate-id
std::pair<int, int> qentry = p;
std::swap(qentry.first, qentry.second);
Q.push(qentry);
});
size_t i = 0;
int prevVoters = INT_MAX;
while(!Q.empty() && i < TOP_LIST_MAX) {
const std::pair<int, int>& qentry = Q.top();
if(prevVoters != qentry.first) {
prevVoters = qentry.first;
++i;
}
std::cout << "#" << i << " candidate-id: " << qentry.second << " with " << qentry.first << " votes"
<< std::endl;
Q.pop();
}
Simple implementation in C++: (assuming cID and vID to be int)
1. create a set<pair<int,int>> S and an unordered_map<int,bool> visited.
2. If current cID present in S then update count by erasing the entry and inserting again with count+1. Otherwise insert with count 1.
3. Mark vID as visited.
4. Query for top 5 candidates.
}
I was wondering if this might be simpler than the proposed solution above:
- Anonymous April 09, 20181. Keep a set of voter IDs to prevent fraud. If an already seen Voter ID is seen again, raise a red flag i.e. Logger statement
2. Use a hash map { Key: Candidate ID, Value: Vote Count } to track # of votes.
2a. Also, use a minHeap of Size = 5 to maintain in real time the top 5 candidates. Populate it initially with dummy candidate of vote count = 0
Every time there is a new candidate is inserted into the hash map, add it in the minHeap if and only if the vote count of the candidate is greater than that of the top of the minHeap.