Katkat
Back

Compute currency conversions with graph algorithms

StripeSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Stripe software-engineer onsite coding question: design data structures and algorithms to compute currency conversions from pairwise exchange rates. It tests modeling currencies as a weighted directed graph, chaining rates with BFS/DFS to answer queries (or -1 when unknown), supporting online updates and many queries efficiently, detecting contradictions and arbitrage in cycles, and computing all rates against a base via topological sort on a DAG, with time and space complexity analysis.

Question

You are given a set of pairwise currency exchange relations such as A:B = 1:1.5 and B:C = 1:1.5, meaning 1 A = 1.5 B and 1 B = 1.5 C. Design the data structures and algorithms to support the following:

  1. Store direct conversions. Ingest the given pairwise rates into a structure you can query and update.
  2. Answer conversion queries. Given a query like A:C, return the implied conversion rate by chaining the known rates, or -1 (unknown) if no path connects the two currencies.
  3. Support many queries efficiently. Explain how to serve a large number of queries without re-deriving every chain from scratch each time.
  4. Support online updates. Allow inserting a new rate or updating an existing one, interleaved with queries, and keep query answers consistent.
  5. Detect and report contradictions. When a newly inserted rate conflicts with the rate implied by existing relations (within a tolerance), detect and report the contradiction instead of silently corrupting the data.
  6. Topological computation for a DAG. When the relation graph is a DAG with a chosen base currency, compute the relative rate of every currency against the base using a topological ordering.
  7. Cycles and arbitrage. Explain how to handle cycles: a consistent cycle should multiply back to 1, while an inconsistent cycle (product != 1) signals a contradiction or an arbitrage opportunity.
  8. Map vs. graph reasoning. Explain when a simple direct-lookup map suffices versus when a graph traversal or topological sort is actually required.
  9. Complexity and edge cases. State the time and space complexity of each operation, and describe how you handle missing paths and contradictory inputs.