Faire Software Engineer Interview Experience — Onsite Day 2 Coding on Discounts Over a Category DAG

Coding Part 1

Product categories on an e-commerce platform are hierarchical. The categories are not a strict tree, they form a DAG. That is, a category can belong to several parent categories at the same time.

For example:

C3_Shirts can belong to both [C2_Mens, C2_Womens]

A product inherits:

• the discount of its own category
• the discounts of all of its ancestor categories

The discount actually applied to a product is the maximum discount value among its own category and all of its ancestor categories.

Implement:

find_discount_sources(category_edges: Dict[str, List[str]], products: Dict[str, str], discounts: Dict[str, int]) -> Dict[str, int]

example:

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,
}
result = find_discount_sources(...)
result["p_3"] == 20

Coding Part 2

Now the team wants an audit, meaning they want to check how the discount logic actually arrives at its result. This time they do not just want to know what the final maximum discount is, they want to know: for each bottom-level C3 category, which discounted categories exist among its ancestors?

It still uses the same category hierarchy and discounts.

This time the return type is:

Dict[str, Set[str]]

for example:

        C1_Apparel
       /          \
C2_Mens            C2_Womens
       \          /
        C3_Shirts

and

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

then return

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