Bloomberg LP Interview Question for SDE1s
- 0of 0 votes
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?- AnonyMous October 11, 2018 in United States
Your code should run in O(1).
Note: Players cannot cheat, i.e. they cannot miss a checkpoint
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)
| Report Duplicate | Flag | PURGE
Bloomberg LP SDE1 Data Structures
Interview Type: In-Person