Re: [algogeeks] Re: Max-Overlapping Intervals
it is better to use Binary Index Tree ( Fenwick Tree) with time complexity O(log n) to update and O(n * log n) for finding max overlapping interval . http://community.topcoder.com/tc?module=Staticd1=tutorialsd2=binaryIndexedTrees this link can be useful for understanding how it will work. Regards, Ritesh Kumar Mishra Information Technology Third Year Undergraduate MNNIT Allahabad On Mon, Feb 25, 2013 at 10:46 AM, Sairam ravu...@gmail.com wrote: First sort the intervals So, in our example it will be as follows (2,7),(5,10),(6,15). make a map which has got interval with corresponding number of overlaps Now, iterate through each of the interval for(i=0;i(n-1);i++) for(j=0;jn;j++) update the map with the number of overlaps. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Amazon interview Question
@anurag : there is no need to SORT. as it will increase complexity O(n) to
O(n log n).
here is the correct code.. please look over it and notify me if i'm wrong .
T.C. = O( n )
// ex: 1 4 3 2 0 i'm explaining on behalf of it.
bool permute (int *arr , int N )
{
if ( N=1 ) return false;
for ( int i = N-2 ; i = 0 ; i-- )
{
if ( arr[i+1] arr[i]) // now i points to 1
{
for ( int j = N-1 ; j i ; j--)
{
if ( arr[i] arr[j]) // now j points to 2(just greater than
1 )
{
swap(arr[i],arr[j]) ;//this will generate 2 4 3 1 0
since 4310 are already sorted in reverse
//thus no need to sort again in
inc order rather than reversing
i++ ; j = N-1;
while(ij) swap(arr[i++],arr[j--]) ; // reversing the
seq 4..0 to 0..4
return true ;
}
}
}
}
return false ;
}
Regards,
Ritesh Kumar Mishra
Information Technology
Third Year Undergraduate
MNNIT Allahabad
On Mon, Dec 24, 2012 at 7:56 PM, marti amritsa...@gmail.com wrote:
I REPEAT, THERE is no need to SORT;
http://en.wikipedia.org/wiki/Permutation#Lexicographical%5Forder%5Fgeneration
On Friday, December 14, 2012 11:56:16 AM UTC+5:30, tapan rathi wrote:
For a given number, find the next greatest number which is just greater
than previous one and made up of same digits.
--
--
Re: [algogeeks] Regex tester
try to solve it by recursion .. http://www.leetcode.com/2011/09/regular-expression-matching.html Regards, Ritesh Kumar Mishra Information Technology Third Year Undergraduate MNNIT Allahabad On Sun, Dec 23, 2012 at 11:14 PM, Prem Krishna Chettri hprem...@gmail.comwrote: Well I can tell you Something about design pattern to solve this case.. What I mean is by using The State Machine Design Pattern, Anyone can solve this. but Ofcourse it is complicated. On Sun, Dec 23, 2012 at 11:01 PM, shady sinv...@gmail.com wrote: that's the point, Have to implement it from scratch... otherwise java has regex and matcher, pattern to solve it... On Sun, Dec 23, 2012 at 10:28 PM, saurabh singh saurab...@gmail.comwrote: If you need to implement this for some project then python and java have a very nice library Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sun, Dec 23, 2012 at 7:48 PM, shady sinv...@gmail.com wrote: http://stackoverflow.com/questions/13144590/to-check-if-two-strings-match-with-alphabets-digits-and-special-characters any solution for this. we need to implement such regex tester some complex cases : *string** regex * - * status* * * reesd re*.d - match re*eed reeed - match can some one help with this ? -- -- -- -- --
Re: [algogeeks] Regex tester
@shady : either the string will be stored in heap or stack. thus accessing
address in heap or stack is not going to give u seg fault . and rest things
are very well handled in the code :)
As saurabh sir has explained in thread
https://mail.google.com/mail/u/1/#inbox/13ba918bdb9aac9e
when seg fault occurs .
Regards,
Ritesh Kumar Mishra
Information Technology
Third Year Undergraduate
MNNIT Allahabad
On Thu, Dec 27, 2012 at 6:43 PM, ~*~VICKY~*~ venkat.jun...@gmail.comwrote:
I'm giving you a simple recursive code which i wrote long back. Please let
me know if it fails for any cases. Ignore the funny cout's It used to help
me debug and i'm lazy to remove it. :P :)
#includeiostream
#includestring
using namespace std;
/*
abasjc a*c
while(pattern[j] == '*' text[i] == pattern[j]) {i++; j++}
*/
bool match(string text, string pattern, int x, int y)
{
if(pattern.length() == y)
{
couthey\n;
return 1;
}
if(text.length() == x)
{
coutshit\n;
return 0;
}
if(pattern[y] == '.' || text[x] == pattern[y])
{
coutin matchendl;
return match(text,pattern,x+1,y+1);
}
if(pattern[y] == '*')
return match(text,pattern,x+1,y) || match(text,pattern,x+1,y+1) ||
match(text,pattern,x,y+1);
if(text[x] != pattern[y])
{
coutshit1\n;
return 0;
}
}
int main()
{
string text,pattern;
cin text pattern;
cout match(text, pattern,0, 0);
}
On Thu, Dec 27, 2012 at 6:10 PM, shady sinv...@gmail.com wrote:
Thanks for the link Ritesh,
if (isMatch(s, p+2)) return true;
isnt this line incorrect in the code, as it can lead to segmentation
fault... how can we directly access p+2 element, we know for sure that p is
not '\0', but p+1 element can be '\0' , therefore leading to p+2 to be
undefined.
On Thu, Dec 27, 2012 at 6:23 AM, Ritesh Mishra rforr...@gmail.comwrote:
try to solve it by recursion ..
http://www.leetcode.com/2011/09/regular-expression-matching.html
Regards,
Ritesh Kumar Mishra
Information Technology
Third Year Undergraduate
MNNIT Allahabad
On Sun, Dec 23, 2012 at 11:14 PM, Prem Krishna Chettri
hprem...@gmail.com wrote:
Well I can tell you Something about design pattern to solve this case..
What I mean is by using The State Machine Design Pattern, Anyone
can solve this. but Ofcourse it is complicated.
On Sun, Dec 23, 2012 at 11:01 PM, shady sinv...@gmail.com wrote:
that's the point, Have to implement it from scratch... otherwise java
has regex and matcher, pattern to solve it...
On Sun, Dec 23, 2012 at 10:28 PM, saurabh singh
saurab...@gmail.comwrote:
If you need to implement this for some project then python and java
have a very nice library
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Sun, Dec 23, 2012 at 7:48 PM, shady sinv...@gmail.com wrote:
http://stackoverflow.com/questions/13144590/to-check-if-two-strings-match-with-alphabets-digits-and-special-characters
any solution for this. we need to implement such regex
tester
some complex cases :
*string** regex * - * status*
*
*
reesd re*.d - match
re*eed reeed - match
can some one help with this ?
--
--
--
--
--
--
--
Cheers,
Vicky
--
--
