Implement hostname-restricted web crawler

Quick Overview

This question evaluates skills in graph traversal and cycle detection, hostname-based filtering, URL parsing, and basic network error handling. Commonly asked in Coding & Algorithms interviews, it assesses algorithmic reasoning about traversal strategy and complexity (time and space) analysis while balancing conceptual understanding with practical implementation details.

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a single-threaded web crawler that, given a starting URL startUrl and an interface getUrls(url) that returns all hyperlinks on the page at url, returns the set of all unique pages reachable whose hostname exactly matches the hostname of startUrl. Requirements: do not fetch pages outside the starting hostname; avoid duplicate fetches and infinite loops (handle cycles); choose BFS or DFS and justify your choice; state time and space complexity; explain how you parse the hostname from a URL; describe basic error handling for failed requests.

Overview: This question evaluates skills in graph traversal and cycle detection, hostname-based filtering, URL parsing, and basic network error handling. Commonly asked in Coding & Algorithms interviews, it assesses algorithmic reasoning about traversal strategy and complexity (time and space) analysis while balancing conceptual understanding with practical implementation details.

You are given a starting URL startUrl and a dictionary web that simulates the interface getUrls(url). If a URL exists as a key in web, fetching that page succeeds and returns the list of hyperlinks on that page. If a URL is missing from web, the request is considered failed. Implement a single-threaded web crawler using BFS that returns all unique reachable pages whose hostname exactly matches the hostname of startUrl. Never fetch pages outside the starting hostname, avoid duplicate fetches, and handle cycles safely. For deterministic grading, return the final set as a lexicographically sorted list. Parse the hostname from a URL using the hostname component only (for example, with urlparse(url).hostname), so scheme, port, path, query, and fragment do not affect the host comparison. For basic error handling, if fetching a discovered same-host URL fails, keep that URL in the result but do not expand its outgoing links.

Constraints

0 <= len(web) <= 10^4
The total number of hyperlinks across all lists in web is at most 2 * 10^5
All URLs in test cases are absolute URL strings, but some discovered URLs may be missing from web to simulate request failures
The crawler must be single-threaded and must not fetch any URL whose hostname differs from the hostname of startUrl

Examples

Input: ('http://a.com', {'http://a.com': ['http://a.com/about', 'http://b.com/out'], 'http://a.com/about': [], 'http://b.com/out': ['http://a.com/hidden'], 'http://a.com/hidden': []})

Expected Output: ['http://a.com', 'http://a.com/about']

Explanation: The crawler visits the start page and http://a.com/about. It must not fetch http://b.com/out because the hostname differs, so http://a.com/hidden is never discovered.

Input: ('http://news.com', {'http://news.com': ['http://news.com/a', 'http://news.com/b', 'http://news.com/a'], 'http://news.com/a': ['http://news.com', 'http://news.com/b'], 'http://news.com/b': ['http://news.com/c'], 'http://news.com/c': ['http://news.com/a']})

Expected Output: ['http://news.com', 'http://news.com/a', 'http://news.com/b', 'http://news.com/c']

Explanation: There are duplicate links and a cycle, but each same-host URL is fetched at most once because of the visited set.

Hints

Use a queue and a visited set. The queue gives you an iterative BFS, and the visited set prevents duplicate fetches and infinite loops.
Compare only the parsed hostname component, not the whole URL string. Two URLs with different schemes or ports can still belong to the same hostname.