Sorting and Searching
Table Of Contents
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())