PracHub
QuestionsPremiumLearningGuidesInterview PrepNEWCoaches

Quick Overview

This question evaluates proficiency in graph algorithms and traversal (shortest-path/BFS and cycle handling), file-path/tree modeling, dependency graph reasoning, and ordering impacts across service producers and consumers.

  • medium
  • LinkedIn
  • Coding & Algorithms
  • Software Engineer

Compute graph distance and impacted services

Company: LinkedIn

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Part A — Graph shortest distance (BFS) You are given an interface representing a node in an unweighted graph: ```java interface Candidate { String id(); List<Candidate> getConnections(); } ``` Implement: ```java int getDistance(Candidate c1, Candidate c2) ``` where `getDistance` returns the length of the shortest path (minimum number of edges) between `c1` and `c2` using the `getConnections()` adjacency list. ### Requirements - Treat connections as edges in an unweighted graph. - Return `0` if `c1` and `c2` are the same node. - Return `-1` if `c2` is unreachable from `c1`. - Avoid infinite loops in the presence of cycles. ### Follow-up (discussion only) If this needs to run in production at large scale (very large graph, frequent queries), discuss how you would optimize and/or redesign the solution (data structures, precomputation, caching, storage, distributed concerns). --- ## Part B — Find services impacted by deleted paths + dependency propagation You are given a JSON-like config mapping service name → I/O paths: ```json { "svcA": {"read_from": "/path123", "write_to": "/path456"}, "svcB": {"read_from": "/path456", "write_to": "/path789"} } ``` You are also given a list of deleted paths: ```text deleted_list = ["/path123", "/path12", ...] ``` ### Task 1 — Directly impacted services Return all services that are impacted by the deletions. A service is **directly impacted** if either its `read_from` or `write_to` is affected by `deleted_list`. ### Task 2 — Directory-tree (subtree) impact rule In addition to exact matches, apply this rule: - If a service’s `read_from` or `write_to` path shares a **common parent directory** with a deleted path, treat it as impacted. - Model paths as a file tree and include **only the affected subtree(s)**; do **not** include sibling subtrees that share a higher-level ancestor. (You should clearly define what you consider the “affected subtree root” and implement consistently, e.g., based on nearest common parent directories / minimal affected roots.) ### Task 3 — Propagate impact through service dependencies (ordered output) Services form a dependency chain via produced/consumed paths: - If service `X.write_to == Y.read_from`, then `Y` depends on `X` (data flows from `X` → `Y`). - If an upstream service is impacted, all downstream dependents are impacted transitively. For each entry in `deleted_list`, output the impacted services **in dependency order** (from upstream producers to downstream consumers). If multiple services are impacted independently, output them in a valid topological order. ### Notes - You may assume `read_from` and `write_to` are single paths per service. - Paths are UNIX-like strings with `/` separators. - The dependency graph may be a chain or a DAG; handle general cases unless otherwise stated.

Quick Answer: This question evaluates proficiency in graph algorithms and traversal (shortest-path/BFS and cycle handling), file-path/tree modeling, dependency graph reasoning, and ordering impacts across service producers and consumers.

Part 1: Shortest Distance in an Unweighted Graph

Given a graph as an adjacency list `graph`, return the length of the shortest path from `start` to `target` using the directed edges listed in `graph`. Return `0` if `start` and `target` are the same node, and `-1` if `target` is unreachable. The graph may contain cycles.

Constraints

  • 0 <= number of nodes <= 10^5
  • 0 <= total number of edges <= 2 * 10^5
  • Node ids are strings
  • The graph may contain cycles
  • Nodes with no outgoing edges may be omitted from `graph` or mapped to an empty list

Examples

