โ˜… Final Challenge

โ€บ Concurrent Crawler

75 pts

Everything at once: bounded concurrency, deduplication under contention, and โ€” the hard part โ€” clean termination.

Implement:

func Crawl(start string, fetch func(url string) []string, workers int) []string
  • fetch(url) returns the URLs linked from url. The graph may contain cycles, self-links, and links to URLs that link nowhere.
  • Visit every URL reachable from start, calling fetch exactly once per URL โ€” deduplication must hold even when two workers discover the same URL at the same moment.
  • At most workers calls to fetch may be in flight at once (assume workers >= 1), and on a wide graph the budget must actually be used โ€” fetches must overlap.
  • Return the set of visited URLs (any order, no duplicates), only after all fetching has finished.

Termination is where naive designs deadlock: the crawl is finished when no worker is fetching and no discovered URL is still waiting โ€” but each fetch can add new work. Track outstanding work explicitly (a counter, a WaitGroup, or a coordinator goroutine) so your workers know when to stop waiting for more.

Log in to submit a solution and earn points.