[Challenge] Top Score Sorter

challenge

#1

Code Challenge #13: July 5, 2017

Every week, we feature the type of brain-teasing question that might be asked in a full-stack developer's job interview at places such as Google and Facebook.

This week's challenge was reported to have been asked in interviews at Amazon:


Basic Difficulty

You've spent decades setting high scores on Donkey Kong but now, a challenger approaches. Write a function, scoreSettler, that will definitively show who is the King of Kong. scoreSettler will take a list of unsorted scores plus the highest possible score and return a sorted list of all of the scores, in descending order from high score to low score.

  • Function Name: scoreSettler
  • Input: list of integers representing scores and a single integer for the highest possible score
  • Output: A sorted list of integers in descending order
  • Example: scoreSettler([ 1, 2, 3, 999999], 1000000) => [999999, 3, 2, 1]
  • In your submission, please use as a test of your function the maximum value of 1218000, with a list of scores [874300, 879200, 1172100, 1141800, 933900, 1177200, 1190200, 1110100, 1158400, 985600, 1047200, 1049100, 1138600, 1170500, 1064500, 1190000, 1050200, 1090400, 1062800, 1061700, 1218000, 1068000, 1127700, 1144800, 1195100]
  • You're expected to create and implement your own sorting algorithms, not to simply use an in-built sort function.
Find out more about basic challenges.

Hard Difficulty

You wouldn't be much of a King of Kong if your settling of the scores didn't itself set records. Write scoreSettler as efficiently as possible.

If you can't make your program any more efficient explain why.
If you need an additional challenge, try to solve this problem in a more unconventional or artful way, or perhaps try a different language!

Find out more about- hard challenges and Big O

Reply to this thread with a link to your code on repl.it and paste your properly formatted code to participate! Don't just submit your code, remember to explain your solution, too! If you want to be considered as the winner, your function must have the correct name and provide output in the format specified above, you also need to abide by our other simple rules.

As always solutions using imports to do all the heavy lifting such as itertools will not be considered for the winner.


The fine print:

Click the links to find out more about:


Essential Information on Code Challenges
#2

My Entry for the Basic/Hard Challenge using Python 2.7: https://repl.it/JOaW/2

# First, I went ahead and stored our test values.
maxScore = 1218000
scores = [874300, 879200, 1172100, 1141800, 933900, 1177200, 1190200, 1110100, 1158400, 985600, 1047200, 1049100, 1138600, 1170500, 1064500, 1190000, 1050200, 1090400, 1062800, 1061700, 1218000, 1068000, 1127700, 1144800, 1195100]

# Next, I set up the function by having the program store all scores that are less than or equal to the highest possible score in new list.
# This is to insure that all the values are legitimate scores.
# After this, the program then returns a reversed version of a sorted version of our new list.
# It has to be a reversed version, because the sorted() function returns from least to greatest by default.
def scoreSettler(scoreList, maximum):
    orderedList = []
    for score in scoreList:
        if score <= maximum:
            orderedList += [score]
    return sorted(orderedList)[::-1]
    
print scoreSettler(scores, maxScore)

I honestly, could have just done this:

def scoreSettler(scoreList, maximum):
    return sorted(scoreList)[::-1]

However, I felt that the maximum value was there for a reason, so I might as well use it.


#3

Hard JavaScript

https://repl.it/JObW/1

I used the max score to sort the score set by their differences. This makes the solution faster than calling Array.prototype.sort.

const maxScore = 1218000;
const scoreSet = [874300, 879200, 1172100, 1141800, 933900, 1177200, 1190200, 1110100, 1158400, 985600, 1047200, 1049100, 1138600, 1170500, 1064500, 1190000, 1050200, 1090400, 1062800, 1061700, 1218000, 1068000, 1127700, 1144800, 1195100];

