Ranking Score System

Question

I have an assignment to solve this problem. There are a total of 12 test case files, 1 of which that I have failed due to exceeding limit on the script.

Question Description

Bob has somehow managed to obtain a class list of \$N\$ students that contains the name of the students, as well as their scores for an exam. The task is to generate the rank of each student in the class list.

Let \$S\$ be the number of students in the class list that have obtained a higher score than student \$X\$. The rank of student \$X\$ in the class list is formally defined as \$(S+1)\$. This means that if there are many students that obtain the same score, they will all have the same rank.

Input

The first line of input contains a single integer \$N\$, the number of students in the class list. \$N\$ lines will follow. Each line will describe one student in the following form: [name] [score].

Output

For each student, print the rank of the student in the following form: [name] [rank]. These students should be printed in the same order as the input.

Limits

• \$1 \leq N \leq 50000

• All the names of students will only contain uppercase and lowercase English letters with no spaces. The names will not be more than 20 characters long. It is possible that there can be 2 students with the same name.

• All scores of students will range from 0 to 109 inclusive.

Does anyone have a solution to my problem? Do inform me if any more information is needed. Any other comments on coding styles and space complexities that may arise are also appreciated, though the focus should be the time.

Here's my code and test cases.

import java.util.*;

//Comparator to rank people by score in ascending order
//No tiebreaking for equal scores is considered in this question
class PairComparator implements Comparator<List<Object>> {

    public int compare(List<Object> o1, List<Object> o2) {
        return (Integer)o1.get(0) - (Integer)o2.get(0);
    }
}




public class Ranking {
    private void run() {
        Scanner sc = new Scanner(System.in);
        ArrayList<List<Object>> inputPairs = new ArrayList<>();
        ArrayList<String> nameIterList = new ArrayList<>();//To store names in scanned order
        HashMap<String, Integer> dupeCount = new HashMap<>();//To consider cases where there are people with same names
        int count = sc.nextInt();
        for (int i=0;i<count;i++) {
            String name = sc.next();
            int score = sc.nextInt();
            name = checkDuplicates(nameIterList,name,dupeCount);//returns a unique name after considering duplicates
            List<Object> pair = List.of(score,name);//simulates a struct data structure in C with non-homogeneous elements
            inputPairs.add(pair);
            nameIterList.add(name);

        }


        Collections.sort(inputPairs, (new PairComparator()).reversed());//descending order sorting

        HashMap<String,Integer> nameRank = new HashMap<>();//name and respective rank in O(1) time
        makeTable(nameRank,inputPairs);
        for (String name: nameIterList) {
            System.out.println(String.format("%s %d",name.trim(),nameRank.get(name)));
        } //for displaying purposes, repeated name is printed


    }

    public static void main(String[] args) {
        Ranking newRanking = new Ranking();
        newRanking.run();
    }

    public static void makeTable(HashMap<String,Integer> nameRank, ArrayList<List<Object>> inputPairs) {
        int lowestRank = 1;
        int previousScore = (Integer)inputPairs.get(0).get(0);
        for (int i=0;i<inputPairs.size();i++) {
            List<Object> pairs = inputPairs.get(i);
            String name = (String) pairs.get(1);
            int score = (Integer) pairs.get(0);
            int currentRank = i+1;//default rank if there are no tiebreakers
            if (score==previousScore) {
                currentRank = lowestRank;//takes the smallest possible rank for a tie-breaker
            } else {
                lowestRank = currentRank;//updates the smallest possible rank as tie-breaker is broken
                previousScore = score;
            }
            nameRank.put(name,currentRank);//updates HashMap
        }
    }


    public static String checkDuplicates(ArrayList<String> nameList, String name, HashMap<String,Integer> dupeCount) {
        if (dupeCount.containsKey(name)) {
            int count = dupeCount.get(name);

            dupeCount.replace(name,count+1); //updates the duplicateTable
            return name+ new String(new char[count]).replace('\0', ' ');//new name is appending with spaces, trimmed later on
        } else {//entry not found, add in as the first one
            dupeCount.put(name,1);
            return name;//no change
        }

    }
}

