Build an In-Memory Workflow Engine with Dependency Ordering and Concurrent Execution

Mid July, 2026

**Time:** ~45 minutes · **Language:** your choice Everything you need is in this document. Use your normal workflow — run code freely and look things up. Please think out loud; we care as much about how you structure and reason about the code as about the final result. New requirements may be added near the end, so design for change. --- ## Context Many systems run **multi-step processes where some steps depend on others finishing first** — payment flows, data pipelines, CI builds, order fulfillment. We want to model this generically. Consider an order-fulfillment flow: ``` validate ─→ reserve ─→ charge ─┬─→ email └─→ ship ─→ notify ``` - `reserve` runs after `validate`; `charge` after `reserve`. - `email` and `ship` both depend only on `charge`, so once `charge` finishes they can run **in parallel**. - `notify` runs after `ship`. Your task is to build a **generic workflow engine** that takes a definition like this and executes it correctly. The logic inside a step does not matter — a step is just a function that returns a value. Spend your effort on the **engine's structure and API**, not on the order domain. --- ## What to build Designing the data model and the shape of the API is part of the exercise — that's for you to decide and walk us through. At minimum your engine should expose two operations: - **Define** — register a step in a workflow, along with the steps it depends on. *Purpose: build up the workflow definition.* - **Run** — execute a given workflow and return the result of each step. *Purpose: validate the definition, then run the steps in dependency order.* Everything else (what a "step" is, how dependencies and outputs are represented, how you name things) is up to you. This is plain in-memory code — no HTTP endpoints, CLI, database, UI, or real I/O needed. --- ## Requirements (in order) 1. **Define & run.** Register steps with dependencies and execute them in correct dependency order. Return a map of `step_name -> output`. 2. **Validate before running.** Reject an invalid workflow with a clear error when: - a step depends on a step that doesn't exist, or - the dependencies contain a **cycle** (can never be scheduled). 3. **Parallelism & data flow.** - Independent steps (no dependency between them) run **concurrently**. - A step can read the outputs of the steps it depends on, via the context passed to it. 4. **Per-step retry (extension — only if time permits).** Allow a step to be configured with a retry policy (max attempts, optional backoff) **without changing the engine's core execution loop**. You are **not** expected to finish all four — depth and clarity matter more than coverage. Get Requirements 1–2 fully working before moving on. --- ## Expected behavior (build your example around the order flow above) - Running the order-fulfillment workflow returns an output for every step, with each step executed only after its dependencies — e.g. `validate → reserve → charge`, then `email` and `ship` in any order (or in parallel), then `notify`. - A workflow where `a` depends on `b` and `b` depends on `a` must fail with a clear "cycle" error before any step runs. --- ## Assumptions (so you don't have to ask) - Single process, in-memory. No persistence or distributed execution. - Step names are unique; the dependency graph is directed. - "Concurrent" can mean threads, async, or a thread/worker pool — your choice. - If a step's function raises (and retries are exhausted), it's fine for `run` to surface that error and stop. - Inputs are small; you don't need to optimize beyond correct, clean code. --- ## What we're looking for - A clean, minimal API that you can explain and justify. - A **generic** engine that knows nothing specific about orders, emails, or payments. - Correct dependency ordering, cycle detection, and parallel execution of independent steps. - Code that is easy to **extend**, since we may ask you to add a behavior live.