Web Crawler

Description

Company: Anthropic

Problem Statement

You are given:

• A starting web address called startUrl.
• A tool called HtmlParser that finds all links on a specific web page.

You need to build a web crawler. It must find all URLs that you can reach from the startUrl.

Important Rule: You must only keep URLs that belong to the same hostname as the startUrl. The order of the list does not matter.

Here is the interface for the HtmlParser:

class HtmlParser:
    def get_urls(self, url: str) -> list[str]:
        """Returns all URLs from a given page URL."""

Your function signature will look like this: def crawl(start_url: str, html_parser: HtmlParser) -> list[str].

Core Rules

Your crawler must follow these steps:

• Start at the startUrl.
• Use HtmlParser.getUrls(url) to get all links from that page.
• Avoid duplicates: Do not visit the same URL more than once.
• Check the Hostname: Only follow links if the hostname matches the startUrl.
• Assume all links use http and do not use port numbers.

Things to Clarify

• URL Fragments: Ask the interviewer about links with # (like http://example.com/page#section1). Should you treat them as the same page or a new page?
• URL Normalization: Ask if you need to clean up or standardise the URLs. Usually, you can assume this is not needed for the basic part.

Part 2: Multithreading (Important!)

First, solve the problem using a single thread. Once that works, make a multithreaded or concurrent version to make it faster.

Goals

• Run in Parallel: Download multiple pages at the same time.
• Thread Safety: Make sure your data (like the visited list) doesn't get corrupted when many threads touch it at once.
• Avoid Duplicates: Even with multiple threads, never visit a URL twice.
• Check the Hostname: Keep following the hostname rule.

Hint for the Candidate

• Use a Thread Pool to manage your threads.
• Do not make a new thread for every single URL. This will crash the system.
• A thread pool limits how many threads run at once.
• Common setup: Use a fixed size (like 10-20 threads) and a queue for tasks.

Solution: Python Implementation

Below is a full Python solution: first single-threaded, then a multithreaded version using a thread pool and a lock.

URL Helper Functions

from urllib.parse import urlsplit, urlunsplit


def normalize_url(url: str) -> str:
    """Remove the fragment (#) so http://example.com/page#1
    and http://example.com/page#2 are seen as the same URL."""
    parts = urlsplit(url)
    return urlunsplit((parts.scheme, parts.netloc, parts.path, parts.query, ""))


def get_hostname(url: str) -> str:
    return urlsplit(url).hostname

Part 1: Single-Threaded Crawler

def crawl(start_url: str, html_parser) -> list[str]:
    start = normalize_url(start_url)
    hostname = get_hostname(start)

    visited = {start}
    stack = [start]

    while stack:
        url = stack.pop()
        for next_url in html_parser.get_urls(url):
            normalized = normalize_url(next_url)
            if get_hostname(normalized) == hostname and normalized not in visited:
                visited.add(normalized)
                stack.append(normalized)

    return list(visited)

Part 2: Multithreaded Crawler

import threading
from concurrent.futures import FIRST_COMPLETED, ThreadPoolExecutor, wait


def crawl_concurrent(start_url: str, html_parser, max_workers: int = 10) -> list[str]:
    start = normalize_url(start_url)
    hostname = get_hostname(start)

    visited = {start}
    visited_lock = threading.Lock()

    def fetch(url: str) -> list[str]:
        """Runs on a pool thread: fetch one page, return the new URLs to crawl."""
        new_urls = []
        try:
            next_urls = html_parser.get_urls(url)
        except Exception as e:
            print(f"Error fetching URLs from {url}: {e}")
            return new_urls

        for next_url in next_urls:
            normalized = normalize_url(next_url)
            if get_hostname(normalized) != hostname:
                continue
            # Check-and-add must be atomic, or two threads could
            # both claim the same URL.
            with visited_lock:
                if normalized in visited:
                    continue
                visited.add(normalized)
            new_urls.append(normalized)
        return new_urls

    with ThreadPoolExecutor(max_workers=max_workers) as pool:
        pending = {pool.submit(fetch, start)}
        while pending:
            done, pending = wait(pending, return_when=FIRST_COMPLETED)
            for future in done:
                for url in future.result():
                    pending.add(pool.submit(fetch, url))

    return list(visited)

