Group Linked Merchant Records
Learn this problem
StripeFULLTIMEPHONE SCREENProblem statement
You are given merchant dictionaries serialized as records. Each row contains alternating key and value strings: [key1, value1, key2, value2, ...]. Every row contains exactly one non-empty merchant_id. A row may also contain the identity fields email, phone, and address, plus arbitrary additional fields.
Two records are directly linked when they share the same non-empty value for at least one identity field with the same key. Merchant groups are the transitive closure of those direct links. Additional fields are valid input but never establish links.
Return every connected group as its merchant IDs sorted lexicographically. Sort the groups lexicographically by their complete sorted ID lists.
Function
linkedMerchantGroups(records: String[][]) → List<List<String>>Examples
Example 1
records = [["merchant_id","m1","email","a@x.com"],["merchant_id","m2","email","a@x.com","phone","222"],["merchant_id","m3","phone","222"],["merchant_id","m4","address","4 Main"]]return = [["m1","m2","m3"],["m4"]]m1 links to m2 by email, and m2 links to m3 by phone, so transitivity joins all three.
Example 2
records = [["merchant_id","b","note","same"],["merchant_id","a","note","same"],["merchant_id","c","email","c@x.com"]]return = [["a"],["b"],["c"]]The shared extra field note does not establish a link.
Constraints
1 <= records.length <= 200000- Each row contains between
1and20key-value pairs. - Keys and values are printable-ASCII strings of length at most
200. - Every
merchant_idis non-empty and unique. - Within a record, each of
merchant_id,email,phone, andaddressappears at most once.