Climbing the leaderboard
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

Question

Climbing the leaderboard

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

Accepted Answer

First of all I removed the duplicates from the given leader board scores.
In each iteration say i, I kept the track of current score by taking the maximum of scores till ith attempt.
Then, I searched for the greatest lower bound of current score. The index of greatest lower bound plus one will be her current position.
If there is no number lesser than current score then her current position will be equal to the number of elements in the list plus one.

Accepted Answer

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.

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.

Space Complexity: O(n)Explanation:

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

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

Time Complexity: O(n^2)Explanation:

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.

Accepted Answer

Using Binary Search

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.

Space Complexity: O(n)Explanation:

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

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

Time Complexity: O(nlogn)Explanation:

O(M * log(N)), 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, the position is found using binary search which takes log(N) time.

Accepted Answer

Optimised solution

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.

Space Complexity: O(1)Explanation:

O(1), as it uses constant space.

Time Complexity: O(n)Explanation:

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

The array with leaderboard score and another with player’s scores are traversed once taking a time of ‘M+N’.

Asymptotically, the total time complexity is O(max(M,N)).

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:

Input format:

Output format:

Note:

Constraints:

Top Goldman Sachs Software Analyst interview questions & answers

Popular interview questions of Software Analyst