How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Decagon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Decagon during technical interviews.

Implement a Recipe Cart | Decagon Coding Question

Implement a Recipe Cart

Company: Decagon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are building a shopping cart for a cooking app. The system is initialized with: - A recipe catalog: each `recipe_name` maps to a list of ingredients used by that recipe. - A discount table: each ingredient maps to a list of bulk-discount rules of the form `(threshold_quantity, discount_dollars)`. Users can add recipes to their cart. At most one copy of each recipe can be in the cart at any time. An ingredient's cart quantity is the number of selected recipes that contain that ingredient. For each ingredient, apply only the best qualifying discount: the discount associated with the largest threshold less than or equal to that ingredient's current quantity. If no threshold qualifies, the discount for that ingredient is `0`. The total discount is the sum of all ingredient discounts. Implement a `ShoppingCart` class with the following API: ```text add_recipe(recipe_name): Adds the recipe to the cart. If the recipe is already in the cart, this is a no-op. remove_recipe(recipe_name): Removes the recipe from the cart. If the recipe is not in the cart, this is a no-op. get_total_discount(): Returns the current total discount in dollars. ``` Example: ```text Cart contains: Chicken Parm, Stir Fry Chicken Parm ingredients include: Garlic Stir Fry ingredients include: Garlic Garlic quantity = 2 Garlic discounts = [(2, 3), (4, 8)] Quantity 0 or 1 -> $0 off Quantity 2 or 3 -> $3 off Quantity 4 or more -> $8 off ``` So if the cart currently has exactly two recipes containing Garlic, Garlic contributes `$3` to the total discount. Part 2: Add undo and redo support. Extend the class with: ```text undo(): Reverses the most recent cart-changing add or remove operation. If there is nothing to undo, this is a no-op. redo(): Re-applies the most recently undone operation. If there is nothing to redo, this is a no-op. ``` Additional rules: - Performing a new cart-changing operation clears the redo history. - `get_total_discount()` must always reflect the current cart state after any sequence of adds, removes, undos, and redos. - No-op `add_recipe` and `remove_recipe` calls do not need to be recorded in undo history.

Quick Answer: This question evaluates the ability to design and implement stateful data structures and aggregation logic for tracking ingredient counts, applying tiered bulk discounts, and managing undo/redo history.

Part 1: Recipe Cart Discount Tracker

You are given a recipe catalog, an ingredient discount table, and a sequence of cart operations. A recipe can appear in the cart at most once. The quantity of an ingredient is the number of currently selected recipes that contain that ingredient. For each ingredient, apply only one discount rule: the rule with the largest threshold less than or equal to the current quantity. If no threshold qualifies, that ingredient contributes 0. Process the operations and return the total cart discount after every get query. This is the function-based version of implementing the ShoppingCart class.

Constraints

0 <= len(recipe_names) == len(recipe_ingredients) <= 10^4
0 <= len(discount_ingredients) == len(discount_rules) <= 10^4
1 <= len(operations) <= 10^5
The sum of all recipe ingredient list lengths is at most 2 * 10^5
The sum of all discount rule counts is at most 2 * 10^5
recipe_names are unique, discount_ingredients are unique, thresholds are positive integers, and discounts are non-negative integers

Examples

Input: (['Chicken Parm', 'Stir Fry', 'Salad'], [['Garlic', 'Chicken', 'Cheese'], ['Garlic', 'Broccoli'], ['Lettuce']], ['Garlic', 'Chicken'], [[[2, 3], [4, 8]], [[1, 2], [2, 5]]], [['add', 'Chicken Parm'], ['get'], ['add', 'Stir Fry'], ['get'], ['remove', 'Chicken Parm'], ['get']])

Expected Output: [2, 5, 0]

Explanation: Chicken Parm alone gives Chicken quantity 1 for a $2 discount. Adding Stir Fry raises Garlic to quantity 2 for $3 more, so total becomes $5. Removing Chicken Parm drops both Garlic and Chicken below their thresholds.

Input: (['A', 'B'], [['x'], ['x', 'y']], ['x', 'y'], [[[2, 4]], [[1, 1]]], [['add', 'A'], ['add', 'A'], ['get'], ['remove', 'B'], ['get'], ['add', 'B'], ['get']])