function scoreSettler(scores, max) {
  "use strict";
  
  // It can't be as simple as just calling Array.protoype.sort(), can it?
  // The below is about as short and concise as can be. Array.sort compares
  // string versions of the data to sort so it can provide incorrect results
  // on numeric data sets. In this case we provide a function to sort the numbers
  // in descending order.
  
  //return scores.sort((a, b) => b - a);
  
  // This is beautiful but the algorithm that is used cannot be any faster than
  // O(n log n), apparently. Lets see if we can use the max score possible to
  // speed this up.
  
  // We can use the max score to sort the values by finding their difference.
  // This will create a very sparse array that we can then filter out the empty
  // indexes from.
  
  const sparseArr = [];
  for (let i = 0, l = scores.length; i < l; i++) {
    let diff = max - scores[i];
    sparseArr[diff] = scores[i];
  }
  
  return sparseArr.filter(ele => ele);
  // This is still linear becasue filter is just checking for truthiness and
  // not employing any crazy long processes.
}

console.log(scoreSettler(scoreSet, maxScore));

EDIT: Just in case my use of the filter method in my solution was out of line I added my own.
https://repl.it/JObW/2

const maxScore = 1218000;
const scoreSet = [874300, 879200, 1172100, 1141800, 933900, 1177200, 1190200, 1110100, 1158400, 985600, 1047200, 1049100, 1138600, 1170500, 1064500, 1190000, 1050200, 1090400, 1062800, 1061700, 1218000, 1068000, 1127700, 1144800, 1195100];

function scoreSettler(scores, max) {
  "use strict";
  const sparseArr = [];
  
  for (let i = 0, l = scores.length; i < l; i++) {
    const diff = (max - scores[i]) / 100;
    sparseArr[diff] = scores[i];
  }
  
  return filter(sparseArr);
}

// To ensure I was building my own processes I replaced a call to the
// Array.prototype.filter method with my own filter to remove empty
// indexes.

function filter(arr) {
  "use strict";
  const newArr = [];
  
  for (let i = 0, l = arr.length; i < l; i++) {
    if (arr[i]) {
      newArr.push(arr[i]);
    }
  }
  return newArr;
}

console.log(scoreSettler(scoreSet, maxScore));

A further refinement that would be specific to this data set would be dividing my difference based index by 100, since the game's smallest score increment seems to be 100. This would cut down on the size of my sparse array.
https://repl.it/JObW/3


#4

You make me want to learn Python so I can understand your wizardry.


#5

You callin' me a witch?


#6

Did some rudimentary benchmarking to see if Array.prototype.sort() really IS slower than my solution. The results can be seen in this repl:
https://repl.it/JOkx/3

Apparently the sort() method on arrays is BLAZING fast, taking ~2.5-5ms to sort through 10000 scores vs ~52ms using my difference based array.

Unless there's something I'm missing scores.sort((a, b) => b - a); is as fast as it is short!


#7

Here's my submission using Python 3: https://repl.it/JOo4/4
I feel like I'm missing something because of that high score, but what I did was just sort the list of scores in descending order and simply return it
edit: now i'm working on my own way of sorting the scores without using the sorted function

def scoreSettler(score_list, high_score):
    #simply sort and reverse the score_list and return it
    return sorted(score_list, reverse = True)
    
print('scoreSettler([874300, 879200, 1172100, 1141800, 933900, 1177200, 1190200, 1110100, 1158400, 985600, 1047200, 1049100, 1138600, 1170500, 1064500, 1190000, 1050200, 1090400, 1062800, 1061700, 1218000, 1068000, 1127700, 1144800, 1195100], 1218000) =>', scoreSettler([874300, 879200, 1172100, 1141800, 933900, 1177200, 1190200, 1110100, 1158400, 985600, 1047200, 1049100, 1138600, 1170500, 1064500, 1190000, 1050200, 1090400, 1062800, 1061700, 1218000, 1068000, 1127700, 1144800, 1195100], 1218000))

#8

Either something got lost in translation between the Amazon interview and the Donkey Kong interpretation or I'm missing something here.

def scoreSettler(scores, maxscore):
    return [x for x in sorted(scores, reverse=True) if x <= maxscore]

