cute interview problem

[Richard Damon]

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.