Reward Top K Students

Medium
1429.

Reward Top K Students

MediumHash TableStringSortingHeap (Priority Queue)AmazonGoogle

Reward Top K Students is a medium coding problem on strings, hash table and sorting, asked in Amazon and Google interviews.

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^4
  • 1 <= positiveFeedback[i].length, negativeFeedback[j].length <= 100
  • the feedback words are lowercase English letters; no word is in both lists
  • n == report.length == studentId.length
  • 1 <= n <= 10^4
  • report[i] is lowercase words separated by single spaces, 1 <= report[i].length <= 100
  • 1 <= studentId[i] <= 10^9, all distinct
  • 1 <= k <= n
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} positiveFeedback
 * @param {string[]} negativeFeedback
 * @param {string[]} report
 * @param {number[]} studentId
 * @param {number} k
 * @return {number[]}
 */
var topStudents = function(positiveFeedback, negativeFeedback, report, studentId, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^4
  • 1 <= positiveFeedback[i].length, negativeFeedback[j].length <= 100
  • the feedback words are lowercase English letters; no word is in both lists
  • n == report.length == studentId.length
  • 1 <= n <= 10^4
  • report[i] is lowercase words separated by single spaces, 1 <= report[i].length <= 100
  • 1 <= studentId[i] <= 10^9, all distinct
  • 1 <= k <= n

Hints for Reward Top K Students

  1. Hint 1

    Put both word lists into hash sets so each word of a report is classified in O(1).

  2. Hint 2

    Score every report by splitting it on spaces: +3 for a positive word, -1 for a negative one.

  3. Hint 3

    Sort (points descending, id ascending) and take the first k — or keep a size-k heap if k is much smaller than n.

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

  1. Build sets from positiveFeedback and negativeFeedback.
  2. For each report, split it into words and add 3 or subtract 1 per word found in a set.
  3. Sort the (points, id) pairs by points descending, then id ascending.
  4. Return the ids of the first k pairs.

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 kind twice 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