Input: ({'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}, 'A', 'D')

Expected Output: 2

Explanation: There are two shortest paths, `A -> B -> D` and `A -> C -> D`, both with length 2.

Input: ({'A': ['B'], 'B': ['C'], 'C': ['A'], 'D': []}, 'A', 'D')

Expected Output: -1

Explanation: The graph has a cycle among `A, B, C`, but `D` is unreachable.

Input: ({}, 'X', 'X')

Expected Output: 0

Explanation: The start and target are the same node, so the distance is 0.

Input: ({'A': ['B'], 'B': []}, 'A', 'C')

Expected Output: -1

Explanation: Node `C` is never reached from `A`.

Hints

  1. In an unweighted graph, breadth-first search explores nodes in increasing distance order.
  2. Use a visited set so cycles do not cause infinite loops.

Part 2: Directly Impacted Services by Exact Deleted Paths

You are given service configurations where each service has exactly one `read_from` path and one `write_to` path. A service is directly impacted if either of those paths exactly matches any path in `deleted_list`. Return all impacted service names in lexicographic order.

Constraints

  • 0 <= number of services <= 10^5
  • 0 <= len(deleted_list) <= 10^5
  • Each service name is unique
  • Each service contains both `read_from` and `write_to` keys
  • Paths are UNIX-like absolute strings

Examples

Input: ({'svcA': {'read_from': '/path123', 'write_to': '/path456'}, 'svcB': {'read_from': '/path456', 'write_to': '/path789'}}, ['/path123'])

Expected Output: ['svcA']

Explanation: Only `svcA` reads from `/path123`.

Input: ({'svcA': {'read_from': '/path123', 'write_to': '/path456'}, 'svcB': {'read_from': '/path456', 'write_to': '/path789'}}, ['/path456'])

Expected Output: ['svcA', 'svcB']

Explanation: `svcA` writes to `/path456` and `svcB` reads from it.

Input: ({'svcA': {'read_from': '/path1', 'write_to': '/path2'}, 'svcB': {'read_from': '/path3', 'write_to': '/path4'}}, ['/missing'])

Expected Output: []

Explanation: No service uses `/missing` exactly.

Input: ({'svcA': {'read_from': '/path1', 'write_to': '/path2'}}, [])

Expected Output: []

Explanation: With no deleted paths, nothing is impacted.

Hints

  1. Checking membership in a set is much faster than checking membership in a list repeatedly.
  2. The result order should be deterministic, so sort the impacted service names before returning.

Part 3: Impacted Services Using Directory-Tree Subtree Rules

You are given service configurations and a list of deleted paths. For each deleted path, define its affected subtree root as the parent directory of that deleted path; for the special path `/`, the affected subtree root is `/` itself. Normalize paths by removing trailing slashes except for `/`. Combine all affected subtree roots and keep only minimal roots: if one root is already contained inside another kept root, discard the deeper root. A service is impacted if either its `read_from` or `write_to` path lies inside any minimal affected subtree root. Return impacted service names in lexicographic order.

Constraints

  • 0 <= number of services <= 10^4
  • 0 <= len(deleted_list) <= 10^4
  • Paths are absolute UNIX-like strings beginning with `/`
  • Ignore trailing slashes except for the root path `/`
  • Each deleted path is either `/` or has at least one non-root parent directory

Examples

Input: ({'svcA': {'read_from': '/data/team1/input.csv', 'write_to': '/tmp/a'}, 'svcB': {'read_from': '/data/team2/input.csv', 'write_to': '/tmp/b'}, 'svcC': {'read_from': '/x', 'write_to': '/data/team1/archive/out.txt'}}, ['/data/team1/deleted.txt'])

Expected Output: ['svcA', 'svcC']

Explanation: The deleted path has parent `/data/team1`, so everything in that subtree is impacted.

Input: ({'svcA': {'read_from': '/logs/app1/in.log', 'write_to': '/out1'}, 'svcB': {'read_from': '/logs/app2/in.log', 'write_to': '/out2'}, 'svcC': {'read_from': '/misc', 'write_to': '/logs/app1/sub/out.log'}}, ['/logs/app1/error.log'])

Expected Output: ['svcA', 'svcC']

Explanation: Only the `/logs/app1` subtree is affected, not sibling subtree `/logs/app2`.

Input: ({'svcA': {'read_from': '/a/b/file1', 'write_to': '/x'}, 'svcB': {'read_from': '/a/b/c/file2', 'write_to': '/y'}, 'svcC': {'read_from': '/a/d/file3', 'write_to': '/z'}}, ['/a/b/lost.txt', '/a/b/c/more.txt'])

Expected Output: ['svcA', 'svcB']

Explanation: The roots `/a/b` and `/a/b/c` reduce to the minimal root `/a/b`.

Input: ({'svcA': {'read_from': '/a/x', 'write_to': '/a/y'}, 'svcB': {'read_from': '/b/x', 'write_to': '/b/y'}}, ['/'])

Expected Output: ['svcA', 'svcB']

Explanation: A deletion at `/` affects the whole tree.

Hints

  1. Write small helper functions for path normalization, finding a parent directory, and checking whether one path lies inside another subtree.
  2. If one affected root is already under another affected root, the deeper one is redundant.

Part 4: Propagate Service Impact Through Dependencies in Topological Order

You are given service configurations where each service has one `read_from` path and one `write_to` path. A service is directly impacted by a deleted path if its `read_from` or `write_to` exactly matches that deleted path. Dependencies are defined by data flow: if `X.write_to == Y.read_from`, then `Y` depends on `X`, so there is a directed edge `X -> Y`. For each deleted path in `deleted_list`, return all impacted services after propagating impact downstream transitively. The output for each deleted path must be a topological ordering of the impacted services. If multiple services are available at the same time, choose the lexicographically smallest one first so the output is deterministic.

Constraints

  • 1 <= number of services <= 2 * 10^4
  • 0 <= len(deleted_list) <= 10^4
  • Each service has exactly one `read_from` and one `write_to` path
  • Service names are unique
  • The dependency graph induced by `write_to -> read_from` is a DAG
  • Deleted paths in `deleted_list` are distinct

Examples

Input: ({'svcA': {'read_from': '/raw', 'write_to': '/mid'}, 'svcB': {'read_from': '/mid', 'write_to': '/out'}, 'svcC': {'read_from': '/out', 'write_to': '/done'}}, ['/mid'])

Expected Output: {'/mid': ['svcA', 'svcB', 'svcC']}

Explanation: `svcA` and `svcB` are directly impacted by `/mid`, and `svcC` is downstream of `svcB`.

Input: ({'svcA': {'read_from': '/src', 'write_to': '/p'}, 'svcB': {'read_from': '/p', 'write_to': '/q'}, 'svcC': {'read_from': '/p', 'write_to': '/r'}, 'svcD': {'read_from': '/q', 'write_to': '/s'}, 'svcE': {'read_from': '/r', 'write_to': '/t'}}, ['/p'])

Expected Output: {'/p': ['svcA', 'svcB', 'svcC', 'svcD', 'svcE']}

Explanation: The impacted subgraph is a DAG with branching. Lexicographic tie-breaking gives a deterministic topological order.

Input: ({'svcX': {'read_from': '/foo', 'write_to': '/bar'}, 'svcY': {'read_from': '/other', 'write_to': '/baz'}}, ['/foo', '/missing'])

Expected Output: {'/foo': ['svcX'], '/missing': []}

Explanation: `/foo` directly impacts only `svcX`, while `/missing` impacts no service.

Input: ({'svcA': {'read_from': '/a', 'write_to': '/b'}}, [])

Expected Output: {}

Explanation: If there are no deleted paths, the result is an empty dictionary.

Hints

  1. First build the service dependency graph from matching `write_to` and `read_from` paths.
  2. For each deleted path, find directly impacted services, do a graph traversal to collect all reachable downstream services, then topologically sort only that impacted subgraph.
Last updated: May 19, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Count Trips From Vehicle Logs - LinkedIn (easy)
  • Design O(1) Randomized Multiset - LinkedIn (easy)
  • Process Mutable Matrix Sum Queries - LinkedIn (medium)
  • Design a Randomized Multiset - LinkedIn (medium)
  • Can You Place N Objects? - LinkedIn (medium)