Skip to main content
All questions
MediumGraphs · Breadth-First Search

In-Memory Web Crawler

Written by a community member · · 1 attempt · 0% pass

0

Design an in-memory web crawler.

Implement a function that, given a starting URL, the pages of an in-memory web, and a maximum crawl depth, returns the URLs reachable from the start URL up to that depth, in any order.

The web is given as two parallel lists: pages[i] is a URL and links[i] is the list of URLs that page links to.

Rules:

  • Treat the web as an in-memory directed graph.
  • You may crawl with multiple worker threads, but the result must be deterministic.
  • Only URLs reachable from the given starting URL should be returned.
  • Do not revisit the same URL more than once.
  • The starting URL is at depth 0.
  • Only include URLs whose shortest distance from the start is less than or equal to max_depth.
  • If the starting URL is not one of the pages, return a list containing only the starting URL.

Example 1:
Input: crawl_web('a', ['a', 'b', 'c', 'd'], [['b', 'c'], ['d'], [], []], 1)
Output: ['a', 'b', 'c']

Example 2:
Input: crawl_web('a', ['a', 'b', 'c'], [['b'], ['c'], ['a']], 2)
Output: ['a', 'b', 'c']