Author |
Topic: Bool Function (Read 630 times) |
|
sulfur
Newbie
Posts: 18
|
 |
Bool Function
« on: Feb 7th, 2010, 8:01pm » |
 Quote  Modify
|
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
ith 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 )
|
| « Last Edit: Feb 7th, 2010, 8:03pm by sulfur » |
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: Bool Function
« Reply #1 on: Feb 8th, 2010, 1:20am » |
Quote Modify
|
I am afraid you will need O(m) space.
|
| « Last Edit: Feb 8th, 2010, 1:20am by Grimbal » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Bool Function
« Reply #2 on: Feb 8th, 2010, 3:28am » |
Quote Modify
|
on Feb 8th, 2010, 1:20am, 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)).
|
| « Last Edit: Feb 8th, 2010, 3:30am by Hippo » |
IP Logged |
|
|
|
sulfur
Newbie
Posts: 18
|
|
Re: Bool Function
« Reply #3 on: Feb 8th, 2010, 7:02am » |
Quote Modify
|
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. 
|
| « Last Edit: Feb 8th, 2010, 7:03am by sulfur » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Bool Function
« Reply #4 on: Feb 8th, 2010, 7:44am » |
Quote Modify
|
on Feb 8th, 2010, 3:28am, Hippo wrote:
O(n), not O(m) I think. Or may be in O(min(m,n)). |
|
I agree with O(min(m,n)).
Either store the time of the last n calls, or store the counters for the last m minutes.
|
|
IP Logged |
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Bool Function
« Reply #5 on: Feb 8th, 2010, 8:30am » |
Quote Modify
|
on Feb 8th, 2010, 7:02am, sulfur wrote:| 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. |
|
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?
|
|
IP Logged |
|
|
|
bmudiam
Junior Member
Gender:
Posts: 55
|
|
Re: Bool Function
« Reply #6 on: Feb 8th, 2010, 6:48pm » |
Quote Modify
|
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.
|
|
IP Logged |
“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Bool Function
« Reply #7 on: Feb 9th, 2010, 5:48am » |
Quote Modify
|
And when and how do you update var1 and var2?
|
|
IP Logged |
|
|
|
bmudiam
Junior Member
Gender:
Posts: 55
|
|
Re: Bool Function
« Reply #8 on: Feb 9th, 2010, 5:50am » |
Quote Modify
|
after every minute and every function call.
|
|
IP Logged |
“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Bool Function
« Reply #9 on: Feb 9th, 2010, 6:09am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Paragon
Newbie
Posts: 2
|
|
Re: Bool Function
« Reply #10 on: Feb 9th, 2010, 8:17am » |
Quote Modify
|
Just to be precise shouldn't it be O(min(m,n-1))?
| hidden: | | You can store the latest call on stack. And after we are done with the comparisons replace it with the oldest. |
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Bool Function
« Reply #11 on: Feb 9th, 2010, 10:50am » |
Quote Modify
|
on Feb 9th, 2010, 8:17am, Paragon wrote:Just to be precise shouldn't it be O(min(m,n-1))?
| hidden: | | You can store the latest call on stack. And after we are done with the comparisons replace it with the oldest. |
|
|
Well if you really want to be precise, the space usage is Omega(min(m,n)).
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Bool Function
« Reply #12 on: Feb 9th, 2010, 3:29pm » |
Quote Modify
|
Or  (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 ...
|
| « Last Edit: Feb 9th, 2010, 3:29pm by Hippo » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Bool Function
« Reply #13 on: Feb 9th, 2010, 5:05pm » |
Quote Modify
|
O(min(m,n)), O(min(m,n-1)) and O(min(2m+1000,3n+1000)*1000) are all the same.
|
| « Last Edit: Feb 9th, 2010, 5:07pm by Grimbal » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Bool Function
« Reply #14 on: Feb 9th, 2010, 9:29pm » |
Quote Modify
|
on Feb 9th, 2010, 3:29pm, Hippo wrote:| Or (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 ... |
|
True
|
|
IP Logged |
|
|
|
srikanth.iiita
Newbie
Posts: 33
|
|
Re: Bool Function
« Reply #15 on: Feb 9th, 2010, 10:11pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print