CareerCup

If you had n racers and m checkpoints, how would you list out the racers in the order in which they are in the race given that each checkpoint gets a notification when a specific racer crosses it?

Your code should run in O(1).

Note: Players cannot cheat, i.e. they cannot miss a checkpoint

Example:

Assume 5 checkpoints(C1, C2, C3, C4, C5) and 10 racers(P1, P2,...P10).

Now once the race begins, lets say P2 first crosses C1. So the current race order is P2.

Now P1, P3, P4 cross C1; so the race order is P2, P1, P3, P4.

Now P1, crosses C2; so the race order becomes P1, P2, P3, P4

Now P3, crosses C2; so the race order becomes P1, P3, P2, P4

Now P5, crosses C1; so the race order becomes P1, P3, P2, P4, P5

Now P1 crosses C3; so the race order remains P1, P3, P2, P4, P5

and so on.

Assume that you get notified of players crossing a checkpoint by a function update(player name, checkpoint). Your task is to show the players in order in O(1) i.e return a vector of players in-order in O(1)