Algorithm Group 6

Algorithm Group 6 focuses on graph relationships, dependency resolution, scheduling, state transitions, and event-stream analysis.

The exercises in this group are designed to model problems that commonly appear in backend services, build systems, deployment tooling, distributed systems, workflow engines, and infrastructure orchestration.

Compared with earlier groups, the input data is less often a simple list.

Instead, the implementation must reason about relationships between entities.

Tasks

Task 1 — Dependency Graph Resolution

Analyze a set of services and their dependencies.

Determine a valid startup order, detect missing dependencies, and identify dependency cycles.

Task 2 — Weighted Route Resolution

Given a weighted graph, find the lowest-cost route between two nodes and return both the selected path and its total cost.

Task 3 — Dependency-Aware Task Scheduler

Schedule tasks that have execution durations and dependencies across a limited number of workers.

Determine when every task starts and finishes and calculate total execution time.

Task 4 — State Machine Validation

Validate a sequence of state transitions against a defined state machine.

Report invalid transitions and determine the final valid state.

Task 5 — Event Stream Window Analysis

Process timestamped events from multiple sources.

Group events into time windows and report source activity, missing intervals, and burst conditions.

Objectives

The exercises in this group provide practice with:

• directed graphs
• dependency traversal
• topological ordering
• cycle detection
• graph validation
• weighted graphs
• shortest-path reasoning
• scheduling
• worker allocation
• dependency completion
• state machines
• transition validation
• event streams
• timestamp ordering
• time-window aggregation
• deterministic reporting

Graph Terminology

Several tasks use graph-like relationships.

A node represents an entity.

Examples include:

service
task
location
state

An edge represents a relationship.

Examples include:

service A depends on service B
location A connects to location B
state A can transition to state B

The direction of an edge is important.

Deterministic Output

Some graph problems may have multiple valid answers.

When several valid results exist, implementations should use deterministic tie-breaking.

Unless a task specifies another rule, prefer:

lexicographical ID order

for equivalent candidates.

This keeps tests reproducible.

Validation

Inputs should be validated before processing.

Examples include:

• duplicate node IDs
• references to missing nodes
• negative route costs
• self-dependencies
• malformed timestamps
• duplicate state transitions
• invalid worker counts

Invalid input should be distinguished from a valid problem that simply has no solution.

Implementation

The tasks are language-independent.

They may be implemented in Go, Rust, or another language.

The exact internal data structures are left to the developer.

The important requirement is that the algorithm solves the general problem rather than only the provided examples.