FastPrepFinite Same-Origin Web Crawler
Problems/Finite Same-Origin Web Crawler

Finite Same-Origin Web Crawler

Opendoor logoOpendoor● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The interview report asks for a web crawler using page retrieval and HTML-link parsing but does not preserve the example, crawl boundary, edge rules, or output. This exercise supplies a finite offline page corpus and conventional same-origin rules so the crawler is deterministic.

You are given parallel arrays urls and html. The string html[i] is the retrieved body for the absolute URL urls[i]. Starting at startUrl, crawl every reachable page in this supplied corpus that has the same origin as startUrl.

  • A link is an exact lowercase href attribute written as href="URL" or href='URL'. Attribute values do not contain their surrounding quote character.
  • Every link URL is absolute and starts with http:// or https://.
  • The origin is the scheme and authority before the first path, query, or fragment character. Host matching is case-sensitive because every supplied URL is already canonical.
  • Remove a URL fragment beginning with # before testing or visiting the link.
  • Follow a link only when its fragment-free URL has the same origin and appears in urls.
  • Visit each URL at most once. Return all visited URLs in lexicographic order.

Function

crawlPages(urls: String[], html: String[], startUrl: String) → String[]

Examples

Example 1

urls = ["https://homes.test/","https://homes.test/a","https://homes.test/b","https://other.test/x"]html = ["<a href='https://homes.test/a'>A</a><a href='https://other.test/x'>X</a>","<a href=\"https://homes.test/b\">B</a>","<a href='https://homes.test/a#top'>A</a>",""]startUrl = "https://homes.test/"return = ["https://homes.test/","https://homes.test/a","https://homes.test/b"]

The crawler reaches pages /a and /b, ignores the external-origin page, and does not revisit /a through its fragment.

Example 2

urls = ["http://site.test/root","http://site.test/kept"]html = ["<a href=\"http://site.test/missing\">Missing</a>",""]startUrl = "http://site.test/root"return = ["http://site.test/root"]

The linked page is absent from the supplied corpus, so only the starting page is visited.

Constraints

  • 1 <= urls.length = html.length <= 5000
  • All strings in urls are unique canonical absolute HTTP or HTTPS URLs.
  • startUrl appears in urls.
  • The total length of all strings in html is at most 200000.
  • Every recognized href value is a nonempty absolute HTTP or HTTPS URL.
All Opendoor interview questionsSee Opendoor hiring insights
Saved
class Solution {
    public String[] crawlPages(String[] urls, String[] html, String startUrl) {
        // Write your code here
    }
}

Not a valid String[]

Checking account…