Frontend School

Metadata Deployment Order

DSA
medium

Metadata Deployment Order

Medium
Graph
Topological Sort
Dependency Resolution

Overview

In Salesforce, managing and deploying metadata components (like Apex classes, custom objects, or Lightning Web Components) is a critical task. These components often have intricate dependencies: for example, an Apex class might depend on a custom object, or a Lightning Web Component might depend on another shared component. To ensure a successful deployment, components must be deployed in a specific order, respecting their dependencies. If a circular dependency exists, deployment becomes impossible.

What you need to do / Task

You are tasked with writing a function that, given a list of metadata components and their dependencies, determines a valid order in which they should be deployed. If a valid order exists, return one such order. If a circular dependency makes deployment impossible, return an empty array.

Input & output

Your function getDeploymentOrder will accept two parameters:

  • components: An array of strings, where each string is the unique name of a metadata component available for deployment.
  • dependencies: An array of [dependent, dependency] string pairs. Each pair signifies that the dependent component requires the dependency component to be deployed first. For example, ["MyApexClass", "MyCustomObject__c"] means MyApexClass depends on MyCustomObject__c.

Your function should return:

  • string[]: An array of component names representing a valid deployment order. If multiple valid orders exist, any one is acceptable.
  • []: An empty array if a circular dependency is detected, making a valid deployment order impossible.

Clarifications

  • Empty Inputs: If components is empty, an empty array should be returned. If dependencies is empty, any order of the components list is valid.
  • Component Uniqueness: All component names in components are unique.
  • Dependency Validity: Assume all component names mentioned in dependencies are valid and either present in the components list or are implicitly known components that could exist. You do not need to handle cases where a dependent or dependency string is entirely unknown/invalid outside the context of the components list.
  • Order Ambiguity: If multiple topological sorts are possible, any one of them is considered a correct answer.

Examples

1

Example 1

Input:

components = ["CustomObject__c", "ApexClass", "LWCComponent", "PermissionSet"], dependencies = [["ApexClass", "CustomObject__c"], ["LWCComponent", "ApexClass"], ["PermissionSet", "ApexClass"], ["PermissionSet", "CustomObject__c"]]

Output:

["CustomObject__c","ApexClass","LWCComponent","PermissionSet"]

Note:

CustomObject__c has no dependencies. ApexClass depends on CustomObject__c. LWCComponent depends on ApexClass. PermissionSet depends on both ApexClass and CustomObject__c. A valid order ensures dependencies are met.

2

Example 2

Input:

components = ["Report", "Dashboard", "Folder"], dependencies = []

Output:

["Report","Dashboard","Folder"]

Note:

No dependencies exist, so any order of the components is valid. The example output is one such valid permutation.

3

Example 3

Input:

components = ["Flow", "Trigger", "ValidationRule"], dependencies = [["Trigger", "Flow"], ["ValidationRule", "Trigger"], ["Flow", "ValidationRule"]]

Output:

[]

Note:

Flow depends on ValidationRule, ValidationRule depends on Trigger, and Trigger depends on Flow. This forms a circular dependency (Flow -> ValidationRule -> Trigger -> Flow), making a valid deployment order impossible.

Constraints

Constraints & assumptions

  • 1 <= components.length <= 1000
  • 0 <= dependencies.length <= 5000
  • Each component name is a string of alphanumeric characters, up to 50 characters long.
  • No component will depend on itself (e.g., ["A", "A"] will not appear in dependencies).
  • All components mentioned in dependencies will also be present in the components list.

Out of scope

  • Detailed error messages for invalid inputs (e.g., duplicate component names, malformed dependency strings).
  • Optimizing for specific deployment tool performance characteristics beyond algorithmic complexity.

What interviewers evaluate

  • Correctly modeling component dependencies as a graph structure.
  • Accurate implementation of a topological sort algorithm (e.g., Kahn's algorithm or DFS-based).
  • Robust handling and detection of cyclic dependencies, returning an empty array when cycles are present.
  • Efficiency of the solution in terms of time and space complexity for the given constraints.

Loading editor...