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])
        self.make_leaderboard()
        
    # This method will make the leaderboard based on score.
    def make_leaderboard(self):
        print("self.leaderboard.items(): ",self.leaderboard.items())
        score_list = [[item[1][0], item[1][1]] for item in self.leaderboard.items()]
        print("score_list: ",score_list)
        # Implement Merge Sort and replace the line below
        # sorted_score_list = sorted(score_list, reverse=True, key= lambda x: x[1])
        self.mergeSort(score_list) # ascending
        score_list.reverse()
        print("score_list: ",score_list)
        self.leaderboard.clear()
        # print("After clearing, self.leaderboard: ",self.leaderboard)
        for key, value in enumerate(score_list):
            # print('key, value: ',key,value)
            self.leaderboard[int(key+1)] = value
        print("Newly Prepared, self.leaderboard: ",self.leaderboard)
        
        
    # This method searches the leaderboard for the score and rank of the participant
    def search_leaderboard(self, username):
        items = self.leaderboard.items()
        sorted_items = sorted(items, key=lambda x: x[1][0]) # Sorting as per names
        print("sorted_items: ",sorted_items)
        # HW: Implement a Binary Search by giving a call to this function
        for item in sorted_items:
            if item[1][0] == username:
                print(username + " score: " + str(item[1][1]) + ", and Rank: " + str(item[0]))
     
    
    # show_leaderboard will print the leaderboard
    def show_leaderboard(self):
        leaderboard_items = self.leaderboard.items()
        print("=========================================================")
        print("leaderboard_items: ",leaderboard_items)
        for item in leaderboard_items:
            print(item[1][0] + " score: " + str(item[1][1]) + ", and Rank: " + str(item[0]))
        
    def mergeSort(self, arr):
        if len(arr) > 1:
            mid = len(arr) // 2  # Finding the mid of the array
            L = arr[:mid]  # Dividing the array elements
            R = arr[mid:]  # into 2 halves

            self.mergeSort(L)  # Sorting the first half
            self.mergeSort(R)  # Sorting the second half

            i = j = k = 0

            # Copy data to temp arrays L[] and R[]
            # The Merge step
            while i < len(L) and j < len(R):
                if L[i][1] < R[j][1]:
                    arr[k] = L[i]
                    i += 1
                else:
                    arr[k] = R[j]
                    j += 1
                k += 1

            # Checking if any element was left
            while i < len(L):
                arr[k] = L[i]
                i += 1
                k += 1

            while j < len(R):
                arr[k] = R[j]
                j += 1
                k += 1