Frontend School

Data Center Drone Path Optimization

DSA
hard

Data Center Drone Path Optimization

Hard
Dynamic Programming
2D DP
Grid
Pathfinding

Overview

Apple's global data centers rely on efficient maintenance routines to ensure peak performance and reliability. Imagine a new generation of autonomous drones tasked with optimizing server maintenance. These drones traverse a grid of servers, collecting critical system data while adhering to strict power budgets. Your task is to develop an algorithm that helps a drone maximize the total 'criticality score' of collected data packets, given its limited processing budget and the various costs associated with each server.

This problem requires careful state management and optimization, reflecting the kind of complex resource allocation challenges faced in large-scale infrastructure management.

What you need to do / Task

Implement the function maxCriticalityPath which calculates the maximum total criticality score a drone can collect by traversing a grid of servers from the top-left corner (0, 0) to the bottom-right corner (R-1, C-1). The drone can move in three directions:

  1. Down: From (r, c) to (r+1, c)
  2. Right: From (r, c) to (r, c+1)
  3. Diagonal (Down-Right): From (r, c) to (r+1, c+1)

When the drone visits a server at (r, c), it collects its criticalityScore and incurs its processingCost. The drone has a maxBudget for processing power. It cannot visit a server if doing so would cause its total processing cost to exceed maxBudget.

Your solution should return the maximum possible total criticality score. If no valid path exists to the destination within the given budget, return -1.

Input & output

Function Signature:

function maxCriticalityPath(criticalityScores: number[][], processingCosts: number[][], maxBudget: number): number

Input Parameters:

  • criticalityScores: A 2D array (matrix) of numbers, where criticalityScores[r][c] represents the criticality score obtained from visiting the server at row r and column c.
  • processingCosts: A 2D array (matrix) of numbers, where processingCosts[r][c] represents the processing power consumed when visiting the server at row r and column c.
  • maxBudget: A number representing the maximum total processing power the drone can expend.

Output:

  • A number representing the maximum total criticality score collected. Returns -1 if no valid path to (R-1, C-1) exists within maxBudget.

Examples

1

Example 1

Input:

criticalityScores = [[10, 5], [1, 20]], processingCosts = [[1, 2], [3, 4]], maxBudget = 10

Output:

35

Note:

The optimal path is (0,0) -> (0,1) -> (1,1). Scores: 10 + 5 + 20 = 35. Costs: 1 + 2 + 4 = 7. Total cost 7 <= maxBudget 10.

2

Example 2

Input:

criticalityScores = [[10, 100], [1, 5]], processingCosts = [[1, 20], [3, 1]], maxBudget = 5

Output:

16

Note:

The optimal path is (0,0) -> (1,0) -> (1,1). Scores: 10 + 1 + 5 = 16. Costs: 1 + 3 + 1 = 5. Total cost 5 <= maxBudget 5. (0,0) -> (0,1) is not possible because (0,1) costs 20, exceeding the remaining budget (5-1=4).

3

Example 3

Input:

criticalityScores = [[10, 100], [1, 5]], processingCosts = [[100, 20], [3, 1]], maxBudget = 5

Output:

-1

Note:

The drone cannot even start at (0,0) as its processing cost (100) exceeds the maxBudget (5). No valid path exists.

Constraints

Constraints & assumptions

  • 1 <= R, C <= 50 (where R is the number of rows and C is the number of columns).
  • 0 <= criticalityScores[r][c] <= 100 for all r, c.
  • 0 <= processingCosts[r][c] <= 100 for all r, c.
  • 0 <= maxBudget <= 5000.
  • criticalityScores and processingCosts will always have R rows and C columns.

Out of scope

  • Path reconstruction (you only need to return the maximum score).
  • Multiple drones or dynamic grid changes.
  • Optimizing for other metrics (e.g., minimum path length).

What interviewers evaluate

  • Dynamic Programming State Definition: Clarity and correctness in defining the DP state to capture necessary information (position and budget).
  • Transition Logic: Accurate implementation of DP transitions considering all three movement types and the budget constraint.
  • Base Cases and Initialization: Proper handling of the starting cell and initialization of the DP table.
  • Edge Cases: Correct behavior for scenarios like an unreachable destination or a zero budget.
  • Time and Space Complexity: Optimal solution within the given constraints (O(R * C * maxBudget) time and space).

Loading editor...