FastPrepAudit Discounted Category Ancestors
Problems/Audit Discounted Category Ancestors

Audit Discounted Category Ancestors

Faire logoFaire● MediumFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The category DAG, the goal of auditing ancestors, and the diamond example match the report at about 95%. We chose these rules: a graph leaf is a category with no children, ancestors are strict, the category lists are written out in full, the output is a sorted array, and the limits.

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 <= 300 and 0 <= categoryEdges.length <= 500.
  • Every edge row has exactly 2 strings.
  • 0 <= discountCategories.length <= 300.
  • Every category name has between 1 and 40 characters, using only ASCII letters, digits and underscores.
  • categories and discountCategories each contain distinct names. Every edge endpoint and discount name occurs in categories.
  • The edges form a DAG. Repeated edges are allowed.

More Faire interview questions

  • Maximum Inherited Product DiscountONSITE 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 String[][] findDiscountAncestorAudit(String[] categories, String[][] categoryEdges, String[] discountCategories) {
        // Write your code here.
    }
}
Checking account…