Interview Cake

You only have free questions left (including this one).

But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.

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 function that takes:

  1. a vector of unsortedScores
  2. the highestPossibleScore in the game

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

For example:

const vector<int> unsortedScores {37, 89, 41, 65, 91, 53}; const int HIGHEST_POSSIBLE_SCORE = 100; vector<int> sortedScores = sortScores(unsortedScores, HIGHEST_POSSIBLE_SCORE); // sortedScores: [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.

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

We can do this in time and space.

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

  1. It's easy and quick. No "reset password" flow. No password to forget.
  2. It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
  3. It makes it harder for one person to share a paid Interview Cake account with multiple people.

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

  1. It's easy and quick. No "reset password" flow. No password to forget.
  2. It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
  3. It makes it harder for one person to share a paid Interview Cake account with multiple people.

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 vector. 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 vector, 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 sortedScores. How many numbers end up in sortedScores in the end? Exactly how many were in our input vector! n.

If we didn't treat highestPossibleScore 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 vector. Could we instead sort the vector in place? Does this change the time complexity? The space complexity?

Reset editor

Powered by qualified.io

. . .