Implement a Bounded Concurrent Web Crawler

Problem

You are given a starting URL startUrl, a page limit maxPages, a worker limit maxWorkers, and a dictionary urlMap that models the web graph. The dictionary maps each URL to a list of its outgoing links (as if you had fetched and parsed that page).

Implement a thread‑safe concurrent crawler that explores pages starting from startUrl and obeys these rules:

• Only URLs whose hostname matches the hostname of startUrl are crawled.
• Each URL may be visited at most once.
• The crawl stops after maxPages distinct URLs have been scheduled (or visited). Once that many URLs are in the work queue, no further URLs may be added.

Requirements

1. Use at most maxWorkers worker threads.
2. Looking up a URL’s links in urlMap may be slow; a single slow URL must not stall other workers.
3. When multiple pages discover the same URL concurrently, that URL must be fetched only once.
4. The crawler must terminate cleanly when there is no pending work and all scheduled tasks have finished. It must not deadlock or exit before all work is done.
5. Return every URL that was successfully scheduled. The order of the returned URLs is unspecified; for local testing you may sort the result lexicographically.

Function Signature

def crawl(startUrl: str, maxPages: int, maxWorkers: int, urlMap: dict[str, list[str]]) -> list[str]:

• startUrl: the entry point URL.
• maxPages: maximum number of distinct URLs that may be crawled.
• maxWorkers: maximum number of concurrent worker threads.
• urlMap: a dictionary where each key is a URL and the associated value is a list of outgoing links found on that page. The dictionary contains the entire known graph; you do not need to call external fetch/parse functions.

Constraints

• 1 <= len(urlMap) <= 10^5
• 1 <= maxPages <= 10^5
• 1 <= maxWorkers <= 64
• The total number of links across all entries in urlMap is at most 2 * 10^5.
• URLs may form cycles and may be referenced by many different pages.

Example

startUrl = "https://a.com/"
maxPages = 10
maxWorkers = 2
urlMap = {
    "https://a.com/":  ["https://a.com/x", "https://a.com/y"],
    "https://a.com/x": ["https://a.com/z"],
    "https://a.com/y": ["https://a.com/z"]
}

All four URLs share the same hostname. The crawler visits https://a.com/, discovers x and y, then visits those and discovers z. No URL is visited more than once. The returned set, when sorted lexicographically, is:

https://a.com/
https://a.com/x
https://a.com/y
https://a.com/z