Reward Top K Students - Practice Coding Problems

Reward Top K Students - Problem

Array Hash Table String Sorting Heap (Priority Queue) Medium

You are given two string arrays positive_feedback and negative_feedback, containing the words denoting positive and negative feedback, respectively. Note that no word is both positive and negative.

Initially every student has 0 points. 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 0-indexed string array report and a 0-indexed integer array student_id, where student_id[i] represents the ID of the student who has received the feedback report report[i]. The ID of each student is unique.

Given an integer k, return the top k students after ranking them in non-increasing order by their points. In case more than one student has the same points, the one with the lower ID ranks higher.

Input & Output

Example 1 — Basic Case

$ Input: positive_feedback = ["smart","brilliant","studious"], negative_feedback = ["not"], report = ["this student is studious","the student is smart"], student_id = [1,2], k = 2

› Output: [1,2]

💡 Note: Student 1: 'studious' (+3) = 3 points. Student 2: 'smart' (+3) = 3 points. Both have same score, so lower ID (1) ranks higher.

Example 2 — With Negative Feedback

$ Input: positive_feedback = ["smart","brilliant","studious"], negative_feedback = ["not"], report = ["this student is not studious","the student is smart"], student_id = [1,2], k = 2

› Output: [2,1]

💡 Note: Student 1: 'not' (-1) + 'studious' (+3) = 2 points. Student 2: 'smart' (+3) = 3 points. Student 2 ranks higher with better score.

Example 3 — Multiple Reports per Student

$ Input: positive_feedback = ["smart","brilliant"], negative_feedback = ["not"], report = ["smart","brilliant","not smart"], student_id = [1,1,2], k = 1

› Output: [1]

💡 Note: Student 1: 'smart' (+3) + 'brilliant' (+3) = 6 points. Student 2: 'not' (-1) + 'smart' (+3) = 2 points. Student 1 wins.

Constraints

1 ≤ positive_feedback.length, negative_feedback.length ≤ 10⁴
1 ≤ positive_feedback[i].length, negative_feedback[i].length ≤ 100
1 ≤ report.length ≤ 10⁴
1 ≤ report[i].length ≤ 100
1 ≤ student_id.length ≤ 10⁴
1 ≤ k ≤ student_id.length

Visualization

Tap to expand

Understanding the Visualization

Input Processing

Parse positive/negative feedback and student reports

Score Calculation

Calculate each student's total score from all their reports

Ranking & Selection

Sort by score (desc) then ID (asc), return top k

Key Takeaway

🎯 Key Insight: Use hash sets for fast word lookup, then custom sort by score and ID for efficient top-k selection

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to use hash sets for O(1) word lookup when calculating student scores, then sort by score (descending) and ID (ascending) for tie-breaking. Best approach uses hash map optimization with Time: O(n×m + s log s), Space: O(p + s).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Set Optimization	O(p + n × m + s log s)	O(p + s)	Use hash sets for O(1) word lookup and calculate scores efficiently
Brute Force with Linear Search	O(n × m × p + s log s)	O(s)	Calculate scores by checking each word against all positive/negative feedback arrays
Priority Queue for Top-K	O(p + n × m + s log k)	O(p + k)	Use min-heap to efficiently maintain only the top k students without full sorting

Hash Set Optimization — Algorithm Steps

Step 1: Convert feedback arrays to hash sets
Step 2: For each report word, check sets in O(1)
Step 3: Sort students and return top k

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Sets

Convert feedback arrays to hash sets

Fast Lookup

Check each word in O(1) time

Sort Results

Sort students by score and ID

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(char** positive_feedback, int pos_size, char** negative_feedback, int neg_size, char** report, int* student_id, int report_size, int k, int* returnSize) {
    // Simplified C implementation
    *returnSize = k;
    int* result = (int*)malloc(k * sizeof(int));
    // Implementation would require hash table library
    return result;
}

int main() {
    // Complex implementation required
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(p + n × m + s log s)

p words to build sets + n reports × m words + s students sorted

⚡ Linearithmic

Space Complexity

O(p + s)

Hash sets store p feedback words + scores for s students

✓ Linear Space

12.4K Views

Medium Frequency

~25 min Avg. Time

350 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Set Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler