Katkat
Back

Multithreaded Web Crawler with Retries for a Failing Fetch API

SnowflakeSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Write a web crawler that visits every page reachable from a start URL through a slow link-fetching API, first with BFS or DFS, then with multiple threads, then with retries when the API fails. It tests visited-set safety, termination detection, backoff and failure reporting.

Write a web crawler. Starting from one URL, it visits every page reachable by following links, using an API that fetches a page and returns the URLs that page links to. Implement it with a breadth-first or depth-first traversal, then make it multithreaded, then make it retry when the fetch API fails.

fetch_links(url: str) -> list[str] # a network call: slow, and it can raise an exception when it fails

Clarifying Questions

  • Which pages are in scope: only URLs on the start URL's host, or everything reachable? Is there a limit on depth or on the number of pages?
  • Which URLs count as the same page: should fragments, trailing slashes or letter case be normalized?
  • What should the crawler return: the set of URLs visited, the order of visits, or the link graph?
  • When fetch_links fails, does the error say whether a retry can help, and is there a rate limit or a concurrency limit on the API?

Part 1 — Single-threaded crawl

Implement crawl(start_url) with BFS or DFS, returning the pages it reached, and explain your choice of traversal.

What This Part Should Cover

  • The traversal, the visited set and URL normalization
  • Scope filtering, and the order in which BFS and DFS visit pages
  • Time and memory in terms of pages and links, and why DFS should use an explicit stack

Part 2 — Multithreaded crawl

Fetches dominate the running time. Use several threads to fetch pages concurrently, and return the same set of pages as the single-threaded crawl.

What This Part Should Cover

  • An atomic check-and-insert on the visited set
  • Correct termination when no URL is waiting and none is being fetched
  • Bounding concurrent fetches, and what happens to an exception raised in a worker thread

Part 3 — Retries when the API fails

fetch_links sometimes fails. Make the crawler retry failed fetches without fetching any page more often than needed and without crawling forever.

What This Part Should Cover

  • Which errors are retried, how many times, and with what delay
  • Keeping threads busy while a retry waits, and limiting the load on a failing host
  • What the result reports about pages that never succeeded

Hints

Hint 1

Mark before you fetch: Think about when a URL should enter the visited set so that it is never fetched twice, even when many pages link to it.

Hint 2

When is the crawl finished: An empty queue does not mean the crawl is over while other threads are still fetching pages that may add new links.

Hint 3

Not every failure deserves a retry: Separate errors that may succeed on a second attempt from errors that never will, and think about what a waiting retry does to a worker thread.

Follow-up questions

  • The crawl covers billions of pages on many machines. How do you split the work and the visited set?
  • Some sites ask crawlers to slow down. How do you enforce a per-host request rate?
  • The crawler crashes halfway through. How does it resume without starting over?
  • Two different URLs serve the same content. How would you detect and skip the duplicates?