Reward Top K Students

Reward Top K Students

What is this problem about?

The Reward Top K Students interview question gives you a list of positive and negative feedback words, and a list of student reports (each report is a list of words). Each positive word in a report earns 3 points, each negative word costs 1 point. You must return the IDs of the top k students sorted by score (descending), with ties broken by student ID (ascending).

Why is this asked in interviews?

Booking.com asks this problem because it combines hash table lookup, score computation, and priority queue or sorting — all common in recommendation systems, content moderation, and student/employee ranking platforms. It tests whether candidates can efficiently score items using a lookup set and then sort by a composite key.

Algorithmic pattern used

The pattern is hash set lookup combined with sorting or heap. Build sets for positive and negative words for O(1) lookup. For each student report, scan each word: if in positive set, add 3 to score; if in negative set, subtract 1. Store (-score, student_id) tuples for sorting (negative score for descending order, student_id for ascending tiebreak). Sort the tuples and return the first k student IDs. Alternatively, use a heap of size k.

Example explanation

Positive words: {"smart", "brilliant"}. Negative words: {"lazy", "bad"}.

Reports:

• Student 0: ["smart", "work", "lazy"] → 3 - 1 = 2.
• Student 1: ["brilliant", "bad"] → 3 - 1 = 2.
• Student 2: ["brilliant", "smart"] → 3 + 3 = 6.

Scores: [(2, 0), (2, 1), (6, 2)]. Sort by (-score, id): [(6,2), (2,0), (2,1)].

Top 2: [2, 0].

Common mistakes candidates make

• Using a list instead of a set for positive/negative words, causing O(w) lookup per word instead of O(1).
• Sorting by score ascending instead of descending — negate the score or reverse the sort.
• Forgetting the tiebreaker: student ID ascending when scores are equal.
• Counting a word as both positive and negative if it somehow appears in both sets — the problem guarantees no overlap, but verify.

Interview preparation tip

For the Reward Top K Students coding problem, the hash table, sorting, and heap interview pattern is the efficient path. Using sorted(scores, key=lambda x: (-x[0], x[1])) in Python naturally handles the composite sort key. Booking.com interviewers appreciate candidates who mention that the heap approach (using heapq.nsmallest with the same tuple key) is more efficient when k << n. Practice expressing composite sort keys cleanly.