Sort Scores: Part 1

So here’s a prompt from InterviewCake:

“You created a game that is more popular than Angry Birds.

Each round, players receive a score between 0 and 100, which you use to rank them from highest to lowest. So far you’re using an algorithm that sorts in O(n log ⁡n) time, but players are complaining that their rankings aren’t updated fast enough. You need a faster sorting algorithm.

Write a function that takes:

1. an array of unsortedScores

2. the highestPossibleScore in the game

and returns a sorted array of scores in less than O(n log ⁡n) time.

For example:

const unsortedScores = [37, 89, 41, 65, 91, 53];

const HIGHEST_POSSIBLE_SCORE = 100;

sortScores(unsortedScores, HIGHEST_POSSIBLE_SCORE);

// returns [91, 89, 65, 53, 41, 37]

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

And, we’ll treat highestPossibleScore 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.”

PART 1 : the process my partner Danielle and I took when solving this sorting algorithm using a hash table.

Since this prompt asked for optimization to a specific Big O right off the bat, my partner and I first had to determine: what’s better than O(n lg n)?

A little quick research confirmed: only O(n), O(log n) or O(1). Since constant or logarithmic time seemed inapplicable (maybe even a little impossible), we aimed for O(n), with a general idea of looping just once through the given scores.

Given this as a starting point, we approached the problem with the aim of using a hash table — if you need more time, you’ll likely need to give up some space right?

We first came up a few simple test specs to get some examples and edge cases down.

- What if there was only one score in the array?

- What if one of the scores given was invalid (greater than the highest possible score)?

- And the most likely to come up: how would we handle multiple appearances of the same score?

We also had to consider the following:

- What was the purpose of including the highest possible score as a parameter?

- If using a hash table, what should be the key? What should be the value?

So, we dove right in with a general idea of setting an object to hold the scores, in which the key would be each element’s distance to / the difference from the HIGHEST_POSSIBLE_SCORE, and the value would be an array containing the score itself. This was a quick, simple way to handle collision; if a score appeared more than once, each instance of it would get pushed to the value array.

We were also working in an interesting feature in Javascript — the Object.keys() method already returns a sorted ascending array of keys. Since our object’s keys were the distance to the HIGHEST_POSSIBLE_SCORE, our scores could then be returned in descending order, as per the prompt.

To generate the solution array, we started with using .map() — but since .map() always returns an array of the same length as the original, we needed a way to handle the depth of each bucket. Using .forEach() instead, we spread each array/value into another solution array, sorted by the keys’s value thanks to Object.keys().

However, we were still a bit unsure of this solution, even though all our tests were passing and there were no nested loops. What is the time complexity of Object.keys() and does it “matter”? Does using .forEach() count using as another loop?

What does all of this mean for our Big O?

Continue to Part 2 for the ACTUAL solution!