DEV Community

loading...

Write better code: Day 4 - Sorted scores

arjunrajkumar profile image Arjun Rajkumar Updated on ・1 min read

This post originally appeared on Arjun Rajkumar's blog. Arjun is a web developer based in Bangalore, India.

--

Day 4: Question 2

Write a method that takes:

an array of unsorted_scores and the highest_possible_score in the game
and returns a sorted array of scores in less than O(nlgn) time.

For example:
unsorted_scores = [37, 89, 41, 65, 91, 53]
HIGHEST_POSSIBLE_SCORE = 100

sort_scores(unsorted_scores, HIGHEST_POSSIBLE_SCORE)
# returns [91, 89, 65, 53, 41, 37]

We’re defining nn as the number of unsorted_scores because we’re expecting the number of players to keep climbing.

And, we'll treat highest_possible_score as a constant instead of factoring it into our big O time and space costs because the highest possible score isn’t going to change. Even if we do redesign the game a little, the scores will stay around the same order of magnitude.

-

If you want to follow along, feel free to post your answers in the comment.

My answers are in the comments.
This problem is from InterviewCake.

Discussion (1)

pic
Editor guide
Collapse
arjunrajkumar profile image
Arjun Rajkumar Author

The problem asked to do this in lesser than O[nlogn] time.
Counting sort has O[n] time, so applied that straight.

def sort_scores(unsorted_scores, highest_score)
  counts = [0] * (highest_score + 1)

  unsorted_scores.each do |score|
    counts[score] += 1
  end

  sorted_score = []
  highest_score.downto(1).each do |score|
    count = counts[score]

    (0...count).each do |i|
      sorted_score << score
    end
  end

  sorted_score
end