How should I practice Evolving Merchant Clusters and Persistent Pins?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Stripe online assessment problems in FastPrep.

Is Evolving Merchant Clusters and Persistent Pins associated with Stripe?

FastPrep tags this as a Stripe online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Evolving Merchant Clusters and Persistent Pins

Learn this problem

● Hard

StripeNEW GRADINTERNOA

See Stripe hiring insights

Problem statement

Build an entity-clustering system for merchants whose shared attributes can expire over three days.

Complete evolvingMerchantClusters. The parameters day1, day2, and day3 contain the records first reported on those days. Every record has this format:

merchant_id,link_type,duration

The integer duration includes the report day. For example, a record with duration 2 reported on day 1 is active on days 1 and 2. A later record may renew the same merchant and link type. That pair is active on a day when at least one of its reported lifetimes covers that day.

A merchant enters the system on the first day it appears and never leaves. On each day, create an undirected graph over all merchants seen so far:

Two distinct merchants are adjacent when they share at least one active link_type.
A cluster is a connected component with at least two merchants.
A merchant's degree is its number of distinct adjacent merchants, even if a pair shares several active link types.

Pin lifecycle

Every cluster has one pin. Process the days in order and choose each current cluster's pin from the previous day's pins that are members of the current component:

If there are no such previous pins, choose a fresh pin: the merchant with greatest current-day degree, breaking ties by lexicographically smaller merchant_id.
If there is exactly one such previous pin, preserve it. This covers a cluster that merely gains merchants and the side of a split that retains its old pin.
If there are two or more such previous pins, the clusters have merged. Choose among those prior pins by greatest current-day degree, breaking ties by lexicographically smaller merchant_id.

This rule also resolves a day on which splits and merges happen simultaneously: only previous pins actually contained in the current component are candidates.

Output

Return a flattened array of strings. For each day, first append Day X:, where X is 1, 2, or 3. Then append one string for each cluster on that day.

Order clusters by decreasing size, then by increasing pin ID when sizes tie. Sort the merchant IDs within a cluster lexicographically and format the line as:

pin_merchant_id:merchant_id1,merchant_id2,...

The pin must also appear in the merchant list. Do not output singleton components.

Function

evolvingMerchantClusters(day1: String[], day2: String[], day3: String[]) → String[]

Examples

Example 1

day1 = ["acct_a,address:main,2","acct_b,address:main,2"]day2 = ["acct_b,email:team,2","acct_c,email:team,2"]day3 = []return = ["Day 1:","acct_a:acct_a,acct_b","Day 2:","acct_a:acct_a,acct_b,acct_c","Day 3:","acct_b:acct_b,acct_c"]

On day 1, acct_a wins the degree tie alphabetically. On day 2, acct_c joins the cluster through acct_b, so the cluster preserves acct_a even though acct_b now has higher degree. On day 3, the address link has expired. The component containing acct_b and acct_c no longer contains the old pin, so it chooses acct_b by the fresh-pin rule.

Example 2

day1 = ["a1,left,3","a2,left,3","b1,right,3","b2,right,3"]day2 = ["a2,bridge,2","b1,bridge,2"]day3 = []return = ["Day 1:","a1:a1,a2","b1:b1,b2","Day 2:","b1:a1,a2,b1,b2","Day 3:","b1:a1,a2,b1,b2"]

The day-1 components have pins a1 and b1. The bridge merges them on day 2. In the merged graph, b1 has degree 2 while a1 has degree 1, so b1 becomes the merged pin. Every link remains active on day 3, and that pin is preserved.

Example 3

day1 = []day2 = ["m1,z,1","m2,z,1","a,x,2","b,x,2","c,x,2"]day3 = []return = ["Day 1:","Day 2:","a:a,b,c","m1:m1,m2","Day 3:","a:a,b,c"]

Day 1 has no clusters, so only its header is emitted. On day 2, the size-3 cluster is listed before the size-2 cluster. The z links expire before day 3, while the x cluster and its pin persist.

Constraints

Exactly three daily batches are supplied, and 0 <= day1.length + day2.length + day3.length <= 600.
There are at most 200 distinct merchant IDs and at most 200 distinct link types.
Every row has exactly three comma-separated, non-empty fields. Neither merchant_id nor link_type contains a comma.
Every merchant_id contains 1 to 30 lowercase ASCII letters, digits, or underscores. Every link_type contains 1 to 60 printable ASCII characters.
1 <= duration <= 3. A daily batch contains no duplicate (merchant_id, link_type) pair.
The same pair may appear again on a later day. It is active while at least one of its reported lifetimes includes the current day.