Just [[currentUser.getNumFreeQuestionsLeft()]] No more free questions left!

Upgrade Now

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

You rank players in the game from highest to lowest score. So far you're using an algorithm that sorts in 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. a list of unsorted_scores
  2. the highest_possible_score in the game

and returns a sorted list of scores in less than time.

For example:

unsorted_scores = [37, 89, 41, 65, 91, 53] HIGHEST_POSSIBLE_SCORE = 100 sort_scores(unsorted_scores, HIGHEST_POSSIBLE_SCORE) # returns [37, 41, 53, 65, 89, 91]

We’re defining n 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.

Multiple players can have the same score! If 10 people got a score of 90, the number 90 should appear 10 times in our output list.

We can do this in time and space.

You must log in with one click to view the rest.

Once you're logged in, you'll get free full access to this and 4 other questions.

You must log in with one click to view the rest.

Once you're logged in, you'll get free full access to this and 4 other questions.

time and space, where n is the number of scores.

Wait, aren't we nesting two loops towards the bottom? So shouldn't it be time? Notice what those loops iterate over. The outer loop runs once for each unique number in the list. The inner loop runs once for each time that number occurred.

So in essence we're just looping through the n numbers from our input list, except we're splitting it into two steps: (1) each unique number, and (2) each time that number appeared.

Here's another way to think about it: in each iteration of our two nested loops, we append one item to sorted_scores. How many numbers end up in sorted_scores in the end? Exactly how many were in our input list! n!

If we didn't treat highest_possible_score as a constant, we could call it k and say we have time and space.

Note that by optimizing for time we ended up incurring some space cost! What if we were optimizing for space?

We chose to generate and return a separate, sorted list. Could we instead sort the list in place? Does this change the time complexity? The space complexity?

What's next?

Code execution powered by Qualified.io

. . .