Frontend School

Expedited Creative Asset Delivery

DSA
hard

Expedited Creative Asset Delivery

Hard
Graph
Shortest Path
Dijkstra
Dynamic Programming
Multi-objective Optimization

Overview

Adobe Creative Cloud empowers millions of users globally, and efficient asset delivery is critical for a seamless experience. Imagine a network of Adobe data centers (nodes) interconnected by various routes (edges). Each route has an associated latency (time) and a usage cost. Some routes might offer faster delivery but at a higher cost. Your task is to optimize asset delivery by finding the fastest path from a source data center to a destination data center, ensuring the total cost of the path does not exceed a specified budget. This problem is crucial for balancing performance with operational expenditure in a large-scale distributed system.

What you need to do / Task

Implement a function findMinTimeWithBudget that determines the minimum possible time to transfer an asset from a source data center to a destination data center, given a maximum budget.

  1. Construct an appropriate graph representation from the given edges.
  2. Design an algorithm that finds the shortest time path while respecting the total cost constraint.
  3. Return the minimum time, or -1 if no such path exists within the given budget.

Input & output

The function signature is findMinTimeWithBudget(n: number, edges: number[][], source: number, destination: number, budget: number): number.

  • n: An integer representing the total number of data centers. Data centers are labeled from 0 to n-1.
  • edges: An array of arrays, where each inner array [u, v, time, cost] represents a directed connection from data center u to data center v.
    • u, v: Integers representing the source and destination data centers of the connection.
    • time: An integer representing the latency (time in milliseconds) to traverse this connection.
    • cost: An integer representing the operational cost to use this connection.
  • source: An integer representing the starting data center.
  • destination: An integer representing the target data center.
  • budget: An integer representing the maximum total operational cost allowed for the entire path.

Return Value: An integer representing the minimum time required to deliver the asset from source to destination within the budget. Return -1 if no such path exists.

Clarifications

  • Self-loops and Parallel Edges: There might be self-loops (u == v) or multiple edges between the same pair of data centers. If multiple edges exist, your algorithm should naturally find the optimal one based on the objective.
  • Path Existence: If no path exists from source to destination that satisfies the budget constraint, return -1.
  • Source equals Destination: If source is the same as destination, the minimum time is 0 and cost is 0.
  • Zero Budget: If budget is 0, only paths with zero total cost are allowed. If an edge has cost=0, it can be used.

Examples

1

Example 1

Input:

n = 3, edges = [[0,1,10,1],[1,2,10,1],[0,2,100,10]], source = 0, destination = 2, budget = 2

Output:

20

Note:

Consider paths from 0 to 2:

  1. Path 0 -> 1 -> 2: Total time = 10 (0->1) + 10 (1->2) = 20. Total cost = 1 (0->1) + 1 (1->2) = 2. This path is within the budget of 2.
  2. Path 0 -> 2: Total time = 100. Total cost = 10. This path exceeds the budget of 2. The minimum time path within budget is 20.
2

Example 2

Input:

n = 2, edges = [[0,1,5,5],[0,1,1,10]], source = 0, destination = 1, budget = 8

Output:

5

Note:

There are two direct paths from 0 to 1:

  1. Path (0,1) with time=5, cost=5. This path is within budget (8).
  2. Path (0,1) with time=1, cost=10. This path exceeds budget (8). The minimum time path within budget is 5.
3

Example 3

Input:

n = 3, edges = [[0,1,10,1],[1,2,10,1],[0,2,100,10]], source = 0, destination = 2, budget = 0

Output:

-1

Note:

With a budget of 0, only paths with a total cost of 0 are allowed. All given edges have a cost of 1 or 10, meaning no path can be formed without exceeding the budget. Thus, no path exists within budget.

Constraints

Constraints & assumptions

  • 1 <= n <= 100
  • 0 <= edges.length <= n * (n - 1)
  • edges[i].length == 4
  • 0 <= u, v < n
  • 1 <= time, cost <= 100
  • 0 <= source, destination < n
  • 0 <= budget <= 1000
  • The solution should aim for optimal time complexity given the constraints.
  • All time and cost values are non-negative.

Out of scope

  • Implementing a custom priority queue from scratch (standard library/language features are acceptable).
  • Handling negative time or cost values (assume they are positive as per constraints).
  • Optimizing for memory beyond what's reasonable for the given constraints (e.g., N*Budget states are fine).

What interviewers evaluate

  • Algorithmic Correctness: Ability to correctly identify and apply a shortest path algorithm (e.g., Dijkstra's) adapted for dual-weighted edges and a budget constraint.
  • Data Structure Proficiency: Effective use of adjacency lists for graph representation and a priority queue for efficient state management.
  • Edge Case Handling: Correctly managing scenarios like no path found, source equals destination, and zero budget.
  • Code Quality & Readability: Clean, well-structured, and commented code that demonstrates an understanding of best practices.

Loading editor...