FastPrepVersioned Recipe Shopping Cart
Problems/Versioned Recipe Shopping Cart

Versioned Recipe Shopping Cart

Decagon logoDecagon● HardFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The report describes recipe-level ingredient discounts and compact version history with checkout that discards later versions. Related base reports specify highest-qualified ingredient tiers and idempotent changes. Only effective mutations create versions here; finite bounds and the batch interface are practice choices. The judged core matches the combined reports at about 90%.

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.
  • ["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 most 10^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.

More Decagon problems

  • Count Complete Tic-Tac-Toe GamesPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Rolling CSAT TrackerPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Batch API Requests with Retry DelaysPHONE SCREEN · Seen Sep 2026
All Decagon interview questionsSee Decagon hiring insights
Saved
class Solution {
    public int[] processCart(String[] recipeNames, String[][] recipeIngredients, String[] discountedIngredients, int[] discountThresholds, int[] discountAmounts, String[][] operations) {
        // write your code here
    }
}
Checking account…