Programming Language = C#
Description:
Alice is playing an arcade game and wants to climb to the top of the leaderboard and wants to track her ranking. The game uses Dense Ranking, so its leaderboard works like this:
- The player with the highest score is ranked number on the leaderboard.
- Players who have equal scores receive the same ranking number, and the next player(s) receive the immediately following ranking number.
For example, the four players on the leaderboard have high scores of 100, 90, 90, and 80 . Those players will have ranks 1, 2, 2, and 3, respectively. If Alice’s scores are 70, 80 and 105, her rankings after each game are 4th, 3rd and 1st.
You can check full question click here
Solution Climbing the Leader board:
1) Set the Rank e.g. 100-90, 90-80, 80-0
2) Implement Binary Search for faster search
static int binarySearch(int[] s, int start, int end, int alice)
{
if (alice < s[end]) return -1;
if (alice >= s[start]) return0;
if (end – start <= 1) return end;
int mid = (start + end) / 2;
if (s[mid] < alice)
return binarySearch(s, start, mid, alice);
elseif (s[mid] == alice)
return mid;
else
return binarySearch(s, mid, end, alice);
}
static int[] climbingLeaderboard(int[] scores, int[] alice)
{
// your code goes here
int n = scores.Length;
int[] rank = newint[n];
rank[0] = 1;
for (int i = 1; i < n; i++)
{
if (scores[i] < scores[i – 1])
{
rank[i] = rank[i – 1] + 1;
}
else
{
rank[i] = rank[i – 1];
}
}
int start = 0, end = n – 1;
int getRank;
int[] output = newint[alice.Length];
for (int i = 0; i < alice.Length; i++)
{
getRank = binarySearch(scores, start, end, alice[i]);
if (getRank == -1)
output[i] = rank[n – 1] + 1;
else
{
end = getRank;
output[i] = rank[getRank];
}
}
return output;
}
Happy Programming!!
Leave a Reply