Ggthjy

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('', ' ');//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

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 %dn", 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.