Bakery Bestsellers
You run a small bakery, and the till keeps a log with one line per item sold: croissant, scone, croissant, bagel, and so on. The front window only has room for a few trays.
Before tomorrow you want to know which items sold the most today, so they get the window. You do not care how they are ranked among themselves, only which ones make the cut.
Your task
Write bestsellers(sales, k). Return the k items that appear most often in sales, in any order, each item once.
The input is chosen so the answer is unique: the k-th best item always sold strictly more than the item in place k + 1.
bestsellers(sales: string[], k: int) → string[] Any order of the returned list is accepted.
Examples
sales = ["scone", "croissant", "bagel", "croissant", "scone", "croissant", "muffin"] k = 2
["croissant", "scone"]
Counts: croissant 3, scone 2, bagel 1, muffin 1. The two bestsellers are croissant and scone. Returning ["scone", "croissant"] is just as correct.
sales = ["bagel", "bagel", "eclair", "donut", "donut", "donut"] k = 1
["donut"]
Donut sold 3, bagel 2, eclair 1. Bagel was sold first, but donut sold the most.
Constraints
- 1 ≤ sales.length ≤ 100,000
- 1 ≤ k ≤ number of different items in sales
- Item names are non-empty lowercase strings.
- The set of the k most sold items is unique.
Start with brute force
Take each different item, count it by scanning the whole log, and then repeatedly pick the item with the largest count that you have not picked yet.
Counting each item by rescanning costs O(n) per item, so O(n · m) for m different items. With 100,000 sales and thousands of items that is hundreds of millions of steps. Counting once with a map, then sorting the m items by count, gets you to O(n + m log m), which is fine. Buckets remove even the sort.
Hints
0 of 4 shown- Hint 1
Before you can pick the top items, what number do you need to know for every item? How would you get it in one pass over the log?
- Hint 2
Count with a map from item to count. Now the problem is: given those counts, pick the k biggest. Sorting the items by count works. Can you avoid a full sort?
- Hint 3
No count can be bigger than
sales.length. What if you made one bucket for every possible count, and dropped each item into the bucket for its count? - Hint 4
Build the count map. Then make a list of buckets indexed 0 to
sales.length, where bucketcholds the items sold exactlyctimes. Walk the buckets from the highest count down, collecting items until you havek.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
There are two steps: count every item, then pick the biggest counts. Counting is one pass with a map. For picking, notice that counts are small whole numbers between 1 and n, so you can file items by count instead of sorting them.
Trace [scone, croissant, bagel, croissant, scone, croissant, muffin] with k = 2:
- Count: scone → 2, croissant → 3, bagel → 1, muffin → 1.
- Buckets (0 to 7): bucket 1 = [bagel, muffin], bucket 2 = [scone], bucket 3 = [croissant], the rest empty.
- Walk down from bucket 7. Buckets 7 to 4 are empty. Bucket 3 gives croissant.
- Bucket 2 gives scone. Now there are 2 items, so stop:
[croissant, scone].
Sorting the m different items by count is a perfectly good answer too, and in an interview it is often what people write first. A heap of size k is the other common choice when k is much smaller than m.
function bestsellers(sales, k) {
const count = new Map(); // item -> times sold
for (const item of sales) count.set(item, (count.get(item) || 0) + 1);
// buckets[c] = items sold exactly c times
const buckets = Array.from({ length: sales.length + 1 }, () => []);
for (const [item, c] of count) buckets[c].push(item);
const top = [];
for (let c = sales.length; c >= 1; c--) { // highest count first
for (const item of buckets[c]) {
top.push(item);
if (top.length === k) return top;
}
}
return top; // never reached: k is at most the number of items
}def bestsellers(sales, k):
count = {} # item -> times sold
for item in sales:
count[item] = count.get(item, 0) + 1
# buckets[c] = items sold exactly c times
buckets = [[] for _ in range(len(sales) + 1)]
for item, c in count.items():
buckets[c].append(item)
top = []
for c in range(len(sales), 0, -1): # highest count first
for item in buckets[c]:
top.append(item)
if len(top) == k:
return top
return top # never reached: k is at most the number of itemsRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.