Page Referrer Reachability
Problem statement
You are given a list of web traffic records. For this cross-language exercise, each record is represented as a two-element string array [url, referrer]:
urlis the page that a visitor reached.referreris the page the visitor came from. An empty string represents a direct arrival with no referrer.
Every record whose referrer is non-empty creates a directed movement from referrer to url. The reverse movement is not implied.
The records may describe disconnected components, repeated movements, and directed cycles.
You are also given query = [start, target]. Return true if target is reachable from start by following zero or more recorded movements. Therefore, return true when start and target are the same page. Otherwise, return false.
Direct-arrival records do not create additional movements.
What the interview report shared
The interview used the Python callable can_reach(records: list[dict], query: list[str]) -> bool. Each record was a dictionary with id, url, and referrer fields. The interviewer said that id was irrelevant to reachability and could be ignored. A null referrer represented a direct arrival and created no movement.
This exercise omits the unused id field and serializes a null referrer as an empty string, leaving the same directed-reachability task in a portable form.
Function
canReachPage(records: String[][], query: String[]) → booleanExamples
Example 1
records = [["/catalog","/home"],["/item/7","/catalog"],["/cart","/item/7"]]query = ["/home","/cart"]return = trueThe records create the directed path /home to /catalog to /item/7 to /cart.
Example 2
records = [["/pricing","/home"],["/signup","/pricing"]]query = ["/pricing","/home"]return = falseThe record creates a movement from /home to /pricing, but not the reverse movement requested by the query.
Example 3
records = [["/landing",""],["/account","/landing"]]query = ["/account","/account"]return = trueA page is reachable from itself without following an edge.
Constraints
1 <= records.length <= 2 * 10^5.- Every row in
recordscontains exactly two strings in the order[url, referrer]. - Every
url,start, andtargetis non-empty and has length at most100. - Every
referreris either an empty string or a page URL of length at most100. query.length == 2.- Page URLs are compared exactly and are case-sensitive.
- The records may contain repeated movements and directed cycles.