Iruka And Marks

Easy
0/40
profile
Contributed by
0 upvote

Problem statement

Iruka Umino is the instructor at the shinobi school at Konoha. He took a test of all the students in his class and evaluated their answer sheets on a grade of 100. He has ‘N’ number of students in his class.

You are given an ‘N’ and then you are provided with ‘N’ students with their names and marks.

You have to organize the list of students in such a way that students with higher marks come first and in the case of students with equal marks, the student with lexicographically smaller names comes first.

Example:- 
Input: ‘N’ = 3, ‘STUDENTS’ = [[‘naruto’, 50], [‘sasuke’, 95], [‘sakura’, 65]]

Output: [[‘sasuke’, 95], [‘sakura’, 65], [‘naruto’, 50]]

In the example above you can see that ‘sasuke’ got the highest marks so he came first in the output followed by ‘sakura’ and ‘naruto’ with the lowest marks.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

For each test case, the first line will contain a single integer 'N', the number of students in the class.

The next ‘N’  line contains two elements first is a string representing the name of the student and the second is an integer denoting the marks of the student.
Output format : 
For each test case print the elements in the defined order above.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^5
1 <= L <= 20
0 <= M <= 100
The Sum of the value of N for all the test cases is <= 10^5.
Time Limit: 1 sec

Here ‘L’ is the size of the string representing the name of the student and ‘M’ is the marks of the student.

Sample Input 1 :
2
3
naruto 50
sakura 65
sasuke 95
2
kiba 70
shikamaru 78
Sample Output 1 :
sasuke 95
sakura 65
naruto 50
shikamaru 78
kiba 70
Explanation Of Sample Input 1 :
For the first case:-
You can see that ‘sasuke’ got the highest marks so he came first in the output followed by ‘sakura’ and ‘naruto’ with the lowest marks.

For the second case-
Here ‘shikamaru’ got 78 marks greater than 70 so he comes first followed by ‘kiba’ with 70 marks.
Sample Input 2 :
2
5
minato 92
sakumo 87
itachi 99
madara 92
ino 80
3
minato 90
madara 90
hiruzen 90
Sample Output 2 :
itachi 99
madara 92
minato 92
sakumo 87
ino 80
hiruzen 90
madara 90
minato 90
Hint

Sorting function with a custom comparator

Approaches (1)
Sorting

We can sort the array in nondecreasing order on the basis of marks and if the two marks are equal then we can put the element with the lexicographically smaller name first. We can use the sort function with a custom comparator.  You can learn more about them for python here and for c++you can directly google it.

The steps are as follows:- 

compare ( pair1, pair 2 ):

  1. Check if the value of marks in both pairs is equal, if Yes:
    1. Compare the name and return the appropriate value according to the programming language.
  2. Else:
    1. Return  pair1.marks > pair2.marks.

arrangeStudents( arr, n ):

  1. Sort the array with the sort function with comparing as a custom comparator.
  2. Return the sorted array.
Time Complexity

O( N * log ( N ) * L ), Where N is the number of elements in the array and L is the maximum size of the name string of students.
 

We are sorting the array with the sort function which takes N * Log ( N ) time but the custom comparison function compares two strings which take the size of string time which is ‘L’.

Hence time complexity is O( N * log ( N ) * L ).

Space Complexity

O( 1 ).

 

We are not using any extra space.

Hence space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Iruka And Marks
Full screen
Console