How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Nextdoor.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Nextdoor during technical interviews.

Implement and use a version comparator | Nextdoor Coding Question

Quick Overview

Implement and use a version comparator evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Implement and use a version comparator

Company: Nextdoor

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given up to 100,000 version-like identifiers (e.g., "1.0", "01.2.0", "2.0.0-alpha", "1.10.3"). Implement compare(a, b) that orders identifiers by: ( 1) split by '.', compare numeric segments as integers; ( 2) missing segments are treated as 0; ( 3) pre-release tags (e.g., '-alpha', '-beta', '-rcN') sort before the corresponding release; numeric build metadata after a '+' is ignored for ordering. Use your comparator to return the list sorted in ascending order. Discuss time and space complexity and edge cases (leading zeros, different lengths, non-numeric segments). Provide code.

Quick Answer: Implement and use a version comparator evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given up to 100,000 version-like identifiers (e.g., "1.0", "01.2.0", "2.0.0-alpha", "1.10.3"). Implement a comparator that orders identifiers by the following rules, then return the list sorted in ascending order: 1. Split each identifier by '.' and compare the numeric segments as integers (so '1.10' > '1.9', and leading zeros are ignored: '01' == '1'). 2. Missing trailing segments are treated as 0, so '1', '1.0', and '1.0.0' are all equal in numeric core. 3. A pre-release tag introduced by '-' (e.g. '-alpha', '-beta', '-rcN') sorts BEFORE the corresponding release with the same numeric core. Among pre-release tags the order is alpha < beta < rc, and an rc's trailing number compares as an integer (rc1 < rc2 < rc10). Build metadata after a '+' (e.g. '+build5') is ignored for ordering. Return the list sorted ascending. When two identifiers compare equal, keep their original relative order (stable sort). Also be able to discuss time/space complexity and edge cases (leading zeros, different lengths, non-numeric segments).

Constraints

0 <= number of identifiers <= 100000
Each identifier is a non-empty string of numeric segments separated by '.', optionally followed by a '-' pre-release tag and/or a '+' build-metadata suffix.
Numeric segments fit in a 64-bit integer; leading zeros are allowed.
Pre-release names considered: alpha, beta, rc (with an optional trailing integer); any other tag is treated as ranking after rc.
Sort must be stable: equal identifiers keep their original relative order.

Examples

Input: (["1.0", "01.2.0", "2.0.0-alpha", "1.10.3"],)

Expected Output: ['1.0', '01.2.0', '1.10.3', '2.0.0-alpha']

Explanation: Numeric cores: 1.0 < 1.2.0 (01 == 1) < 1.10.3 < 2.0.0. The pre-release '-alpha' on 2.0.0 only matters relative to a 2.0.0 release, which is absent, so it stays last.

Input: (["1.0.0", "1.0.0-alpha", "1.0.0-beta", "1.0.0-rc1"],)

Expected Output: ['1.0.0-alpha', '1.0.0-beta', '1.0.0-rc1', '1.0.0']

Explanation: Same numeric core 1.0.0. Pre-releases sort before the release in the order alpha < beta < rc, and the plain '1.0.0' release comes last.

Input: (["1.0.0+build5", "1.0.0+build1", "1.0.0"],)

Expected Output: ['1.0.0+build5', '1.0.0+build1', '1.0.0']

Explanation: Build metadata after '+' is ignored for ordering, so all three compare equal; the stable sort preserves their original input order.

Input: (["1", "1.0", "1.0.0"],)

Expected Output: ['1', '1.0', '1.0.0']

Explanation: Missing trailing segments are treated as 0, so all three are numerically equal; stable sort keeps input order.

Input: (["2.0.0-rc2", "2.0.0-rc10", "2.0.0-rc1"],)

Expected Output: ['2.0.0-rc1', '2.0.0-rc2', '2.0.0-rc10']

Explanation: Within rc tags the trailing number is compared as an integer, so rc1 < rc2 < rc10 (not lexicographically, where rc10 would precede rc2).

Input: ([],)

Expected Output: []

Explanation: Empty input returns an empty list.

Input: (["1.10.3", "1.2.0", "1.9.9"],)

Expected Output: ['1.2.0', '1.9.9', '1.10.3']

Explanation: Second segment compared as integers: 2 < 9 < 10, so 1.2.0 < 1.9.9 < 1.10.3 (lexicographic string compare would wrongly put 1.10.3 first).

Hints

Strip build metadata (everything from '+' onward) first; it never affects ordering.
Split the numeric core on '.' and compare segment-by-segment as integers, treating any missing segment in the shorter version as 0. Parsing each segment as an int automatically handles leading zeros (01 -> 1).
Only after the numeric cores tie does the pre-release tag matter: map it to a sortable key where a missing tag (a real release) ranks ABOVE every pre-release, and alpha < beta < rc, with rc's trailing number compared numerically (rc2 < rc10).
Use a custom comparator (functools.cmp_to_key in Python, Comparator in Java, a lambda in C++, or Array.prototype.sort's compare fn in JS) and rely on a stable sort for ties.

Quick Overview