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. ```python 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 ```python 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. ```hint Look upward, once The map lists each parent's children, but a product needs the categories above it. Decide which direction to traverse, and what to remember per category so that ancestors shared by many categories, such as `C2_Kitchen` under both `C1_Gifts` and `C1_Home`, are not re-walked for every product. ``` #### 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. ```text 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. ```hint Combine what the parents know A category's ancestry is its parents plus their ancestries. Think about the order in which to visit categories so that each one can build its set from sets already computed, and what happens when two parents report the same ancestor. ``` #### 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 ### What a Strong Answer Covers - Settles the unresolved policies before coding: products with no discount, self-inclusion, how bottom-level categories are identified, empty sets - Notices that the edges point from parent to child, while both parts need information to flow from ancestors down to descendants - Shares work across the DAG instead of starting a fresh walk for every product or every bottom-level category - Handles deep hierarchies without hitting the recursion limit, and detects a cycle if the input breaks the DAG promise - Tests covering a diamond, several roots, a category outside the hierarchy, and agreement between Part 1 and Part 2 ### Follow-up Questions - For each product, also report which category supplied the applied discount. How do you break ties when two categories share the largest value? - Discounts change many times a day while the hierarchy rarely changes. What would you precompute, and what must be recomputed when one category's discount changes? - The hierarchy has millions of categories but only a handful carry discounts. Would a different traversal make Part 2 cheaper? - A product can now belong to several categories. What changes in each part?