Weekly Challenge 092

Challenge 092

TASK #1 › Isomorphic Strings

Task

You are given two strings $A and $B.

Write a script to check if the given strings are Isomorphic. Print 1 if they are otherwise 0.

My solution

This seems pretty straight forward, so not much explanation required. :)

Strings that are different length can't be isomorphic, so I return 0 if that happens. I then compare the first string to the second string, and then compare in the other direction. This is to prevent something like abcb matching xyxy.

For the function, I walk through the string using a for loop and substr. If we have seen the first character before, I return 0 if the map is something different. If we haven't seen the string, then we store it for later use.

Examples

» ./ch-1.pl abc xyz
1

» ./ch-1.pl abb xyy
1

» ./ch-1.pl sum add
0

TASK #2 › Insert Interval

Task

You are given a set of sorted non-overlapping intervals and a new interval.

Write a script to merge the new interval to the given set of intervals.

My solution

This is one of those tasks where I'm interested in how other Team PWC members solved it as much as my own attempt. Like task one last week I've written a solution that works, but I'm not sure it's the best solution.

This is the way I solved this task. The term 'new interval' refers to the last two numbers.

• Grab all the numbers in the input. Remove the last two (the new interval) and put the rest of the numbers in a hash.
• Loop through a sorted list of the hash (the start number for each interval).
• If the new interval is after the end ($new_start > $end), then move to the next interval.
• If the new interval is before the start ($new_end < $start), then add the new interval to the hash and return.
• If we got here, it means the interval intersects the new interval. If the start of the new interval is less the start of the interval, we move the start. We take the same action with the end, and remove any intervals we subsumed in the process.
• If we have gone through the list of intervals, then it means the new interval is after the last interval. We add the interval to the hash, and return
• Finally I print out the result.

Examples

» ./ch-2.pl "(1,4), (8,10) (2,6)"
(1,6), (8,10)

» ./ch-2.pl "(1,2), (3,7), (8,10) (5,8)"
(1,2), (3,10)

» ./ch-2.pl "(1,5), (7,9) (10,11)"
(1,5), (7,9), (10,11)