Task 1 — Dependency Graph Resolution

Objective

Create a function that analyzes dependencies between services.

The function must determine:

• whether the dependency graph is valid
• whether every referenced dependency exists
• whether dependency cycles exist
• a valid startup order when the graph is valid

A service may start only after all of its dependencies have started.

Input Model

Each service has:

ID
Dependencies

A possible representation is:

type Service struct {
    ID           string
    Dependencies []string
}

Input

Use the following services:

services := []Service{
    {
        ID:           "gateway",
        Dependencies: []string{"api"},
    },
    {
        ID:           "api",
        Dependencies: []string{"auth", "database"},
    },
    {
        ID:           "auth",
        Dependencies: []string{"database"},
    },
    {
        ID:           "database",
        Dependencies: []string{},
    },
    {
        ID:           "metrics",
        Dependencies: []string{"api"},
    },
}

Dependency Meaning

For:

gateway -> api

the meaning is:

gateway depends on api

Therefore:

api must start before gateway

For:

api -> database

the database must start before the API.

Expected Startup Relationships

The following relationships must be satisfied:

database before auth
database before api
auth before api
api before gateway
api before metrics

Possible Startup Order

One valid startup order is:

[]string{
    "database",
    "auth",
    "api",
    "gateway",
    "metrics",
}

Another valid order could be:

[]string{
    "database",
    "auth",
    "api",
    "metrics",
    "gateway",
}

Both satisfy the dependency graph.

Deterministic Result

When multiple nodes are available at the same time, use lexicographical ID ordering.

With that rule, the expected result is:

[]string{
    "database",
    "auth",
    "api",
    "gateway",
    "metrics",
}

because:

gateway < metrics

lexicographically.

Result Model

A structured result is recommended:

type DependencyResult struct {
    Valid               bool
    StartupOrder        []string
    MissingDependencies []MissingDependency
    Cycles              [][]string
}

For example:

type MissingDependency struct {
    ServiceID    string
    DependencyID string
}

Missing Dependency Case

Consider:

services := []Service{
    {
        ID:           "api",
        Dependencies: []string{"database"},
    },
}

but no service with:

ID = database

exists.

The resolver must report:

api references missing dependency database

The graph is invalid.

Cycle Case

Consider:

service-a depends on service-b
service-b depends on service-c
service-c depends on service-a

This creates the cycle:

service-a
    ↓
service-b
    ↓
service-c
    ↓
service-a

No valid startup order exists.

The resolver must report the cycle.

Self Dependency

A service must not depend on itself.

Invalid example:

Service{
    ID:           "api",
    Dependencies: []string{"api"},
}

This should be treated as a dependency cycle or explicit validation error.

Duplicate Services

Service IDs must be unique.

For example:

Service{ID: "api"}
Service{ID: "api"}

is invalid input.

Duplicate Dependencies

A service should not need to declare the same dependency multiple times.

For example:

Dependencies: []string{
    "database",
    "database",
}

should either be rejected or normalized.

The implementation must use one consistent rule.

Requirements

The resolver must:

1. validate unique service IDs
2. validate all dependency references
3. detect self-dependencies
4. detect dependency cycles
5. produce a valid startup order
6. use deterministic ordering when multiple choices exist

Additional Test — Independent Services

Input:

[]Service{
    {ID: "database"},
    {ID: "cache"},
    {ID: "worker"},
}

No service depends on another.

With lexicographical ordering, the result is:

[]string{
    "cache",
    "database",
    "worker",
}

Additional Test — Multiple Dependency Levels

Input:

A depends on B and C
B depends on D
C depends on D
D has no dependencies

A valid execution relationship is:

D
↓
B and C
↓
A

Implementation Notes

This problem can be solved using a topological ordering algorithm.

Possible approaches include:

• dependency-count processing
• depth-first traversal
• another correct graph-based solution

The implementation should not rely on repeatedly hard-coding known service names.

The same resolver must work for arbitrary service graphs.