Sample Inputs

25
Sloane 15
RartheCat 94
Taylor 34
Shark 52
Jayce 58
Westin 91
Blakely 6
Dexter 1
Davion 78
Saanvi 65
Tyson 15
Kiana 31
Roberto 88
Shark 55
MrPanda 25
Rar 26
Blair 12
RartheCat 81
Zip 74
Saul 58
ProfTan 77
SJShark 0
Georgia 79
Darian 44
Aleah 7

Sample Output

Sloane 19
RartheCat 1
Taylor 15
Shark 13
Jayce 10
Westin 2
Blakely 23
Dexter 24
Davion 6
Saanvi 9
Tyson 19
Kiana 16
Roberto 3
Shark 12
MrPanda 18
Rar 17
Blair 21
RartheCat 4
Zip 8
Saul 10
ProfTan 7
SJShark 25
Georgia 5
Darian 14
Aleah 22

Answer 1

Your data model is slowing down your code.

    ArrayList<List<Object>> inputPairs = new ArrayList<>();
    ArrayList<String> nameIterList = new ArrayList<>();//To store names in scanned order
    HashMap<String, Integer> dupeCount = new HashMap<>();//To consider cases where there are people with same names

Calling ArrayList.add() will add an item to the array list. If insufficient room exists in its storage area, the area reallocated double its previous size, and the information copied to the new storage area. With 50000 names, with an initial allocated space of 8 items, you will go through 13 reallocations of the inputPairs and nameIterList containers.

The HashMap stores its information differently, but it will suffer from the same doubling of capacity steps, with an additional penalty of "rebinning" the contents into the proper bins.

All of this takes time, and all of this can all be avoided by pre-allocating your storage container sizes. You know what the limit is: 50000. Alternately, you can read in N and then allocate properly sized storage containers.

    int count = sc.nextInt();
    ArrayList<List<Object>> inputPairs = new ArrayList<>(count);
    ArrayList<String> nameIterList = new ArrayList<>(count);
    HashMap<String, Integer> dupeCount = new HashMap<>(count*2);

A HashMap will rebin by default at 75% capacity, so I've initialized it at double the required capacity, so it won't exceed the limit.

---

ArrayList<List<Object>> may not be the worst storage structure to use, but it comes close. List.of(score,name) should allocate a specialized, immutable two-member structure to use for the list, but you still have to go through the overhead of the List interface to .get() at the members. Worst, the score has to be boxed from an efficient int into a full blown Integer object. This auto boxing takes both time and space. Worse, the additional object allocations will cause additional cache misses, slowing down the program. True, the Integer objects will probably all be interned varieties, due to their restricted range, but it all adds up to your time-limit-exceeded issue.

List.of(score, name) was used to avoid creating your own simple class:

class StudentRecord {
    String name;
    int score;
}

Instead of 3 objects (at least) per student, you only have two: the StudentRecord and the name. Access to the member fields is fast; no .get(int) overhead. (But even this is overhead that you don't need!)

---

Checking for duplicate names, and creating fake names to avoid the duplicates is a time wasting operation. We can avoid it, with a smarter algorithm.

---

The better way

First: let's simplify the data down to the bare minimum...

int count = sc.nextInt();
String[] names = new String[count];
int[] score = new int[count];

... two parallel arrays, one containing the student names (in order), and one containing the scores (in order).

Let's jump to the middle...

int[] rank = new int[110];

You have 110 possible score values, each which corresponds to exactly one rank. If you have 5 students with a score of 109 and one student with a score of 108, then rank[109] should contain 1, and rank[108] should contain 6.

Jumping to the end...

for(int i=0; i<count; i++) {
   System.out.printf("%s %d\n", name[i], rank[score[i]]);
}

... prints out the student, looks up the rank corresponding to their score and prints that as well.

Creation of the rank[] array

Since this is a programming challenge, I'll leave this up to you. There are several ways to do it. Good luck.