Katkat
Back

Build a concurrent web crawler

AnthropicSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests your ability to design a concurrent crawler that manages shared state across multiple threads, handles URL de-duplication, and prevents infinite cycles during graph traversal.

Problem Statement

Design a multi-threaded web crawler that fetches the content of web pages starting from a seed URL. The crawler should follow all discovered links recursively up to a specified depth max_depth.

Your implementation must be thread-safe and efficient, ensuring that:

  1. The same URL is not visited multiple times.
  2. The system handles potential network latency gracefully.
  3. The crawler respects a limit on the number of concurrent requests.

Implement the following interface:

class WebCrawler:
    def __init__(self, max_depth, max_threads):
        """Initializes the crawler."""

    def crawl(self, start_url):
        """Starts the crawling process from the given URL."""

    def _fetch_page(self, url):
        """Helper to simulate fetching HTML. Returns a list of discovered URLs."""

Constraints

  • max_depth will be a positive integer.
  • max_threads will be between 1 and 20.
  • Use a thread-safe approach to manage the set of visited URLs.
  • You may use a thread pool or a semaphore to limit concurrency.

Examples

Example 1 Input: start_url = "http://a.com", max_depth = 1 Output: Returns a set of all URLs reachable from a.com that are at most 1 link away.

Example 2 Input: start_url = "http://a.com", max_threads = 2 Output: Crawler should process multiple URLs in parallel without redundant visits.

Hints

Hint 1

Use a thread-safe Set (e.g., protected by a Lock or using ConcurrentSet) to track visited URLs and avoid redundant work.

Hint 2

Utilize a ThreadPoolExecutor to manage the worker threads and a task queue to hold discovered URLs that need to be processed.

Hint 3

To handle depth tracking, store the current depth alongside the URL in the task queue or use a level-order traversal approach.

Follow-up questions

  • How would you modify your design to be distributed across multiple physical machines instead of multiple threads on one machine?
  • How can you add 'politeness' to your crawler (e.g., ensuring you don't overwhelm a single domain with requests)?
  • What changes would be required to persist the crawler's state so it can resume after a crash?