I’ve been doing the Weekly
Challenges. The
latest
involved set intersections and merging intervals. (Note that this is
open until 29 August 2021.)
TASK #1 › Disjoint Sets
You are given two sets with unique integers.
Write a script to figure out if they are disjoint.
I.e. they have no members in common, which is the same as saying that
the intersection of the two sets is empty.
The "modern" languages on my palette have sets and set operations
built in, so for example in Raku:
my $sa=set @a;
my $sb=set @b;
my $inter=$sa (&) $sb;
if $inter.elems == 0 {
return 1;
} else {
return 0;
}
Ruby has &
, and Python and Rust have an intersection()
method in
their Set class. So that's easy.
Perl doesn't have a set class, but its hashes are ferociously
optimised; so I turn the first set into a hash (the values are
irrelevant, it's just the keys that matter), then test each member of
the second set to see if it's in the first.
sub ds {
my ($a,$b)=@_;
my %h=map {$_ => 1} @{$a};
foreach my $n (@{$b}) {
if (exists $h{$n}) {
return 0;
}
}
return 1;
}
PostScript doesn't have sets either, but it does have dicts which
include a known
method, so I use the same trick. (Interesting how
divergent the terminology is round associative arrays, starting with
whether they're called that, a dictionary, a hash, a map, a collection
or a table. For testing whether a particular key is defined, we might
have exists
, known
, has_key?
, in
, contains
… the idea has
been around for a while, I believe first getting language support in
1969's SNOBOL4, so it's surprising the terminology hasn't settled out
the way e.g. arrays and indices have.)
/ds {
dup length dict /dd exch def
{
dd exch 1 put
} forall
/dj 1 def
{
dd exch known {
/dj 0 def
exit
} if
} forall
dj
} def
TASK #2 › Conflict Intervals
You are given a list of intervals.
Write a script to find out if the current interval conflicts with
any of the previous intervals.
Not quite the standard coding-interview problem (see PWC #50), which
would ask you to reduce the intervals to a minimal set (e.g. if you
had (1,3)
and (2,4)
you'd merge them and spit out (1,4)
). One
normally starts the approach to that problem by sorting the input,
but the desired result here will differ based on the order in which
things occur (the first interval given can never conflict with
anything).
So for each interval after the first, check all earlier intervals for
possible overlap. If we find one, put this interval in the output
queue and go on to the next one. One might also do the merge to reduce
the list of earlier intervals that need to be checked, but I'm not
convinced it would be helpful.
Any overlap will match at least one of these conditions:
- the lower bound lies within the earlier interval
- the upper bound lies within the earlier interval
- the lower bound is below the earlier interval, and the upper bound
is above it
The Ruby code is probably the easiest to read.
def ci(a)
o=[]
1.upto(a.length-1) do |i|
0.upto(i-1) do |j|
if (a[i][0] >= a[j][0] && a[i][0] <= a[j][1]) ||
(a[i][1] >= a[j][0] && a[i][1] <= a[j][1]) ||
(a[i][0] <= a[j][0] && a[i][1] >= a[j][1]) then
o.push(a[i])
break
end
end
end
return o
end
Full code on
github.
Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.