Reward Top K Students

Here’s an explanation of the problem and a guide to solving it:

Problem

Given positive and negative feedback words and a set of reports with associated student IDs, the task is to calculate the points for each student and return the top k students. Positive feedback words add 3 points, while negative feedback words subtract 1 point.

Solution

The solution can be broken down into several steps:

1. Create Feedback Sets: Convert positive and negative feedback words into sets for faster lookup.

2. Initialize Student Points: Create a dictionary or an array to store points for each student, initialized to 0.

3. Calculate Points: Iterate through the feedback reports and corresponding student IDs. For each report, split the report into words and check if each word is in the positive or negative feedback sets. Update the student’s points accordingly.

4. Sort Students: Sort the students based on their points in non-increasing order, and if the points are the same, then by their ID in non-decreasing order.

5. Get Top k Students: Return the top k students after sorting.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:
        # Create sets for fast lookup
        positive_set = set(positive_feedback)
        negative_set = set(negative_feedback)

        # Initialize student points
        points = collections.defaultdict(int)

        # Calculate points for each student
        for r, student in zip(report, student_id):
            words = r.split()
            for word in words:
                if word in positive_set:
                    points[student] += 3
                elif word in negative_set:
                    points[student] -= 1

        # Sort students based on points and ID
        sorted_students = sorted(points.keys(), key=lambda x: (-points[x], x))

        # Return top k students
        return sorted_students[:k]

Explanation

• positive_set and negative_set are used for fast lookup of positive and negative feedback words.
• points dictionary keeps track of the points for each student.
• sorted_students contains student IDs sorted by their points in non-increasing order and by their ID in non-decreasing order if points are the same.
• Finally, the top k students are returned.

This code will provide the correct solution for the given problem and constraints.