A release engineer is rolling out a platform built from $N$ microservices, numbered $1$ through $N$. The deployment tooling can push exactly **one service at a time**, so the whole rollout is a sequence in which every service appears exactly once. The architecture imposes $M$ **dependency rules**. Rule $i$ is a pair $(u_i, v_i)$ meaning service $u_i$ must already be running before service $v_i$ may be deployed. A deployment order is **valid** if it respects every rule. The dependency graph is guaranteed to be acyclic, so at least one valid order always exists - but usually there are many. To keep rollouts reproducible, the team adopted a tie-breaking policy: among all valid deployment orders, always use the **lexicographically smallest** one. An order $a_1, a_2, \ldots, a_N$ is lexicographically smaller than $b_1, b_2, \ldots, b_N$ if at the first position where they differ, the service number in $a$ is smaller. Compute the deployment order the team must use. ### Function Description Complete the function `deploymentOrder` provided in the editor. The function receives the following parameters: | Parameter | Type | Description | |---|---|---| | $N$ | integer | number of microservices, labelled $1..N$ | | $M$ | integer | number of dependency rules | | $edges$ | array of $M$ pairs of integers | rule $(u, v)$: service $u$ must be deployed before service $v$ | The function must return an array of $N$ integers - the lexicographically smallest valid deployment order. ### Input Format - The first line contains two space-separated integers $N$ and $M$. - Each of the next $M$ lines contains two space-separated integers $u$ and $v$, one dependency rule. ### Output Format Print the $N$ service numbers of the chosen deployment order on a single line, separated by single spaces. ### Notes - The tie-break is **global and lexicographic**: at every step you must deploy the smallest-numbered service whose prerequisites are all already deployed. Greedily printing $1, 2, \ldots, N$ is wrong whenever a small-numbered service is still blocked. - The dependency graph is guaranteed to be a DAG (no cyclic dependencies), so an answer always exists and is unique. - Services with no rules touching them can be deployed at any time; the tie-break decides when.

Interview Questions/Coding/Deployment Pipeline Order

Deployment Pipeline Order

Preview mode. Log in to edit, run, submit, and save progress.

Medium

Deployment Pipeline Order

A release engineer is rolling out a platform built from $N$ microservices, numbered $1$ through $N$. The deployment tooling can push exactly one service at a time, so the whole rollout is a sequence in which every service appears exactly once. The architecture imposes $M$ dependency rules. Rule $i$ is a pair $(u_i, v_i)$ meaning service $u_i$ must already be running before service $v_i$ may be deployed. A deployment order is valid if it respects every rule. The dependency graph is guaranteed to be acyclic, so at least one valid order always exists - but usually there are many. To keep rollouts reproducible, the team adopted a tie-breaking policy: among all valid deployment orders, always use the lexicographically smallest one. An order $a_1, a_2, \ldots, a_N$ is lexicographically smaller than $b_1, b_2, \ldots, b_N$ if at the first position where they differ, the service number in $a$ is smaller. Compute the deployment order the team must use. ### Function Description Complete the function `deploymentOrder` provided in the editor. The function receives the following parameters:

Parameter	Type	Description
$N$	integer	number of microservices, labelled $1..N$
$M$	integer	number of dependency rules
$edges$	array of $M$ pairs of integers	rule $(u, v)$: service $u$ must be deployed before service $v$

The function must return an array of $N$ integers - the lexicographically smallest valid deployment order. ### Input Format - The first line contains two space-separated integers $N$ and $M$. - Each of the next $M$ lines contains two space-separated integers $u$ and $v$, one dependency rule. ### Output Format Print the $N$ service numbers of the chosen deployment order on a single line, separated by single spaces. ### Notes - The tie-break is global and lexicographic: at every step you must deploy the smallest-numbered service whose prerequisites are all already deployed. Greedily printing $1, 2, \ldots, N$ is wrong whenever a small-numbered service is still blocked. - The dependency graph is guaranteed to be a DAG (no cyclic dependencies), so an answer always exists and is unique. - Services with no rules touching them can be deployed at any time; the tie-break decides when.

Examples

Example 1

Input:

```text
4 3
3 1
4 2
3 4
```

Output:

```text

Explanation: Service $1$ waits on $3$, service $2$ waits on $4$, and service $4$ waits on $3$. At the start only service $3$ is deployable, so the order begins with $3$ even though $1$ has a smaller number. Deploying $3$ unblocks $1$ and $4$; the smaller choice is $1$. Then $4$ is deployed, which unblocks $2$. The result is $3\ 1\ 4\ 2$. Orders such as $3\ 4\ 1\ 2$ are also valid but lexicographically larger, because at the second position $4 > 1$.

Approach hint

Model the services as nodes of a directed graph with an edge $u \to v$ for each rule. Which services are safe to deploy at any given moment? Think about how many unmet prerequisites each service has.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

Input

```text
4 3
3 1
4 2
3 4
```

Output

```text