Build an Exactly-Once Crawler and Add Safe Concurrency

Implement a web crawler using the supplied operation `fetchAndParse(String url)`, which returns the links on that page. Your entry point is `void crawl(String seedUrl)`: starting from the seed, visit every reachable page exactly once. The method has no result collection to return. First explain a single-threaded implementation. Then identify its bottleneck and design a concurrent version with production-quality synchronization, termination, and failure handling. ### Constraints & Assumptions - The supplied operation performs fetching and link extraction. Do not implement an HTML parser or replace it with a graph-array input. - **Baseline practice assumptions:** the reachable graph is finite and static; links are canonical absolute URL strings; every fetch eventually succeeds; and the supplied operation can be called concurrently. Under these assumptions, exactly once means one call to `fetchAndParse` for each distinct reachable URL, including the seed. - The report gives no same-host restriction, depth limit, page cap, retry contract, or crash-recovery guarantee. Do not silently add a boundary that excludes reachable URLs from the baseline requirement. - For the production discussion, relax the success assumption and explain what retries, timeouts, cancellation, and restart recovery do to the exactly-once claim. Concurrency must be bounded; no fixed worker count or throughput target is supplied. ### Clarifying Questions to Ask - Does a URL string identify a page, or must aliases, fragments, and redirects be canonicalized before claiming uniqueness? - Is `fetchAndParse` safe for concurrent calls, and can it time out or be cancelled? - Does “exactly once” count attempts, successful fetches, or processing of their results when failures occur? - If an operational page limit is necessary, may the crawl report an incomplete outcome rather than claiming all reachable pages were visited? ### Part 1 — Traverse Without Repeating Fetches Describe the frontier, visited state, and placement of the visited check. Explain why the crawler handles self-links, cycles, and several pages linking to the same destination. State when the void method can return. #### What This Part Should Cover - Reserving a URL before it enters the frontier. - Exhausting reachable work under the finite, successful-fetch baseline. - Traversal and state complexity separated from network and parsing cost. ### Part 2 — Add Concurrency Without Losing Work Design a bounded worker architecture. Explain what happens when two workers discover the same URL and when the frontier is temporarily empty while another fetch is still running. #### What This Part Should Cover - An atomic check-and-reserve transition and fetching outside shared locks. - Work accounting that includes queued and active pages. - An enqueue/backpressure policy that cannot deadlock all workers while they publish discovered links. ### Part 3 — Define the Production Failure Contract Explain how a failed fetch is represented, how retries are owned, how the caller learns about incomplete execution, and what happens if the process fails after a request was sent but before its completion was recorded. #### What This Part Should Cover - Separate discovery, attempt, and terminal states without duplicate retry scheduling. - Resource shutdown and cancellation that do not claim successful exhaustive completion. - The boundary between in-process duplicate prevention and durable exactly-once external effects. ```hint Count work beyond the queue A worker that removed the last frontier item may still discover several new URLs. Identify the state that remains nonzero during that fetch. ``` ### What a Strong Answer Covers - A crawler faithful to the supplied I/O API and void entry point. - A precise exactly-once guarantee under the baseline assumptions and explicit weaker guarantees under failures. - Atomic discovery, bounded network concurrency, and correct completion detection without holding a global lock during I/O. ### Follow-up Questions - What breaks if a URL is added to the visited set only after its fetch finishes? - How can a bounded queue deadlock if every worker is also a producer of child URLs? - How would you resume a crawl after a process crash while acknowledging that an uncertain fetch may need to be repeated?