Graph Problems and Their Trading Interview Variants

Graph questions in trading interviews reduce settlement order, account clustering, currency conversion and hedging to four standard algorithms.

Graph problems in trading interviews recur in four shapes: ordering a set of dependent trades or settlements, grouping accounts or instruments that are connected through shared activity, finding the cheapest path through a chain of currency conversions, and building a minimum-cost network that connects a set of instruments for hedging. Each variant reduces to a graph algorithm covered in an undergraduate course, but the reduction itself, not the algorithm, is what the interview is testing.

State the problem precisely: a batch of trades must settle in an order that respects dependencies, where trade B cannot settle until trade A has settled because B uses collateral or inventory that A frees up. Represent each trade as a node and each dependency as a directed edge, and the settlement order is any topological sort of the graph, computed with repeated removal of nodes that have no remaining incoming edges, in O(V plus E).

The standard follow-up asks what to report when the dependency graph contains a cycle, which in a real settlement system means two trades are each waiting on the other and neither can proceed. The candidate is expected to detect the cycle during the topological sort itself, since a correct implementation naturally stalls with nodes remaining and no in-degree-zero node left, rather than writing a separate cycle-detection pass afterward.

State the problem precisely: given a set of trading accounts and edges connecting two accounts whenever they have traded directly against each other or share an identifying attribute such as a funding source, find the connected components, since a component with unusually tight internal trading can indicate coordinated activity worth a closer look. Union-find with path compression and union by rank solves this close to O(alpha of n) per operation, which is effectively constant for any input size a real system would see.

The follow-up usually asks for the answer to update as new edges arrive continuously rather than being computed once over a static graph, since real account activity streams in throughout a session. Union-find already supports this well because merging two components on a new edge costs the same near-constant time as the static case, but the candidate is expected to say so explicitly and to note that union-find does not support removing an edge cheaply, which matters if a firm needs to unwind a stale connection.