Versioned Recipe Shopping Cart
Learn this problem
DecagonFULLTIMEPHONE SCREENProblem statement
You are building a shopping cart for a cooking app. Each recipe has a unique name and a list of ingredients. The cart contains at most one copy of each recipe.
A bulk-discount rule names an ingredient, a minimum quantity, and a discount amount. Count one unit of an ingredient for every cart recipe whose ingredient list contains it. A rule contributes its discount amount exactly once when the current count of its ingredient is at least its minimum quantity. The total discount is the sum contributed by all qualifying rules.
The cart starts empty at version 0. Process the rows in operations in order:
["add_recipe", recipeName]adds an absent recipe and creates the next version.["remove_recipe", recipeName]removes a present recipe and creates the next version.["get_total_discounts"]appends the current total discount to the answer without creating a version.["get_version"]appends the current version number to the answer without creating a version.["checkout", version]restores the cart to the state at that version and permanently discards every later version. It does not itself create a version. The next add or remove operation createsversion + 1on the new history branch.
Return the results of all get_total_discounts and get_version operations in encounter order.
Store compact add/remove history rather than a complete cart snapshot for every version. A checkout may reconstruct its selected state by replaying the retained history prefix.
Function
processCart(recipeNames: String[], recipeIngredients: String[][], discountedIngredients: String[], discountThresholds: int[], discountAmounts: int[], operations: String[][]) → int[]Examples
Example 1
recipeNames = ["A","B","C"]recipeIngredients = [["Chicken","Garlic"],["Garlic","Rice"],["Chicken"]]discountedIngredients = ["Chicken","Garlic"]discountThresholds = [2,2]discountAmounts = [5,3]operations = [["add_recipe","A"],["get_version"],["add_recipe","B"],["get_total_discounts"],["checkout","1"],["get_version"],["get_total_discounts"]]return = [1,3,1,0]Adding A creates version 1. Adding B creates version 2, where Garlic occurs twice and contributes 3. Checkout restores version 1, so only A remains and no discount rule qualifies.
Example 2
recipeNames = ["A","B","C"]recipeIngredients = [["Chicken","Garlic"],["Garlic","Rice"],["Chicken"]]discountedIngredients = ["Chicken","Garlic"]discountThresholds = [2,2]discountAmounts = [5,3]operations = [["add_recipe","A"],["add_recipe","B"],["remove_recipe","A"],["get_total_discounts"],["get_version"],["checkout","2"],["get_version"],["add_recipe","C"],["get_total_discounts"],["get_version"]]return = [0,3,2,8,3]After removing A, only B remains at version 3, so the total discount is 0. Checkout to version 2 restores A and B. Adding C replaces the discarded branch with a new version 3; both discount rules then qualify for a total of 8.
Example 3
recipeNames = ["A","B"]recipeIngredients = [["Garlic"],["Garlic"]]discountedIngredients = ["Garlic"]discountThresholds = [2]discountAmounts = [4]operations = [["add_recipe","A"],["add_recipe","B"],["get_total_discounts"],["checkout","0"],["get_version"],["add_recipe","B"],["get_total_discounts"]]return = [4,0,0]At version 2, two recipes contribute Garlic, so the discount is 4. Checkout to version 0 empties the cart and discards both later versions. Adding B creates a new version 1, where the threshold is not met.
Constraints
1 <= recipeNames.length == recipeIngredients.length <= 2000.- Recipe names are unique non-empty strings.
1 <= recipeIngredients[i].length <= 20, and each recipe lists an ingredient at most once.discountedIngredients.length == discountThresholds.length == discountAmounts.length.0 <= discountedIngredients.length <= 2000, and discounted ingredient names are unique and occur in the recipe catalog.2 <= discountThresholds[i] <= recipeNames.length.1 <= discountAmounts[i] <= 10^6, and their sum is at most10^9.1 <= operations.length <= 2000.- Every add names a known recipe that is absent from the current cart, and every remove names a recipe that is present.
- Every checkout names an integer version from
0through the current version. - At least one operation is
get_total_discountsorget_version. - Do not retain a complete cart snapshot for every version; use space linear in the recipe catalog, current cart state, and compact mutation history.