4
\$\begingroup\$

This has been asked a couple of times but here is my implementation in C++. I have 11/12 solutions completed. The 6th test case which has 200000 intial scores and Alice has even more scores causes my program to timeout. Below is the problem statement and the code. My question is, am I missing something in code complexity, or is this a more of a C++ optimization I need to add to get the last test data set through?

Problem

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 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. For example, the four players on the leaderboard have high scores of , , , and . Those players will have ranks 100, 90, 90, and 80, respectively. If Alice's scores are 70, 80 and 105, her rankings after each game are 4th, 3rd and 1st.

Function Description

Complete the climbingLeaderboard function in the editor below. It should return an integer array where each element res[j] represents Alice's rank after the j-th game.

climbingLeaderboard has the following parameter(s):

  • scores: an array of integers that represent leaderboard scores
  • alice: an array of integers that represent Alice's scores

Input Format

The first line contains an integer n, the number of players on the leaderboard. The next line contains n space-separated integers scores[i], the leaderboard scores in decreasing order. The next line contains an integer, m, denoting the number games Alice plays. The last line contains m space-separated integers alice[j], the game scores.

Constraints

The existing leaderboard, scores, is in descending order. Alice's scores, alice, are in ascending order.

Output Format

Print m integers. The j-th integer should indicate Alice's rank after playing the j-th game.

Code

std::vector<int>::iterator m_binary_search(std::vector<int>::iterator begin,
  std::vector<int>::iterator end, int score)
{
  std::vector<int>::iterator ret;

  if (score > (*begin)) {
    return begin;
  } else if (score < (*(end - 1))) {
    return end - 1;
  }

  if (*begin == score) {
    ret = begin;
  } else if (*(end - 1) == score) {
    ret = end - 1;
  } else if (begin + 1 == end) {
    ret = begin;
  } else {
    std::ptrdiff_t middle = std::distance(begin, end) / 2;
    if (*(begin + middle) == score) {
      ret = begin + middle;
    } else if ((score < (*begin)) && (score > * (begin + middle))) {
      ret = m_binary_search(begin, begin + middle, score);
    } else {
      ret = m_binary_search(begin + middle, end, score);
    }
  }

  return ret;
}

// Complete the climbingLeaderboard function below.
std::vector<int> climbingLeaderboard(
  const std::vector<int> &scores,
  const std::vector<int> &alice)
{
  std::vector<int> rankBuckets;
  for (std::size_t s = 0; s < scores.size();) {
    int curr = scores[s];
    while (s < scores.size() && scores[s] == curr) {
      ++s;
    }
    rankBuckets.push_back(curr);
  }

  typedef std::vector<int>::iterator VectIt_t;
  std::vector<int> ranks;
  for (int score : alice) {
    VectIt_t cit = m_binary_search(
      rankBuckets.begin(),
      rankBuckets.end(),
      score);
    VectIt_t nit = cit;
    ++nit;

    std::ptrdiff_t rank = std::distance(rankBuckets.begin(), cit);

    if (nit == rankBuckets.end()) {
      if (*cit != score) {
        rankBuckets.push_back(score);
        rank += 2;
      } else {
        rank += 1;
      }
      ranks.push_back(rank);
      continue;
    }

    int crank = *cit;
    int nrank = *nit;

    if (score > crank) {
      rankBuckets.insert(cit, score);
      rank += 1;
    } else if (score == crank) {
      rank += 1;
    } else if (score < crank && score > nrank) {
      rankBuckets.insert(nit, score);
      rank += 2;
    }

    ranks.push_back(rank);
  }
  return ranks;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Could you please copy the text of the programming challenge into this question. Links often go bad over time. I know you didn't write main, but some reviewers may want to see it to show how the code gets used. \$\endgroup\$ – pacmaninbw Sep 20 at 16:46
  • \$\begingroup\$ Unlike stackoverflow you don't have to worry about a duplicate question in this case because everyone codes differently and as you pointed out the other times this question was posted it was in different languages. \$\endgroup\$ – pacmaninbw Sep 20 at 17:07
  • 1
    \$\begingroup\$ @pacmaninbw question updated as per your request. \$\endgroup\$ – Matthew Hoggan Sep 20 at 17:11
3
\$\begingroup\$

(Adapted from my answer to How can I make my solution to “Climbing the Leaderboard” not time out?)

It is nice that you used size_t and ptrdiff_t. However, int is still directly used for the score. I would prefer an alias:

using score_t = long;
using rank_t = long;

(Note that int is not guaranteed to have \$10^9\$.)

The m_binary_search function is redundant because we have std::lower_bound which should be optimized better.

The climbingLeaderboard is way too long. The function is illogical. It should handle one Alice-score at a time. Also, climbingLeaderboard isn't really a good function name. (I know HackerRank forces you to code sub-optimally sometimes, but you should be aware.)

The problem is very simple and can be finished in several lines without sacrificing readability:

using score_t = long;
using rank_t = long;

// scores is passed by value to take advantage of possible optimization.
rank_t get_rank(std::vector<score_t> scores, score_t alice_score)
{
    scores.erase(std::unique(scores.begin(), scores.end()), scores.end());

    auto it = std::lower_bound(scores.begin(), scores.end(), alice_score, std::greater<>{});
    return it - scores.begin() + 1;
}

The code is \$O(n)\$ and I don't think you can do better in terms of asymptotic analysis. Note that each score of Alice's is independent, so it makes no sense to process them together in a function. I used long because the problem seems to require numbers as large as \$10^9\$. scores will be modified in the function, so instead of making a copy manually, we let the compiler do so for us in the parameter list. This enables possible optimization opportunities.

Here, we used two standard algorithms:

  • std::unique, which "removes" adjacent equal elements. Standard algorithms cannot change the size of scores via iterators, so std::unique makes sure that the first \$N\$ elements are the result, where \$N\$ is the number of elements in the result. The rest of the elements are placed in a valid but otherwise unspecified state. Then, we call erase to erase these garbage elements. This is also known as the remove-erase idiom.

  • std::lower_bound, which performs a binary search and returns the first element that compares not "less" than the provided value. By default, "less" is defined by <, thus operating on an ascending sequence. In this case, we use std::greater<> to define "less" by >, so that std::lower_bound is adapted to work on a descending sequence.

Of course, you will need to adapt to HackerRank's strange interface, but that should be trivial.

\$\endgroup\$
  • \$\begingroup\$ I see your point about int versus long even though most computers today would default to a 64 bit int rather than a 32 bit int, but why alias long? \$\endgroup\$ – pacmaninbw Sep 21 at 12:00
  • \$\begingroup\$ @pacmaninbw I don't really like directly seeing long ... IMO, "This number represents a score" is better than "This number represents a long". \$\endgroup\$ – L. F. Sep 21 at 12:30
  • \$\begingroup\$ I understand, I read declarations different then you, "This long represents a score". \$\endgroup\$ – pacmaninbw Sep 21 at 12:33
  • 1
    \$\begingroup\$ @pacmaninbw I get your point. Anyway, sometimes it is inconvenient to introduce a declarator (e.g., std::pair<score_t, rank_t>), so I prefer encoding this information in the type specifier. But I'd say it's a matter of style \$\endgroup\$ – L. F. Sep 21 at 12:37
  • \$\begingroup\$ I can see where that might make the code more readable, also easier to modify. \$\endgroup\$ – pacmaninbw Sep 21 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.