CareerCup

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) {
	unordered_map<string, int> votes_per_name;
	string max_votes_name;
	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_count = it->second;
				max_votes_name = vote.name_; // O(l)
			}
		}
	}
	return max_votes_name;
}