Validate Editable DAGs and Bound Runtime Repetition
Qualified HealthSoftware Engineer · OnsiteLast updated
Validate editable workflow DAGs, reason about cycle-check latency, and enforce durable retry and expansion limits that prevent unbounded runtime loops.
A workflow platform lets users create and modify dependency graphs. It must reject cyclic DAG definitions, and it also supports dynamic conditional branches and bounded retry behavior at runtime.
Design topology validation and runtime execution limits. The reported goal is sub-millisecond configuration validation, but no maximum graph size or edit size is supplied. Explain the assumptions under which that target might be achievable and why it cannot be promised for arbitrary graph submissions.
Constraints & Assumptions
- Dependency edges impose predecessor-before-successor ordering.
- A run must have a well-defined graph version even when the user later edits the workflow.
- Retries or dynamic transitions must not create an unbounded execution loop.
- This is a platform-design question, not a request to invent a fixed numeric bound or benchmark result.
Clarifying Questions to Ask
- Are edits single-edge changes or whole-graph replacements, and how many vertices and edges can a definition contain?
- Are running workflows pinned to immutable versions, or is live migration required?
- Are retries represented as attempt state on one node or as new graph transitions?
- What limits apply to attempts, dynamic node creation, and total run duration?
Hints
Hint 1
Separate two notions of a loop: A retry of one task can repeat work even when the static dependency graph is acyclic. Decide which validation belongs at definition time and which belongs in durable execution state.
Follow-up questions
- How can two individually valid concurrent edge additions jointly create a cycle?
- Why does a local recursion counter fail to bound retries after a process restart?
- How would a branch join distinguish a skipped predecessor from one that has not yet finished?
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.