FastPrep
Problem · Graph

Finite Same-Origin Web Crawler

Learn this problem
● MediumOpendoor logoOpendoorFULLTIMEPHONE SCREEN

Problem statement

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.
drafts saved locally
public String[] crawlPages(String[] urls, String[] html, String startUrl) {
    // Write your code here
}
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/"
expected["https://homes.test/", "https://homes.test/a", "https://homes.test/b"]
checking account