Task 1: Invert Tree
You are given a binary tree. Write a script to invert the binary tree (mirror image).
Example Output
Original tree:
|--7
|--3
|--6
1
|--5
|--2
|--4
Inverted tree:
|--4
|--2
|--5
1
|--6
|--3
|--7
Logic
Swap the left and right child nodes at the root node, then recursively invert the left and right subtrees.
Perl Solution
ch-1.pl
package BinaryTree;
sub invert {
my $self = shift;
( $self->{left}, $self->{right} ) = ( $self->{right}, $self->{left} );
$self->{left}->invert() if defined $self->{left};
$self->{right}->invert() if defined $self->{right};
}
Python Solution
ch-1.py
class BinaryTree:
def invert(self):
self.left, self.right = self.right, self.left
if self.left:
self.left.invert()
if self.right:
self.right.invert()
Task 2: Shortest Unique Prefix
Write a script to find the shortest unique prefix for each word in a given list of words.
Example Output
Input: ["alphabet", "book", "carpet", "cadmium", "cadeau", "alpine"]
Output: ["alph", "b", "car", "cadm", "cade", "alp"]
Logic
For each word, incrementally expand a prefix character by character until the prefix is unique (i.e. does not match the prefix of any previously determined prefix / word in the list).
Perl Solution
ch-2.pl
sub shortest_unique_prefixes {
my @words = @_;
my @result;
for my $word (@words) {
my $prefix = "";
for my $char ( split //, $word ) {
$prefix .= $char;
if ( !grep { $_ =~ /^$prefix/ } @result ) {
push @result, $prefix;
last;
}
}
}
return \@result;
}
Python Solution
ch-2.py
def shortest_unique_prefixes(words: List[str]) -> List[str]:
result = []
for word in words:
prefix = ""
for char in word:
prefix += char
if not any(res.startswith(prefix) for res in result):
result.append(prefix)
break
return result