Dependent Payment Operations
Stripe's platform processes billions of dollars in payments annually, often involving complex workflows with multiple internal operations. For a single large transaction, there might be a series of steps such as fraud_check, currency_conversion, deduct_fees, settle_funds, and send_receipt. These operations frequently have dependencies: some must complete before others can begin. Ensuring operations are processed in a valid order is critical for the integrity and efficiency of the payment system.
You are tasked with designing a system to determine a valid processing order for a set of payment operations, given their interdependencies. Your function should output a sequence of operations such that all prerequisites for each operation are met before it is processed. If a circular dependency exists, making it impossible to establish a valid order, your function should indicate this.
Your function getProcessingOrder will accept two arguments:
operations: An array of unique strings, where each string represents the ID of a distinct payment operation.dependencies: An array of [prerequisite, dependent] string pairs. Each pair indicates that the prerequisite operation must be completed before the dependent operation can begin.The function should return:
string[]: An array of operation IDs representing a valid topological sort of the operations. Any valid order is acceptable if multiple exist.[]: An empty array if a cyclic dependency is detected among the operations, indicating that no valid processing order can be formed.dependencies are guaranteed to be present in the operations array.operations array is empty, an empty array should be returned.Examples
Example 1
Input:
operations = ["A", "B", "C"], dependencies = [["A", "B"], ["A", "C"]]
Output:
["A", "B", "C"]
Note:
Operation 'A' must complete before 'B' and 'C'. 'B' and 'C' have no dependencies on each other, so their relative order can vary. ['A', 'C', 'B'] would also be a valid output.
Example 2
Input:
operations = ["fraud_check", "currency_conversion", "deduct_fees", "settle_funds", "send_receipt"], dependencies = [["fraud_check", "currency_conversion"], ["currency_conversion", "deduct_fees"], ["deduct_fees", "settle_funds"], ["settle_funds", "send_receipt"]]
Output:
["fraud_check", "currency_conversion", "deduct_fees", "settle_funds", "send_receipt"]
Note:
This represents a linear chain of dependencies, so there is only one valid processing order.
Example 3
Input:
operations = ["A", "B", "C"], dependencies = [["A", "B"], ["B", "C"], ["C", "A"]]
Output:
[]
Note:
Operations 'A', 'B', and 'C' form a cyclic dependency (A -> B -> C -> A). No valid processing order can be established, so an empty array is returned.
Example 4
Input:
operations = ["op1", "op2", "op3"], dependencies = []
Output:
["op1", "op2", "op3"]
Note:
No dependencies exist, so any permutation of the operations is a valid processing order. ['op3', 'op1', 'op2'] would also be valid.
Constraints
1 <= operations.length <= 10^40 <= dependencies.length <= 10^4operations are unique.Loading editor...