Frontend School

Dynamic Content Propagation with Hop Constraints

DSA
hard

Dynamic Content Propagation with Hop Constraints

Hard
Graph
Shortest Path
Dynamic Programming
Bellman-Ford

Overview

In Sharechat's vast social network, content needs to propagate efficiently from creators to users. However, simply reaching a user isn't enough; the 'cost' or 'latency' of propagation through various intermediary nodes (e.g., re-shares, algorithmic boosts) can vary. Furthermore, content often has a 'shelf life' or a maximum 'viral distance' it can travel before losing relevance, implying a limit on the number of hops it can take. This problem challenges you to find the most efficient propagation path under such constraints.

What you need to do / Task

Given a directed graph representing a social network where nodes are users and edges represent potential content propagation channels (e.g., A shares to B), each with an associated latency. You need to find the minimum total latency for content to travel from a source user to a target user, adhering to a strict limit on the maximum number of hops (edges) the content can traverse.

Implement the function findMinPropagationLatency that takes the network details, source, target, and maximum hops, and returns the minimum total latency. If no path exists within the given maxHops, return -1.

Input & output

Function Signature:

function findMinPropagationLatency(n: number, edges: number[][], source: number, target: number, maxHops: number): number
  • n: An integer representing the total number of users (nodes) in the network, indexed from 0 to n-1.
  • edges: An array of arrays, where each inner array [u, v, latency] represents a directed edge from user u to user v with a propagation latency (cost).
  • source: An integer representing the starting user's ID.
  • target: An integer representing the destination user's ID.
  • maxHops: An integer representing the maximum number of edges allowed in the propagation path.
  • Returns: The minimum total latency as a number. Return -1 if the target user cannot be reached from the source user within maxHops.

Clarifications

  • Self-loops and parallel edges: The graph may contain self-loops (u == v) or multiple edges between the same pair of nodes. If multiple edges exist, content can only use one at a time, but the algorithm should consider all options.
  • Source equals Target: If source is the same as target, the latency is 0 if maxHops >= 0. This counts as 0 hops.
  • Disconnected graph: The graph may not be fully connected. If target is unreachable, return -1.
  • Edge latencies: All latency values are non-negative integers.
  • Node IDs: Users are identified by integers from 0 to n-1.

Examples

1

Example 1

Input:

n = 3, edges = [[0,1,10],[1,2,20],[0,2,5]], source = 0, target = 2, maxHops = 1

Output:

5

Note:

From user 0 to 2:

  • Path 0 -> 2 has latency 5 and 1 hop. This is within maxHops = 1.
  • Path 0 -> 1 -> 2 has latency 10 + 20 = 30 and 2 hops. This exceeds maxHops = 1. The minimum latency within 1 hop is 5.
2

Example 2

Input:

n = 4, edges = [[0,1,1],[0,2,5],[1,3,1],[2,3,1]], source = 0, target = 3, maxHops = 2

Output:

2

Note:

From user 0 to 3:

  • Path 0 -> 1 -> 3: Latency 1 + 1 = 2, Hops = 2. This is within maxHops = 2.
  • Path 0 -> 2 -> 3: Latency 5 + 1 = 6, Hops = 2. This is within maxHops = 2. The minimum latency within 2 hops is 2.
3

Example 3

Input:

n = 3, edges = [[0,1,10],[1,2,20]], source = 0, target = 2, maxHops = 1

Output:

-1

Note:

From user 0 to 2:

  • Path 0 -> 1 -> 2: Latency 10 + 20 = 30, Hops = 2. This exceeds maxHops = 1. There is no path from 0 to 2 within 1 hop. So, return -1.
4

Example 4

Input:

n = 2, edges = [[0,1,10]], source = 0, target = 0, maxHops = 0

Output:

0

Note:

Source is target, 0 hops, latency is 0. This is allowed by maxHops = 0.

Constraints

Constraints & assumptions

  • 1 <= n <= 1000
  • 0 <= edges.length <= 10000
  • edges[i].length == 3
  • 0 <= u, v < n
  • 1 <= latency <= 1000 (for each edge)
  • 0 <= source, target < n
  • 0 <= maxHops < n
  • The graph is directed.

Out of scope

  • Handling negative edge latencies (all latencies are positive).
  • Dynamic graph updates; the network structure is static during the calculation.
  • Optimizing for multiple source/target pairs simultaneously.

What interviewers evaluate

  • Correctness: The solution accurately calculates the minimum latency under hop constraints for all valid inputs and edge cases.
  • Efficiency: The algorithm demonstrates optimal time and space complexity for the given constraints.
  • Code Quality: The code is well-structured, readable, and uses appropriate data structures.
  • Edge Case Handling: Correctly handles scenarios like source == target, unreachable targets, or maxHops = 0.

Loading editor...