Problem · Tree
Normalize Loan Merchants to Root Businesses
Learn this problem● Medium
AffirmFULLTIMEPHONE SCREEN
AffirmFULLTIMEPHONE SCREENProblem statement
A lender receives loans associated with merchant names. The lender also has a fixed business hierarchy represented by parallel arrays: parents[i] is the direct parent business of children[i].
For every value in loanMerchants, follow parent links until you reach a root business: a name that has no parent. Return the root business name for each loan merchant in the original loan order.
A root business used directly as a loan merchant resolves to itself.
Function
normalizeLoanMerchants(parents: String[], children: String[], loanMerchants: String[]) → String[]Examples
Example 1
parents = ["Northstar","Northstar","FreshCo"]children = ["FreshCo","Spark","Market"]loanMerchants = ["Market","Spark","Northstar"]return = ["Northstar","Northstar","Northstar"]Market belongs to FreshCo, which belongs to Northstar. Spark also belongs to Northstar, and the root merchant resolves to itself.
Example 2
parents = ["Atlas","Atlas","Beta"]children = ["Beta","Gamma","Delta"]loanMerchants = ["Delta","Gamma","Atlas","Beta"]return = ["Atlas","Atlas","Atlas","Atlas"]Every merchant in this hierarchy reaches Atlas.
Example 3
parents = ["A","B"]children = ["A1","B1"]loanMerchants = ["B1","A1","B"]return = ["B","A","B"]The two independent hierarchies resolve to roots A and B while preserving loan order.
Constraints
0 <= parents.length == children.length <= 100000.1 <= loanMerchants.length <= 100000.- Names are nonempty, case-sensitive strings of at most 100 characters.
- Each child has at most one parent, and the hierarchy is acyclic.
- Every loan merchant appears in the hierarchy or is a root business.