On Sat, Mar 3, 2018 at 3:26 PM, Richard Damon <rich...@damon-family.org> wrote: > On 2/28/18 3:51 PM, Ian Kelly wrote: >> >> On Wed, Feb 28, 2018 at 12:55 PM, <jrlc...@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 -- https://mail.python.org/mailman/listinfo/python-list