Frontend School

Asset Group Consolidation

DSA
medium

Asset Group Consolidation

Medium
Union Find
Disjoint Set Union

Overview

Zerodha manages a vast portfolio of financial assets for its clients. As market conditions evolve or corporate actions occur (e.g., mergers), certain distinct assets might become functionally equivalent for risk assessment, reporting, or portfolio rebalancing purposes. This problem challenges you to efficiently track and manage these equivalency relationships among assets.

What you need to do / Task

You are tasked with implementing a system to manage asset equivalency groups. Initially, all assets are considered distinct. Your system must support two types of operations:

  1. Consolidate (UNION): Mark two specified assets as equivalent. If they are already equivalent, the state remains unchanged. This operation effectively merges their respective equivalency groups.
  2. Check Equivalency (QUERY): Determine if two specified assets are currently considered equivalent.

You need to process a sequence of these operations and return the results for all QUERY operations in the order they appear.

Input & output

Your function consolidateAssetGroups will take two arguments:

  • n: An integer representing the total number of distinct assets, labeled from 0 to n-1.
  • operations: An array of arrays. Each inner array represents an operation:
    • ["UNION", assetA, assetB]: Indicates that assetA and assetB should be considered equivalent. assetA and assetB are integers within the range [0, n-1].
    • ["QUERY", assetA, assetB]: Asks whether assetA and assetB are currently considered equivalent. assetA and assetB are integers within the range [0, n-1].

The function should return an array of booleans. Each boolean corresponds to the result of a QUERY operation, in the exact order they were processed. true if the assets are equivalent, false otherwise.

Clarifications

  • Asset IDs: Assets are identified by integers from 0 to n-1.
  • Self-Equivalency: An asset is always equivalent to itself. If a QUERY operation asks about assetA and assetA, it should always return true.
  • Transitivity: If asset A is equivalent to B, and B is equivalent to C, then A is also equivalent to C. Your solution should implicitly handle this transitivity.

Examples

1

Example 1

Input:

n = 5, operations = [["UNION", 0, 1], ["QUERY", 0, 1], ["UNION", 2, 3], ["QUERY", 1, 3], ["UNION", 0, 2], ["QUERY", 1, 3]]

Output:

[true,false,true]

Note:

Initial groups: {0}, {1}, {2}, {3}, {4}

  1. UNION(0, 1): Groups: {0,1}, {2}, {3}, {4}
  2. QUERY(0, 1): 0 and 1 are in the same group -> true
  3. UNION(2, 3): Groups: {0,1}, {2,3}, {4}
  4. QUERY(1, 3): 1 is in {0,1}, 3 is in {2,3} -> false
  5. UNION(0, 2): Groups: {0,1,2,3}, {4} (merges {0,1} and {2,3})
  6. QUERY(1, 3): 1 and 3 are now in the same group {0,1,2,3} -> true
2

Example 2

Input:

n = 3, operations = [["QUERY", 0, 0], ["UNION", 0, 1], ["QUERY", 1, 2], ["UNION", 1, 2], ["QUERY", 0, 2]]

Output:

[true,false,true]

Note:

Initial groups: {0}, {1}, {2}

  1. QUERY(0, 0): An asset is always equivalent to itself -> true
  2. UNION(0, 1): Groups: {0,1}, {2}
  3. QUERY(1, 2): 1 is in {0,1}, 2 is in {2} -> false
  4. UNION(1, 2): Groups: {0,1,2} (merges {0,1} and {2})
  5. QUERY(0, 2): 0 and 2 are now in the same group {0,1,2} -> true
3

Example 3

Input:

n = 1, operations = [["QUERY", 0, 0], ["UNION", 0, 0]]

Output:

[true]

Note:

Initial groups: {0}

  1. QUERY(0, 0): An asset is always equivalent to itself -> true
  2. UNION(0, 0): No change to groups -> {0}

Constraints

Constraints & assumptions

  • 1 <= n <= 10^5
  • 1 <= operations.length <= 2 * 10^5
  • 0 <= assetA, assetB < n for all operations.
  • The strings "UNION" and "QUERY" will be exact.
  • assetA and assetB can be the same in an operation. UNION(A, A) means nothing changes. QUERY(A, A) should be true.

Out of scope

  • Handling invalid asset IDs (e.g., outside [0, n-1]). Assume all inputs are valid.
  • Concurrent operations or thread safety. Operations are processed sequentially.
  • Persistence of asset groups beyond a single function call.

What interviewers evaluate

  • Correctness: The solution accurately determines asset equivalency for all operations.
  • Efficiency: The chosen algorithm handles the given constraints efficiently, particularly for large N and operations.length.
  • Data Structure Choice: Appropriate use of Union-Find (Disjoint Set Union) data structure with standard optimizations.
  • Code Quality: Readability, modularity, and adherence to good coding practices.

Loading editor...