wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Bool Function
        
(Message started by: sulfur on Feb 7^th, 2010, 8:01pm)

Title: Bool Function
Post by sulfur on Feb 7^th, 2010, 8:01pm

Construct a function which returns TRUE or FALSE.
It returns TRUE if the function is invoked less than n times in last m minutes else returns FALSE.
The expected answer is to be done in constant space.

e.g. n=5 times ; m=2 minutes

i^th Minute No. of times Func called

1 3 ( Returns 3 TRUE's )
2 2 ( Returns 2 TRUE's )
3 4 ( Returns 3 TRUE's & 1 FALSE )

Title: Re: Bool Function
Post by Grimbal on Feb 8^th, 2010, 1:20am

I am afraid you will need O(m) space.

Title: Re: Bool Function
Post by Hippo on Feb 8^th, 2010, 3:28am

on 02/08/10 at 01:20:43, Grimbal wrote:

I am afraid you will need O(m) space.

O(n), not O(m) I think. Or may be in O(min(m,n)).

Title: Re: Bool Function
Post by sulfur on Feb 8^th, 2010, 7:02am

Quote:

I am afraid you will need O(m) space.

Yeah. You are absolutely right. The implementation code needs O(m) space. I used Queue for that . But the interviewer was interested in looking a solution which involves constant space. :-[

Title: Re: Bool Function
Post by Grimbal on Feb 8^th, 2010, 7:44am

on 02/08/10 at 03:28:37, Hippo wrote:

O(n), not O(m) I think. Or may be in O(min(m,n)).

I agree with O(min(m,n)).

[hide]Either store the time of the last n calls, or store the counters for the last m minutes.[/hide]

Title: Re: Bool Function
Post by JohanC on Feb 8^th, 2010, 8:30am

[quote author=sulfur link=board=riddles_cs;num=1265601681;start=0#3 date=02/08/10 at 07:02:56]Yeah. You are absolutely right. The implementation code needs O(m) space. I used Queue for that . But the interviewer was interested in looking a solution which involves constant space. :-[/quote]
Maybe she/he expected you to tell that an exact solution seems impossible, but that good aproximations could be practical?
So, rephrasing, what would be the best approximation using constant space?

Title: Re: Bool Function
Post by bmudiam on Feb 8^th, 2010, 6:48pm

I will maintain two variables.

var1 = number of minutes passed
var2 = number of calls made.

Now my function will look at follows.
<code>
if( var1 > m || var2 > n)
return false
else
return true
</code>

I think this is constant time as you are storing only two variables.

Title: Re: Bool Function
Post by Grimbal on Feb 9^th, 2010, 5:48am

And when and how do you update var1 and var2?

Title: Re: Bool Function
Post by bmudiam on Feb 9^th, 2010, 5:50am

after every minute and every function call.

Title: Re: Bool Function
Post by Grimbal on Feb 9^th, 2010, 6:09am

You increment var1 every minute? That would mean after m minutes you always return false. In the example above, you would always return FALSE in the 3rd minute, and not 3 time TRUE and 1 time FALSE.

Title: Re: Bool Function
Post by Paragon on Feb 9^th, 2010, 8:17am

Just to be precise shouldn't it be O(min(m,n-1))?
[hideb]You can store the latest call on stack. And after we are done with the comparisons replace it with the oldest.[/hideb]

Title: Re: Bool Function
Post by Aryabhatta on Feb 9^th, 2010, 10:50am

on 02/09/10 at 08:17:00, Paragon wrote:

Just to be precise shouldn't it be O(min(m,n-1))?
[hideb]You can store the latest call on stack. And after we are done with the comparisons replace it with the oldest.[/hideb]

Well if you really want to be precise, the space usage is Omega(min(m,n)).

Title: Re: Bool Function
Post by Hippo on Feb 9^th, 2010, 3:29pm

Or http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ctheta.gif(min(m,n)). :), Yes I have known the O was not accurate, but I didn't want to confuse by correcting 2 things in on reply. Later I have discovered both m and n solutions exist ...

Title: Re: Bool Function
Post by Grimbal on Feb 9^th, 2010, 5:05pm

O(min(m,n)), O(min(m,n-1)) and O(min(2m+1000,3n+1000)*1000) are all the same.

Title: Re: Bool Function
Post by Aryabhatta on Feb 9^th, 2010, 9:29pm

on 02/09/10 at 15:29:31, Hippo wrote:

True :)

Title: Re: Bool Function
Post by srikanth.iiita on Feb 9^th, 2010, 10:11pm

For each test case.. we are required to take at least
m (minutes information & number of calls in each minute).. so the input should be O(m) .
Can't we use the same storage of O(m) for solving.???