Compute currency conversions with graph algorithms

Q: Compute currency conversions with graph algorithms

This is a Coding & Algorithms interview question from Stripe for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given a set of 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 algorithms and data structures to: (

answer queries like 'A:C' by returning the implied conversion rate, or -1 if unknown; (
support online updates by inserting or updating a rate and handling multiple queries efficiently; (
detect and report contradictions when a new rate conflicts with implied rates; and (
when the relation graph is a DAG, compute consistent relative rates for all nodes using a topological ordering and explain how to handle cycles and potential arbitrage. Analyze time and space complexity.

Compute currency conversions with graph algorithms

Comments (0)