Task 1: Diff-K
You are given a sorted array @N of positive integers and a non-negative integer k. Write a script to find if there exist 2 indices i and j such that A[j] - A[i] = k and i != j. Print pairs of indices if any such pairs exist.
Example Output
Input: k = 2, arr = [2, 7, 9]
Output: (2,1)
Input: k = 2, arr = [2, 4, 6]
Output: (1,0)(2,1)
Logic
Iterate through the array with a left index i and advance a right pointer j while the difference A[j] - A[i] is less than k. If the difference equals k, store/print the index pair (j, i).
Perl Solution
ch-1.pl
sub get_valid_pairs {
my ($k, @arr) = @_;
my $answer;
for my $i (0 .. scalar @arr - 2) {
my $j = $i + 1;
while (($arr[$j] - $arr[$i] < $k) and ($j < scalar @arr - 1)) {
$j++;
}
$answer .= "($j,$i)" if $arr[$j] - $arr[$i] == $k;
}
return $answer;
}
Python Solution
ch-1.py
def get_valid_pairs(k: int, arr: list):
answer = ''
for i in range(0, len(arr)-1):
j = i + 1
while (arr[j] - arr[i] < k) and (j < len(arr) - 1):
j += 1
if arr[j] - arr[i] == k:
answer += f"({j},{i})"
return answer
Task 2: Path Sum
Given a binary tree and a target sum, write a script to find if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Only complete paths (from root to leaf node) may be considered.
Example Output
Tree with root 5 and target sum 22:
Path found: 5 -> 4 -> 11 -> 2 (Sum: 22)
Logic
Represent the tree using a directed graph structure. Identify all leaf nodes (exterior / external vertices with out-degree 0) and find paths from the root to each leaf. Sum the node values along each path and output paths matching the target sum.
Perl Solution
ch-2.pl
use Graph::Directed;
use List::Util qw/sum/;
my $g = Graph::Directed->new;
$g->add_edge(5,4); $g->add_edge(4,11); $g->add_edge(11,7); $g->add_edge(11,2);
$g->add_edge(5,8); $g->add_edge(8,13); $g->add_edge(8,9); $g->add_edge(9,1);
my $start = 5;
my $sum = 22;
for ($g->exterior_vertices) {
my @path = $g->SP_Dijkstra($start, $_);
say join '->', @path if sum(@path) == $sum;
}
Python Solution
ch-2.py
import networkx as nx
g = nx.DiGraph()
g.add_edge(5, 4); g.add_edge(4, 11); g.add_edge(11, 7); g.add_edge(11, 2)
g.add_edge(5, 8); g.add_edge(8, 13); g.add_edge(8, 9); g.add_edge(9, 1)
start = 5
my_sum = 22
external_vertices = (x for x in g.nodes() if g.out_degree(x)==0 and g.in_degree(x)==1)
for vert in external_vertices:
path = nx.shortest_path(g, start, vert)
if sum(path) == my_sum:
print(path)