Implement transaction network queries
Company: Square
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
## 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.
Quick Answer: This question evaluates the ability to model and query dynamic graph connectivity and reachability for pairwise transactions, testing competencies in graph representation, dynamic data structures, and reachability queries within the Coding & Algorithms domain and emphasizing practical application of algorithmic concepts.
Transaction Network — Part 1: Ever Transacted Together
You are building a small in-memory library to track **pairwise customer transactions**. Each transaction connects **exactly two** customers and the relationship is **undirected** (if A transacts with B, then B has transacted with A). Once two customers transact, they are directly connected, and connectivity is transitive through the transaction graph.
Given a list of `transactions` (each a 2-element pair `[x, y]`) recorded so far and two customers `x` and `y`, return `True` if and only if `x` and `y` are in the **same connected component** of the transaction graph (i.e., they have ever transacted together, directly or indirectly). Return `False` if either customer has never appeared in any transaction, or if they belong to different components.
**Example**
- Before any transaction: `Jim` and `Pam` -> `False`
- After `Jim` pays `Pam`: `Jim` and `Pam` -> `True`
- After `Pam` pays `Michael`: `Michael` and `Jim` -> `True` (Michael—Pam—Jim is one component)
A customer is trivially connected to themself if they appear in any transaction.
Constraints
- 0 <= number of transactions
- Each transaction is a pair of two customer identifiers (strings).
- The relationship is undirected.
- x and y may or may not have appeared in any transaction.
- A customer that appears in any transaction is connected to itself.
Examples
Input: ([], 'Jim', 'Pam')
Expected Output: False
Explanation: No transactions recorded yet, so Jim and Pam have never transacted.
Input: ([['Jim', 'Pam']], 'Jim', 'Pam')
Expected Output: True
Explanation: Jim and Pam directly transacted.
Hints
- Connectivity that is transitive across many edges is the classic use case for a disjoint-set (Union-Find) structure, or you can BFS/DFS from x and check if y is reachable.
- Union the two endpoints of every transaction, then two customers are connected iff find(x) == find(y).
- Handle the case where a queried customer never appears in any transaction — they cannot be connected to anyone (return False), unless x == y and they appear.
Transaction Network — Part 2: Find Full Network
Building on the pairwise transaction graph from Part 1 (undirected edges given as a list of `[x, y]` pairs), implement `findNetwork(person)`.
A person's **network** is everyone reachable from that person via one or more transactions — i.e., **all other nodes in the same connected component**, **excluding the person themself**.
Given `transactions` and a `person`, return the network as a **sorted list of distinct customer identifiers**. If the person never appears in any transaction, return an empty list.
**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 (cycle)**
Transactions: `(a,b), (b,d), (d,c), (c,a)`
- `findNetwork(a)` -> `['b', 'c', 'd']`
Constraints
- 0 <= number of transactions
- Each transaction is an undirected pair of customer identifiers (strings).
- Exclude the queried person from the returned network.
- Return distinct identifiers; the graph may contain cycles, so guard against revisiting nodes.
- If the person never appears, return an empty list.
Examples
Input: ([['a', 'b'], ['b', 'c'], ['a', 'd'], ['d', 'e'], ['g', 'f']], 'a')
Expected Output: ['b', 'c', 'd', 'e']
Explanation: a's component is {a,b,c,d,e}; excluding a gives {b,c,d,e}.
Input: ([['a', 'b'], ['b', 'c'], ['a', 'd'], ['d', 'e'], ['g', 'f']], 'g')
Expected Output: ['f']
Explanation: g is in the separate component {g,f}.
Hints
- Build an undirected adjacency list (each edge added in both directions), then explore the connected component with BFS or DFS.
- Track visited nodes so cycles do not cause infinite loops or duplicate entries.
- Remove the starting person from the result before returning, and sort for a deterministic answer.
Transaction Network — Part 3: Find Network Within N Degrees
Extend `findNetwork` to accept a degree limit `n`. Given the undirected transaction graph (list of `[x, y]` pairs), a `person`, and an integer `n`, return all customers within **at most `n` degrees of separation** from `person`, **excluding `person`**.
- Degree 1 = direct transaction partners
- Degree 2 = partners of partners
- ... up to degree `n`
Because the graph may contain cycles, each customer should be counted at its **shortest** degree of separation, and only included if that shortest distance is `<= n`. Return the result as a **sorted list of distinct identifiers**. If `person` is absent or `n <= 0`, return an empty list.
**Example 1**
Transactions: `(a,b), (b,c), (a,d), (d,e), (g,f)`
- `findNetwork(a, 1)` -> `['b', 'd']`
- `findNetwork(g, 1)` -> `['f']`
**Example 2 (cycle)**
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)` -> `['b', 'c', 'f', 'g', 'h']`
- `findNetwork(h, 3)` -> `['c', 'd', 'f', 'g']`
- `findNetwork(a, 1)` -> `['b']`
Constraints
- 0 <= number of transactions
- Each transaction is an undirected pair of customer identifiers (strings).
- n is an integer; if n <= 0 the result is empty.
- Exclude the queried person.
- Count each customer at its shortest degree of separation; the graph may contain cycles, so use a level-order (BFS) traversal and mark nodes visited the first time they are reached.
Examples
Input: ([['a', 'b'], ['b', 'c'], ['a', 'd'], ['d', 'e'], ['g', 'f']], 'a', 1)
Expected Output: ['b', 'd']
Explanation: Degree-1 partners of a are b and d only.
Input: ([['a', 'b'], ['b', 'c'], ['a', 'd'], ['d', 'e'], ['g', 'f']], 'g', 1)
Expected Output: ['f']
Explanation: g's only direct partner is f.
Hints
- Level-order BFS naturally tracks degrees of separation: the level at which you first reach a node is its shortest distance from the source.
- Carry a depth with each queued node; stop expanding once depth reaches n so you never include nodes beyond n degrees.
- Mark a node visited the first (shortest) time you reach it, which both prevents cycle re-entry and guarantees each node is counted at its minimum degree.