DEV Community

Arjun Rajkumar
Arjun Rajkumar

Posted on • Updated on

Write better code: Day 4 - Sorted scores

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]

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

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.

Top comments (1)

arjunrajkumar profile image
Arjun Rajkumar

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

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

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