Task 1: Partition List
Given a linked list and a value k, partition it such that all nodes less than k come before nodes greater than or equal to k, preserving original relative order.
Example Output
Original list: 1 → 4 → 3 → 2 → 5 → 2 → END
Partitioned list with k=3: 1 → 2 → 2 → 4 → 3 → 5 → END
Logic
Maintain two separate linked lists (one for nodes < k and one for nodes ≥ k). Traverse the original list, append each node to the appropriate list, and join the two lists at the end.
Perl Solution
ch-1.pl
sub partition {
my ( $self, $k ) = @_;
my ( $less_head, $greater_head, $less_tail, $greater_tail );
my $current = $self;
while ( defined $current ) {
if ( $current->{value} < $k ) {
defined $less_tail ? ($less_tail->{next} = $current) : ($less_head = $current);
$less_tail = $current;
} else {
defined $greater_tail ? ($greater_tail->{next} = $current) : ($greater_head = $current);
$greater_tail = $current;
}
$current = $current->{next};
}
$less_tail ? ($less_tail->{next} = $greater_head) : ($less_head = $greater_head);
$greater_tail->{next} = undef if defined $greater_tail;
return $less_head;
}
Python Solution
ch-1.py
def partition(self, k):
less_head = greater_head = less_tail = greater_tail = None
current = self
while current:
if current.value < k:
if less_tail:
less_tail.next = current
else:
less_head = current
less_tail = current
else:
if greater_tail:
greater_tail.next = current
else:
greater_head = current
greater_tail = current
current = current.next
if less_tail:
less_tail.next = greater_head
else:
less_head = greater_head
if greater_tail:
greater_tail.next = None
return less_head
Task 2: Bit Sum
Given an array of positive integers, calculate the sum of bit differences between all pairs of integers in the array.
Example Output
Input: [2, 3, 4]
Output: 6
Logic
For every pair of numbers (a, b) in the array, count the number of set bits in a ^ b (XOR), and sum these count values across all pairs.
Perl Solution
ch-2.pl
sub count_different_bits {
my ( $a, $b ) = @_;
my $count = 0;
while ( $a > 0 or $b > 0 ) {
$count += ( $a % 2 ) ^ ( $b % 2 );
$a >>= 1;
$b >>= 1;
}
return $count;
}
sub sum_different_bits {
my @numbers = @_;
my $sum = 0;
for my $i ( 0 .. $#numbers ) {
for my $j ( $i + 1 .. $#numbers ) {
$sum += count_different_bits( $numbers[$i], $numbers[$j] );
}
}
return $sum;
}
Python Solution
ch-2.py
def count_different_bits(a: int, b: int) -> int:
count = 0
while a > 0 or b > 0:
count += (a % 2) ^ (b % 2)
a >>= 1
b >>= 1
return count
def sum_different_bits(numbers: List[int]) -> int:
total = 0
for i in range(len(numbers)):
for j in range(i+1, len(numbers)):
total += count_different_bits(numbers[i], numbers[j])
return total