Implementing a custom sort algorithm could help eliminate the iteration over already sorted array, but it's impossible to tell which one to try when given no constrains on the input size. And almost certainly, can't be done in-place like here. So, memory-wise my "solution" should be in the hard category, speed-wise can't tell. Also not sure what's the purpose of the maximum score parameter. Perhaps I will refactor after seeing more submissions and getting a better idea of what we're shooting at here.

repl.it


#9

Hey @chrinkus,

Your results are tainted because there is a missing Array#filter on the Array#sort function. While Array#sort is still faster (on Chrome 59) the number you got was misleading because it doesn't properly filter the array as expected.


#10

Which results are tainted, my solution or my attempt at speed checking?

@envygeeks checked the results for all formulas, everything returns as expected. There is a filter in my solution but that was only to eliminate the empty array elements.

Sort has no need of a filter in these instances. It does take a compare function but that's because of the aforementioned default string sorting behaviour.


#11

Here is my Python 3 submission:

def scoreSettler(scoreList, maxScore):
    return sorted([score for score in scoreList if score <= maxScore], reverse=True)
    
print(scoreSettler([1, 2, 3, 999999], 1000000))
print(scoreSettler([874300, 879200, 1172100, 1141800, 933900, 1177200, 1190200, 1110100, 1158400, 985600, 1047200, 1049100, 1138600, 1170500, 1064500, 1190000, 1050200, 1090400, 1062800, 1061700, 1218000, 1068000, 1127700, 1144800, 1195100], 1218000))
print(scoreSettler([1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144], 100))

I use list comprehension to filter the input list
And the list function sorted() with reverse=True to generate the result
With the highest score first.

Here is the repl.it link: https://repl.it/JOrm/11

And the corresponding output:

[999999, 3, 2, 1]
[1218000, 1195100, 1190200, 1190000, 1177200, 1172100, 1170500, 1158400, 1144800, 1141800, 1138600, 1127700, 1110100, 1090400, 1068000, 1064500, 1062800, 1061700, 1050200, 1049100, 1047200, 985600, 933900, 879200, 874300]
[89, 55, 34, 21, 13, 8, 5, 3, 2, 1]

#12

My Java Solution Hard Difficulty: https://repl.it/JOtH/0

There's an explanation of my approach in the comments but I'll explain it again and then past my method here.

PseudoCode
1. put all values in a HashMap, key: number, value: frequency. If number is already in HashMap increase frequency
2. Iterate from the max value (the highest score possible) through the lowest value which we will keep track of;
3. If the number is in HashMap add value to ArrayList keeping sure track of the fact that there could be multiple occurrences of the same score
4. Make an array from the arrayList. Used arrayList initially since it is dynamic and easier to implement but could also be done with a single array and then just return that.

Note: This algorithm technically is O(N) time and space complexity. However there are cases where a sorting algorithm like quicksort would be faster. For example if the scores are really spread out like 1, 2, 3, Integer.MAX_VALUE then this algorithm would still technically be O(N) but much slower than a quicksort like algorithm. Also note it is not necessary to keep track of the min value in the array but it will increase the efficiency of the algorithm.

public static int [] scoreSettler(int [] array, int maxValue){

        // Step 1:
        HashMap<Integer, Integer> hMap = new HashMap<>();
        int minValue = Integer.MAX_VALUE;

        for (int i: array){
            // Get min value which will be used later in this method
            if (i < minValue)
                minValue = i;

            // If it is already in the hash map
            if(hMap.containsKey(i)){
                // Increment the value for the corresponding key
                hMap.put(i, hMap.get(i)+ 1);
            }else{
                // It is not in the hashmap, put it in
                hMap.put(i, 1);
            }
        }

        ArrayList<Integer> arrayList = new ArrayList<>();

        // Step 2:
        for (int i = maxValue; i >= minValue; i--){

            // Step 3
            if (hMap.containsKey(i)){
                for (int j = 0; j < hMap.get(i); j++){
                    arrayList.add(i);
                }
            }

        }

        // Step 4:

        int[] sortedArray = new int [array.length];
        for (int i = 0; i < arrayList.size(); i++){
            sortedArray[i] = arrayList.get(i);
        }

        return sortedArray;
    }

