COURSES
MBAData Science & AnalyticsDoctorate Software & Tech AI | ML MarketingManagement
Professional Certificate Programme in HR Management and AnalyticsPost Graduate Certificate in Product ManagementExecutive Post Graduate Program in Healthcare ManagementExecutive PG Programme in Human Resource ManagementMBA in International Finance (integrated with ACCA, UK)Global Master Certificate in Integrated Supply Chain ManagementAdvanced General Management ProgramManagement EssentialsLeadership and Management in New Age BusinessProduct Management Online Certificate ProgramStrategic Human Resources Leadership Cornell Certificate ProgramHuman Resources Management Certificate Program for Indian ExecutivesGlobal Professional Certificate in Effective Leadership and ManagementCSM® Certification TrainingCSPO® Certification TrainingLeading SAFe® 5.1 Training (SAFe® Agilist Certification)SAFe® 5.1 POPM CertificationSAFe® 5.1 Scrum Master Certification (SSM)Implementing SAFe® 5.1 with SPC CertificationSAFe® 5 Release Train Engineer (RTE) CertificationPMP® Certification TrainingPRINCE2® Foundation and Practitioner Certification
Law
Job Linked
Bootcamps
Study Abroad
Master of Business Administration (90 ECTS)Master of Business Administration (60 ECTS)Master in Computer Science (120 ECTS)Master in International Management (120 ECTS)Bachelor of Business Administration (180 ECTS)B.Sc. Computer Science (180 ECTS)MS in Data AnalyticsMS in Project ManagementMS in Information TechnologyMasters Degree in Data Analytics and VisualizationMasters Degree in Artificial IntelligenceMBS in Entrepreneurship and MarketingMSc in Data AnalyticsMS in Data AnalyticsMaster of Science in AccountancyMS in Computer ScienceMaster of Science in Business AnalyticsMaster of Business Administration MS in Data ScienceMS in Information TechnologyMaster of Business AdministrationMS in Applied Data ScienceMaster of Business AdministrationMS in Data AnalyticsM.Sc. Data Science (60 ECTS)Master of Business AdministrationMS in Information Technology and Administrative Management MS in Computer Science Master of Business Administration MBA General Management-90 ECTSMSc International Business ManagementMS Data Science MBA Business Technologies MBA Leading Business Transformation Master of Business Administration MSc Business Intelligence and Data ScienceMS Data Analytics MS in Management Information SystemsMSc International Business and ManagementMS Engineering ManagementMS in Machine Learning EngineeringMS in Engineering ManagementMSc Data EngineeringMSc Artificial Intelligence EngineeringMPS in InformaticsMPS in Applied Machine IntelligenceMS in Project ManagementMPS in AnalyticsMS in Project ManagementMS in Organizational LeadershipMPS in Analytics - NEU CanadaMBA with specializationMPS in Informatics - NEU Canada Master in Business AdministrationMS in Digital Marketing and MediaMS in Project ManagementMaster in Logistics and Supply Chain ManagementMSc Sustainable Tourism and Event ManagementMSc in Circular Economy and Sustainable InnovationMSc in Impact Finance and Fintech ManagementMS Computer ScienceMS in Applied StatisticsMS in Computer Information SystemsMBA in Technology, Innovation and EntrepreneurshipMSc Data Science with Work PlacementMSc Global Business Management with Work Placement MBA with Work PlacementMS in Robotics and Autonomous SystemsMS in Civil EngineeringMS in Internet of ThingsMSc International Logistics and Supply Chain ManagementMBA- Business InformaticsMSc International ManagementMS Computer Science with AIML ConcentrationMBA in Strategic Data Driven ManagementMaster of Business AdministrationMSc Digital MarketingMBA Business and MarketingMaster of Business AdministrationMSc Digital MarketingMSc in Sustainable Luxury and Creative IndustriesMSc in Sustainable Global Supply Chain ManagementMSc in International Corporate FinanceMSc Digital Business Analytics MSc in International HospitalityMSc Luxury and Innovation ManagementMaster of Business Administration-International Business ManagementMS in Computer EngineeringMS in Industrial and Systems EngineeringMSc International Business ManagementMaster in ManagementMSc MarketingMSc Business ManagementMSc Global Supply Chain ManagementMS in Information Systems and Technology with Business Intelligence and Analytics ConcentrationMSc Corporate FinanceMSc Data Analytics for BusinessMaster of Business AdministrationMaster of Business Administration 60 ECTSMaster of Business Administration 90 ECTSMaster of Business Administration 60 ECTSMaster of Business Administration 90 ECTSBachelors in International Management
For College Students

Leader-Board Problem in Data Structure

$$/$$

Now that a lot about sorting algorithms has been discussed, you must try to solve the second query of the leaderboard problem discussed at the beginning of the module. In the next video, industry expert Ankit Maheshwari will discuss the approach one needs to take to crack that problem. Let’s see what he has to say before we move on to the code.

