InternDoor

Who is ahead at time t?

Mediumdesign · binary search · countingDesign a class

Reported in interviews at (where)

Votes come in one at a time. persons[i] receives a vote at time times[i], and times is strictly increasing. At any moment the leader is the person with the most votes so far; when several are tied for the most, the one of them who received a vote most recently leads.

VoteLeader(persons, times) takes all the votes.

leader(t) returns who leads at time t, counting every vote with a time at or before t. It is only called with t no earlier than the first vote.

There can be many calls: aim for O(log n) per call.

Example 1
Input
["VoteLeader","leader","leader","leader","leader"]
[[[2,1,1,2,2],[0,4,9,12,20]],[5],[9],[12],[100]]
Output
[null,1,1,2,2]

At time 5, persons 1 and 2 have one vote each and 1 got theirs later, so 1 leads. At 9, person 1 has two. At 12 they tie at two, and 2 got the latest vote.

Limits

  • 1 <= persons.length == times.length <= 5000
  • 0 <= persons[i] < persons.length
  • 0 <= times[i] <= 1000000000, strictly increasing
  • times[0] <= t <= 1000000000
  • at most 10000 calls to leader

Hints

Hint 1

The leader can only change when a vote arrives. Work out the leader after every vote once, in the constructor.

Hint 2

For leader(t), binary-search for the last vote time at or before t and return the leader stored for it.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.