NeetCode #607LC-1236MediumGraphsNC Algo100
← Back to All Problems#607 · #1236 · Web Crawler(网络爬虫)
📌 Problem Statement & Constraints
This is an interactive problem. Given a
startUrl and an HtmlParser with getUrls(url) returning the links on a page, return all URLs reachable from startUrl that share its hostname. Constraints: at most 10^4 URLs; total content at most 10^6 characters.💡 Core Algorithmic Approaches
- A standard BFS/DFS over the link graph, filtered by hostname.
- The hostname is the substring up to the first
/after the protocol; comparing it requires parsing. - Only follow links whose hostname matches the start URL's.
- A visited set prevents infinite loops.
💻 Benchmark Python3 Implementation
class Solution:
def crawl(self, startUrl: str, htmlParser: "HtmlParser") -> List[str]:
from collections import deque
# hostname = everything up to the first '/' after "://"
host = startUrl[:startUrl.find("/", 8)]
seen = {startUrl}
q = deque([startUrl])
while q:
url = q.popleft()
for nxt in htmlParser.getUrls(url):
if nxt not in seen and nxt.startswith(host):
seen.add(nxt)
q.append(nxt)
return list(seen)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(total content + number of URLs): each page is parsed once.
💾 Space Complexity
O(number of URLs) for the visited set and the queue.
⚠️ Interview Pitfalls & Follow-ups
- Using
startswith(startUrl): that filters by path prefix, not hostname;"http://news.yahoo.com"and"http://news.yahoo.com.cn"would be confused. - Extracting the hostname with a naive split:
url.split("/")[2]is the usual approach; thefindvariant used here avoids the leading empty segment. - Forgetting the visited set: cycles would loop forever.
- Parsing the HTML yourself: the
HtmlParserAPI already extracts the links.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.