Web Crawler (single-threaded first, then concurrent)

Problem: Implement a Web Crawler (single-threaded first, then concurrent) Given a starting URL startUrl, implement a crawler that fetches links from web pages. You are given an API getUrls(url) which returns a list of URLs found on the given page. Starting from startUrl, recursively crawl and collect all URLs that belong to the same website (same host) as startUrl, and return the set/list of these URLs (order does not matter). Requirements Single-threaded version: Implement a single-threaded crawler using either BFS or DFS. Concurrent version (follow-up): After the single-threaded solution works correctly, extend it to a multi-threaded/concurrent implementation to improve throughput. Input/Output (equivalent abstraction for local testing) In interviews this is usually presented as an API getUrls(url). For description purposes, you may model it as a directed graph: Input: startUrl: string links: a mapping (fromUrl -> [toUrls]) representing the return value of getUrls(fromUrl) Output: All URLs reachable from startUrl that have the same host as startUrl (deduplicated), order does not matter Constraints / clarifications (ask during interview) How to extract the host from a URL (e.g., http(s)://host/path...). Whether “same website” means exact host match. Whether getUrls may return duplicates. Whether cycles may exist (usually yes; you need a visited set). For the concurrent version: Whether getUrls is thread-safe / can be called concurrently. The max number of threads (fixed-size pool or configurable). Sample test cases (equivalent abstraction) See the 5 cases in the Chinese statement above; outputs are sets of same-host reachable URLs including startUrl itself. Example Input startUrl=http://news.example.com/a links=http://news.example.com/a->[http://news.example.com/b,http://news.example.com/c,http://other.com/x] http://news.example.com/b->[http://news.example.com/a] http://news.example.com/c->[] Output {http://news.example.com/a,http://news.example.com/b,http://news.example.com/c}