The recruiter reached out to me and connected me with a random member at Rubrik, which was amazing.

We had an initial chat about my resume and then started the interview process.

To my surprise, I wasn't asked to code. Instead, I had to discuss my entire approach and write down pseudocode.

I was also questioned about my space and time complexity, as well as basic data structure concepts.

We are building an online game that has unfortunately become viral, something akin to agar.io.

The challenge with such games is the large number of players interacting simultaneously, with scores updating every second. This means the rank list changes very quickly. We need to devise a data structure that can efficiently handle this dynamic rank list. Assume player scores are distinct at any given point, and players are identified by unique IDs.

Expected operations:

1. Get Player Rank: Quickly retrieve the RANK (not score) of any given player. This is needed to display their rank and update it approximately every second. Technically, given a player ID, return their rank in O(1) or O(log N) time.

2. Get Player by Rank: Determine the player associated with any given rank. This is required to display ranks on the dashboard. Technically, given a rank, return the player with that rank at the current time in O(1) or O(log N) time.

3. Update Player Score: This is our most critical operation. Technically, given a player ID and a new score, update the player's score (which should affect the ranks of other players) in O(1) or O(log N) time.

4. Add/Delete Players: Add or remove players, including their IDs and initial scores (initialized to zero), in O(1) or O(log N) time.