FastPrepMaximum Inherited Product Discount
Problems/Maximum Inherited Product Discount

Maximum Inherited Product Discount

Faire logoFaire● MediumFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The category DAG, inherited maximum and supplied example match the report at about 95%. Missing discounts count as zero; numeric and size bounds are practice rules.

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 <= 1000 and 0 <= products.length <= 500.
  • Every row of categoryEdges and products contains exactly 2 strings.
  • 0 <= discountCategories.length <= 300 and discountCategories.length == discountValues.length.
  • Every name has between 1 and 40 characters, using only ASCII letters, digits and underscores.
  • 0 <= discountValues[i] <= 10^9.
  • The category edges form a DAG. There are at most 300 distinct 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

  • Audit Discounted Category AncestorsONSITE INTERVIEW · Seen Oct 2026
  • Peak Bike Demand IntervalsONSITE INTERVIEW · Seen Oct 2026
  • Find the First Contiguous HaikuPHONE SCREEN · Seen Sep 2026

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
See Faire hiring insights
Saved
class Solution {
    public int[] findDiscountSources(String[][] categoryEdges, String[][] products, String[] discountCategories, int[] discountValues) {
        // Write your code here.
    }
}
Checking account…