Bank ID Resolution - Resolve Merged Bank Account Identifiers
Interview Experience
Problem
A bank has undergone several mergers. Each merger maps old account IDs to new ones. Given a list of mergers [(old_id, new_id)] applied in sequence and a query account ID,
return the final canonical ID it resolves to.
Mergers may chain: if A -> B and B -> C, then A ultimately resolves to C.
python
def resolve_bank_id(
mergers: List[Tuple[str, str]],
query_id: str
) -> str:
...
def resolve_all(
mergers: List[Tuple[str, str]],
queries: List[str]
) -> List[str]:
...
Example:
mergers = [("ACC001", "ACC002"), ("ACC002", "ACC999"), ("ACC050", "ACC999")]
resolve_bank_id(mergers, "ACC001") -> "ACC999"
resolve_bank_id(mergers, "ACC050") -> "ACC999"
resolve_bank_id(mergers, "ACC999") -> "ACC999" # no further mapping
Approach
Model as a Union-Find (Disjoint Set Union) structure. Each merge(old, new) is a union operation with path compression.
Follow-ups
- How does path compression in Union-Find achieve near-O(1) amortized
find? - What if a merger maps one new ID to multiple old IDs simultaneously?
- How would you detect and handle circular mergers (A -> B -> A)?
- How would you audit which original IDs all map to the same canonical ID?
Full Details
Problem
A bank has undergone several mergers. Each merger maps old account IDs to new ones. Given a list of mergers [(old_id, new_id)] applied in sequence and a query account ID,
return the final canonical ID it resolves to.
Mergers may chain: if A -> B and B -> C, then A ultimately resolves to C.
python
def resolve_bank_id(
mergers: List[Tuple[str, str]],
query_id: str
) -> str:
...
def resolve_all(
mergers: List[Tuple[str, str]],
queries: List[str]
) -> List[str]:
...
Example:
mergers = [("ACC001", "ACC002"), ("ACC002", "ACC999"), ("ACC050", "ACC999")]
resolve_bank_id(mergers, "ACC001") -> "ACC999"
resolve_bank_id(mergers, "ACC050") -> "ACC999"
resolve_bank_id(mergers, "ACC999") -> "ACC999" # no further mapping
Approach
Model as a Union-Find (Disjoint Set Union) structure. Each merge(old, new) is a union operation with path compression.
Follow-ups
- How does path compression in Union-Find achieve near-O(1) amortized
find? - What if a merger maps one new ID to multiple old IDs simultaneously?
- How would you detect and handle circular mergers (A -> B -> A)?
- How would you audit which original IDs all map to the same canonical ID?
About This Question
This is a candidate experience report from a plaid interview during the phone round.
It covers the following topics: Coding, Union Find, Phone, Onsite .