Uber Interview Question for Software Engineers


Team: Seattle
Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
3
of 3 vote

I was wondering if this might be simpler than the proposed solution above:
1. 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.

- Anonymous April 09, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- PenChief October 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

}

- rexwulf October 01, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More