Task 1: Longest Common Substring
Write a script that takes 2 or more strings as command line parameters and prints the longest common substring.
Example
Input: "ABABC", "BABCA", "ABCBA"
Output: Common string ABC
Logic
Generate all possible substrings of the first string. For each subsequent string, filter our list of candidate substrings to keep only those that are present. Sort the remaining common substrings by length in descending order, and return the longest one.
Perl Solution
ch-1.pl
my %all_strings;
my $seen_first;
sub insert_to_all_strings {
my $str = shift;
my %seen_str;
my $length = length($str);
for my $pos ( 0 .. $length - 1 ) {
for my $length_remain ( 1 .. $length - $pos ) {
my $sub_string = substr( $str, $pos, $length_remain );
next if $seen_first and not defined $all_strings{length($sub_string)}{$sub_string};
next if $seen_str{$sub_string};
$seen_str{$sub_string} = 1;
$all_strings{ length($sub_string) }{$sub_string}++;
}
}
$seen_first = 1;
}
sub longest_str {
my @strings = @_;
my $found_solution;
insert_to_all_strings($_) for (@strings);
foreach my $str_length ( sort { $b <=> $a } keys %all_strings ) {
foreach my $string ( keys %{ $all_strings{$str_length} } ) {
if ( $all_strings{$str_length}{$string} == scalar @strings ) {
say "Common string $string";
$found_solution = $string;
}
}
last if $found_solution;
}
return $found_solution;
}
Python Solution
ch-1.py
def longest_common_substring(strings: list[str]) -> str:
if not strings:
return ""
# Generate all substrings of the first string
first = strings[0]
n = len(first)
candidates = set()
for i in range(n):
for j in range(i + 1, n + 1):
candidates.add(first[i:j])
# Keep only those present in all other strings
for s in strings[1:]:
candidates = {cand for cand in candidates if cand in s}
if not candidates:
return ""
return max(candidates, key=len)
Task 2: Priority Queue
Implement a Priority Queue. It should support:
is_empty: Check if the queue is empty.
insert_with_priority: Add an element with an associated priority.
pull_highest_priority_element: Remove and return the element with the highest priority (FIFO for ties).
Logic
We use a hash table (or dictionary) where the keys are priorities and the values are array references (or lists) storing elements of that priority. Since elements with the same priority are added to the end of the array, pulling using shift (or pop/dequeue from the front) naturally respects FIFO order for ties.
Perl Solution
ch-2.pl
sub is_empty {
my $hash_ref = shift;
return %{$hash_ref} ? 0 : 1;
}
sub insert_with_priority {
my ( $hash_ref, $priority, $element ) = @_;
my %queue = %{$hash_ref};
push @{ $queue{$priority} }, $element;
return %queue;
}
sub pull_highest_priority_element {
my $hash_ref = shift;
foreach my $priority ( sort { $b <=> $a } keys %$hash_ref ) {
my $element = shift @{ %${hash_ref}{$priority} };
delete $$hash_ref{$priority} unless scalar @{ %${hash_ref}{$priority} };
return $element;
}
return 1;
}
Python Solution
ch-2.py
class PriorityQueue:
def __init__(self):
self.queue = {}
def is_empty(self) -> bool:
return len(self.queue) == 0
def insert_with_priority(self, priority: int, element: str):
if priority not in self.queue:
self.queue[priority] = []
self.queue[priority].append(element)
def pull_highest_priority_element(self) -> str:
if self.is_empty():
raise IndexError("Queue is empty")
highest = max(self.queue.keys())
element = self.queue[highest].pop(0)
if not self.queue[highest]:
del self.queue[highest]
return element