We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Reward Top K Students

Difficulty: Medium

Problem Description

You are given two string arrays positive_feedback and negative_feedback, containing the words denoting positive and negative feedback, respectively. Each positive word in a feedback report increases the points of a student by 3, whereas each negative word decreases the points by 1. You are given n feedback reports represented by a string array report and a unique integer array student_id. Given an integer k, return the top k students after ranking them in non-increasing order by their points.

Key Insights

  • Each student starts with 0 points.
  • Positive words increase points by 3, while negative words decrease points by 1.
  • The students must be ranked by their points, and in the event of ties, by their student ID.
  • Efficient string processing is needed to count occurrences of feedback words in the reports.

Space and Time Complexity

Time Complexity: O(n * m + p + k log k), where:

  • n is the number of feedback reports,
  • m is the average length of each report,
  • p is the number of unique students,
  • k is the number of top students to return.

Space Complexity: O(p + m), where:

  • p is the number of unique students,
  • m is the space used for the positive and negative feedback sets.

Solution

The solution involves the following steps:

  1. Create sets for positive and negative feedback words to allow O(1) lookup.
  2. Initialize a dictionary to maintain scores for each student.
  3. Iterate through the reports and for each report:
    • Split the report into words.
    • Count the occurrences of positive and negative words and update the student's score accordingly.
  4. Store the results in a list and sort it based on the score and student ID.
  5. Return the top k student IDs.

The data structures used include sets for quick word lookup and a dictionary for storing student scores, followed by sorting to determine the top students.

Code Solutions

def topKStudents(positive_feedback, negative_feedback, report, student_id, k):
    # Create sets for positive and negative feedback
    positive_set = set(positive_feedback)
    negative_set = set(negative_feedback)
    
    # Dictionary to store scores of students
    scores = {}
    
    # Calculate scores for each report
    for i in range(len(report)):
        student = student_id[i]
        feedback_words = report[i].split()
        
        # Initialize student score if not present
        if student not in scores:
            scores[student] = 0
            
        for word in feedback_words:
            if word in positive_set:
                scores[student] += 3
            elif word in negative_set:
                scores[student] -= 1
                
    # Create a list of (student_id, score) pairs
    score_list = [(-score, student) for student, score in scores.items()]
    
    # Sort the list: first by score (desc), then by student_id (asc)
    score_list.sort()
    
    # Extract the top k student IDs
    return [student for _, student in score_list[:k]]
← Back to All Questions