Single-thread Web Crawler, then Multi-threaded Crawler

Problem: Build a Web Crawler (single-thread first, then multi-thread) Given a starting URL start_url, implement a crawler that visits qualifying linked pages and returns the set (or list) of visited pages/URLs. Part 1: Single-threaded crawler Implement a single-threaded crawler that: Fetches the HTML of start_url. Extracts links from the page (assume you can call parse_links(html) to get a list of URLs). Only crawls URLs on the same host as start_url. Crawls each URL at most once (avoid duplicates / cycles). Traversal order is not important (BFS or DFS is fine). Return the set of crawled same-host URLs (order does not matter). Part 2: Multi-threaded / concurrent crawler Extend Part 1 to a concurrent version: Use multiple threads (or a thread pool) to fetch pages concurrently. Still guarantee: Only same-host URLs are crawled. Each URL is crawled at most once (thread-safe). The function returns only after all work is finished. Assumptions fetch(url) -> str: a synchronous function that returns HTML for a URL (potentially slow; I/O bound). parse_links(html) -> List[str]: extracts URLs from HTML. Total reachable URLs can be up to 1e5. Discussion points (may be discussed rather than fully implemented) A thread-safe design for the visited set and the work queue. Controlling concurrency (don’t spawn unbounded threads). Handling retries/timeouts/cancellation. Example Input: start_url = "https://example.com" Assume link graph: https://example.com links to https://example.com/a, https://example.com/b, https://other.com/x https://example.com/a links to https://example.com/b Output (any order): { "https://example.com", "https://example.com/a", "https://example.com/b" } Scale Total URLs: up to 100,000 Links per page: up to 1,000 fetch latency: ~10ms to seconds Example Input start_url=https://example.com links: https://example.com -> https://example.com/a https://example.com/b https://other.com/x https://example.com/a -> https://example.com/b https://example.com/b -> Output https://example.com,https://example.com/a,https://example.com/b (any order)