Interview Cake

You're out of free questions.

Upgrade now

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 time, but players are complaining that their rankings aren't updated fast enough. You need a faster sorting algorithm.

Write a method that takes:

  1. an array of unsorted_scores
  2. the highest_possible_score in the game

and returns a sorted array 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 [91, 89, 65, 53, 41, 37]

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 array.

We can do this in time and space.

is the time to beat. Even if our array of scores were already sorted we'd have to do a full walk through the array to confirm that it was in fact fully sorted. So we have to spend at least time on our sorting method. If we're going to do better than , we're probably going to do exactly .

What are some common ways to get runtime?

One common way to get runtime is to use a greedy algorithm. But in this case we're not looking to just grab a specific value from our input set (e.g. the "largest" or the "greatest difference")—we're looking to reorder the whole set. That doesn't lend itself as well to a greedy approach.

Another common way to get runtime is to use counting. We can build an array score_counts where the indices represent scores and the values represent how many times the score appears. Once we have that, can we generate a sorted array of scores?

What if we did an in-order walk through score_counts. Each index represents a score and its value represents the count of appearances. So we can simply add the score to a new array sorted_scores as many times as count of appearances.

We use counting sort.

def sort_scores(unsorted_scores, highest_possible_score) # Array of 0s at indices 0..highest_possible_score. score_counts = [0] * (highest_possible_score+1) # Populate score_counts. unsorted_scores.each do |score| score_counts[score] += 1 end # Populate the final sorted array. sorted_scores = [] # For each item in score_counts, highest_possible_score.downto(0) do |score| count = score_counts[score] # for the number of times the item occurs, (0...count).each do |time| # add it to the sorted array. sorted_scores.push(score) end end sorted_scores end

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 array. 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 array, 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 array! 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 array. Could we instead sort the array in place? Does this change the time complexity? The space complexity?

Reset editor

Powered by qualified.io

. . .