[Challenge] Top Score Sorter

Hello, my first challenge here with Python.
Explanation:
I iterate through the list given in first parameter and if that list have more than 0 items and those items
are lower than the max argument, then I store them into the scores list.
In the end I print the scores list starting from the last one.
Sorry for bad English.

scorelist = [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]
scoremax = 1218000

def scoreSettler(list, max):
	scores = []
	for item in list: 
		if len(list) > 0 and item < max:
			scores.append(item)
			
	print scores[::-1] 
	
scoreSettler(scorelist, scoremax)

There is also another smaller solution:

def scoreSettler(list, max):
	scores = []	
	[scores.append(x) for x in list if list > 0 and x < max]
	print scores[::-1] 

Fully agree with you, always feel like pointless to ask candidate to do sorting in interview. My answer is always to look it up in google. This remind me of a "new* sorting algorithm call “StackSort” from XKCD.

And how do those interviews generally go?

1 Like

When I am the interviewer, I never ask sorting.
As an interviewee, I never tasked to solve a sorting problem. :smiley:

As we note in our post about why we’re issuing these challenges, we hope that people will be able to learn here in a totally open and accessible manner how these sorts of challenges are answered, so that they can prepare for these questions when and if they are asked. Like it or not, these sorts of questions are often used as a test before one can proceed further in a job interview process, and they are often asked when users are self-taught too. We’d prefer to prepare our learners for that eventuality and not hope that interviewers will buck the trend or that they will be lucky or that they should find a more “enlightened” interviewer.

4 Likes

Understand, sorting question is simple to understand, and it is a good way to test the thinking process of a candidate.

Just that some interviewer that I know, already has a best answer in his mind, and expecting candidate to tell the answer that the interviewer wanted, not so much focus on thinking process. Well, I guess perhaps every single interview question has the same problem.

2 Likes

I have reworked my submission to use my own sorting routine.
I decided to go with a Cocktail Shaker sort, a bidirectional Bubble sort.
I’ve been looking for an opportunity to do something using mutual recursion.
I found it quite challenging to get all the bugs out.
I guess there is a reason behind not trying to reinvent the wheel.

def bubble_up(a_list,l,k):
    if k > 1 :
        i = l
        j = a_list.index(max(a_list[l:k+l]))
        if i != j :
            a_list[i], a_list[j] = a_list[j], a_list[i]
        sink_down(a_list,l+1,k-1)

def sink_down(a_list,l,k):
    if k > 1 :
        i = k+l-1
        j = a_list.index(min(a_list[l:k+l]))
        if i != j :
            a_list[i], a_list[j] = a_list[j], a_list[i]
        bubble_up(a_list,l,k-1)

def shaker_sort(a_list):
    bubble_up(a_list, 0, len(a_list))
    return a_list

def scoreSettler(scoreList, maxScore):
    return shaker_sort([score for score in scoreList if score <= maxScore])

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))

bubble_up moves larger values toward one end of the list,
while sink_down moves smaller values toward the other end.
I tried using slices, but soon discovered that they were just copies
and changes to them were not showing up in the list as a whole.
So I passed around the entire list, along with a starting index and
a length, kind of a pseudo-slice.
Here is a repl.it link:
https://repl.it/JRLT/18

(Perhaps) Hard Difficulty in Java https://repl.it/JRyQ/8

class Main{
public static void main(String args[])
    {
      int numbers[]={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};
      int max = 1218000;
        //Numbers which need to be sorted
        scoreSettler(numbers, max);
    }
    
