DEV Community is a community of 615,372 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

loading...

Write better code: Day 4 - Sorted scores

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)

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
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
``````