Graph Traversal for Interactions | Dataford Interview Questions

Coalition Technologies models relationships between users and items in an interaction graph. Given user-item interactions and a starting user, return every reachable user in breadth-first search order.

Treat each interaction [user, item] as an undirected edge between a user node and an item node. A user is reachable if a path from the starting user alternates through users and items. Return each reachable user once, including the starting user. The order must follow BFS discovery order, and neighbors must be processed in the same order their edges first appear in interactions.

Formal Specification

Implement connected_users(interactions, start_user).

interactions is a list of two-element lists of strings, where each pair contains a user ID and an item ID.
start_user is a string identifying a user present in interactions.
Return a list of user IDs in BFS discovery order. Item IDs must not appear in the result.
Repeated interactions do not create duplicate results.

Constraints

1 <= len(interactions) <= 10^5
Each interaction contains exactly two non-empty strings
There are at most 2 * 10^5 distinct users and items
start_user appears as a user in interactions
User and item identifiers are unique within their respective categories

Function Signature

def connected_users(interactions, start_user):

Your question is Graph Traversal for Interactions. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem