Apply Discount Every n Orders

Apply Discount Every n Orders

What is this problem about?

The "Apply Discount Every n Orders interview question" is a system design and implementation task. You need to create a Cashier class for a store. This store has a special promotion: every $n^{th}$ customer gets a discount on their total bill. The class needs to store product prices and handle a getBill method that processes a customer's order and applies the discount if applicable.

Why is this asked in interviews?

Meta asks the "Apply Discount Every n Orders coding problem" to evaluate a candidate's ability to design a simple class and maintain internal state. It tests your proficiency with "Hash Table interview pattern" (for looking up product prices) and basic arithmetic (for calculating totals and percentages). It's a practical problem that mimics real-world point-of-sale systems.

Algorithmic pattern used

This problem uses the Class Design and Hash Map patterns.

1. Initialization: In the constructor, store the product IDs and their prices in a hash map for $O(1)$ lookup time. Initialize a counter to track the number of customers.
2. State Management: Increment the customer counter every time getBill is called.
3. Price Calculation: Iterate through the ordered items, look up their prices in the map, and sum them up.
4. Discount Logic: Use the modulo operator count % n == 0 to determine if the current customer is the $n^{th}$ customer. If so, apply the discount formula: total - (discount * total / 100).

Example explanation

Store: n=3, Discount=50%. Prices: [Apples: 10, Bananas: 20]

1. Customer 1 buys 2 Apples. Bill: 20. (Counter=1)
2. Customer 2 buys 1 Banana. Bill: 20. (Counter=2)
3. Customer 3 buys 1 Apple and 1 Banana. Base Total: $10+20=30$.
   • Counter is 3, so apply 50% discount.
   • Final Bill: $30 - (50\% imes 30) = 15$.

Common mistakes candidates make

• Inefficient Lookup: Using a list to find product prices, which makes the getBill method $O(P imes I)$ where $P$ is total products and $I$ is items in order. A map makes it $O(I)$.
• Integer Division: Forgetting that discount calculations often require floating-point numbers. Dividing by 100 in integer math can lead to precision loss.
• Counter Reset: Misunderstanding the "every $n$ orders" rule and resetting the counter incorrectly. Using counter % n == 0 is the safest way.

Interview preparation tip

Practice designing classes that store state. This is a common requirement for "Object-Oriented Design" or "System Implementation" interviews. Always choose the most efficient data structure for lookups, which is almost always a Hash Map.