Expected Output: [0, 0, 5]

Explanation: Adding A twice is a no-op on the second call. Removing B before it is in the cart is also a no-op. After B is added, x reaches 2 for $4 and y reaches 1 for $1.

Input: ([], [], [], [], [['get']])

Expected Output: [0]

Explanation: Edge case: empty catalog and no discounts. The total discount is always 0.

Input: (['R1', 'R2', 'R3', 'R4'], [['g'], ['g'], ['g'], ['g']], ['g'], [[[2, 3], [4, 8]]], [['add', 'R1'], ['get'], ['add', 'R2'], ['get'], ['add', 'R3'], ['get'], ['add', 'R4'], ['get']])

Expected Output: [0, 3, 3, 8]

Explanation: This checks threshold boundaries: quantity 1 gives $0, 2 gives $3, 3 still gives $3, and 4 gives $8.

Hints

Recomputing the full discount from scratch after every add or remove is too slow. Track the current quantity of each ingredient and update only the ingredients touched by the recipe being added or removed.
Sort each ingredient's discount rules by threshold. Then you can use binary search to find the best qualifying rule for a given quantity.

Part 2: Recipe Cart with Undo and Redo

Extend the recipe cart simulator with undo and redo. The cart rules are the same as in Part 1: a recipe can appear at most once, ingredient quantity is the number of selected recipes containing that ingredient, and each ingredient contributes only its best qualifying discount. In addition, undo reverses the most recent successful add or remove, and redo reapplies the most recently undone operation. A new successful add or remove clears the redo history. No-op add/remove calls are not recorded. Return the total discount after every get query.

Constraints

0 <= len(recipe_names) == len(recipe_ingredients) <= 10^4
0 <= len(discount_ingredients) == len(discount_rules) <= 10^4
1 <= len(operations) <= 10^5
The sum of all recipe ingredient list lengths is at most 2 * 10^5
The sum of all discount rule counts is at most 2 * 10^5
recipe_names are unique, discount_ingredients are unique, thresholds are positive integers, and discounts are non-negative integers

Examples

Input: (['A', 'B'], [['x'], ['x', 'y']], ['x', 'y'], [[[2, 4]], [[1, 1]]], [['add', 'A'], ['add', 'B'], ['get'], ['undo'], ['get'], ['redo'], ['get']])

Expected Output: [5, 0, 5]

Explanation: After adding both recipes, x qualifies for $4 and y for $1. Undo removes the effect of adding B, and redo restores it.

Input: (['A', 'B', 'C'], [['g'], ['g'], ['z']], ['g', 'z'], [[[2, 3]], [[1, 2]]], [['add', 'A'], ['add', 'B'], ['remove', 'A'], ['get'], ['undo'], ['get'], ['redo'], ['get'], ['undo'], ['add', 'C'], ['redo'], ['get']])

Expected Output: [0, 3, 0, 5]

Explanation: The final redo does nothing because adding C is a new successful cart-changing operation, so it clears the redo history.

Input: (['A'], [['m']], ['m'], [[[1, 7]]], [['undo'], ['redo'], ['remove', 'A'], ['add', 'A'], ['get'], ['add', 'A'], ['undo'], ['get'], ['redo'], ['get']])

Expected Output: [7, 0, 7]

Explanation: Edge case: undo and redo with empty history do nothing. The duplicate add is also a no-op and must not overwrite the real history.

Input: (['R1', 'R2'], [['a'], ['b']], ['a', 'b'], [[[1, 1]], [[1, 2]]], [['add', 'R1'], ['add', 'R2'], ['undo'], ['undo'], ['undo'], ['get'], ['redo'], ['get'], ['redo'], ['get']])

Expected Output: [0, 1, 3]

Explanation: This checks multiple undos past the available history, followed by redoing the undone operations in order.

Hints

Use one stack for undo history and one stack for redo history. When you undo an add, you perform a remove; when you undo a remove, you perform an add.
Do not recompute the whole cart after every history action. Reuse the same incremental ingredient-count update logic from add/remove for undo and redo too.

Quick Overview

This question evaluates the ability to design and implement stateful data structures and aggregation logic for tracking ingredient counts, applying tiered bulk discounts, and managing undo/redo history.