Fewest Page Fetches
MediumGraphs ยท Ramp
responses[url] lists the results of that page's successive fetches: each 503 is a failed fetch, and a list of URLs is a successful fetch giving the page's links. A page can be fetched at most max_retries + 1 times. It is usable only if a list arrives within that limit; a page with no list, or a URL missing from responses, is unusable.
Starting at start, follow links between usable pages. Return the fewest total fetches, failed ones included, needed to reach and successfully fetch exit_url, counting every page on the route, or -1 if it cannot be reached.
Example 1
- Input:
- responses = {"home": [503, ["a", "b"]], "a": [503, 503, ["goal"]], "b": [["c"]], "c": [["goal"]], "goal": [[]]}, start = "home", exit_url = "goal", max_retries = 2
- Output:
- 5
- Explanation
- Going home, a, goal costs 2 + 3 + 1 = 6 fetches. Going home, b, c, goal costs 2 + 1 + 1 + 1 = 5.
Example 2
- Input:
- responses = {"s": [["t"]], "t": [503, 503, 503, ["e"]], "e": [[]]}, start = "s", exit_url = "e", max_retries = 2
- Output:
- -1
- Explanation
- Page
twould need 4 fetches but only 3 are allowed.
Example 3
- Input:
- responses = {"p": [503, []]}, start = "p", exit_url = "p", max_retries = 1
- Output:
- 2
Constraints
1 <= responses.length <= 20001 <= responses[url].length <= 21and0 <= max_retries <= 20- The total number of links across all pages is at most
10^4 - URLs are non-empty strings of at most 30 characters; links may point to URLs missing from
responses