Climbing the leaderboard

Moderate
0/80
Average time to solve is 15m
3 upvotes
Asked in companies
Goldman SachsDunzoLenskart

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
7
100 100 50 40 40 20 10
4
5 25 50 120
6
100 90 90 80 75 60
5
50 65 77 90 102
Sample Output 1:
6 4 2 1
6 5 4 2 1
Explanation of sample input 1:
Test case 1:

Leaderboard Scores: 100   100   50   40   40   20   10
Ranks          :     1    1     2    3    3    4    5 

Since 2 players scored 100, they get rank 1. Also, 2 players scored 40 and hence have the same rank, i.e rank 3. While others received different rankings according to their scores.

For the first round player scores 5 points, the player will stand at a position after the player at position 5 because the score is less than 10. So, the player gets position 6.

For the second round player scores 25 points, the player will stand after the player at position 3 and before the player at position 4. So, gets position 4, shifting the other players by 1 position.

The same goes for other rounds.

Test case 2:

Leaderboard Scores: 100    90    90    80    75    60   
Ranks            :   1     2     2     3     4     5 

So, 50 points will get position 6.
65 points will get position 5
And so on.
Sample Input 2:
1
5
80 66 54 42 30
3
45 55 65
Sample Output 2:
4 3 3
Hint

 Leaderboard scores are given in descending order.

Approaches (3)
Brute force approach

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.

 

  1. Store the leaderboard scores in a set so that the duplicates get removed. Call it ‘LEADERBOARD’.
  2. Find the size of the set and store it in a variable ‘N’.
  3. Run a loop where variable ‘ROUNDS’ ranges from ‘0’ to ‘M’, where ‘M’ denotes the total number of rounds.
  4. 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.
  5. Store these positions and then return the complete answer.
Time Complexity

O(N * M), where ‘N’ is the number of players on the leaderboard and ‘M’ is the number of rounds of the game.

 

In the worst case, for every round, an array of size ‘N’ is traversed. 

Space Complexity

O(N), where ‘N’ is the number of players on the leaderboard.

 

We use a set of the space of order ‘N’.

Code Solution
(100% EXP penalty)
Climbing the leaderboard
Full screen
Console