I was recently asked this in an interview.

Given below are the the candidates and the time at which they got a vote.

Q. Given a time, print the person winning till that time.

Cand. Time

A 4

B 10

C 15

C 18

C 21

B 35

B 40

B 42

E.g In the Qsn above, if we are asked to find the winner at time 20, answer would be C -> Since C has 2 votes.

Tried Solution

Have a Map<String, List> to store Map<Candidate, [Time, votes]>

We can iterate through the array & fetch only the times which are less than 20 (as per the question).

But I believe there will be a more optimum way to solve this type of problem. Essentially store the given data in a proper Data Structure which will give us the result in optimum time.

Thanks

CodePudding user response：

This is an O(N) solution, I'm assuming you have in input 2 arrays one for candidates and one for times. Who will win if there are the same amount of votes is not clear so in this case the first wins.

public Optional<Character> findCandidateWithMaxVotes(Character[] candidates, int[] times, int timeLimit) {
    Character cadidateWithMaxVotes = null;
    int max = 0, count = 0;
    Map<Character, Integer> numberOvVotesForCandidate = new HashMap<>();
    for(int i = 0; i < times.length; i  ) {
        if(times[i] <= timeLimit) {
            count = numberOvVotesForCandidate.merge(candidates[i], 1, Integer::sum);
            if(max < count) {
                max = count;
                cadidateWithMaxVotes = candidates[i];
            }
        }
    }
    return Optional.ofNullable(cadidateWithMaxVotes);
}

CodePudding user response：

It's a bit unclear should we answer just one question ("who is the winner at time 20") or we are supposed to preprocess the data provided and then answer several queries ("who is the winner at time 20", "who is winner at time 8" etc.).

The first problem is easy:

// Nobody is leading before elections with 0 votes
String leader = null;
int leaderVotes = 0;

HashMap<string, Integer> ballots = new HashMap<string, Integer>();

for (int i = 0; i < candidates.length;   i) {
    // too late, don't count this vote
    if (times[i] > givenTime)
        continue;

    // number of votes 
    int current = ballots.containsKey(candidates[i]) 
      ? ballots.get(candidates[i])   1
      : 1;

    ballots.set(candidates[i], current);

    // do we have a leader change?
    //TODO: add tie breaking logic here
    if (current > leaderVotes) {
        leaderVotes = current;
        leader = candidates[i];
    }
}

// at givenTime we have leader with leaderVotes

The second problem is trickier:

1. We sort the votes by time
2. Scan them as we do in the first problem
3. On every leader change we add a record into (time, leader) list
4. Having all these done we have a sorted list which is ready for binary search: for given time we are looking for the latest record which is not later than time.

CodePudding user response：

What I would do is as follows:

1. First, implement a naive solution, such as the one you thought of, or the one suggested by Pp88 above.
2. Then, immediately write a test for it, which shows⁽¹⁾ that it works.
3. Then, implement a more optimal solution, such as the one which follows.
4. Finally, re-use the previous test to show⁽¹⁾ that the more optimal solution also works.

A more optimal solution could be as follows:

1. Build a LinkedHashMap where the key is a time coordinate, and the value is one more map, in which the keys are the names of all candidates, and the values are the accumulated vote count of each candidate at that time coordinate.
2. Traverse this LinkedHashMap and create a new map, where the key is again a time coordinate, and the value is the name of the winning candidate at that time coordinate. Throw away the previous map.
3. Build an ArrayList containing all the keys in the map.

Once you have done all of the above, any query of the type "who is the winner at time X" can be answered by performing a binary search in the ArrayList to find the time coordinate which is closest to but does not exceed X, and then a look-up of the time coordinate in the map to find the name of the candidate who was winning at that moment.

Ignoring the overhead of preparing the data structures, the time complexity of each query is equal to the time complexity of binary search, which is O(log₂ n). This is sub-linear, so it is better than O(N).

---

⁽¹⁾ At best, we can say that a test "shows that it works"; it does not prove anything. The most accurate way of putting it is that it "gives sufficient reason to believe that it works", but that's too long, so "it shows that it works" is a decent alternative.