Write better code: Day 4 - Sorted scores

#challenge

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.

Top comments (1)

Arjun Rajkumar • Dec 8 '18

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

DEV Community

Write better code: Day 4 - Sorted scores

Day 4: Question 2

Top comments (1)

Read next

Confusing JRE and JDK package naming in Linux Distros

3163. String Compression III

my title

What is VPC Flow Log ? How to Enable VPC Log