Last Updated: 4 Nov, 2020
Climbing the leaderboard
Moderate
Asked in companies
Given a leaderboard of a game with the following ranking pattern:
The player with the highest score is ranked number 1 on the leaderboard.
Players who have equal scores receive the same ranking number, and the next player(s) receive the immediately following ranking number.
You are given game scores of a player of ‘M’ rounds. Your task is to return the position obtained in each round.
Note:
The leaderboard scores are in descending order.
The game scores are given in ascending order.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘4*T’ lines represent the ‘T’ test cases.
The first line of each test case contains an integer ‘N’ denoting the number of players on the leaderboard.
The second line of each test case contains ‘N’ space-separated integers denoting the leaderboard scores in decreasing order.
The third line of each test case contains an integer ‘M’ denoting the number of rounds of the game.
The last line contains ‘M’ space-separated integers denoting the game scores, for each round, in ascending order.
Output format:
For each test case, return the ranks of the player corresponding to the game scores obtained.
Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 50
1 <= N <= 10^4
1 <= M <= 10^3
0 <= LEADERBOARD_SCORE[i] <= 10^9
0 <= PLAYER_SCORE[i] <= 10^9
Time limit: 1 second
Approaches
For the score of the player for each round, we will be finding the appropriate position in the leaderboard by comparing it with the scores in the leaderboard.
- Store the leaderboard scores in a set so that the duplicates get removed. Call it ‘LEADERBOARD’.
- Find the size of the set and store it in a variable ‘N’.
- Run a loop where variable ‘ROUNDS’ ranges from ‘0’ to ‘M’, where ‘M’ denotes the total number of rounds.
- For each round, run a loop where variable ‘LEADERBOARD_INDEX’ ranges from ‘0’ to ‘N’.
a. Initialize ‘COUNT’ variable with ‘0’.
b. Traverse through the set. If the leaderboard score is greater than the player’s score, increment count.
c. When the leaderboard score becomes lesser than player’s score, store ‘COUNT+1’ as the answer as it is the required position. - Store these positions and then return the complete answer.
For the score of the player for each round, we will be finding the appropriate position in the leaderboard by comparing it with the scores in the leaderboard.
- Store the unique elements in the vector/list. Call it ‘LEADERBOARD_SCORE’.
- Find the size of the vector/list and store it in a variable ‘N’.
- Run a loop where the variable ‘ROUND’ ranges from ‘0’ to ‘M’, where ‘M’ denotes the total number of rounds.
- For each round, find the appropriate position using binary search on the ‘LEADERBOARD_SCORE’ vector. Below is the procedure used for binary search.
a. Compare the score of the player with the middle element.
b. If the score matches the middle element, we return the MID index.
c. Else if the score is greater than the MID element, then X can only lie in the left half subarray before the MID element because elements are in descending order. So we search in the left half.
d. Else (score is smaller) search in the right half. - Store all the positions and return the answer.
For the score of the player for each round, we will be finding the appropriate position in the leaderboard by comparing it with the scores in the leaderboard.
- Count all the unique elements in the ‘LEADERBOARD’ array and store the count in variable ‘CURRENT_POSITION’. It stores the actual position in the leaderboard.
- Store the last position in the leaderboard in the variable ‘LEADERBOARDINDEX’.
- Run a loop where ‘PLAYER_INDEX’ ranges from ‘0’ to ‘M’ where ‘M’ is the total number of rounds of the game.
a. While the score at ‘PLAYER_INDEX’ is greater than that at the position ‘LEADERBOARD_INDEX’, keep decrementing the ‘LEADERBOARD_INDEX’ variable. If the ‘LEADERBOARD[LEADERBOARD_INDEX]’ is not equal to ‘LEADERBOARD[LEADERBOARD_INDEX+1])’, decrement the ‘CURRENT_POSITION’ variable, keeping the note of the actual position. If they are equal, there will be no change in ‘CURRENT_POSITION’ as duplicate elements have the same position.
b. If the scores of the player at ‘PLAYER_INDEX’ is equal to the score in the leaderboard at ‘LEADERBOARD_INDEX’, the player gets the position ‘CURRENT_POSITION’.
c. Else, the player gets the position ‘CURRENT_POSITION+1’.
4. Store these positions and then return the complete answer.
Similar problems