REPOSITORY CODING · MEDIUM
Backtrack after transitive version conflicts
A greedy first choice makes a satisfiable multi-root dependency graph appear unsatisfiable. Search remaining versions after a branch conflict, carrying all root and transitive requirements and preserving deterministic version preference.
Repository ImplementationOffline package dependency resolver
Work through a real codebase.
Choose an environment, investigate the existing implementation and use the tests to check your change. Sign in to open a workspace; execution and Ono usage follow your plan’s allowances.
Task requirements and environments
Java · 55 minute session
- Resolve an offline package catalogue with unique package/version rows, explicit root constraints and transitive dependency constraints. Versions are canonical major.minor.patch integers; prerelease/build syntax is outside this bounded exercise. Supported constraints are exact versions, *, ^ and ~.
- Caret ranges stop at the next major for positive major versions, at the next minor for 0.minor.patch with positive minor, and at the next patch for 0.0.patch. Tilde stops at the next minor. Lower bounds are inclusive and upper bounds exclusive.
- Choose one version per reachable package satisfying every accumulated requirement. Backtrack when a later root or transitive dependency conflicts with an earlier selection. Cyclic dependency graphs are allowed if the selected versions satisfy their constraints. Missing or incompatible packages are unsatisfiable.
- With a nonempty lock map, minimize changed, added and removed package identities before preferring higher version vectors in lexical package-name order. Without a lock map, prefer the highest version vector. Report selected packages and every changed identity, including removed lock entries, in lexical order. An unavailable locked version is a preference rather than a requirement.
- The Java and Spring Boot APIs execute the same checked-in resolver. This is bounded offline dependency resolution with at most 12 package names, eight versions each and 100000 explored states. It downloads and executes no packages.
Spring Boot · 55 minute session
- Resolve an offline package catalogue with unique package/version rows, explicit root constraints and transitive dependency constraints. Versions are canonical major.minor.patch integers; prerelease/build syntax is outside this bounded exercise. Supported constraints are exact versions, *, ^ and ~.
- Caret ranges stop at the next major for positive major versions, at the next minor for 0.minor.patch with positive minor, and at the next patch for 0.0.patch. Tilde stops at the next minor. Lower bounds are inclusive and upper bounds exclusive.
- Choose one version per reachable package satisfying every accumulated requirement. Backtrack when a later root or transitive dependency conflicts with an earlier selection. Cyclic dependency graphs are allowed if the selected versions satisfy their constraints. Missing or incompatible packages are unsatisfiable.