Audit Discounted Category Ancestors
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. Audit the categories at the bottom of this hierarchy: for each one, report every discounted category among its ancestors, rather than only its largest discount.
For this exercise, assume categories lists every category, including isolated ones, and a bottom category is a graph leaf with no outgoing edge. The array discountCategories lists the keys of the discount dictionary; discount amounts do not affect this audit. Any listed key counts as discounted, even if its amount was zero. An ancestor must be reached through at least one edge, so a leaf's own discount is excluded.
Represent the result dictionary as a two-dimensional string array. Each row starts with a leaf's name, followed by its distinct discounted ancestors in increasing ASCII lexicographic order. Sort rows by leaf name in the same order. A leaf with no discounted ancestor still has a row containing just its name. Names are case-sensitive. If there are no categories, return an empty array.
Interview example
For example, a diamond has C1_Apparel above C2_Mens and C2_Womens; both lead to C3_Shirts. With discounts on C1_Apparel and C2_Womens, the audit set for C3_Shirts is {C1_Apparel, C2_Womens}. Reaching a category through several paths does not repeat it.
Function
findDiscountAncestorAudit(categories: String[], categoryEdges: String[][], discountCategories: String[]) → String[][]Examples
Example 1
categories = ["C1_Apparel","C2_Mens","C2_Womens","C3_Shirts"]categoryEdges = [["C1_Apparel","C2_Mens"],["C1_Apparel","C2_Womens"],["C2_Mens","C3_Shirts"],["C2_Womens","C3_Shirts"]]discountCategories = ["C1_Apparel","C2_Womens"]return = [["C3_Shirts","C1_Apparel","C2_Womens"]]The two discounted ancestors are C1_Apparel and C2_Womens. Each appears once, and the row begins with the leaf name C3_Shirts.
Example 2
categories = ["Root","Leaf","Isolated"]categoryEdges = [["Root","Leaf"]]discountCategories = ["Leaf","Isolated"]return = [["Isolated"],["Leaf"]]The leaves are Isolated and Leaf, in that order. Neither has a discounted strict ancestor. Their own discounts do not belong in the audit sets.
Example 3
categories = []categoryEdges = []discountCategories = []return = []An empty category list has no leaves to audit.
Constraints
- For this exercise, assume
0 <= categories.length <= 300and0 <= categoryEdges.length <= 500. - Every edge row has exactly
2strings. 0 <= discountCategories.length <= 300.- Every category name has between
1and40characters, using only ASCII letters, digits and underscores. categoriesanddiscountCategorieseach contain distinct names. Every edge endpoint and discount name occurs incategories.- The edges form a DAG. 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