You are given a list of service definitions describing a directed acyclic graph (DAG) of microservices. Each definition has the format <service_name>=<dep1>,<dep2>,... (services with no dependencies appear as <service_name>=). One service is designated as the entrypoint. When the entrypoint receives 1 unit of load, it triggers all its dependencies, which in turn trigger their own dependencies, and so on. If multiple dependency paths lead to the same service, the loads accumulate (e.g., if service D is reachable via both B and C, and B and C each carry load 1, then D carries load 2). Dependencies that are not explicitly defined in the list should be ignored. Compute the load factor for every service reachable from the entrypoint (including the entrypoint itself, which has load 1). Return results as an array of strings formatted as <service_name>*<load_factor>, sorted lexicographically by service name. Only include reachable services.
Alternate framing (also seen): given a 2D array prerequisites where [a, b] means program a depends on program b, compute for each program the total number of unique programs that directly or indirectly depend on it (i.e., in-degree count / reverse load). Return as a map from program name to load factor; ignore prerequisite entries that involve programs not in the initial program list.
Example (forward load): Entry E, edges E→A→B→C, E→D→B→C. Load: E=1, A=1, D=1, B=2, C=2. Example (reverse load): programs=[A,B,C,D], prerequisites=[[A,B],[B,C],[A,C],[D,C],[E,A]]. Output: {A:0, B:1, C:3, D:0} (E is ignored as not in programs list).
Where is there repeated work? Can you optimize this?
You mentioned topological sort — go ahead and implement it
What is the time and space complexity?
How do you handle dependencies not defined in the input list / programs not in the initial list?
| Approach | Notes |
|---|---|
| Naive DFS (no memoization) | Simple to implement; correctly counts total traversals per node but revisits nodes multiple times, leading to exponential time in dense DAGs. Interviewer will typically ask for an optimization after this. |
| Memoized DFS / DP on DAG | Add a cache so each node's load is computed once. Achieves O(V+E) but requires care about when a node's full load is finalized (all parents must be processed first). Can be trickier to reason about than explicit topological sort. |
| BFS Topological Sort (Kahn's algorithm) | Process nodes in topological order using in-degree counts and a queue; propagate load to children as each node is dequeued. Clean and iterative; preferred by interviewers as the 'optimized' solution. |
Common mistakes: Using naive DFS without memoization and not proactively offering the optimization; Failing to handle Java's String.split() regex special character | — must use \\| or Pattern.quote("|"); Not handling prerequisites/dependencies involving undefined programs (failing to filter them out before building the graph); Including unreachable (disconnected) nodes in the output; Spending too much time on code design/OOD rather than getting working code first; Not being able to implement topological sort cleanly under time pressure after proposing it verbally; Forgetting to include the entrypoint itself in the result
Interviewer hints: After DFS solution: 'Is there any repeated work that can be eliminated?' / 'Can you improve this?'; 'You mentioned topological sort earlier — why don't you try implementing that?'; 'I believe you can add memoization — no need to implement it now' (letting candidate move on); Interviewer helped candidate debug during the interview when candidate was stuck (but candidate still failed); 'You've already passed the interview' (said after candidate proposed topo sort, allowing relaxed implementation)
What passers do: Mentioning both DFS and topological sort as options during initial problem discussion, then implementing at least one correctly; Implementing working DFS first, then proactively identifying the memoization/topo-sort optimization when prompted; Explicitly verbalizing complexity analysis (O(V+E) for topo sort); Handling edge cases (undefined deps, disconnected nodes) without being prompted; Prioritizing a working solution over perfect OOD design, then refactoring
Why people fail: Getting stuck on Java string parsing (pipe delimiter regex) and running out of time; Not being able to debug without print statements (CoderPad print() not outputting to terminal); Implementing topological sort with bugs and not having time to fix them; Not filtering out programs/services not in the initial list, causing wrong answers on edge case test cases; Spending too much time on class design instead of producing working code
Edge cases probed: Services/programs listed in prerequisites but not in the main input list — should be ignored; Services with no dependencies (leaf nodes with empty dep list, e.g., logging=); Multiple paths converging on the same node — loads must be summed, not taken as max; Disconnected nodes not reachable from entrypoint — should be excluded from output; Input delimiter parsing: pipe character | is a regex special character in Java's String.split() and must be escaped; Ambiguous or inconsistent test case format in the problem statement vs. example; Entry point node itself must be included in output with load factor 1
What you just read — canonical solution, follow-up arc, what passing candidates actually did — exists for all 46 Robinhood questions, refreshed monthly from new candidate reports.