Maintain an Escape-Room Leaderboard

Question

Design and implement a system to maintain a leaderboard for an escape room competition, allowing for the addition of new scores and retrieval of the top scores.

Codemia · Accepted Answer

To maintain an escape-room leaderboard, we need to support the following functionalities:
1. **Add a score**: Insert a new score for a player.
2. **Retrieve top scores**: Get a list of the top N scores.
3. **Handle ties**: If multiple players have the same score, they should be treated equally in the leaderboard.
4. **Dynamic updates**: The leaderboard should efficiently update as new scores are added.

For this system, we can use a combination of a hash map and a sorted list:
- **Hash Map**: Store player IDs as keys and their scores as values. This allows for O(1) time complexity when adding or updating scores.
- **Sorted List**: Maintain a separate list of scores that is kept sorted to allow for efficient retrieval of the top scores. We could use a balanced binary search tree or a max-heap for this purpose.

Here is a simple implementation in Python:
```python
class Leaderboard:
    def __init__(self):
        self.scores = {}
        self.sorted_scores = []

def add_score(self, player_id, score):
        if player_id in self.scores:
            self.sorted_scores.remove(self.scores[player_id])
        self.scores[player_id] = score
        self.sorted_scores.append(score)
        self.sorted_scores.sort(reverse=True)

def top(self, N):
        return self.sorted_scores[:N]
```
This implementation allows us to add scores and retrieve the top N scores efficiently.

The time complexity for adding a score is O(N) due to the sorting step, while retrieving the top N scores is O(N) as well. If we use a max-heap for maintaining scores, we can reduce the add operation to O(log N) and top retrieval to O(N), making it more efficient for larger datasets.

Using a sorted list is straightforward but may not scale well with a large number of players. Instead, using a max-heap can significantly improve performance. Additionally, we should consider how we handle memory usage and potential data persistence if the leaderboard needs to be stored long-term.

Maintain an Escape-Room Leaderboard

Pinterest

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Requirements

High-Level Design

Submit Your Answer

Pinterest Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string