cute interview problem

[Ian Kelly]

On Sat, Mar 3, 2018 at 3:26 PM, Richard Damon <Richard at damon-family.org> wrote:
> On 2/28/18 3:51 PM, Ian Kelly wrote:
>>
>> On Wed, Feb 28, 2018 at 12:55 PM,  <jrlcgmx at gmail.com> wrote:
>>>
>>> On Tuesday, 27 February 2018 00:42:02 UTC+1, Paul Rubin  wrote:
>>>>
>>>> Ron Aaron posted the below url on comp.lang.forth.  It points to what I
>>>> thought was a cute problem, along with his solution in his Forth dialect
>>>> 8th:
>>>>
>>>>    https://8th-dev.com/forum/index.php/topic,1584.msg8720.html
>>>>
>>>> I wrote a solution in Forth and additional ones in Python and Haskell
>>>> and thought people here might like trying it themselves.  I'll post my
>>>> Python version here in a few days if anyone wants to see it.  Time limit
>>>> for the problem is supposed to be 45 minutes.  I spent a lot longer
>>>> because I ended up writing several versions in various languages.
>>>
>>>
>>> I dont think its cute at all.
>>> how did the interview go?
>>
>>
>> Yeah, seems to me this is basically just asking "have you ever heard
>> of an interval tree (or can you invent one on the fly)".
>>
>
> An interval tree sounds a bit more complicated than you really need (there
> is no need to keep the original list of intervals intact, we just need to
> know if a number was in ANY forbidden interval). All you really need to do
> is build a binary search tree of disjoint intervals, where before actually
> adding the next interval in the list you find the intervals it is between
> and merge rather than add if it overlaps (or is adjacent), and merging the
> two intervals (the prior and next) if it fills all the space between.
>
> The output is just a simple walking of the tree and processing the gaps
> between recorded forbidden intervals.
>
> You also could just build up a tree of forbidden intervals, sorted by
> starting value, and not consider overlaps, and in the output walk just keep
> track of the highest end of interval encountered so far to effectively merge
> them at readout time.

For that matter, I suppose that you don't even really need a tree.
Just put all the intervals in a list, sort the list by the low
endpoint of each interval, and iterate as above.

Maybe it's a better interview question that I first thought, due to
the propensity to overthink it.

Quick and dirty Python implementation, assuming that the intervals
have already been read (because file I/O is boring):

def number_allowed_and_smallest(minval, maxval, forbidden):
    allowed = 0
    smallest = None
    previous_high = minval - 1
    for (low, high) in sorted(forbidden):
        if low > previous_high + 1:
            allowed += low - 1 - previous_high
            if smallest is None:
                smallest = previous_high + 1
        previous_high = max(high, previous_high)
    if maxval > previous_high:
        allowed += maxval - previous_high
        if smallest is None:
            smallest = previous_high + 1
    return allowed, smallest