Katkat
Back

Fewest Link Clicks Between Two Wiki Pages, Then Scale the Search

SnowflakeSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Find the fewest link clicks between two wiki pages when each page's links come from a slow fetch call, returning the path. Follow-ups cover parallel level-by-level search, bidirectional search with a correct stopping rule, and caching fetched link lists across searches.

On a wiki, every page links to other pages. Given a start page and a target page, find the fewest link clicks needed to get from the start to the target, and the pages along the way. The interview then pushed on speed: run the search in parallel, search from both ends at once, and cache what has been fetched.

Assume a helper that fetches a page and returns the titles it links to:

get_links(title: str) -> list[str] # a network call; slow compared with local work

start = "Coffee", target = "Philosophy"
Coffee -> Caffeine -> Chemistry -> Philosophy # 3 clicks

Constraints

  • The wiki has about a billion pages, and a breadth-first search fans out enormously from one level to the next. The search must cut the work needed to build a shortest path, and the visited set and parent records must still work at that size.

Clarifying Questions

  • Should the answer be the number of clicks, one shortest path, or every shortest path?
  • What should be returned when the target cannot be reached?
  • Is there a way to list the pages that link to a given page, or only the links out of it?
  • Can two titles refer to the same page, for example through redirects or different capitalization?
  • How many requests per second may the search send, and is there a limit on the total number of pages fetched?

Part 1 — Fewest clicks

Implement fewest_clicks(start, target) returning a shortest path as a list of titles.

What This Part Should Cover

  • The search, the visited set and how the path is rebuilt
  • Correctness: why the first path found is a shortest one
  • Cost in fetched pages, and the start-equals-target and unreachable cases

Part 2 — Parallel search

Each get_links call takes a noticeable amount of time. Speed up the search by fetching many pages at once.

What This Part Should Cover

  • How fetches are issued concurrently while keeping shortest-path correctness
  • Shared state: the visited set and parent pointers under concurrency
  • Bounding concurrency, handling failed fetches, and stopping early

Part 3 — Search from both ends

Search forward from the start and backward from the target at the same time.

What This Part Should Cover

  • What the backward search needs and how it gets it
  • When the two searches have met, and how to confirm the path is shortest
  • Which side to expand next

Part 4 — Caching

Many searches run over time. Add caching.

What This Part Should Cover

  • What is cached and for how long
  • How the cache is shared between concurrent searches
  • Memory bounds and invalidation when pages change

Hints

Hint 1

Every click is one level: Think about which search order guarantees that the first time you reach the target, no shorter route exists.

Hint 2

Keep the levels: Ask what must still be true about the order in which pages are expanded for the answer to stay shortest.

Hint 3

Two smaller balls: Compare how many pages a search of depth d touches with two searches of depth d/2, and what the backward search needs from the wiki.

Hint 4

What is worth keeping: Decide which results are reused across searches and how stale they may become.

Follow-up questions

  • Pages change while a search is running. Does that matter for the answer you return?
  • Return every shortest path instead of one. What changes in the bookkeeping?
  • Only a fixed number of fetches is allowed per search. How do you spend them?
  • The search runs on many machines. How do they share the frontier and the visited set?
  • `get_links` is a call to a remote service, and a network partition cuts the search off from it, briefly or for a long time. How do timeouts and retries work, how does the result stay truthful when some pages could not be expanded, and how does the search pause and resume?
  • Across a graph of about a billion pages, many paths may connect the start and the target. How do you optimize further in that case?