Task 1: Compare Version Numbers
Compare two given version number strings v1 and v2. Return 1 if v1 > v2, -1 if v1 < v2, and 0 if they are equal.
Example Output
compare_versions('0.1', '1.1') => -1
compare_versions('2.0', '1.2') => 1
compare_versions('1.2.1', '1.2_1') => 1
Logic
Parse numbers and separator characters (. vs _). Compare numeric parts component by component. If numbers match, a dot . has higher precedence than an underscore _.
Perl Solution
ch-1.pl
sub compare_versions {
my ($ver1, $ver2) = @_;
my ( $nums1, $seps1 ) = _parse_version($ver1);
my ( $nums2, $seps2 ) = _parse_version($ver2);
my $min = @$nums1 < @$nums2 ? scalar(@$nums1) : scalar(@$nums2);
for my $i ( 0 .. $min - 1 ) {
return -1 if $nums1->[$i] < $nums2->[$i];
return 1 if $nums1->[$i] > $nums2->[$i];
next if $i == 0;
my $s1 = $seps1->[ $i - 1 ];
my $s2 = $seps2->[ $i - 1 ];
next if $s1 eq $s2;
return 1 if $s1 eq '.';
return -1;
}
return -1 if @$nums1 < @$nums2;
return 1 if @$nums1 > @$nums2;
return 0;
}
Python Solution
ch-1.py
def compare_versions(v1: str, v2: str) -> int:
nums1, seps1 = _parse_version(v1)
nums2, seps2 = _parse_version(v2)
m = min(len(nums1), len(nums2))
for i in range(m):
if nums1[i] != nums2[i]:
return 1 if nums1[i] > nums2[i] else -1
if i > 0 and seps1[i - 1] != seps2[i - 1]:
return 1 if seps1[i - 1] == "." else -1
if len(nums1) != len(nums2):
return 1 if len(nums1) > len(nums2) else -1
return 0
Task 2: Ordered Lineup
Given arrays of unique heights @H and, for each height, the count @T of taller people in front of that person, reconstruct the lineup.
Example Output
Input: H = [2, 6, 4, 5, 1, 3], T = [1, 0, 2, 0, 1, 2]
Output: [5, 1, 2, 6, 3, 4]
Logic
Greedy insertion algorithm: sort people by height descending. Insert each person into index T of the output array. Because taller people are inserted first, inserting at position T guarantees exactly T taller people precede them.
Perl Solution
ch-2.pl
sub ordered_lineup ( $heights, $taller_in_front ) {
my @people;
for my $i ( 0 .. $#$heights ) {
push @people, { h => $heights->[$i], t => $taller_in_front->[$i] };
}
@people = sort { $b->{h} <=> $a->{h} } @people;
my @line;
for my $p (@people) {
my $idx = $p->{t};
splice @line, $idx, 0, $p->{h};
}
return \@line;
}
Python Solution
ch-2.py
def ordered_lineup(heights: Sequence[int], taller_in_front: Sequence[int]) -> List[int]:
people = [Person(h, t) for h, t in zip(heights, taller_in_front)]
people.sort(key=lambda p: p.height, reverse=True)
line: List[int] = []
for p in people:
line.insert(p.taller_in_front, p.height)
return line