Prompt and scope
You maintain a file, organization, or knowledge-graph API whose resources can point to other resources through aliases or bindings. A client requests recursive expansion similar to WebDAV Depth: infinity. Design traversal, cycle reporting, depth and node budgets, and explain when 508 is wrong. This fits backend, storage, and platform interviews.
RFC 5842 defines 508 for terminating an infinite-depth operation after a loop is found; it is not a generic redirect-loop or CPU-timeout code. Assume the graph can cross tenants and every edge and node requires authorization.
What the interviewer is testing
- Whether you model recursive traversal as a graph rather than waiting for stack overflow.
- Whether you distinguish a repeated node from a node on the current path, using global visited and path state for different jobs.
- Whether you set budgets for depth, nodes, edges, bytes, and time, then return a client-actionable failure.
A weak answer adds a maximum recursion depth. A strong answer covers stable resource identity, path cycles versus shared subgraphs, budget exhaustion, 508 boundaries, and multi-tenant cache safety.
Clarifying questions to ask first
- Is the relation a tree, a DAG, or an arbitrary directed graph? A DAG still needs visited to avoid duplicate work; an arbitrary graph also needs current-path cycle detection.
- Does the client need a complete expansion, paged results, or only reachability? The output contract determines whether partial results or an asynchronous job is valid.
- Are resource IDs globally unique? Aliases and cross-tenant bindings require canonical identity before visited keys are built.
- Who controls the budget? The service must impose hard limits; a client-provided depth cannot directly choose database or memory consumption.
A 30-second answer
“I model the relation as a directed graph and canonicalize each resource to a stable ID. During traversal I keep a current-path set to detect real cycles and a global visited set to avoid re-expanding shared subgraphs. The service enforces hard limits on depth, nodes, edges, response bytes, and wall time. A detected cycle can produce 508; exhausted budgets produce an explicit limit error or asynchronous job state. Results include a redacted cycle edge, truncation reason, and request ID, never unauthorized nodes. Tests cover self-cycles, alias cycles, shared subgraphs, denied edges, and hostile deep graphs.”
Step-by-step solution
1. Define the 508 boundary
RFC 5842 uses 508 when a recursive resource operation encounters an infinite loop. Ordinary URL redirects need redirect-chain protection; a timeout or exhausted budget needs its own error. The status explains the class of failure, while the body provides diagnostics.
2. Canonicalize resource identity
Resolve an alias to a tuple of tenant, resource type, and immutable ID. Do not use path strings, case variants, or different URLs as visited keys. Alias resolution also needs a hop limit so it cannot loop before graph traversal begins.
3. Keep path and visited state separate
path represents the current DFS branch; an edge to a node in path is a cycle. visited represents nodes already completed or queued for this request and removes duplicate work in a diamond-shaped graph. One combined set either reports legal sharing as a cycle or misses a cycle on another branch.
4. Set budgets and truncation rules
Limit maximum depth, nodes, edges, response bytes, and wall-clock time. Apply budgets per tenant and request, and page database reads. On exhaustion, return counts, a truncation reason, and a continuation mechanism. If the protocol requires a complete result, create an asynchronous traversal job instead of returning a misleading partial tree.
5. Handle authorization and caching
Authorize each resource before adding it to the visible result. Cache keys must include tenant, permission version, and traversal parameters; otherwise one tenant may infer another tenant’s hidden node from cycle diagnostics. For expensive graphs, cache canonical edges but recheck authorization for every request.
6. Choose the response shape
When a cycle is found and the client understands diagnostics, return 508 with redacted cycle IDs, the cut location, and a request ID. If the client wants best effort, return a successful paged collection marked truncated; that differs from 508’s whole-operation failure. Do not label database stack overflow or a proxy self-loop as 508 without matching the cause.
7. Test attacks and failure paths
Test a self-cycle, A-to-B-to-A, multiple aliases for one node, a shared subgraph, a depth exactly at the limit, huge fan-out, a denied cross-tenant edge, and timeout. Assert that each node is expanded at most once, denial does not change visible counts, and errors reveal no hidden resource IDs.
High-quality sample answer
“I treat recursive expansion as a directed-graph problem. I resolve aliases to a tenant and stable resource ID, use current-path state for real cycles, and use global visited state for shared-subgraph deduplication. Depth, node, edge, response-size, and time budgets are hard limits passed into paged queries. I return 508 only when the recursive operation actually encounters a cycle and the client supports that contract; ordinary redirects and timeouts use their own errors. The response contains only authorized, redacted cycle data and a request ID. Cache keys include tenant, permission version, and parameters. Tests cover self-cycles, alias cycles, diamond graphs, denied edges, and hostile depth.”
Common mistakes
- Equating maximum depth with cycle detection → Valid deep trees fail while shallow cycles can remain → Use path state for cycles and depth only as a budget.
- Keeping only global visited → A shared subgraph is reported as a cycle → Separate current path from global traversal state.
- Returning 508 for every timeout → Clients cannot distinguish a graph cycle from overload → Make the status match the actual cause.
- Expanding before authorization → Error details can leak hidden nodes → Authorize before visible traversal and counting.
- Omitting permission version from cache keys → Results from old access remain visible → Bind cache entries to tenant, permission version, and parameters.
Follow-up questions and responses
If the graph is a DAG, why keep current-path state?
The data model may promise a DAG, but migrations, aliases, or concurrent writes can temporarily violate it. Path state is a cheap runtime guard; a detected cycle should also identify its write source and block new bindings.
Can you return 508 when the customer wants whatever nodes were found?
Do not disguise partial data as a complete 508 failure. Define a paged or asynchronous contract that returns completed pages, truncation reason, and a continuation cursor. Use 508 only when the client requires atomic complete expansion.
How do you stop a high-fan-out tenant from exhausting the database?
Set per-tenant concurrency, node, edge, query-time, and response-byte quotas; limit batch prefetch and apply backpressure. Queue or reject over-budget requests, monitor per-tenant consumption and failure causes, and do not let clients bypass limits by increasing depth.