How to Run the Code

import random
import time


class FakeHtmlParser:
    """Fake parser for testing: a dict of url -> links, with a fake delay."""

    def __init__(self, urls):
        self.urls = urls

    def get_urls(self, url):
        time.sleep(random.random() * 0.015)  # fake network delay
        return self.urls.get(url, [])


urls = {
    "http://news.yahoo.com": [
        "http://news.yahoo.com/news/topics/",
        "http://news.yahoo.com/news",
    ],
    "http://news.yahoo.com/news/topics/": [
        "http://news.yahoo.com/news",
        "http://news.yahoo.com/news/sports",
    ],
    "http://news.yahoo.com/news": [
        "http://news.google.com",
    ],
    "http://news.yahoo.com/news/sports": [],
}

parser = FakeHtmlParser(urls)
result = crawl_concurrent("http://news.yahoo.com", parser, max_workers=2)
print("Crawled URLs:", result)
# Output should be yahoo.com URLs only (no google.com)

Why We Built It This Way

• Thread Pool: ThreadPoolExecutor limits how many downloads run at once so we don't overwhelm the system (or create a thread per URL).
• Threads, not processes: Crawling is I/O bound — threads spend their time waiting on the network, so the GIL is not a bottleneck here.
• URL Normalization: We remove the # fragment so the same page is never treated as two different links.
• Thread Safety: The visited set is shared by all threads, so the check-and-add is done inside a Lock. Without it, two threads could pass the in visited check at the same time and crawl the same URL twice.
• Completion detection: The while pending loop over wait(..., FIRST_COMPLETED) keeps submitting work until no futures remain — no manual task counting needed.
• Error Handling: If one link fails, we log the error, but the crawler keeps going.

System Design Questions

The interviewer may ask these questions verbally. You usually don't need to code these, but you should know how to explain them.

1. Threads vs Processes

Question: What is the difference between a thread and a process? Which one is better for a web crawler?

Answer Strategy:

• Threads: These are "lightweight." They share memory. They are great for tasks that wait a lot (like waiting for a website to load). This is called I/O-bound.
• Processes: These are "heavy." They have their own separate memory. They are better for tasks that do heavy math (CPU-bound).
• For Crawling: Use Threads. Crawling is mostly waiting for the internet, and threads are more efficient for that.

2. Scaling to Many Machines

Question: If we have millions of URLs, one computer isn't enough. How do we build a distributed system?

Answer Strategy:

• URL Distribution: How do we split the work? We can use Consistent Hashing on the hostname to decide which machine crawls which website.
• Coordination: Machines need to talk to check for duplicates. We can use a shared cache like Redis.
• Load Balancing: We need to make sure every machine has roughly the same amount of work.
• Fault Tolerance: If a machine crashes, another machine needs to pick up its work.

3. Being "Polite" (Rate Limiting)

Question: If we crawl too fast, we might crash the website. How do we prevent this?

Answer Strategy:

• robots.txt: Always check this file first. It tells us what we are allowed to crawl.
• Rate limiting: Set a limit. For example, "only 1 request per second for yahoo.com."
• Throttling: If the server starts responding slowly, our crawler should slow down automatically.
• Distributed Control: If multiple machines are crawling the same site, they need to coordinate so they don't attack the site together.

4. Handling Duplicate Pages

Question: Many URLs point to the exact same content. How do we detect this so we don't waste space?

Answer Strategy:

• Fingerprinting: Create a hash (like MD5 or SHA-256) of the page content. If the hash matches one we already have, it's a duplicate.
• URL Normalization: Clean up the URL text (remove tracking IDs, sort parameters) before fetching.
• Similarity Check: Use algorithms like Simhash or Jaccard similarity to find pages that are mostly the same, even if a few words changed.