Award top k hotels from reviews: A Sample Coding Interview Solution

The coding question

You get lists of positive and negative words, and reviews tagged with a hotel ID. Each positive word in a review is worth 3 points and each negative word -1. Return the k best hotel IDs, highest score first, with ties broken by lower ID.

Ask a few questions first

Ask	What we'll assume
What do the inputs look like?	Positive and negative words as space-separated strings, a list of hotel IDs, and a list of reviews where review i is about hotel i.
Do case and punctuation matter?	No. 'Clean,' and 'clean' are the same word, so lowercase everything and keep only letters.
If a word shows up twice in one review, does it count twice?	Yes, every time it appears.
Does a hotel with no matching words get ranked?	Yes, with a score of 0. It had reviews, it just didn't score.
What if k is bigger than the number of hotels?	Return all of them, best first.

A couple of examples

Input	Output
Positive 'clean comfy', negative 'dirty noisy'. Hotel 7: 'Clean, comfy room!' Hotel 3: 'Clean but noisy, NOISY.' k = 2	[7, 3]. Hotel 7 scores 6, and hotel 3 scores 3 - 2 = 1
Positive 'good', negative 'bad'. Hotel 5: 'good'. Hotel 2: 'bad bad bad'. Hotel 9: 'fine'. k = 3	[5, 9, 2], with scores 3, 0 and -3
Positive 'good', negative 'bad'. Hotels 4 and 1 each get the review 'good'. k = 5	[1, 4]. They tie at 3, so the lower ID goes first

Start with brute force

For each review, go through every positive word and every negative word and count how often it appears. Add that to the hotel's score. Then sort all hotels by score and take the first k.

Cost: O(W × (P + N) + h log h), where W is the total words in all reviews, P and N are the word list sizes, and h is the number of hotels. Checking each word against both whole lists is the slow part.

A better way

Put the words in a hash map from word to points: 3 for positive, -1 for negative. Now each word in a review is one O(1) lookup instead of a scan through both lists.

Splitting is where people slip. 'Clean,' and 'NOISY.' won't match unless you lowercase and drop punctuation. A regular expression that grabs runs of letters does both in one go.

For the top k, you don't need to sort every hotel. A heap of size k keeps just the best k as you go. Rank by (negative score, ID) so higher scores come first and ties go to the lower ID. Python's heapq.nsmallest does exactly that.

Build a map from word to points.
For each review, lowercase it, pull out the words, and add up their points.
Add that to the hotel's running score in another map.
Pick the best k by (negative score, hotel ID) with a size-k heap.

The code

solution.pypython

import heapq
import re


def award_top_k_hotels(positive, negative, hotel_ids, reviews, k):
    # positive and negative are space-separated word lists.
    # hotel_ids[i] is the hotel that reviews[i] is about.
    points = {}
    for word in positive.lower().split():
        points[word] = 3
    for word in negative.lower().split():
        points[word] = -1

    scores = {}
    for hotel_id, review in zip(hotel_ids, reviews):
        # Lowercase and keep only letters, so "Clean," matches "clean".
        words = re.findall(r"[a-z]+", review.lower())
        score = sum(points.get(word, 0) for word in words)
        scores[hotel_id] = scores.get(hotel_id, 0) + score

    # Highest score first, then lower ID. A heap of size k does the work.
    best = heapq.nsmallest(k, scores.items(), key=lambda item: (-item[1], item[0]))
    return [hotel_id for hotel_id, _ in best]

	Cost	Why
Time	O(P + N + W + h log k)	Build the map, look up each review word once, then one pass over h hotels with a heap of size k
Space	O(P + N + h)	The word map and one score per hotel

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

Punctuation and capitals: 'Clean,' and 'NOISY.' still match, because we lowercase and keep only letters.
A hotel whose reviews match nothing: it scores 0 and still gets ranked, ahead of hotels with negative scores.
Ties: the lower ID wins, so the output's the same every time.
k bigger than the number of hotels: returns all of them. k of 0, or no reviews at all: returns an empty list.

Common mistakes

Splitting on spaces only, so 'clean,' never matches 'clean'.
Matching substrings, so 'not' counts inside 'nothing'. Compare whole words.
Getting the tie-break backwards, or sorting IDs as strings when they're numbers, so 10 comes before 9.
Scoring each review separately and ranking reviews instead of adding them up per hotel.
Sorting every hotel when k is small. It works, but it's what the interviewer wants you to avoid.

Follow-up questions

What if a review says 'not clean'?

Now word order matters. Look at pairs of neighboring words, and when a negation like 'not' comes right before a positive word, flip its points. It's still one pass.

What if reviews keep streaming in and top k is asked often?

Keep the score map updated as reviews arrive, so each review is O(its words). Answer top k from the map with the same size-k heap.

What if there are millions of hotels across many machines?

Split hotels by ID across machines, have each return its own top k, and merge those small lists for the overall answer.

How the time adds up

Minutes	What you're doing
0–5	Ask about case, punctuation, ties and hotels with no matches
5–10	Brute force: check every word against both lists
10–20	A word to points map, and a size-k heap
20–35	Write the code
35–40	Test with the examples, ties and punctuation
40–45	Follow-up questions

Key concepts used here

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Booking.com.