Context

In safety- and compliance-heavy domains like medical devices (FDA 21 CFR Part 820) and automotive (ISO 26262), teams often adopt the V-Model to ensure every requirement is implemented and verified. At scale (e.g., a platform with 10k+ requirements, 50k tests, and multiple releases), the core engineering risk isn’t writing code—it’s losing traceability: requirements that aren’t implemented, tests that don’t verify anything, or circular dependencies that make audits fail.

Core Question

Explain how you would represent and validate V-Model traceability using core CS concepts.

1. Modeling: How would you model relationships like Requirement -> Design -> Code -> Test as a data structure? When would you choose a graph vs. a tree?
2. Validation algorithms: Given the traceability structure, how would you:
   • Detect missing coverage (e.g., requirements with no verifying tests)?
   • Detect cycles (e.g., design artifacts that depend on each other in a loop)?
   • Compute impact analysis (e.g., if a requirement changes, which tests must be rerun)?
3. Trade-offs: Discuss time/space complexity, and how you’d handle scale (incremental updates, caching, or precomputation).

Scope Guidance

Answer at a Staff+ depth: define the data model, walk through the algorithms (DFS/BFS, topological sorting, reachability), call out edge cases (many-to-many links, orphan nodes, versioned artifacts), and describe how you’d make this robust in a real engineering workflow (CI gates, audit reports, and change impact).

Directed Graph Representation (Adjacency Lists)

Traceability links are naturally many-to-many, so a directed graph is a better fit than a tree. An adjacency list keeps memory proportional to nodes + edges and supports fast traversals for coverage and impact analysis.

adj: dict[str, list[str]] = {
    "REQ-1": ["DES-7", "DES-9"],
    "DES-7": ["CODE-12"],
    "CODE-12": ["TEST-3", "TEST-4"],
}

Cycle Detection with DFS (Recursion Stack)

In a valid V-Model traceability DAG, dependencies should flow “down” the V without cycles. DFS with a recursion-stack (gray set) detects back-edges that indicate circular dependencies that break topological ordering and auditability.

def has_cycle(u: str) -> bool:
    visiting.add(u)
    for v in adj.get(u, []):
        if v in visiting:  # back-edge
            return True
        if v not in visited and has_cycle(v):
            return True
    visiting.remove(u)
    visited.add(u)
    return False

Reachability for Coverage (Requirements → Tests)

Coverage is a reachability question: for each requirement node, can you reach at least one test node following edges? You can compute this via DFS/BFS per requirement, or more efficiently via memoization / DP on a DAG.

def reaches_test(u: str) -> bool:
    if u in memo: return memo[u]
    memo[u] = (u.startswith("TEST-")) or any(reaches_test(v) for v in adj.get(u, []))
    return memo[u]

Impact Analysis via Reverse Graph Traversal

To find what’s impacted by a change, traverse forward (what depends on this) or backward (what this depends on) depending on the question. Building a reverse adjacency list enables O(nodes+edges) queries for affected tests from a changed artifact.

rev: dict[str, list[str]] = {}
for u, vs in adj.items():
    for v in vs:
        rev.setdefault(v, []).append(u)

# impacted tests from a changed requirement: forward traversal from REQ-*

Topological Sort for Ordering and Incremental Re-computation

If the traceability graph is acyclic, a topological order lets you compute properties bottom-up (e.g., whether a node is ultimately verified by tests). This is essentially dynamic programming on a DAG and supports incremental recomputation when a small subgraph changes.

from collections import deque

def topo(nodes, adj):
    indeg = {n: 0 for n in nodes}
    for u in nodes:
        for v in adj.get(u, []):
            indeg[v] = indeg.get(v, 0) + 1
    q = deque([n for n, d in indeg.items() if d == 0])
    order = []
    while q:
        u = q.popleft(); order.append(u)
        for v in adj.get(u, []):
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return order