$$/$$

Video Transcript

 

Now that you have understood different sorting techniques, we can move on to the second part of the leaderboard example which we took at the beginning of the module. In the leaderboard of the game which I created in my previous company, the second most frequent query which we received in the leaderboard was to fetch top k rankers. Now let's see how we can solve this problem. We could achieve that easily by doing passes on our array and picking the next highest every time. This obviously will take order NK time. Or we can simply sort the players by their scores using an order and login based sorting algorithm and then return the top k players from the sorted list of players. So which method is better? Should we make k passes over the list of players? Or should we sort the list of players once by their scores and then return the top k players from the sorted list? Let's think this through. What if our k is slightly higher, let's say of the order of 51 hundred? In that case, login will be significantly less than k. Even if we take n, that is a total number of players as large as 1 million. Even then, login will still remain less than 20. In that case, order unlock n would be much better than order NK. Most of the queries which we received in our leaderboard were to fetch top 50 players. This means order n login would be faster than order NK because remember, log n of a million is 20 which is lesser than 50. So we decided to use an efficient sorting algorithm which takes at most order n login time, as speed was our biggest concern. Now let's take a moment to recall what sorting algorithm Professor Mulli has taught us and see which we can leverage over here. So we have learned five sorting algorithms so far bubble sort, selection sort, insertion sort, merge sort and Quicksort. Since we need to sort our list of players as quickly as possible, bubble selection and insertion sort wouldn't work for us because they have order n square time complexity. This leaves us with Merge and Quicksort since they are faster at order n login time complexity. But among those, Quicksort has an average of order n login, but a worst case of order n square. But we want our algorithm to take order n login time at most, even if it takes more memory. Since speed was our biggest concern, this leaves us no choice but to use merge sort. But we don't have to implement the merge sort algorithm all over again. We have a standard library function of collections class in Java which uses an enhanced version of merge sort. You can see that mentioned in its Java doc. Now, this method, collections sort takes in two argument. One is the list which needs to be sorted and the other one is a comparator object. The purpose of the comparator object is to provide rules for sorting. In our case, a player with higher score should come first. In case two players have the same score, then the older player should come first. Let's see how we can use comparator object to incorporate these rules. You can infer from the Java dot that compare method takes in two player arguments p one and p two. And it should return a negative value if p one is to appear before p two. Now let's say p one score is greater than p two score, then we would want p one to appear before. Therefore, we shall return a negative value. On the contrary, if p two score is greater than p one score, we shall return a positive value. We can achieve this by simply returning p two score minus p one score in the compare method. But wait, what if the scores are equal? In that case, we will use created at timestamp as a tiebreaker and we shall return p one created at timestamp minus p two created at timestamp I'll leave it up to you guys to figure out why did we choose this return statement for timestamp comparison. Now let's look at the pseudo code for compare function. Compare function takes in two argument player one p one and player two p two. First we calculate the difference that is p two dot score minus p one dot score. And if difference is not zero, that means it's either negative or positive. In that case we simply return the difference. But if difference is zero, that means the score of both the players are the same. In that case, we have to compare the timestamp and hence we will return p one dot created at timestamp minus p two dot created at timestamp after we have created the comparator with the write compare function, the sorting the list is just calling a single library method. Now let's look at the Java code.

 

Video Recap

 

 

  • One way to achieve this is by doing passes on the array and picking the next highest every time, which takes order (N*K) time.

  • Alternatively, the list of players can be sorted by their scores using an order and login-based sorting algorithm and then return the top K players from the sorted list of players.

  • For large values of k, the order N(log(N)) method is better than the order (N*K) method.

  • Merge sort and Quicksort are two sorting algorithms with order (N) login time complexity, but Quicksort has a worst-case scenario of order (N) square time complexity.

  • The standard library function of the collections class in Java uses an enhanced version of merge sort and takes in two arguments: the list to be sorted and a comparator object that provides rules for sorting.

  • The comparator object in this case compares the score of the players and uses the timestamp as a tiebreaker if the scores are equal.

  • The pseudo code for the compare function is to calculate the difference between the scores of the two players, and if the difference is not zero, return the difference. If the difference is zero, compare the timestamps and return the result.

  • Sorting the list is just calling a single library method after creating the comparator with the right compare function.

 

Great! You saw that you can use the ‘Collections.sort’ function to implement merge sort in our program. This program takes a comparator as an input, which basically sets the rules for this sorting. In case of a tie, you shall use timestamps of the players to assign them to the ranks. Let’s see the Java code for this in the video below.

$$/$$

As you saw in the video, Ankit used timestamps in the occurrence of a tie. Also, if the email ID does not exist in the list, the program prints a message saying that the email ID does not exist.