How should I practice Recipe Cart with Undo and Redo?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Decagon phone screen problems in FastPrep.

Is Recipe Cart with Undo and Redo associated with Decagon?

FastPrep tags this as a Decagon phone screen coding practice problem when the problem catalog has that company and stage context.

Recipe Cart with Undo and Redo

Decagon● MediumFULLTIMEPHONE SCREEN

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 tag get_total_discounts is an equivalent query alias.
["undo"] reverses the most recent effective add/remove and makes it available for redo.
["redo"] reapplies the most recently undone effective mutation.

A new effective add or remove discards all redo history. A duplicate add, an absent remove, a discount query, or an undo/redo with no available event is a no-op for history and does not discard redo.

Return query results in encounter order. Mutations and history-control operations produce no result.

Function

processRecipeCart(recipeNames: String[], recipeIngredients: String[][], discountedIngredients: String[], discountThresholds: int[], discountAmounts: int[], operations: String[][]) → int[]

Examples

Example 1

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_discount"],["undo"],["get_total_discount"],["redo"],["get_total_discount"]]return = [8,3,8]

Four recipes share Garlic, so threshold 4 gives8. Undo removes the last recipe and leaves three, giving3. Redo restores four and the discount 8.

Example 2

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"],["undo"],["add_recipe","Chicken Parm"],["redo"],["get_total_discount"]]return = [3]

After undoing Stir Fry, adding Chicken Parm again is a no-op and keeps the redo event. Redo restores both recipes, giving discount 3.

Example 3

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"],["undo"],["add_recipe","Soup"],["redo"],["get_total_discount"]]return = [3]

Adding Soup is an effective new mutation after undo, so the redo of Stir Fry is discarded. The two current Garlic recipes give discount 3.

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 most 10^9.
1 <= operations.length <= 2000. Rows have exactly the stated tags and arities, and every mutation names a known catalog recipe.
At least one row is a discount query.