Frontend School

Dependent Payment Operations

DSA
medium

Dependent Payment Operations

Medium
Graph
Topological Sort
BFS
DFS

Overview

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.

What you need to do / Task

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.

Input & output

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.

Clarifications

  • All operation IDs mentioned in dependencies are guaranteed to be present in the operations array.
  • Operations that have no prerequisites can be processed first, in any order relative to each other.
  • If the operations array is empty, an empty array should be returned.

Examples

1

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.

2

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.

3

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.

4

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

Constraints & assumptions

  • 1 <= operations.length <= 10^4
  • 0 <= dependencies.length <= 10^4
  • Each operation ID is a non-empty string, consisting of alphanumeric characters and underscores, with a maximum length of 20.
  • All operation IDs in operations are unique.

Out of scope

  • Optimizing for specific network latency or hardware configurations.
  • Handling invalid input formats (e.g., non-string operation IDs, dependencies referencing non-existent operations, malformed dependency pairs).

What interviewers evaluate

  • Ability to correctly model the problem as a directed graph.
  • Correct implementation of a topological sort algorithm (e.g., Kahn's algorithm or DFS-based approach).
  • Proper handling of edge cases, including empty inputs, operations with no dependencies, and cyclic dependencies.
  • Efficiency of the solution in terms of time and space complexity.

Loading editor...