Watch 3 video solutions for Apply Discount Every n Orders, a medium level problem involving Array, Hash Table, Design. This walkthrough by Coding Interviews has 259 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There is a supermarket that is frequented by many customers. The products sold at the supermarket are represented as two parallel integer arrays products and prices, where the ith product has an ID of products[i] and a price of prices[i].
When a customer is paying, their bill is represented as two parallel integer arrays product and amount, where the jth product they purchased has an ID of product[j], and amount[j] is how much of the product they bought. Their subtotal is calculated as the sum of each amount[j] * (price of the jth product).
The supermarket decided to have a sale. Every nth customer paying for their groceries will be given a percentage discount. The discount amount is given by discount, where they will be given discount percent off their subtotal. More formally, if their subtotal is bill, then they would actually pay bill * ((100 - discount) / 100).
Implement the Cashier class:
Cashier(int n, int discount, int[] products, int[] prices) Initializes the object with n, the discount, and the products and their prices.double getBill(int[] product, int[] amount) Returns the final total of the bill with the discount applied (if any). Answers within 10-5 of the actual value will be accepted.
Example 1:
Input
["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"]
[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]]
Output
[null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]
Explanation
Cashier cashier = new Cashier(3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]);
cashier.getBill([1,2],[1,2]); // return 500.0. 1st customer, no discount.
// bill = 1 * 100 + 2 * 200 = 500.
cashier.getBill([3,7],[10,10]); // return 4000.0. 2nd customer, no discount.
// bill = 10 * 300 + 10 * 100 = 4000.
cashier.getBill([1,2,3,4,5,6,7],[1,1,1,1,1,1,1]); // return 800.0. 3rd customer, 50% discount.
// Original bill = 1600
// Actual bill = 1600 * ((100 - 50) / 100) = 800.
cashier.getBill([4],[10]); // return 4000.0. 4th customer, no discount.
cashier.getBill([7,3],[10,10]); // return 4000.0. 5th customer, no discount.
cashier.getBill([7,5,3,1,6,4,2],[10,10,10,9,9,9,7]); // return 7350.0. 6th customer, 50% discount.
// Original bill = 14700, but with
// Actual bill = 14700 * ((100 - 50) / 100) = 7350.
cashier.getBill([2,3,5],[5,3,2]); // return 2500.0. 7th customer, no discount.
Constraints:
1 <= n <= 1040 <= discount <= 1001 <= products.length <= 200prices.length == products.length1 <= products[i] <= 2001 <= prices[i] <= 1000products are unique.1 <= product.length <= products.lengthamount.length == product.lengthproduct[j] exists in products.1 <= amount[j] <= 1000product are unique.1000 calls will be made to getBill.10-5 of the actual value will be accepted.Problem Overview: Design a cashier system that calculates the bill for customer orders. Each order contains product IDs and quantities. Every n-th customer receives a percentage discount on the total bill. The challenge is maintaining product prices and efficiently computing each order’s cost while tracking when the discount should be applied.
Approach 1: HashMap for Product Prices (Time: O(k) per order, Space: O(P))
Store product prices in a hash map where the key is the product ID and the value is its price. When getBill is called, iterate through the product list, perform a constant-time hash lookup for each price, multiply by the corresponding amount, and accumulate the total. Maintain an internal order counter. If the counter is divisible by n, apply the discount percentage to the computed bill. This approach works well when product IDs are sparse or not guaranteed to be contiguous. The hash lookup keeps price retrieval efficient and keeps the overall order processing time proportional to the number of products in the order.
This method relies heavily on constant-time lookups from a hash table. It fits naturally with problems that require quick key-based access and flexible product identifiers. In most real-world systems where product IDs may be arbitrary, this approach is the most practical.
Approach 2: Index Mapping with Arrays (Time: O(k) per order, Space: O(P))
If product IDs fall within a predictable numeric range, an array can replace the hash map. Use the product ID as the direct index in the array and store its price at that position. During billing, iterate through the ordered products and fetch prices using direct array indexing, which is slightly faster than hashing due to lower overhead.
The rest of the logic remains identical: increment the order counter, compute the total by multiplying price and quantity for each product, and apply the discount when orderCount % n == 0. This technique uses the strengths of arrays for constant-time access and minimal memory overhead when IDs are dense. It also keeps the implementation simple in languages where arrays are the default structure.
Because the problem focuses on maintaining internal state across calls, it also falls under classic design problems where the object must efficiently manage data and operations over time.
Recommended for interviews: The hash map approach is usually the expected solution. It handles arbitrary product IDs and clearly demonstrates understanding of constant-time lookups and stateful class design. Showing the array mapping optimization afterward highlights awareness of performance tradeoffs when IDs are bounded.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap for Product Prices | O(k) per order | O(P) | General case when product IDs may be sparse or non-contiguous |
| Index Mapping with Arrays | O(k) per order | O(P) | When product IDs fall within a small bounded range and direct indexing is possible |