Katkat
Back

Expand a Serial and Parallel Task Composition Specification

Jump TradingSoftware Engineer · Online Assessment
EasySoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Tests parsing structured workflow specifications with nested delimiters and quoted literals, then generating all concrete serial execution paths via Cartesian expansion.

Expand Task Composition Specification

You are building a workflow execution engine for high-frequency trading pipelines. Pipelines are defined using a mini-specification that supports serial stages, parallel alternatives, and quoted arguments.

A specification string follows these rules:

  • Serial composition: Steps executed in sequence are delimited by -> (e.g., A -> B).
  • Parallel alternatives: A set of alternative sub-pipelines is enclosed in brackets [...], with options separated by commas , (e.g., [A, B]). Exactly one branch is chosen per concrete execution pipeline.
  • Nested expressions: Parallel groups can be nested inside one another (e.g., [A -> [B, C], D]).
  • Quoted strings: Tokens enclosed in double quotes "..." must be treated as atomic units. They can contain spaces, commas, brackets, or -> without triggering parsing splits. The double quotes should be preserved in the final output.
  • Whitespace: Whitespace around operators (->, ,, [, ]) is ignored unless enclosed in quotes.

Write a function that parses a specification string and returns all possible expanded serial execution paths as a list of strings, preserving the order of alternatives.

Function Signature

def expand_pipeline(spec: str) -> list[str]:
    pass

Examples

Example 1:

Input: spec = 'init -> [clean, "filter -> raw"] -> train'
Output: [
    'init -> clean -> train',
    'init -> "filter -> raw" -> train'
]
Explanation: The bracket group contains two alternatives. The second alternative is a quoted string containing "->", which is preserved as an atomic token.

Example 2:

Input: spec = 'load -> [A -> [B, C], D] -> done'
Output: [
    'load -> A -> B -> done',
    'load -> A -> C -> done',
    'load -> D -> done'
]
Explanation: Nested bracket groups are fully expanded in order.

Constraints

  • 1 <= len(spec) <= 1000
  • Brackets [ and ] are always balanced and non-empty.
  • Quotes " are always properly paired.
  • The number of generated paths will not exceed 500.
  • Token names outside quotes contain only alphanumeric characters, underscores, and dashes.

Hints

Hint 1

Tokenize or parse the input string while keeping track of whether the current character is inside double quotes to avoid splitting on structural delimiters.

Hint 2

Model the parser recursively or as an abstract syntax tree where each node is either a Literal, a Serial sequence of nodes, or an Alternative (Parallel) set of nodes.

Hint 3

Evaluate the tree bottom-up: an Alternative node returns the union of its branch paths, and a Serial node returns the Cartesian product of its sequential step paths.

Follow-up questions

  • How would you detect and handle syntax errors, such as unbalanced brackets or unclosed quotes?
  • If the spec allows an empty alternative `[]` or optional steps `[A, ]`, how should that modify the Cartesian product logic?
  • How would you stream the generated paths as an iterator instead of building the full list in memory for very large expansions?