Expand a Serial and Parallel Task Composition Specification
Company: Jump Trading
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Online Assessment
## Problem
Expand a workflow specification into all composed function-call expressions. Top-level stages are separated by commas outside parentheses and braces and run in series. A brace stage contains semicolon-separated alternatives that run in parallel; an empty alternative is the identity. Task arguments remain attached to their task. Multiple parallel stages form a Cartesian product.
### Function Contract
Implement `expand_workflow(spec) -> list[str]`. Begin every branch with the literal expression `input`; applying task text `f(args)` to expression `x` produces `f(x,args)`, while applying `f` produces `f(x)`. Ignore whitespace outside quoted strings and preserve branch order from left to right.
### Constraints
- `0 <= len(spec) <= 20000`.
- Task names are identifiers; arguments may contain quoted strings, numbers, identifiers, keyword assignments, and commas inside one balanced parenthesis pair.
- Braces are not nested, and a brace alternative contains at most one task; top-level commas do not occur inside a brace.
- The expanded output contains at most 10000 expressions.
### Examples
- `task1,task2,task3` returns `["task3(task2(task1(input)))"]`.
- `task1,task2,{task3;}` returns `["task3(task2(task1(input)))", "task2(task1(input))"]`.
- `{func1;func2},{func3;func4}` returns four expressions in order: `func3(func1(input))`, `func4(func1(input))`, `func3(func2(input))`, `func4(func2(input))`.
- `task1('b',kw=1),task2(1,2,var1='a')` returns `["task2(task1(input,'b',kw=1),1,2,var1='a')"]`.
```hint Tokenize by nesting depth
A comma separates stages only at brace depth zero and parenthesis depth zero; quoted commas are data.
```
```hint Carry a branch list
A serial task maps over existing branches; a parallel stage replaces each current branch with one result per alternative.
```
### Edge Cases
- An empty specification returns `["input"]`.
- An empty parallel alternative leaves the current expression unchanged.
- Whitespace inside a quoted string is preserved.
Overview: Parse a serial and parallel workflow specification with nested arguments and quoted text, then expand its alternatives into ordered composed expressions through a Cartesian product.
Expand a workflow specification into every composed function-call expression. Top-level comma-separated stages run in series. A brace stage contains semicolon-separated parallel alternatives; an empty alternative is the identity, and multiple parallel stages form a Cartesian product. Begin every branch with input. Applying f(args) to x yields f(x,args), while applying f yields f(x). Ignore whitespace outside quoted strings, preserve whitespace and separators inside quotes, and preserve left-to-right branch order.
Constraints
- 0 <= len(spec) <= 20000.
- Top-level stages are comma-separated outside parentheses and braces.
- Braces are not nested and contain semicolon-separated alternatives of at most one task each.
- Arguments use one balanced parenthesis pair and may contain quoted strings and commas.
- Whitespace outside quoted strings is ignored; quoted whitespace is preserved.
- The expanded output contains at most 10000 expressions.
Examples
Input: ('task1,task2,task3',)
Expected Output: ['task3(task2(task1(input)))']
Explanation: Serial stages wrap the current expression from left to right.
Input: ('task1,task2,{task3;}',)
Expected Output: ['task3(task2(task1(input)))', 'task2(task1(input))']
Explanation: The empty parallel alternative is the identity branch.
Hints
- Track quotes plus parenthesis and brace depth before treating punctuation as a separator.
- For each current branch, emit parallel alternatives from left to right to preserve product order.