[FIXED] Optimal way to solve the below problem based on Data Structure

Issue

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

Solution

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.

Answered By - Mike Nakis
Answer Checked By - David Marino (JavaFixing Volunteer)