Max inherited discount and discount-source audit in a category DAG

An e-commerce platform organizes product categories in a hierarchy that is not a strict tree but a directed acyclic graph (DAG): a category can belong to several parent categories at the same time. For example, C3_Shirts belongs to both C2_Mens and C2_Womens.

A discount can be attached to any category. A product inherits the discount of its own category and the discounts of all ancestors of that category, and the discount actually applied to the product is the largest discount value among its own category and all of its ancestors.

The inputs are three maps:

• category_edges: each parent category mapped to the list of its direct child categories;
• products: each product ID mapped to the one category it belongs to;
• discounts: a category mapped to its integer discount value; a category without an entry has no discount.

category_edges = {
 "C1_Apparel": ["C2_Mens", "C2_Womens"],
 "C1_Gifts": ["C2_Kitchen", "C2_Souvenirs"],
 "C1_Home": ["C2_Kitchen", "C2_Living", "C2_Patio"],
 "C1_Outdoor": ["C2_Patio"],
 "C2_Kitchen": ["C3_Plates", "C3_Towels"],
 "C2_Living": ["C3_Candles"],
 "C2_Mens": ["C3_Shirts"],
 "C2_Patio": ["C3_Grills"],
 "C2_Souvenirs": ["C3_Magnets", "C3_Snowglobes"],
 "C2_Womens": ["C3_Jewelry", "C3_Shirts"],
}
products = {
 "p_0": "C3_Plates",
 "p_1": "C3_Towels",
 "p_2": "C3_Candles",
 "p_3": "C3_Shirts",
 "p_4": "C3_Shirts",
}
discounts = {
 "C1_Apparel": 10,
 "C2_Mens": 15,
 "C2_Womens": 20,
 "C3_Shirts": 5,
}

The interview had two coding parts on this hierarchy.

Constraints and Clarifications

• The hierarchy is acyclic: no category is its own ancestor.
• In the example, the prefixes C1_, C2_ and C3_ mark three levels, and no C3_ category has children. Whether real inputs always have exactly three levels is not specified.
• Input sizes were not given.

Clarifying Questions

• In Part 1, what should a product map to when neither its category nor any ancestor has a discount: 0, or no entry at all?
• Can a product's category be missing from category_edges altogether, with no parent and no children?
• Are discount values always positive, and is 0 a meaningful discount?
• Should bottom-level categories be recognized by having no children, or by the C3_ prefix?
• In Part 2, does a bottom-level category's own discount put that category in its own set?
• In Part 2, should a bottom-level category with no discounted category in its ancestry appear with an empty set, or be left out?
• How large and how deep can the hierarchy get? Is a recursive traversal safe?

Part 1 — Applied discount per product

Implement

def find_discount_sources(
 category_edges: dict[str, list[str]],
 products: dict[str, str],
 discounts: dict[str, int],
) -> dict[str, int]:

which returns, for every product, the discount applied to it.

In the example, result["p_3"] == 20: C3_Shirts carries 5, its parents C2_Mens and C2_Womens carry 15 and 20, and their common parent C1_Apparel carries 10, so the largest value is 20. p_4 is also in C3_Shirts, so result["p_4"] == 20 as well. No category at or above p_0, p_1 or p_2 has a discount; what those products map to is the first clarifying question.

What This Part Should Cover

• Every path upward is considered when a category has several parents
• Each category is evaluated once, with the time and space complexity stated
• Edge cases: no applicable discount, a category with no parents, a category absent from the hierarchy, deep hierarchies

Part 2 — Audit the discount sources of each bottom-level category

The team now wants to audit the discount logic: instead of only the largest discount, it wants to know which discounted categories exist in the ancestry of each bottom-level category. Implement a function that takes the same category_edges and discounts and returns a dict[str, set[str]] mapping each bottom-level category to the set of discounted categories in its ancestry.

 C1_Apparel
 / \
 C2_Mens C2_Womens
 \ /
 C3_Shirts

discounts = {"C1_Apparel": 10, "C2_Womens": 20}

result = {"C3_Shirts": {"C1_Apparel", "C2_Womens"}}

C2_Mens is an ancestor of C3_Shirts but has no discount, so it is not listed. C1_Apparel is reachable along two paths and appears once.

What This Part Should Cover

• A precise definition of the bottom-level categories and of which categories belong in each set
• Deduplication across several paths, and reuse of work among categories that share ancestors
• Complexity in terms of categories, edges and discounted categories, including the size of the output
• Consistency with Part 1: the largest discount among a bottom-level category's sources equals the discount Part 1 applies to its products