Best Data Structure to store marks and ranks of students

Question

I have the following information of students with corresponding marks and ranks

Name   Marks  Rank
 A      30     1
 B      20     2
 C      10     3

The rank of the student is inversely proportional to the marks of the student. I have to find the best data structure to store the above information so that the following operations are executed in the most optimal manner(Best time complexity) . It can be assumed that student name is unique.

1. Given student name , find marks and rank
2. Given rank, find marks and name of the student
3. Update marks of a student.

I am thinking of using two hashmaps one for student and marks mapping and another for student name and rank mapping. Is there a better data structure for this?. Is there a way that i can make use of the fact that rank is inversely proportional to marks.

Answer 1

This can be done with two data structures:

1. A hash map that maps from student name to his grade.
2. An order statistic tree of students, where the key for comparisons is the grade.

---

This allows you to do all of the following operations in O(logn):

1. Find a student's rank: find it in the hash map, and then find its order statistic (rank) in the tree.
2. Update a student grade: find his old grade in the map, remove it from both map and tree, and reinsert it again with the new values.
3. Given a rank, use the order statistic tree to find the relevant student and his grade.

In addition, Finding a student's grade is done in O(1) (average case) using the hash map alone.

---

Note:

You can switch implementation of the student name->grade map to a tree map rather than hash map without influencing the complexity too much, and guaranteeing better worst case behavior. (Finding a grade will also be O(logn) and not O(1) with this change).

Answer 2

My suggestion is also to use two HashMap, but one of them is filled gradually instead of adding it's sorting complexity to update time. This would provide the following properties:

• fast reading byStudent
• slower updates O(n). If you update a lot, you could consider pulling reorder out of the addOrUpdate method, updating in batches, and calling reorder after each batch from the outside.
• eventually fast byRank reading.

---

class MyClass {
    Comparator<RankedStudent> comp = Comparator.comparingInt(e -> e.marks);
    private Map<String, RankedStudent> repo = new HashMap<>();
    private Map<Integer, RankedStudent> rankCache = new HashMap<>();

    public RankedStudent getByStudent(String student) {
        return repo.get(student);
    }

    public RankedStudent getByRank(Integer rank) {
        return Optional.ofNullable(rankCache.get(rank)).orElseGet(() -> {
            rankCache.putIfAbsent(rank, repo.values().stream().sorted((s1, s2) -> rank == s1.rank ? 1 : 0)
                    .findFirst().orElse(null));
            return rankCache.get(rank);
        });
    }

    public void addOrUpdate(String student, Integer marks) {
        repo.put(student, new RankedStudent(student, marks, -1));
        reorder();
    }

    public void reorder() {
        final Iterator<RankedStudent> it = repo.values().stream().sorted(comp.reversed()).iterator();
        IntStream.range(0, repo.size()).boxed().forEach(i -> it.next().rank = i + 1);
        rankCache.clear();
    }
}

class RankedStudent {

    public String name;
    public int marks;
    public int rank;

    public RankedStudent(String name, int marks, int rank) {
        this.name = name;
        this.marks = marks;
        this.rank = rank;
    }
}