URL reachability from navigation records

A table of navigation events has rows (user_id, source_url, destination_url): a user went straight from source_url to destination_url. Treat every such pair as a directed link between pages, whichever user made it. Given two URLs, decide whether you can get from the first to the second by following one or more links.

Interface

Unless you agree on a different interface with the interviewer, assume:

• build(records: list[tuple[str, str, str]]) -> None — loads the records into an in-memory graph.
• can_reach(url1: str, url2: str) -> bool — True if a path of one or more links leads from url1 to url2.

Example

records = [("u1", "/home", "/search"), ("u1", "/search", "/item/7"),
           ("u2", "/home", "/deals"), ("u3", "/item/7", "/cart"),
           ("u2", "/cart", "/checkout")]

can_reach("/home", "/checkout")  ->  True    # home > search > item/7 > cart > checkout
can_reach("/deals", "/cart")     ->  False   # nothing leaves /deals
can_reach("/checkout", "/home")  ->  False   # links only go one way

Constraints

• All records fit in memory. V distinct URLs, E distinct links; the same link may appear in many records.

Clarifying questions

• Does can_reach(u, u) need a loop back to u, or is it always true?
• Does the user matter, or only the pages?
• Is the graph built once and queried many times?

What a strong answer covers

• An adjacency map from each URL to a set of destinations, which also removes duplicate records.
• Breadth-first or depth-first search from url1 with a visited set, so cycles between pages don't loop forever; stop early when url2 is found.
• O(R) to build from R records, O(V + E) time and O(V) extra space per query.
• An iterative search for deep chains, and unknown URLs answering False.

Follow-ups

• Return the shortest path of pages, not just yes or no.
• Many queries: precompute strongly connected components, or cache the set reachable from popular pages.
• The records don't fit in memory: how would you answer from a distributed store?