#13

This is just too easy in Python... Unless I misunderstood something...

def scoreSettler(scores=[], maxs=0):                                              
    return [x for x in sorted(scores, reverse=True) if x <= maxs]

I'll try another one using my own sorting.


#14

In an interview setting you are usually expected to create something from scratch (in this case, a sorting algorithm) and not to simply use in-built tools. Only creating something from scratch truly tests your scripting skills and creative thinking!


#15

I missed the part about:

You're expected to create and implement your own sorting algorithms, not to simply use an in-built sort function

I will start working on my own sorting routine.


#16

Was that line even there originally? If so then I missed it too.


#17

No, it wasn't there originally.
I went back and checked what I had initially printed out.
I have heard that at times during job interviews they switch things up
to see how the candidates handle changing requirements.


#19

That, or my "wizardry" was just too much for them to handle. :smirk:

What's next @danieloduffy? You gonna throw me in a river and see if I float? :sweat_smile:


#20

Corrected my submission, creating a script to sort the scores without using built-in functions: https://repl.it/JOo4/17

I manually search for the highest score in score_list, then append it to sorted_score_list and remove it from the initial score_list, so that the next highest score I find is lower than the previous highest score. This process is repeated while there's at least 1 value in score_list

edit: edited my submission one last time, thanks to @ajaxwhiz49308 bringing something to my attention, and after i read the challenge one more time

def scoreSettler(score_list, high_score):
    #list to hold the sorted values
    sorted_score_list = []
    
    #while there's at least 1 value in score_list, determine which value \ 
    #is the highest (max_score), then append it to sorted_score_list, \
    #and remove it from score_list
    while score_list:
        max_score = 0 
        #initialize max_score
        for score in score_list: 
            #loop through score_list to determine max_score
            if score > max_score:
                max_score = score
        
        #if the current max_score is lower or equal to the highest score \
        #possible (high_score)
        if max_score <= high_score:
            sorted_score_list.append(max_score)
            #append max_score to sorted_score_list
            score_list.remove(max_score)
            #and then remove the current max_score from score_list
        else:
            #if the current max_score is higher than the highest \
            #score possible (high_score)
            score_list.remove(max_score)
            #just remove max_score from score_list

    return sorted_score_list
    
    
print('scoreSettler(scoreSettler([ 1, 2, 3, 999999], 1000000) =>', scoreSettler([ 1, 2, 3, 999999], 1000000))
print('scoreSettler([874300, 879200, 1172100, 1141800, 933900, 1177200, 1190200, 1110100, 1158400, 985600, 1047200, 1049100, 1138600, 1170500, 1064500, 1190000, 1050200, 1090400, 1062800, 1061700, 1218000, 1068000, 1127700, 1144800, 1195100], 1218000) =>', scoreSettler([874300, 879200, 1172100, 1141800, 933900, 1177200, 1190200, 1110100, 1158400, 985600, 1047200, 1049100, 1138600, 1170500, 1064500, 1190000, 1050200, 1090400, 1062800, 1061700, 1218000, 1068000, 1127700, 1144800, 1195100], 1218000))

#21

I'd argue that expecting a sorting algorithm on an interview tests whether you've been to school. It has nothing to do with creative thinking - one does not simply create quicksort when asked to sort something. The sorting algorithms in use today are a result of decades of work of thousands of scientists, and aside of the pointlessness of reinventing the wheel, trying to create one from scratch without access to math/CS theory will inevitably result in something uselessly inefficient - if it even works. On the other hand, due to said decades of work people had spent on these, searching the net for theory brings up readymade code that both spoils the fun and kills the motivation. This is the same gripe I had with the Binary Tree and Edit Distance challenges - there's no room for creative thinking, you either know how to do it right (presumably having done it before, so where's the challenge), put together an ugly something noone will ever use or learn from - that makes you look stupid as well - or copypasta. Please throw us a bone and get us busy solving problems with own code, not someone else's science.