Maximum Inherited Product Discount
Updated
Problem statement
Product categories form a directed acyclic graph. An edge [parent, child] means that the child belongs to the parent. A category can have several parents.
Each product inherits discounts from its own category and every ancestor. Its applicable discount is the maximum of those values, not their sum.
The dictionaries are passed as entries: categoryEdges contains parent-child pairs, products contains [productId, category] pairs, and discountValues[i] is the discount for discountCategories[i]. Names are case-sensitive. Return one integer for each row of products, in that row order.
For this exercise, assume missing discounts count as 0. A category mentioned only by a product or discount is still a category; it has no other edges beyond those listed. An empty products array returns an empty result.
Interview example
The dictionaries are:
{
"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
}
}Here p_3 receives 20 through C2_Womens, which beats 15 at C2_Mens, 10 at C1_Apparel and 5 at C3_Shirts.
Function
findDiscountSources(categoryEdges: String[][], products: String[][], discountCategories: String[], discountValues: int[]) → int[]Examples
Example 1
categoryEdges = [["C1_Apparel","C2_Mens"],["C1_Apparel","C2_Womens"],["C1_Gifts","C2_Kitchen"],["C1_Gifts","C2_Souvenirs"],["C1_Home","C2_Kitchen"],["C1_Home","C2_Living"],["C1_Home","C2_Patio"],["C1_Outdoor","C2_Patio"],["C2_Kitchen","C3_Plates"],["C2_Kitchen","C3_Towels"],["C2_Living","C3_Candles"],["C2_Mens","C3_Shirts"],["C2_Patio","C3_Grills"],["C2_Souvenirs","C3_Magnets"],["C2_Souvenirs","C3_Snowglobes"],["C2_Womens","C3_Jewelry"],["C2_Womens","C3_Shirts"]]products = [["p_0","C3_Plates"],["p_1","C3_Towels"],["p_2","C3_Candles"],["p_3","C3_Shirts"],["p_4","C3_Shirts"]]discountCategories = ["C1_Apparel","C2_Mens","C2_Womens","C3_Shirts"]discountValues = [10,15,20,5]return = [0,0,0,20,20]The categories of p_0, p_1 and p_2 have no discounted ancestor or own discount, so their results are 0. Both p_3 and p_4 belong to C3_Shirts and receive the inherited maximum 20.
Example 2
categoryEdges = []products = [["p","Only"]]discountCategories = ["Only"]discountValues = [7]return = [7]An isolated category still applies its own discount of 7.
Example 3
categoryEdges = []products = []discountCategories = []discountValues = []return = []There are no product rows, so the result is empty.
Constraints
- For this exercise, assume
0 <= categoryEdges.length <= 1000and0 <= products.length <= 500. - Every row of
categoryEdgesandproductscontains exactly2strings. 0 <= discountCategories.length <= 300anddiscountCategories.length == discountValues.length.- Every name has between
1and40characters, using only ASCII letters, digits and underscores. 0 <= discountValues[i] <= 10^9.- The category edges form a DAG. There are at most
300distinct category names across edges, product categories and discount categories. - Product IDs are unique. Discount category names are unique. Repeated edges are allowed.
More Faire interview questions
Similar questions at other companies
- Course SchedulePlaud · ONSITE INTERVIEW
- Course ScheduleAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Course Schedule Cycle DetectionGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Detect a Cycle in a Directed GraphMakeMyTrip.com · ONSITE INTERVIEWMakeMyTrip.com interview questions
- Course ScheduleFlexTrade · ONSITE INTERVIEWFlexTrade interview questions
- Remove Redundant Task DependenciesMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Course ScheduleBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Can All Courses Be FinishedC3.ai · ONSITE INTERVIEWC3.ai interview questions
- Trace Terminal Company OwnershipPalantir · ONSITE INTERVIEWPalantir interview questions
- Deepest Common Ancestors in a Multi-Parent DAGSalesforce · ONSITE INTERVIEWSalesforce interview questions