## Google Interview Question for SDETs

Country: United States

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

For the first question, just travers the vote list and if vote.T <= T increment
the vote for person vote.Name. While doing that maximize the vote number.
(O(n*l) time, O(c*l) space, c is the number of candidates, l is average length of name)

follow-up 1: instead of maximizing one, keep the hashtable with votes[person] = no. votes
now, put that into a vector and find the k-th element (using e.g. quicksort's partion
method which is linear)
(O(n*l) time, O(c*l) space)

follow-up 2: I assume given are the top K candidates at a certain time T I have to find.
I have to keep all candidates sorted at each step and compare the top k of them with
the given list. The first part (keeping candidates sorted at each step) can be done
using a balanced binary-tree, so I have O(n*lg(n)+n*l) for creating and maintaining that tree.
(I will have to transpose the name into an integer, and have a nameId instead of the
string in the tree)
Then I would have k compare's per iteration, which is then O(k*n*lg(n)+n*l). the factor k
I can get rid of if I implement the tree in a way, so I monitor when elements enter and
leave the top k. If one of the desired candidates enters top k, I reduce the amount of
candidates I need in top k, if one leaves, I increment back. If that counter (which
starts with k) is 0 I'm done, I found the first time where the desired condition happend.

``````#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

struct Vote
{
int time_;
string name_;
};

string find_top_at_time(const vector<Vote>& votes, int time) {
int max_votes_count = -1;
for (const Vote& vote : votes) { // O(n)
if (vote.time_ <= time) {
auto it = votes_per_name.find(vote.name_); // O(l)
if (it == votes_per_name.end()) {
it = votes_per_name.insert({ vote.name_, 0 }).first; // O(l) compensated
}
it->second++;
if (it->second > max_votes_count) {
max_votes_name = vote.name_; // O(l)
}
}
}
}``````

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.

### 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.