Task 1: Peak Elements
Write a script that prints all the peak elements in the given array. A peak element is an element that is greater than its neighbours.
Example Output
Input: [18, 45, 38, 25, 10, 7, 21, 6, 28, 48]
Output: [45, 21, 48]
Input: [47, 11, 32, 8, 1, 9, 39, 14, 36, 23]
Output: [47, 32, 39, 36]
Logic
Check the boundaries separately: the first element is a peak if it is strictly greater than the second, and the last element is a peak if it is strictly greater than the penultimate. For elements in between (indices 1 to $n-2), check if the current element is greater than both its left and right neighbours.
Perl Solution
ch-1.pl
sub find_peaks (@arr) {
my $n = scalar @arr;
return [] if $n == 0;
return [ $arr[0] ] if $n == 1;
my @peaks;
push @peaks, $arr[0] if $arr[0] > $arr[1];
for my $i ( 1 .. $n - 2 ) {
push @peaks, $arr[$i]
if $arr[$i] > $arr[ $i - 1 ] && $arr[$i] > $arr[ $i + 1 ];
}
push @peaks, $arr[-1] if $arr[-1] > $arr[-2];
return \@peaks;
}
Python Solution
ch-1.py
def find_peaks(arr: list[int]) -> list[int]:
"""Find all peak elements in the array."""
n = len(arr)
if n == 0:
return []
if n == 1:
return [arr[0]]
peaks: list[int] = []
# First element
if arr[0] > arr[1]:
peaks.append(arr[0])
# Middle elements
for i in range(1, n - 1):
if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
peaks.append(arr[i])
# Last element
if arr[-1] > arr[-2]:
peaks.append(arr[-1])
return peaks
Task 2: Trim Linked List
You are given a linked list and a positive integer $N. Write a script to remove the $Nth element from the end of the list and print the linked list.
Example Output
Input: 1 -> 2 -> 3 -> 4 -> 5, N = 2
Output: 1 -> 2 -> 3 -> 5
Input: 1 -> 2 -> 3 -> 4 -> 5, N = 1
Output: 1 -> 2 -> 3 -> 4
Logic
Traverse the linked list once to find its total length $size. If $N >= $size, advance the head to $head->next. Otherwise, traverse $size - $N - 1 steps from the head to reach the predecessor of the node to be removed, and update its next pointer to $cur->next->next.
Perl Solution
ch-2.pl
sub remove_from_end ( $self, $n ) {
return if !$self->{head} || $n <= 0;
my $size = 0;
my $cur = $self->{head};
while ($cur) {
$size++;
$cur = $cur->{next};
}
if ( $n >= $size ) {
$self->{head} = $self->{head}->{next};
}
else {
$cur = $self->{head};
for ( 1 .. $size - $n - 1 ) {
$cur = $cur->{next};
}
$cur->{next} = $cur->{next}->{next} if $cur->{next};
}
}
Python Solution
ch-2.py
def remove_from_end(self, n: int) -> None:
"""Remove the n-th element from the end of the list (1-indexed)."""
if self.head is None or n <= 0:
return
size = 0
cur: Optional[Node] = self.head
while cur:
size += 1
cur = cur.next
if n >= size:
self.head = self.head.next
else:
cur = self.head
for _ in range(size - n - 1):
if cur is not None:
cur = cur.next
if cur is not None and cur.next is not None:
cur.next = cur.next.next