FastPrepRecipe Shopping Cart Discounts

Recipe Shopping Cart Discounts

Decagon logoDecagon● MediumFULLTIMEPHONE SCREEN

Updated

Problem statement

A cooking application has a fixed recipe catalog. Each recipe has a unique name and a list of distinct ingredient labels. The shopping cart initially contains no recipes and can contain each recipe at most once.

Process the operation rows in order:

  • ["add_recipe", name] adds the named recipe. Adding a recipe already in the cart does nothing.
  • ["remove_recipe", name] removes the named recipe. Removing an absent recipe does nothing.
  • ["get_total_discount"] appends the cart's current total discount to the answer.

Each selected recipe contributes one unit of every ingredient it lists. Discount row i applies to discountedIngredients[i] when that ingredient's count is at least discountThresholds[i]. For each ingredient, choose exactly the qualifying row with the greatest threshold and contribute its corresponding discountAmounts[i]. If no row qualifies, its contribution is zero. Sum the contributions of all discounted ingredients.

Amounts need not increase with thresholds. Do not sum multiple tiers for one ingredient or choose a row merely because its amount is greatest. Return the results of the discount queries in order.

Function

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

Examples

Example 1

recipeNames = ["A","B","C","D"]recipeIngredients = [["Garlic","Chicken"],["Garlic","Rice"],["Garlic","Chicken"],["Garlic","Herbs"]]discountedIngredients = ["Garlic","Garlic","Garlic","Chicken","Herbs"]discountThresholds = [1,2,4,2,1]discountAmounts = [1,3,8,5,7]operations = [["get_total_discount"],["add_recipe","A"],["get_total_discount"],["add_recipe","B"],["get_total_discount"],["add_recipe","A"],["get_total_discount"],["remove_recipe","A"],["get_total_discount"]]return = [0,1,3,3,1]

The empty cart contributes 0. A alone qualifies for discount 1; A and B qualify for 3. Adding A again leaves 3, and removing A leaves B with discount 1.

Example 2

recipeNames = ["A","B","C","D"]recipeIngredients = [["Garlic","Chicken"],["Garlic","Rice"],["Garlic","Chicken"],["Garlic","Herbs"]]discountedIngredients = ["Garlic","Garlic","Garlic","Chicken","Herbs"]discountThresholds = [1,2,4,2,1]discountAmounts = [1,3,8,5,7]operations = [["add_recipe","A"],["add_recipe","B"],["add_recipe","C"],["get_total_discount"],["add_recipe","D"],["get_total_discount"],["remove_recipe","C"],["get_total_discount"]]return = [8,20,10]

A, B and C yield Garlic 3 plus Chicken 5 = 8. Adding D yields Garlic 8, Chicken 5 and Herbs 7 = 20. Removing C leaves Garlic 3 and Herbs 7 = 10.

Example 3

recipeNames = ["A","B","C","D"]recipeIngredients = [["Garlic","Chicken"],["Garlic","Rice"],["Garlic","Chicken"],["Garlic","Herbs"]]discountedIngredients = ["Garlic","Garlic","Garlic"]discountThresholds = [4,1,2]discountAmounts = [2,7,9]operations = [["add_recipe","A"],["add_recipe","B"],["add_recipe","C"],["add_recipe","D"],["get_total_discount"]]return = [2]

Four Garlic units select threshold 4 with amount 2. The lower threshold 2 has a greater amount 9, but it is not the selected tier.

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.

More Decagon Phone Screen questions

Similar questions at other companies

Decagon interview experiences

All Decagon interview questionsSee Decagon hiring insights
Saved
class Solution {
    public int[] processRecipeCart(String[] recipeNames, String[][] recipeIngredients, String[] discountedIngredients, int[] discountThresholds, int[] discountAmounts, String[][] operations) {
        return new int[0];
    }
}
Checking account…