Exploring a friend network through a restricted API with as few calls as possible

A social product stores friendships between users, but you cannot read the graph directly. The only access is a remote API: ```python def get_friends(user_id: str) -> list[str]: """Return the IDs of the users who are friends with user_id.""" ``` Each call is a network round trip, and the API has a usage restriction. On a whiteboard, discuss how you would find the friend network you need while making as few API calls as possible. For concreteness, assume the goal is to collect every user within `k` friendship hops of a starting user `s`. ### Constraints and Clarifications - The API's exact restriction is not specified; treat it as something to ask about and design for. - Assume friendship is mutual unless told otherwise: if `b` appears in `get_friends(a)`, then `a` appears in `get_friends(b)`. - The result is the set of users within `k` hops of `s`, including `s`; ask whether the friendships among them are also needed. ### Clarifying Questions - What is the restriction: a cap on how many friends one call returns (with pagination), a rate limit, or a total call budget? - Is the goal the neighborhood of one user, or the connection between two specific users? - Do you need only the set of users, or also every friendship edge among them? - Is the relation symmetric, or is it a directed follow graph? - Can results be cached across requests, and how stale may they be? ### Part 1 — Build the network with the fewest calls Describe an exploration strategy, state how many calls it makes in terms of the graph, and argue why it does not waste calls. ```hint Which users must be expanded For a user at a given distance from `s`, ask whether calling the API on them could reveal anyone you still need. ``` #### What This Part Should Cover - A layered exploration with deduplication so no user is fetched twice - An exact statement of which users are called and why users on the outer boundary can be skipped - A call-count argument (what is necessary and what is saved) and how the edge requirement changes it ### Part 2 — Work within the API restriction Explain how your approach changes under the restriction the interviewer names. At minimum, consider a cap on the number of friends returned per call and a limit on the call rate. ```hint Cost is not one call per user Think about how a per-call cap changes the cost of expanding different users. ``` #### What This Part Should Cover - The cost model per user under pagination and its effect on the order of expansion - Rate limiting: pacing, backoff, parallelism within the limit, resumable progress - What to return when a budget is too small for a complete answer ### What a Strong Answer Covers - Clarifies the goal, the symmetry of the relation and the restriction before designing - A correct exploration that never calls the same user twice and skips calls that cannot add information - A clear call-count analysis with a lower-bound argument - Practical handling of pagination, rate limits and budgets, including caching and failure recovery ### Follow-up Questions - The goal changes to finding a shortest friendship path between two given users. How do you minimize calls? - Some users have enormous friend lists. How do you keep them from consuming your budget? - The graph changes while you are exploring it. What does your result mean, and is that acceptable? - Several workers share one global rate limit. How do you coordinate them?