LeetLLM
MediumGraph TraversalPython 3

Same-host Crawler

Traverse a web graph in breadth-first order while enforcing same-host and duplicate-visit invariants.

30m3 sample tests6 hidden tests

Implement crawl(start_url, get_links) for a small web graph. The crawler starts from start_url, calls get_links(url) to discover outgoing links, and returns only URLs on the same host.

Requirements

  • Return URLs in deterministic breadth-first order.
  • Don't visit the same URL twice.
  • Resolve relative links against the current URL.
  • Ignore malformed URLs, non-HTTP(S) URLs, and off-host URLs.
  • Keep the implementation single-threaded for the base problem.
  • URL identity is the full resolved string. Keep fragments and query strings; #frag and ?q=… are part of the visit key and of the returned URLs (e.g. https://a.test/leaf#frag is distinct from https://a.test/leaf).
  • Assume start_url is a valid HTTP(S) URL on the crawl host and always include it in the result. Validation applies to discovered links.
  • Treat a candidate as malformed if the resolved string contains whitespace (e.g. "not a url"). Other junk may still parse as a path after urljoin; this problem only requires the whitespace rule.
  • Same host means matching netloc (host and port). http and https on the same netloc are both allowed regardless of scheme.

Example

python
1graph = { 2 "https://docs.example.com/": ["/a", "/b", "https://other.example.com/x"], 3 "https://docs.example.com/a": ["/c"], 4 "https://docs.example.com/b": ["/c"], 5} 6 7def get_links(url): 8 return graph.get(url, []) 9 10assert crawl("https://docs.example.com/", get_links) == [ 11 "https://docs.example.com/", 12 "https://docs.example.com/a", 13 "https://docs.example.com/b", 14 "https://docs.example.com/c", 15]

Constraints

  • Assume get_links is synchronous.
  • Use standard-library Python only.
  • Treat the start URL host as the only allowed host.

Editor