Reward Top K Students — Solution in Python, Java & C++
Reward Top K Students solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Reward Top K Students is a medium coding problem on strings, hash table and sorting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Sorting, Heap
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A mentor writes one feedback report per student. Words in positiveFeedback signal praise and words in negativeFeedback signal criticism; no word is in both lists.
Every student starts with 0 points. Each occurrence of a positive word in a student's report adds 3 points, and each occurrence of a negative word subtracts 1. Report report[i] belongs to the student with id studentId[i]; reports are lowercase words separated by single spaces, and ids are distinct.
Rank the students by points, highest first; students with equal points are ranked by smaller id first. Return the ids of the top k students in rank order.
Example 1
Input: positiveFeedback = ["sharp","kind"], negativeFeedback = ["late","rude"], report = ["sharp and kind","late again","kind but late"], studentId = [7,3,5], k = 2
Output: [7,5]
Explanation: Student 7 scores 6, student 5 scores 3 - 1 = 2, student 3 scores -1.
Example 2
Input: positiveFeedback = ["sharp","kind"], negativeFeedback = ["late","rude"], report = ["rude","late"], studentId = [4,2], k = 1
Output: [2]
Explanation: Both score -1; the smaller id ranks first.
Constraints
1 <= positiveFeedback.length, negativeFeedback.length <= 10^41 <= positiveFeedback[i].length, negativeFeedback[j].length <= 100the feedback words are lowercase English letters; no word is in both listsn == report.length == studentId.length1 <= n <= 10^4report[i] is lowercase words separated by single spaces, 1 <= report[i].length <= 1001 <= studentId[i] <= 10^9, all distinct1 <= k <= n
Hints for Reward Top K Students
Hint 1
Put both word lists into hash sets so each word of a report is classified in O(1).
Hint 2
Score every report by splitting it on spaces: +3 for a positive word, -1 for a negative one.
Hint 3
Sort
(points descending, id ascending)and take the firstk— or keep a size-kheap ifkis much smaller thann.
How to solve Reward Top K Students
Scoring is a hash-set lookup per word; ranking is a sort by a composite key. The only care needed is the tie rule.
Approach
- Build sets from
positiveFeedbackandnegativeFeedback. - For each report, split it into words and add 3 or subtract 1 per word found in a set.
- Sort the
(points, id)pairs by points descending, then id ascending. - Return the ids of the first
kpairs.
Why it works
Points depend only on each word's membership, and the two sets are disjoint, so the classification is unambiguous. The composite key is a total order (ids are distinct), so the top k is unique.
Complexity
- Time —
O(L + n log n) - Space —
O(W + n)
Pitfalls
- Count every occurrence: a report that says
kindtwice earns 6 points. - Points can be negative — do not clamp at zero.
- Ties go to the smaller id, the opposite direction from the points.
Reference solution
Python
from typing import List
def topStudents(positiveFeedback: List[str], negativeFeedback: List[str], report: List[str], studentId: List[int], k: int) -> List[int]:
pos, neg = set(positiveFeedback), set(negativeFeedback)
rows = []
for text, sid in zip(report, studentId):
points = 0
for w in text.split():
if w in pos:
points += 3
elif w in neg:
points -= 1
rows.append((-points, sid))
rows.sort()
return [sid for _, sid in rows[:k]]Java
public static int[] topStudents(String[] positiveFeedback, String[] negativeFeedback, String[] report, int[] studentId, int k) {
Set<String> pos = new HashSet<>(Arrays.asList(positiveFeedback));
Set<String> neg = new HashSet<>(Arrays.asList(negativeFeedback));
int n = report.length;
int[][] rows = new int[n][2];
for (int i = 0; i < n; i++) {
int points = 0;
for (String w : report[i].split(" ")) {
if (pos.contains(w)) points += 3;
else if (neg.contains(w)) points -= 1;
}
rows[i][0] = points;
rows[i][1] = studentId[i];
}
Arrays.sort(rows, (a, b) -> a[0] != b[0] ? Integer.compare(b[0], a[0]) : Integer.compare(a[1], b[1]));
int[] res = new int[k];
for (int t = 0; t < k; t++) res[t] = rows[t][1];
return res;
}C++
vector<int> topStudents(vector<string>& positiveFeedback, vector<string>& negativeFeedback, vector<string>& report, vector<int>& studentId, int k) {
unordered_set<string> pos(positiveFeedback.begin(), positiveFeedback.end());
unordered_set<string> neg(negativeFeedback.begin(), negativeFeedback.end());
vector<pair<int, int>> rows; // (-points, id) sorts into rank order
for (size_t i = 0; i < report.size(); i++) {
istringstream in(report[i]);
string w;
int points = 0;
while (in >> w) {
if (pos.count(w)) points += 3;
else if (neg.count(w)) points -= 1;
}
rows.push_back({-points, studentId[i]});
}
sort(rows.begin(), rows.end());
vector<int> res;
for (int t = 0; t < k; t++) res.push_back(rows[t].second);
return res;
}JavaScript
var topStudents = function(positiveFeedback, negativeFeedback, report, studentId, k) {
var pos = new Set(positiveFeedback), neg = new Set(negativeFeedback);
var rows = [];
for (var i = 0; i < report.length; i++) {
var words = report[i].split(' ');
var points = 0;
for (var j = 0; j < words.length; j++) {
if (pos.has(words[j])) points += 3;
else if (neg.has(words[j])) points -= 1;
}
rows.push([points, studentId[i]]);
}
rows.sort(function(a, b) { return b[0] - a[0] || a[1] - b[1]; });
var res = [];
for (var t = 0; t < k; t++) res.push(rows[t][1]);
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets