Frontend School

Monitored Merchant Clusters

DSA
hard

Monitored Merchant Clusters

Hard
Union Find
Data Structures
Graph

Overview

Razorpay processes a vast number of transactions daily, involving a complex network of merchants. To maintain financial stability and detect potential anomalies, it's crucial to monitor how merchants form operational clusters through 'trust' relationships. Some merchants are flagged as 'high-risk' based on various criteria. We need to ensure that as new trust relationships are established, the resulting merchant clusters remain stable, meaning the proportion of high-risk merchants does not exceed a predefined threshold.

What you need to do / Task

Implement a function countStableClusters that, given an initial set of merchants (some marked as high-risk) and a series of potential trust relationships, determines the final number of stable merchant clusters.

Your solution should:

  1. Initialize each merchant as an independent cluster.
  2. Process each trustRelationship sequentially.
  3. For each relationship (u, v):
    • If u and v are already in the same cluster, do nothing.
    • Otherwise, calculate the characteristics (total merchants, high-risk merchants) of the hypothetical merged cluster.
    • If the high-risk merchant ratio (high-risk count / total count) of this hypothetical merged cluster is less than or equal to k, then u and v's clusters should be merged.
    • If the ratio exceeds k, the trust relationship is deemed unstable and the clusters remain separate.
  4. After processing all relationships, return the total count of distinct stable clusters.

Input & output

Function Signature:

function countStableClusters(n: number, highRiskMerchants: number[], trustRelationships: number[][], k: number): number
  • n: An integer representing the total number of merchants, indexed from 0 to n-1.
  • highRiskMerchants: An array of integers, where each integer is the 0-based index of a merchant identified as high-risk.
  • trustRelationships: An array of [u, v] pairs. Each pair represents a potential trust relationship between merchant u and merchant v.
  • k: A floating-point number representing the maximum allowed ratio of high-risk merchants to total merchants within any stable cluster. A ratio R is stable if R <= k.
  • Returns: An integer, the final count of distinct stable merchant clusters after processing all relationships.

Clarifications

  • Merchant indices are 0-based.
  • k can be 0.0 (no high-risk merchants allowed in any cluster) or 1.0 (any number of high-risk merchants allowed).
  • An empty cluster (which wouldn't happen in this problem with n >= 1) would have an undefined ratio. A cluster with 0 high-risk merchants and any positive total count has a ratio of 0.
  • Comparisons involving floating-point numbers should be handled carefully to avoid precision issues. A direct a / b <= k comparison is generally acceptable for typical competitive programming scenarios unless extreme precision is specified. For strictness, consider a <= k * b to avoid floating-point division issues, especially if b can be 0 (though b will be at least 1 here).

Examples

1

Example 1

Input:

n = 5, highRiskMerchants = [0, 2], trustRelationships = [[0, 1], [3, 4]], k = 0.5

Output:

3

Note:

Initial: 5 clusters. High-risk merchants: {0, 2}.

  1. Process [0, 1]: Merchants 0 and 1 merge. Cluster {0,1} has 2 members, 1 high-risk (0). Ratio = 1/2 = 0.5. Since 0.5 <= 0.5 (k), merge is stable. Current clusters: {0,1}, {2}, {3}, {4}.
  2. Process [3, 4]: Merchants 3 and 4 merge. Cluster {3,4} has 2 members, 0 high-risk. Ratio = 0/2 = 0. Since 0 <= 0.5 (k), merge is stable. Current clusters: {0,1}, {2}, {3,4}. Final distinct clusters: 3.
2

Example 2

Input:

n = 4, highRiskMerchants = [0, 1], trustRelationships = [[0, 2], [1, 3], [2, 3]], k = 0.3

Output:

3

Note:

Initial: 4 clusters. High-risk merchants: {0, 1}.

  1. Process [0, 2]: Merchant 0 (HR) and 2 (not HR). Hypothetical merge {0,2} has 2 members, 1 high-risk. Ratio = 1/2 = 0.5. Since 0.5 > 0.3 (k), merge is NOT stable. Clusters remain separate: {0}, {1}, {2}, {3}.
  2. Process [1, 3]: Merchant 1 (HR) and 3 (not HR). Hypothetical merge {1,3} has 2 members, 1 high-risk. Ratio = 1/2 = 0.5. Since 0.5 > 0.3 (k), merge is NOT stable. Clusters remain separate: {0}, {1}, {2}, {3}.
  3. Process [2, 3]: Merchants 2 (not HR) and 3 (not HR). Hypothetical merge {2,3} has 2 members, 0 high-risk. Ratio = 0/2 = 0. Since 0 <= 0.3 (k), merge is stable. Current clusters: {0}, {1}, {2,3}. Final distinct clusters: 3.
3

Example 3

Input:

n = 6, highRiskMerchants = [0, 1, 3], trustRelationships = [[0, 2], [1, 4], [2, 5], [3, 5]], k = 0.4

Output:

4

Note:

Initial: 6 clusters. High-risk merchants: {0, 1, 3}.

  1. Process [0, 2]: Merchant 0 (HR) and 2 (not HR). Hypothetical merge {0,2} (size 2, HR 1). Ratio 1/2 = 0.5. Since 0.5 > 0.4 (k), NO merge. Clusters: {0}, {1}, {2}, {3}, {4}, {5}.
  2. Process [1, 4]: Merchant 1 (HR) and 4 (not HR). Hypothetical merge {1,4} (size 2, HR 1). Ratio 1/2 = 0.5. Since 0.5 > 0.4 (k), NO merge. Clusters: {0}, {1}, {2}, {3}, {4}, {5}.
  3. Process [2, 5]: Merchants 2 (not HR) and 5 (not HR). Hypothetical merge {2,5} (size 2, HR 0). Ratio 0/2 = 0. Since 0 <= 0.4 (k), YES merge. Clusters: {0}, {1}, {2,5}, {3}, {4}.
  4. Process [3, 5]: Merchant 3 (HR, in {3}) and 5 (not HR, in {2,5}). Root of 3: {3} (size 1, HR 1). Root of 5: {2,5} (size 2, HR 0). Hypothetical merged cluster {2,3,5} (size 1+2=3, HR 1+0=1). Ratio 1/3 = 0.333... Since 0.333... <= 0.4 (k), YES merge. Clusters: {0}, {1}, {2,3,5}, {4}. Final distinct clusters: 4.

Constraints

Constraints & assumptions

  • 1 <= n <= 10^5
  • 0 <= highRiskMerchants.length <= n
  • 0 <= trustRelationships.length <= 2 * 10^5
  • 0.0 <= k <= 1.0
  • Each u, v in trustRelationships are distinct merchant indices, 0 <= u, v < n.
  • u != v for all relationships.
  • Relationships are bidirectional; [u, v] is the same as [v, u].

What interviewers evaluate

  • Correctness of Union-Find Implementation: Demonstrates a robust Union-Find data structure, including path compression and union by rank/size optimizations.
  • Efficient State Management: Successfully tracks and updates auxiliary cluster properties (total size, high-risk count) at the root during union operations.
  • Conditional Merge Logic: Accurately implements the logic for merging clusters only if the stability ratio k is maintained.
  • Time and Space Complexity: Achieves an optimal time complexity (near-constant amortized time per operation) and reasonable space complexity for the given constraints.

Loading editor...