Implement version string comparator with extensions
Company: Nextdoor
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a function compareVersions(a, b) that compares two software version strings. Each version consists of dot-separated numeric components (e.g., 1.02.
3). Treat missing trailing components as 0 and compare numerically, ignoring leading zeros. Extend the comparator to support optional pre-release identifiers (e.g., -alpha, -rc.
1) that sort before the corresponding release; compare pre-release identifiers by dot-separated tokens where numeric tokens are compared numerically and non-numeric tokens lexicographically; ignore build metadata (everything after '+'). Return -1 if a < b, 0 if equal, and 1 if a > b. Analyze time and space complexity and describe test cases covering tricky inputs (very long components, many segments, leading zeros, empty segments, pre-release ordering).
Quick Answer: This question evaluates string parsing and comparison algorithms, handling of numeric versus lexical ordering and versioning semantics (including pre-release identifiers and ignored build metadata), within the Coding & Algorithms domain.
Part 1: Compare Dot-Separated Numeric Version Strings
Write a function `solution(a, b)` that compares two software version strings made only of dot-separated numeric components. Compare each component numerically, not lexicographically, so `'10' > '2'`. Ignore leading zeros inside a component. If one version has fewer components, treat the missing trailing components as `0`. Also treat empty components caused by consecutive dots or leading/trailing dots as `0`, so `'1..2'` is equivalent to `'1.0.2'` and `''` is equivalent to `'0'`. Return `-1` if `a < b`, `0` if they are equal, and `1` if `a > b`. Your solution should handle very long numeric components without relying on fixed-width integer conversion.
Constraints
- 0 <= len(a), len(b) <= 200000
- Each string contains only digits `0-9` and `.`
- The empty string is allowed and represents version `0`
- Empty components are allowed and should be treated as `0`
- A numeric component may be much longer than standard integer ranges
Examples
Input: ('1.02.3', '1.2.3.0')
Expected Output:
Explanation: Leading zeros are ignored, and the missing trailing component in the first version is treated as 0.
Input: ('1.0.5', '1.0.12')
Expected Output:
Explanation: Compare numerically: 5 < 12.
Hints
- Compare the versions component by component. If one version runs out of components, use `0` for the missing parts.
- To compare very long numeric components safely, strip leading zeros, then compare by length and finally lexicographically.
Part 2: Compare Version Strings with Pre-Release Identifiers and Build Metadata
Write a function `solution(a, b)` that compares two software version strings with these rules:
1. A version has a numeric core, optionally followed by a pre-release part after `-`, and optionally followed by build metadata after `+`.
2. Ignore everything after `+` completely.
3. Compare the numeric core exactly as in Part 1: dot-separated numeric components, compared numerically, ignoring leading zeros, with missing trailing components treated as `0`, and empty core components treated as `0`.
4. If the cores are equal, a version **without** a pre-release part is greater than the same core **with** a pre-release part. For example, `1.0.0 > 1.0.0-alpha`.
5. If both have pre-release parts, split them by dots and compare token by token:
- If both tokens are numeric, compare them numerically.
- If one token is numeric and the other is non-numeric, the numeric token is smaller.
- If both are non-numeric, compare them lexicographically.
- If all compared tokens are equal but one pre-release has fewer tokens, the shorter one is smaller.
Return `-1` if `a < b`, `0` if equal, and `1` if `a > b`.
Constraints
- 0 <= len(a), len(b) <= 200000
- Core version components contain digits and dots; empty core components should be treated as `0`
- A pre-release part, if present, is dot-separated and may contain letters, digits, or hyphens
- Build metadata starts after the first `+` and must be ignored
- Numeric core components and numeric pre-release tokens may be very long
Examples
Input: ('1.0.0-alpha', '1.0.0')
Expected Output:
Explanation: A pre-release version is smaller than the corresponding final release.
Input: ('1.0.0-alpha.1', '1.0.0-alpha.beta')
Expected Output:
Explanation: After matching 'alpha', numeric token 1 is smaller than non-numeric token 'beta'.
Hints
- First strip off build metadata, then separate the core part from the optional pre-release part.
- After the core versions compare equal, remember that a release version beats any pre-release of the same core.