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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Reward Top K Students

Number: 2603

Difficulty: Medium

Paid? No

Companies: Booking.com, Amazon

Problem Description

We are given two arrays: positive_feedback and negative_feedback, which list the words that contribute positively and negatively (respectively) to a student's feedback score. Each student initially has 0 points, with each occurrence of a positive word in their feedback adding 3 points and each occurrence of a negative word subtracting 1 point. The input also includes a list of feedback reports and their corresponding unique student IDs. The task is to calculate each student's score based on the report feedback and then return the top k students ranked in non-increasing order by their score. In case of a tie in the score, the student with the lower ID should rank higher.

Key Insights

  • Use sets for positive and negative feedback words to allow constant time lookups.
  • Parse each report by splitting the string based on spaces and summing the scores for each word.
  • Maintain a mapping between student IDs and their computed scores.
  • Sort the students first by descending score and then by ascending student ID to handle tie-breakers.
  • The use of a sort with a custom key or a heap can both be effective methods to obtain the top k students.

Space and Time Complexity

Time Complexity: O(n * m + n log n), where n is the number of reports and m is the average number of words per report. Space Complexity: O(n + p + q), where n is the number of students/reports, p is the number of positive words, and q is the number of negative words.

Solution

The solution involves several clear steps:

  1. Convert positive_feedback and negative_feedback arrays into sets for efficient lookups.
  2. For each report in the feedback array, split the report into words.
  3. Calculate the score for each report by adding 3 for every positive word and subtracting 1 for every negative word.
  4. Create a list of tuples (student_id, score) from the processed reports.
  5. Sort this list using a custom sort key that sorts by descending score and ascending student_id.
  6. Extract the top k student IDs from this sorted list.

This sequential approach ensures that the solution is both clear and efficient while meeting the problem constraints.

Code Solutions

# Python solution with line-by-line comments

def top_k_students(positive_feedback, negative_feedback, report, student_id, k):
    # Convert positive and negative feedback lists to sets for O(1) lookups
    pos_set = set(positive_feedback)
    neg_set = set(negative_feedback)
    
    # List to store tuples of (student_id, score)
    scores = []
    
    # Process each report and calculate the score for each student
    for i in range(len(report)):
        # Split report into words
        words = report[i].split()
        score = 0
        # Calculate score: add 3 for each positive word and subtract 1 for each negative word
        for word in words:
            if word in pos_set:
                score += 3
            elif word in neg_set:
                score -= 1
        # Append the student's id and his score
        scores.append((student_id[i], score))
    
    # Sort students by descending score and in case of tie, ascending by student id
    scores.sort(key=lambda x: (-x[1], x[0]))
    
    # Extract the top k student ids
    return [stu_id for stu_id, _ in scores[:k]]

# Example usage:
if __name__ == '__main__':
    positive_feedback = ["smart", "brilliant", "studious"]
    negative_feedback = ["not"]
    report = ["this student is studious", "the student is smart"]
    student_id = [1, 2]
    k = 2
    print(top_k_students(positive_feedback, negative_feedback, report, student_id, k))
← Back to All Questions