Kata Potter
Level: Advanced 60–90 minConcepts: AlgorithmsBusiness LogicEdge CasesIncremental Design
A bookshop sells five different books in a series at €8 each. Buying multiple unique titles earns a discount. Your job: calculate the cheapest price for any basket of books.
Pricing Rules
| Unique Titles in Set | Discount |
|---|---|
| 1 book | 0% (€8) |
| 2 different books | 5% (€15.20) |
| 3 different books | 10% (€21.60) |
| 4 different books | 20% (€25.60) |
| 5 different books | 25% (€30.00) |
Books are identified as Book 1 through Book 5.
The Catch
When a basket contains multiple copies, you must group them into sets that minimize total cost. The greedy approach (always making the biggest set) doesn’t always work.
Example
Basket: 2× Book 1, 2× Book 2, 2× Book 3, 1× Book 4, 1× Book 5
Greedy grouping (wrong):
- Set of 5: (1,2,3,4,5) = 5 × €8 × 0.75 = €30.00
- Set of 3: (1,2,3) = 3 × €8 × 0.90 = €21.60
- Total: €51.60
Optimal grouping (correct):
- Set of 4: (1,2,3,4) = 4 × €8 × 0.80 = €25.60
- Set of 4: (1,2,3,5) = 4 × €8 × 0.80 = €25.60
- Total: €51.20
Two sets of 4 is cheaper than a set of 5 plus a set of 3.
Test Cases
| Basket | Expected Price |
|---|---|
| (empty) | €0.00 |
| 1× Book 1 | €8.00 |
| 2× Book 1 | €16.00 |
| 1× Book 1, 1× Book 2 | €15.20 |
| 1× Book 1, 1× Book 2, 1× Book 3 | €21.60 |
| 1× Book 1, 1× Book 2, 1× Book 3, 1× Book 4 | €25.60 |
| 1× each of all 5 | €30.00 |
| 2× Book 1, 1× Book 2 | €23.20 (€15.20 + €8.00) |
| 2× each of Books 1–5 | €60.00 (2 sets of 5) |
| 2×(1,2,3), 1×(4,5) | €51.20 (2 sets of 4, not 5+3) |
The last test case is the critical one — it proves your algorithm handles optimization correctly.
Bonus
- Generalize to N books with configurable discount tiers
- Return the grouping breakdown alongside the price
- Handle large baskets efficiently (100+ books)
Hint
Start with the simple cases — single books, single sets of unique titles. The algorithm gets interesting when you have duplicates. One approach: generate all possible groupings and pick the cheapest. A smarter approach: recognize that splitting a set of 5 + set of 3 into two sets of 4 always saves money, and apply that transformation.