Versioned Recipe Shopping Cart
Problem statement
Maintain a cooking-app cart containing at most one copy of each named recipe. Parallel arrays recipeNames and recipeIngredients give the catalog. Each selected recipe contributes one unit of every ingredient in its list.
Discount rows are given by discountedIngredients, discountThresholds and discountAmounts. An ingredient may have several tiers. For each ingredient, select the row with the greatest threshold not exceeding its current count, and contribute that row's amount exactly once. If no tier qualifies, it contributes 0. Sum these per-ingredient discounts. Row order and the relative amounts do not change which threshold wins.
The cart starts empty. Process these operation rows in order:
["add_recipe", recipeName]adds a catalog recipe; if already present, do nothing.["remove_recipe", recipeName]removes it; if absent, do nothing.["get_total_discount"]appends the current total discount. The existing plural tagget_total_discountsis an equivalent query alias.["get_version"]appends the current version number. It does not create a version.["checkout", version]restores an existing version and permanently discards every later version. It does not create a version.
The empty cart is version 0. Only an effective add or remove creates the next version. No-op mutations and queries leave it unchanged. After checkout to version v, the next effective mutation creates version v+1 on the new branch. Store compact add/remove history rather than a complete cart snapshot per version.
Return query results in encounter order. Mutations and history-control operations produce no result.
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.
Example 4
recipeNames = ["Chicken Parm","Stir Fry","Soup","Salad"]recipeIngredients = [["Garlic"],["Garlic"],["Garlic"],["Garlic"]]discountedIngredients = ["Garlic","Garlic"]discountThresholds = [2,4]discountAmounts = [3,8]operations = [["add_recipe","Chicken Parm"],["add_recipe","Stir Fry"],["add_recipe","Soup"],["add_recipe","Salad"],["get_total_discounts"],["add_recipe","Chicken Parm"],["get_version"],["checkout","2"],["get_total_discount"],["get_version"]]return = [8,4,3,2]Four effective adds create version 4 with discount 8. The duplicate add creates no version. Checkout to version 2 retains two Garlic recipes, giving discount 3 and version 2.
Constraints
1 <= recipeNames.length == recipeIngredients.length <= 2000. Recipe names are unique nonempty strings.1 <= recipeIngredients[i].length <= 20. Ingredient labels are strings and occur at most once per recipe.0 <= discountedIngredients.length == discountThresholds.length == discountAmounts.length <= 2000. Every discounted ingredient occurs in the catalog, and each (ingredient,threshold) pair is unique.1 <= discountThresholds[i] <= 10^9.1 <= discountAmounts[i] <= 10^6, and their sum is at most10^9.1 <= operations.length <= 2000. Rows have exactly the stated tags and arities, and every mutation names a known catalog recipe.- Every checkout version is a decimal integer string from 0 through the current version.
- At least one row is a discount query or get_version.