This post originally appeared on Arjun Rajkumar's blog. Arjun is a web developer based in Bangalore, India.
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.