The Anthropic technical screen I got was the web crawler problem. They first had me write a single-threaded version, then after chatting for a while I had to write a multi-threaded one. I want to talk about this problem on its own, because at first I also thought it was just a BFS.
The problem is a concurrent web crawler: you're given a startUrl and an htmlParser, and you have to find all URLs that have exactly the same hostname as startUrl. It looks simple, but a few rules in the problem statement are annoying: you have to strip the fragment after the # before comparing URLs, the hostname has to match exactly, and the link graph can have cycles. Once you sort these rules out, the single-threaded version is not actually hard. My main worry at the time was missing one of the conditions.
The multi-threaded part is where the real time went. Below is my own review of it afterwards, so it's not necessarily the answer the interviewer wanted.
You have to be careful with the visited set. In the single-threaded version you can write it any way you like, but once multiple threads are checking and adding at the same time, if the check and the add are not under the same lock, the same URL will get crawled twice, and the problem statement explicitly says you can't visit a URL twice. My idea was to dedupe before enqueuing, with the check and the insert in the same lock.
Then there's the termination condition, which I think is the easiest part to get wrong when I look back. In the single-threaded version you're done when the queue is empty. With multiple threads, a queue that is empty for the moment doesn't mean the crawl is finished, because another thread may still be parsing a page and about to add new links. My idea was to look at both the queue and the number of threads still working, and only call it done when both are zero. Otherwise it's very easy to exit too early or to hang.
Also, a crawler is bottlenecked on waiting for the network, not on computation, so using threads really does help, and there's no need to agonize over threads versus processes.
I'd suggest writing the version with locks by hand yourself, and see whether it deadlocks.
Discussion
Loading comments…