LinkedIn·Software Engineer·Technical Phone Screen·Senior

Senior

Jun 2026

Summary

LinkedIn system design question focused on dependency propagation across services. Pretty niche problem, the kind where you either see it immediately or you're drawing boxes on a whiteboard hoping something clicks.

Questions Asked (1)

Given a set of services where each service declares what data it reads from and writes to, forming a producer-consumer dependency chain, and given a list of deleted data paths, identify all affected services in propagation order (i.e., transitively downstream from each deleted path).

Algorithms & Data StructuresSystem DesignData Modeling

Author's notes

I knew this was a graph traversal problem pretty fast, but I fumbled on the transitive part for longer than I'd like to admit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the services and their data dependencies as a directed graph where nodes are services and edges represent data flow from producer to consumer. Then, for each deleted data path, identify the services that directly read or write that path and perform a BFS/DFS to find all transitively affected services, ensuring the output is in topological order of propagation.

Pro tip: Clarify whether the propagation should consider only direct dependencies or also indirect ones through multiple hops, and mention that you would handle cycles gracefully (e.g., by detecting and breaking them or reporting them as errors) to avoid infinite loops.

1. Parse and model dependencies

Extract each service's read and write data paths and build a directed graph where an edge from service A to service B exists if A writes data that B reads.

2. Identify initial affected services

For each deleted data path, find all services that directly read from or write to that path; these are the starting points for propagation.

3. Propagate impact transitively

Perform a graph traversal (BFS or DFS) from the initial affected services, following edges in the direction of data flow, to collect all downstream services.

4. Order by propagation

Ensure the affected services are listed in the order they are reached during traversal, which naturally reflects the propagation order (e.g., using BFS levels or topological sort).

5. Handle edge cases and validate

Consider cycles, multiple deleted paths, and services that both read and write the same path; deduplicate services and verify the result against the dependency graph.

Key Points to Mention

Graph representation: services as nodes, data dependencies as directed edges.
Transitive closure or reachability analysis to find all downstream services.
Topological ordering or BFS levels to ensure propagation order.
Cycle detection to prevent infinite loops in traversal.
Handling multiple deleted paths and merging results without duplicates.
Time and space complexity: O(V+E) for graph traversal, where V is number of services and E is number of dependencies.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.