Sorting and Searching

Use Case 1: Leaderboard

Leaderboard : Problem Statement

Suppose you are a backend engineer at a gaming company. You are tasked with implementing the sorting and searching algorithm for the leaderboard of a high participation game.

We have provided a python project which has two files, Driver.py and Leaderboard.py.

Driver.py contains the code which will drive the project.

Leaderboard.py contains all the business logic of maintaining and updating the leaderboard.

Leaderboard is implemented using a dict, where the key corresponds to the rank and value is a list of order

[‘username’, score].

Ex: leaderboard = {1: ["alice",90], 2: ["bob", 89], 3: ["darwin", 87]}

Tasks

In Leaderboard.py,

-- You have to implement the ‘make_leaderboard’ method, which first sorts the dictionary items in reverse order and assigns them the ranking. And prints the leaderboard.

-- Implement ‘search_leaderboard’ method, which takes ‘username’ as a param and searches the leaderboard. This prints the queried user’s score and rank.

Expectations

-- Your ‘make_leaderboard’ logic should sort the leaderboard in O(n log n) time.

-- Your ‘search_leaderboard’ implementation should search the leaderboard in O(log n) time.

class Leaderboard:
    
    leaderboard = None
    
    # Constructor: Initialization
    def __init__(self, leaderboard):
        self.leaderboard = leaderboard
        print("Constructor called: ", self.leaderboard)
        
    # Add a score of a new user
    def add_score(self, username, score):
        key = 1+max(self.leaderboard.keys()) # 6
        self.leaderboard[key] = [str(username), int(score)]
        print("add_score --> self.leaderboard: ",self.leaderboard)
        print("add_score --> self.leaderboard[key]: ",self.leaderboard[key])
        
    # This mtd will make a leaderboard based on score in the descending order
    def make_leaderboard(self):
        print("self.leaderboard.items():",self.leaderboard.items())