Re: cute interview problem

[Ian Kelly]

On Sat, Mar 3, 2018 at 3:26 PM, Richard Damon  wrote:
> On 2/28/18 3:51 PM, Ian Kelly wrote:
>>
>> On Wed, Feb 28, 2018 at 12:55 PM,   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

Re: cute interview problem

[Richard Damon]

On 2/28/18 3:51 PM, Ian Kelly wrote:

On Wed, Feb 28, 2018 at 12:55 PM,   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.

--
https://mail.python.org/mailman/listinfo/python-list

Re: cute interview problem

[Ian Kelly]

On Wed, Feb 28, 2018 at 12:55 PM,   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)".
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: cute interview problem

[jrlcgmx]

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.

teh interview how did it go
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: cute interview problem

[jrlcgmx]

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?
-- 
https://mail.python.org/mailman/listinfo/python-list