No cache: inherited discounts
Why it matters "It repeats work, so remember the answers" is one of the strongest habits in programming, human or AI. Sometimes the work does not need repeating at all.
A shop's categories form a tree: Garden sits under Home, Tools under Garden, and so on. A marketing manager can set a discount on any category, and it applies to everything below it unless a nearer category sets its own. The checkout looks up the effective discount for thousands of categories at a time.
The data
parents = {"home": None, "garden": "home", "tools": "garden", "seeds": "garden"}
own = {"garden": 10, "seeds": 25} # discounts set directly, in percent
queries = ["tools", "seeds", "home"]
# effective_discounts(parents, own, queries) -> [10, 25, 0]The obvious fix for repeated walks up the tree is a cache. In this problem caches are banned. Look for a way that never repeats the work in the first place.
Write effective_discounts(parents, own, queries). parents maps every category to its parent, or None for a top-level category (there may be several, and the dict is in no particular order). own maps some categories to their own discount. For each category in queries, return the discount of the nearest category on its path to the top, starting with itself, that has one in own; 0 if none does. Rule: no cache or memo: no functools cache decorators and no name containing "cache" or "memo". Budget: at most 500,000 steps (steps()) for 3,000 categories, trees up to a few hundred levels deep, and 20,000 lookups.
Spotted a problem in this lesson? Report it · Ask about this lesson
This exercise opens soon
Finish the lesson before it and this one unlocks. The whole course is free, no account needed, and you can read this lesson right now.
This browser is blocking cookies for learn.floati.life, so lessons you finished here cannot open in order. Allow cookies for this site and reload.