Task 1: Median of Arrays
You are given two sorted arrays. Write a script to merge the two given sorted arrays and return the median of the merged array.
Example Output
Input: @arr1 = (2), @arr2 = (4)
Output: 3.0
Input: @arr1 = (1,2,3), @arr2 = (7,8,9,10)
Output: 7.0
Input: @arr1 = (), @arr2 = (10,20,30,40)
Output: 25.0
Logic
Using a two-pointer merge algorithm in O(N + M) time, merge the two already sorted arrays. If the combined length is odd, the median is the middle element. If the length is even, it is the arithmetic average of the two middle elements.
Perl Solution
ch-1.pl
sub find_median_sorted_arrays ( $arr1, $arr2 ) {
my @merged;
my $i = 0;
my $j = 0;
my $n = scalar @$arr1;
my $m = scalar @$arr2;
while ( $i < $n && $j < $m ) {
if ( $arr1->[$i] <= $arr2->[$j] ) {
push @merged, $arr1->[ $i++ ];
}
else {
push @merged, $arr2->[ $j++ ];
}
}
while ( $i < $n ) { push @merged, $arr1->[ $i++ ]; }
while ( $j < $m ) { push @merged, $arr2->[ $j++ ]; }
my $total = scalar @merged;
die "Both arrays are empty" if $total == 0;
if ( $total % 2 == 1 ) {
return sprintf( "%.1f", $merged[ int( $total / 2 ) ] ) + 0.0;
}
else {
my $mid = $total / 2;
my $val = ( $merged[ $mid - 1 ] + $merged[$mid] ) / 2.0;
return sprintf( "%.1f", $val ) + 0.0;
}
}
Python Solution
ch-1.py
def find_median_sorted_arrays(arr1: list[int], arr2: list[int]) -> float:
"""Merge two sorted integer arrays and compute their median."""
merged: list[int] = []
i, j = 0, 0
n, m = len(arr1), len(arr2)
while i < n and j < m:
if arr1[i] <= arr2[j]:
merged.append(arr1[i])
i += 1
else:
merged.append(arr2[j])
j += 1
merged.extend(arr1[i:])
merged.extend(arr2[j:])
total = len(merged)
if total == 0:
raise ValueError("Both input arrays are empty.")
if total % 2 == 1:
return float(merged[total // 2])
mid = total // 2
return (merged[mid - 1] + merged[mid]) / 2.0
Task 2: Nested Boxes
You are given an array of box dimensions [width, height]. Write a script to determine the maximum number of these boxes that can fit inside each other in a single stack (each nested box must be strictly smaller in both dimensions).
Example Output
Input: @boxes = ([1, 3], [3, 5], [6, 8], [2, 4])
Output: 4
([1, 3] -> [2, 4] -> [3, 5] -> [6, 8])
Input: @boxes = ([4, 5], [4, 6], [6, 7], [2, 3], [4, 3])
Output: 3
([2, 3] -> [4, 5] -> [6, 7])
Logic
This is the classic Russian Doll Envelopes problem. We sort the boxes by width in ascending order, and for boxes with equal width, by height in descending order. By sorting heights in reverse for identical widths, a box can never contain another box of the same width. Then, finding the maximum stack reduces to finding the Longest Increasing Subsequence (LIS) on the heights array, which we solve in O(N log N) time using binary search / patience sorting.
Perl Solution
ch-2.pl
sub max_nested_boxes (@boxes) {
return 0 if !@boxes;
my @sorted = sort {
$a->[0] <=> $b->[0] || $b->[1] <=> $a->[1]
} @boxes;
my @tails;
for my $box (@sorted) {
my $h = $box->[1];
my $left = 0;
my $right = scalar @tails;
while ( $left < $right ) {
my $mid = int( ( $left + $right ) / 2 );
if ( $tails[$mid] >= $h ) {
$right = $mid;
}
else {
$left = $mid + 1;
}
}
if ( $left == scalar @tails ) {
push @tails, $h;
}
else {
$tails[$left] = $h;
}
}
return scalar @tails;
}
Python Solution
ch-2.py
def max_nested_boxes(boxes: list[list[int]]) -> int:
"""Determine maximum number of boxes that can nest strictly within each other."""
if not boxes:
return 0
sorted_boxes = sorted(boxes, key=lambda b: (b[0], -b[1]))
tails: list[int] = []
for _, h in sorted_boxes:
idx = bisect.bisect_left(tails, h)
if idx == len(tails):
tails.append(h)
else:
tails[idx] = h
return len(tails)