← All Problems

5. Reachable Tools in a Multi-Step Tool-Use Chain

General Medium Anthropic-Style Coding Rounds
Grounding: General pattern common across ML-research-lab technical interviews, not tied to one specific reported example. Graph reachability (BFS/DFS over a directed graph) is a standard category cited broadly across crowdsourced interview-question databases for engineering interviews in general; no source in this batch's research names a specific reported instance of this exact question at Anthropic.

Problem

An agent can call tools, and some tools' outputs feed into other tool calls (e.g. a "search" result gets passed to "summarize"). The dependency chain is modeled as a directed graph where an edge tool_a -> tool_b means tool_a's execution can lead to tool_b being called next.

Given a starting tool, the agent's runtime needs to know every tool that could possibly execute during that chain, including cases where tools call back into each other in a loop.

Source: src/5_reachable_tools_chain.py

def reachable_tools(start_tool: str, dependencies: dict[str, list[str]]) -> set[str]:
    ...

Examples:
>>> deps = {"search": ["browse", "calculator"], "browse": ["summarize"], "calculator": [], "summarize": ["search"]}
>>> sorted(reachable_tools("search", deps))
['browse', 'calculator', 'search', 'summarize']

>>> sorted(reachable_tools("calculator", deps))
['calculator']

Step-by-Step Approach

  1. Recognize this as graph reachability from a single source: which nodes can you reach by following directed edges from start_tool?
  2. Initialize a visited set containing just start_tool, and a stack (or queue) seeded with start_tool.
  3. Pop a node, look up its successors in the dependencies map (defaulting to an empty list for tools with no outgoing edges), and push any successor not already in the visited set.
  4. Add every newly discovered successor to the visited set at the moment it's discovered, not when it's popped — this is what prevents infinite loops on cyclic graphs.
  5. Continue until the stack/queue is empty; the visited set is exactly the answer.

The key insight is that marking a node visited at discovery time (not processing time) is what makes this safe on cyclic graphs — a tool that calls back into an earlier tool never gets pushed a second time, so the traversal always terminates in O(V + E).

Reference solution

def reachable_tools(start_tool: str, dependencies: dict[str, list[str]]) -> set[str]:
    # iterative DFS with a visited set guards against cycles; O(V + E)
    seen = {start_tool}
    stack = [start_tool]
    while stack:
        node = stack.pop()
        for nxt in dependencies.get(node, []):
            if nxt not in seen:
                seen.add(nxt)
                stack.append(nxt)
    return seen

Key Functions & Tricks

  • seen = {start_tool} — visited set doubles as the accumulating answer
  • dependencies.get(node, []) — safely handles tools with no recorded outgoing edges
  • mark-on-discovery — adding to seen before pushing (not after popping) is what prevents cycles from causing infinite loops
  • stack.pop() / stack.append() — iterative DFS avoids Python's recursion depth limit on long chains

How to Recognize This Pattern

The signal is "what can I reach from here" over a graph described as an adjacency list or edge list, especially when the graph might contain cycles. BFS and DFS both solve pure reachability in O(V + E); pick DFS with an explicit stack when recursion depth could be a concern, or BFS with a queue when you also need shortest hop-count. Common variations ask for the reachable set from *multiple* start nodes at once (seed the frontier with all of them), or ask you to detect whether a specific target is reachable at all (short-circuit as soon as it's found). A common pitfall is marking nodes visited only when popped/processed instead of when first discovered, which lets the same node get pushed onto the stack multiple times and, on a cyclic graph, can blow up the queue/stack size well beyond O(V).

← Previous Next →