How should I practice Finite Web Crawler?

Start by reading the full statement, solve the visible examples, then compare the pattern against related MongoDB onsite interview problems in FastPrep.

Is Finite Web Crawler associated with MongoDB?

FastPrep tags this as a MongoDB onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Finite Web Crawler

Learn this problem

● Medium

MongoDBFULLTIMEONSITE INTERVIEW

Problem statement

You are given a finite collection of pages. urls[i] is the URL of page i, and links[i] is the ordered list of normalized URLs returned by the provided fetch-and-parse helpers for that page.

Starting from startUrl, crawl the reachable pages in breadth-first order:

Discover startUrl first.
When a discovered page is processed, inspect its links from left to right.
If a link exactly matches a URL in urls and that page has not been discovered, discover it and schedule it for processing.
Ignore links that are not present in the finite collection.

Return the URLs in discovery order. Discover each page at most once. The finite collection, rather than a hostname restriction, defines the crawl boundary.

Function

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

Examples

Example 1

urls = ["https://a.test/start","https://a.test/docs","https://b.test/news","https://a.test/end"]links = [["https://a.test/docs","https://b.test/news","https://missing.test/page"],["https://a.test/end"],["https://a.test/end","https://a.test/start"],[]]startUrl = "https://a.test/start"return = ["https://a.test/start","https://a.test/docs","https://b.test/news","https://a.test/end"]

The start page discovers the docs page and the cross-domain news page in that order. The missing page is outside the finite collection. The docs page then discovers the end page; later links to already discovered pages do not add them again.

Example 2

urls = ["https://site.test/root","https://site.test/a","https://site.test/b","https://site.test/isolated"]links = [["https://site.test/a","https://site.test/a"],["https://site.test/b"],["https://site.test/root"],["https://site.test/root"]]startUrl = "https://site.test/root"return = ["https://site.test/root","https://site.test/a","https://site.test/b"]

The duplicate link to a and the cycle back to root are ignored after discovery. The isolated page is present in the collection but is not reachable from the start page.

Example 3

urls = ["https://x.test/alpha","https://x.test/beta","https://x.test/start","https://x.test/zeta"]links = [[],["https://x.test/alpha"],["https://x.test/beta","https://outside.test/no-copy"],["https://x.test/start"]]startUrl = "https://x.test/start"return = ["https://x.test/start","https://x.test/beta","https://x.test/alpha"]

The start page need not be first in urls. The outside link is ignored because it has no supplied page, and zeta is not reachable.

Constraints

1 ≤ urls.length ≤ 5,000.
links.length = urls.length.
Every value in urls is a unique normalized absolute HTTP or HTTPS URL.
startUrl appears exactly once in urls.
Every entry in links is a normalized absolute HTTP or HTTPS URL and may be absent from urls.
The total number of entries across all links[i] is at most 100,000.
URL equality is exact and case-sensitive; no redirects, fragments, or additional canonicalization are performed.