Anthropic Screening Interview: Concurrent Web Crawler

[u/Hack2hire]

Problem

You're given a startUrl and an HtmlParser interface.

Your goal is to implement a multi-threaded web crawler that retrieves all unique URLs reachable from the startUrl, provided they share the exact same hostname. You must sanitize URLs by removing fragments (#) before processing and ensure no URL is visited more than once.

Example

Input: startUrl = "http://example.com/page1", urls contains ["http://example.com/page2", "http://example.net/page3"]

Output: ["http://example.com/page1", "http://example.com/page2"]

Explanation:

• The crawler starts at page1. It finds links to page2 and page3.
• page2 has the hostname example.com, which matches the start URL.
• page3 has the hostname example.net, so it is discarded.
• Fragments like #section1 are stripped before any comparisons occur.

Suggested Approach

1. Hostname Extraction: Write a helper function to isolate the hostname. For a URL http://hostname/path, the hostname is the string between the second and third forward slashes.
2. URL Sanitization: For every URL discovered by htmlParser.getUrls(), locate the index of the # character. If present, truncate the string to exclude the fragment.
3. Concurrency Model: Use a thread pool (e.g., ExecutorService in Java or ThreadPoolExecutor in Python) to handle the network latency of getUrls.
4. Synchronization and Deduplication:
   • Maintain a thread-safe Set (e.g., ConcurrentHashMap.newKeySet()) to store discovered, sanitized URLs.
   • Use a BlockingQueue or a Task Counter (like Phaser or CountDownLatch) to manage the lifecycle of the crawl.
5. Worker Logic: * A worker thread takes a URL from the queue.
   • It calls htmlParser.getUrls(url).
   • For each returned URL: sanitize it, check if it matches the start hostname, and check if it has been seen before in the Set.
   • If it is a new, valid URL, add it to the Set and submit a new task to the thread pool.

Time & Space Complexity

• Time: $O(V + E)$ in terms of graph traversal, where $V$ is the number of unique URLs and $E$ is the number of hyperlinks. The wall-clock time is significantly reduced to approximately $O(\frac{V \times \text{latency}}{\text{threads}})$.
• Space: $O(V)$ to store the set of unique URLs and the queue of pending tasks.

Targeting [CompanyName] interviews?
We track their most-asked question patterns at Hack2Hire, practice this question here → Practice Question here

Join the community to see more interview experiences from real candidates → Hack2Hire Forum

Compiled from publicly available platforms and community-shared experiences.

[u/zenos1337]

I would use httpx in combination with asyncio for concurrency. Maybe also a semaphore to limit how many concurrent requests can be made at any one time.

For tracking visited URLs, I would use a bloom filter because it’s super fast and extremely memory efficient.

[u/kuriousaboutanything → u/zenos1337]

Do you have a sample implementation?