FastPrepConcurrent Web Crawler Reachability

Concurrent Web Crawler Reachability

Temporal logoTemporal● MediumFULLTIMEPHONE SCREEN
Learn

Problem statement

A production crawler fetches many discovered pages concurrently while ensuring that each known page is fetched at most once.

For this deterministic judge adapter, pages[i] identifies a known page and outgoing[i] contains the links found after fetching it. Starting at startUrl, return every reachable known page in lexicographic order. Ignore links that do not occur in pages.

The result must be independent of worker completion order. In a production discussion, explain how an atomic visited set and a bounded worker queue prevent duplicate fetches and unbounded concurrency.

Function

crawlReachable(startUrl: String, pages: String[], outgoing: String[][]) → String[]

Examples

Example 1

startUrl = "a"pages = ["a","b","c","d"]outgoing = [["b","c"],["d"],["d"],[]]return = ["a","b","c","d"]

Both branches reach d, but it is returned once.

Example 2

startUrl = "home"pages = ["home","about","orphan"]outgoing = [["about","external"],[],["home"]]return = ["about","home"]

Unknown external is ignored and orphan is not reachable.

Example 3

startUrl = "solo"pages = ["solo"]outgoing = [["solo"]]return = ["solo"]

A self-link does not duplicate the page.

Constraints

  • 1 <= pages.length == outgoing.length <= 100000.
  • Page identifiers are unique non-empty strings, and startUrl occurs in pages.
  • The total number of links is at most 300000.

More Temporal problems

See Temporal hiring insights
public String[] crawlReachable(String startUrl, String[] pages, String[][] outgoing) {
    // Write your code here.
}
startUrl"a"
pages["a","b","c","d"]
outgoing[["b","c"],["d"],["d"],[]]
expected["a", "b", "c", "d"]
Checking account…