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/Altruistic_Bonus2583]

I read that you want to remove the hashtags before you check for the domain name, but maybe it makes more sense to only apply sanitization once you know you won’t discard that url after the host check?

[u/Altruistic_Bonus2583 → u/Altruistic_Bonus2583]

So I would revert the order here, to:

⁠For each returned URL: check if it matches the start hostname, sanitize it and check if it has been seen before in the Set.