Implement transaction network queries

Problem

You are building a small in-memory library to track pairwise customer transactions and answer connectivity questions about who has transacted with whom.

Model each transaction as an interaction between exactly two customers (e.g., "Jim pays Pam"). Once two customers transact, they are considered directly connected. Treat the relationship as undirected (if A transacts with B, then B has transacted with A).

Design a class (e.g., Transactions) that supports the following capabilities.

Part 1 — Direct/indirect existence query ("ever transacted together")

Implement an operation to record a transaction between two customers, and a query:

• haveEverTransactedTogether(x, y) -> bool

Return true if and only if customers x and y have ever been part of the same connected component in the transaction graph at the time of the query (i.e., based on all transactions recorded so far).

Example

1. haveEverTransactedTogether(Jim, Pam) -> false
2. Record: Jim transacts with Pam
3. haveEverTransactedTogether(Jim, Pam) -> true
4. Record: Pam transacts with Michael
5. haveEverTransactedTogether(Michael, Jim) -> true (because Michael—Pam—Jim forms a connected component)

Part 2 — Full network query

Implement:

• findNetwork(person) -> list/set

A person’s network is everyone who is reachable from that person via one or more transactions (i.e., all nodes in the same connected component), excluding the person themself.

Example 1 (two disconnected components)

Transactions: (a,b), (b,c), (a,d), (d,e), (g,f)

• findNetwork(a) -> {b,c,d,e}
• findNetwork(g) -> {f}

Example 2 (loop)

Transactions: (a,b), (b,d), (d,c), (c,a)

• findNetwork(a) -> {b,c,d}

Part 3 — Network query with degree limit

Extend the previous method to accept a second parameter n:

• findNetwork(person, n) -> list/set

Return all customers within at most n degrees of separation from person, excluding person.

• Degree 1: direct transaction partners
• Degree 2: partners of partners, etc.

Example 1

Transactions: (a,b), (b,c), (a,d), (d,e), (g,f)

• findNetwork(a, 1) -> {b,d}
• findNetwork(g, 1) -> {f}

Example 2 (loop)

Transactions: (a,b), (b,d), (d,c), (c,a)

• findNetwork(a, 1) -> {b,c}

Example 3

Transactions: (a,b), (b,c), (c,d), (b,e), (c,f), (d,g), (f,g), (g,h)

• findNetwork(d, 2) -> {c,g,b,f,h}
• findNetwork(h, 3) -> {g,d,f,c}
• findNetwork(a, 1) -> {b}

Notes / expectations

• You may assume customer identifiers are strings.
• The class should support adding transactions over time and answering queries at any point.
• Clearly define any helper methods and choose appropriate data structures.
• Be careful about cycles and repeated visits when exploring the network.