 public static void scoreSettler(int[] numbers, int max){
   //Sorting in descending order using merge sort
   mergesort(numbers,0,numbers.length-1);
   //Displaying the numbers after sorting
        System.out.print("After sorting, scores are: [");
        for(int i = 0; i < numbers.length; i++)
        {
            System.out.print(numbers[i]+" ");
        }
        System.out.print("]");
 }
static void merge(int numbers[], int low, int middle, int high)
    {
        // Find sizes of two subarrays to be merged
        int n1 = middle - low + 1;
        int n2 = high - middle;
 
        /* Create temp arrays */
        int L[] = new int [n1];
        int R[] = new int [n2];
 
        /*Copy data to temp arrays*/
        for (int i=0; i<n1; ++i)
            L[i] = numbers[low + i];
        for (int j=0; j<n2; ++j)
            R[j] = numbers[middle + 1+ j];
 
 
        /* Merge the temp arrays */
 
        // Initial indexes of first and second subarrays
        int i = 0, j = 0;
 
        // Initial index of merged subarray array
        int k = low;
        while (i < n1 && j < n2)
        {
            if (L[i] >= R[j])
            {
                numbers[k] = L[i];
                i++;
            }
            else
            {
                numbers[k] = R[j];
                j++;
            }
            k++;
        }
 
        /* Copy remaining elements of L[] */
        while (i < n1)
        {
            numbers[k] = L[i];
            i++;
            k++;
        }
 
        /* Copy remaining elements of R[] */
        while (j < n2)
        {
            numbers[k] = R[j];
            j++;
            k++;
        }
    }
   static void mergesort(int numbers[], int low, int high)
    {
        if (low < high)
        {
            // Find the middle point
            int middle = (low+high)/2;
 
            // Sort first and second halves
            mergesort(numbers, low, middle);
            mergesort(numbers , middle+1, high);
 
            // Merge the sorted halves
            merge(numbers, low, middle, high);
        }
    }
}
1 Like

It seems like you might have forgotten about the “high_score” variable - you/re not limiting to given max score. Regards

I’m sorry, but do you mean that only scores lower than ‘high_score’ should be added to the final ‘sorted_score_list’?

2 Likes

Yes, at least this is how I understood this requirement. But if I was wrong then you’re not using that variable anywhere, are you?
Regards

3 Likes

Having said all that I have to admit that I like how you approached sorting - it’s clean. I was just trying to wrote my own sorting and I did but mine is a bit an overkill :wink:

Now, another one but with my own sorting.

The sorting function is iterating over all elements of array and comparing them: if needed elements are swapped around and this restarts the iteration over the array. This continues until all elements are in their position. The scoreSettler is only filtering sorted results to cap it to the max score.

1 Like

Since filtering is O (n) and sorting is always worse, wouldn’t it make more sense to only sort after filtering.

Valid point I guess :slight_smile:

My basic/hard difficulty challenge:

def scoreSettler(mylist, high_score):
#defining the function with 2 values: the list of integers and the highest score
    newlist=[]
    #creating an empty list. It will contain the sorted numbers.
    for score in mylist:
        if score>high_score:
            mylist.remove(score)
    #This loop will remove any score that is largest than the highest score.
    while mylist!=[]:
        maximum=max(mylist)
        newlist.append(maximum)
        mylist.remove(maximum)
    #In this while statement:The maximum number in "mylist" will be found and stored in a variable, maximum.
    #If maximum is lower than or equal to the highest possible score, it will be added to "newlist".
    #And then, maximum will be removed from "mylist".
    #This process will go on untill there is no more number in "mylist".
    print(newlist)
    #This print statement will print out the scores sorted.
    #Because we are adding the numbers on by one in order from the highest to the lowest score, "newlist" will come out sorted.
        
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))

https://repl.it/JVQX/2
My code will find the maximum score from the entered list and if that score is lower than or equal to the highest possible score, it will be added to another list and removed from the first list.
This process will go on until the entered list is empty.And the second list comes out in order from the highest to the lowest score.This is the simplest and shortest solution I could find.

2 Likes

There is a pretty big issue with your code. If any of the numbers in my_list are greater than high_score your code results in an infinite loop.

For proof, try running this:

print(scoreSettler([874300, 879200, 1172100, 1141800, 933900, 1177200, 1190200, 1110100, 1158400, 985600, 1047200, 1049100, 1138600, 1170500, 1064500, 1190000, 1050200, 1090400, 1062800, 1061700, 1218001, 1068000, 1127700, 1144800, 1195100],1218000))

It’s basically using the test, but one of the numbers has been changed to be greater than the highest possible score. This results in an infinite loop.

I think I haven’t understood the challenge well.
What should I do exactly with the number which is largest than the highest possible score?

It’s an invalid score. That means that it should be immediately thrown out of (or removed from :wink:) the original list before any further actions take place.

2 Likes