Katkat
Back

Implement a web crawler using a provided API

AnthropicMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to design a multi-threaded web crawler that efficiently traverses a site while respecting domain constraints and avoiding redundant work.

Web Crawler Implementation

You are tasked with building a web crawler that extracts all unique URLs from a given starting page, subject to specific constraints. You are provided with a utility function fetch_urls(url) which returns a list of URLs linked from the input page. Your crawler must only visit URLs belonging to the same hostname as the starting URL.

Requirements

  • Implement a function crawl(start_url, max_depth) that performs a breadth-first search of the web graph.
  • The crawler must be multi-threaded to speed up fetching.
  • Prevent redundant visits and infinite loops caused by cyclical links.
  • Use thread-safe data structures to manage the set of visited URLs.

Function Signature

def crawl(start_url: str, max_depth: int) -> set:
    # Returns a set of all visited URLs within the allowed depth

Constraints

  • max_depth will be a non-negative integer.
  • You must not visit the same URL twice.
  • The crawler should stop once all reachable URLs within max_depth have been processed.

Examples

Example 1 Input: start_url = "http://example.com/home", max_depth = 1 Output: {"http://example.com/home", "http://example.com/about", "http://example.com/contact"} Explanation: The crawler visits the home page and fetches all linked URLs from the same host, stopping at depth 1.

Edge Cases

  • The starting URL is invalid or the fetcher returns an empty list.
  • Links point to external hostnames (e.g., google.com inside example.com).
  • High volume of concurrent requests causing rate-limiting (ignore actual network latency, focus on structure).

Hints

Hint 1

Use a thread-safe set (like a set protected by a Lock or a concurrent hash set) to keep track of already visited URLs to avoid redundant processing.

Hint 2

Structure your traversal as a queue of tuples containing `(url, current_depth)`, and use a thread pool to process these entries concurrently.

Hint 3

Use `urllib.parse.urlparse` to easily extract the hostname of a URL to ensure your crawler stays within the allowed domain scope.

Follow-up questions

  • How would you modify this crawler to be polite and avoid overwhelming a server if you were hitting it with 50+ threads?
  • If the set of visited URLs becomes too large to fit in memory, what storage architecture would you use to maintain the 'visited' state?
  • How would you change your design if the web pages were rendered dynamically using JavaScript, meaning `fetch_urls` is no longer sufficient?