Re: [algogeeks] Regex tester
ya, it is correct, i misunderstood it..
any optimization on the same though ?
On Fri, Dec 28, 2012 at 9:55 AM, shady sinv...@gmail.com wrote:
@ritesh
umm, well here's a simple testcase to show the problem in the code..
isMatch(aa, a*)
On Thu, Dec 27, 2012 at 7:17 PM, Ritesh Mishra rforr...@gmail.com wrote:
@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.com
wrote:
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
--
--
--
Re: [algogeeks] Linked List question
@Sanjeev: Set a pointer p to the first node. Traverse the list. When at the
kth node, set p to the kth node with probability 1/k. When you reach the
end of the list, return p, which will point to a random node with uniform
probability.
Dave
On Thursday, December 27, 2012 11:18:20 PM UTC-6, Sanjeev wrote:
i mean the length of the linked list is not known to us.
@udit how can we do this in single traversal ? i think we need to traverse
the linked list twice in your case.
Please reply if i am wrong ?
On Thu, Dec 27, 2012 at 10:48 PM, Udit Agarwal udit...@gmail.comjavascript:
wrote:
If the length of the linked is infinite then the above algo would do
the needful.
In case you have a finite length linked list, then you can normalize
the random value using following:
Suppose length of linked list is: l
random number is: r; and r l
then new random number would be: r1 = r%l;
now again use the above algo using new random number r1;
On Thu, Dec 27, 2012 at 4:12 PM, Vineeth vineet...@gmail.comjavascript:
wrote:
You said : Given a linked list of infinite length
On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
naveenshukla...@gmail.com javascript: wrote:
But suppose a random number generate a value 5 and your linked list
has only
four elements. In that case what would be the answer ???
On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri
hpre...@gmail.com javascript:
wrote:
Well my algo will be Something like this
1 Get a Random number. Perhaps You can have the function like
Randon(List
*head, int Randomnumber)
2 Use the function argument Randomnumber to loop the list.
i.e. for(int count=0;count=Randomnumber;count++ ){
head = head - next;
}
3 print (head-value);
4 return ;
Now as we are using byvalue when we return the value of head remains
the
same old head value. So everytime we call we are traversing the same
old
list.
The Random variable can be taken inside the function itself if the
user
is not taking the random value.
i.e. int Randomnumber = random(); and now the user can calll Simple
Random(head);
On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla
naveenshukla...@gmail.com javascript: wrote:
random node
--
--
With Best Wishes
From:
Naveen Shukla
IIIT Allahabad
B.Tech IT 4th year
Mob No: 07860896972
E-mail naveenshukla...@gmail.com javascript:
--
--
--
Udit Agarwal
B.Tech. ( Information Technology ) , 7th Semester,
Indian Institute of Information Technology
Allahabad - 211012, India
Email : udit...@gmail.com javascript:
Mobile: +91-9411656264
--
--
With Best Wishes
From:
Naveen Shukla
IIIT Allahabad
B.Tech IT 4th year
Mob No: 07860896972
E-mail naveenshukla...@gmail.com javascript:
--
Re: [algogeeks] Linked List question
@Dave: U said that the node p returned will be assigned to some kth
node with probability 1/k. then the probability for p to be assigned
to 1,2,3... nodes would be like 1/1, 1/2, 1/3, and so on.. the how is
the node p is assigned with uniform probability.
On Fri, Dec 28, 2012 at 7:35 PM, Dave dave_and_da...@juno.com wrote:
@Sanjeev: Set a pointer p to the first node. Traverse the list. When at the
kth node, set p to the kth node with probability 1/k. When you reach the end
of the list, return p, which will point to a random node with uniform
probability.
Dave
On Thursday, December 27, 2012 11:18:20 PM UTC-6, Sanjeev wrote:
i mean the length of the linked list is not known to us.
@udit how can we do this in single traversal ? i think we need to traverse
the linked list twice in your case.
Please reply if i am wrong ?
On Thu, Dec 27, 2012 at 10:48 PM, Udit Agarwal udit...@gmail.com wrote:
If the length of the linked is infinite then the above algo would do
the needful.
In case you have a finite length linked list, then you can normalize
the random value using following:
Suppose length of linked list is: l
random number is: r; and r l
then new random number would be: r1 = r%l;
now again use the above algo using new random number r1;
On Thu, Dec 27, 2012 at 4:12 PM, Vineeth vineet...@gmail.com wrote:
You said : Given a linked list of infinite length
On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
naveenshukla...@gmail.com wrote:
But suppose a random number generate a value 5 and your linked list
has only
four elements. In that case what would be the answer ???
On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri
hpre...@gmail.com
wrote:
Well my algo will be Something like this
1 Get a Random number. Perhaps You can have the function like
Randon(List
*head, int Randomnumber)
2 Use the function argument Randomnumber to loop the list.
i.e. for(int count=0;count=Randomnumber;count++ ){
head = head - next;
}
3 print (head-value);
4 return ;
Now as we are using byvalue when we return the value of head remains
the
same old head value. So everytime we call we are traversing the same
old
list.
The Random variable can be taken inside the function itself if the
user
is not taking the random value.
i.e. int Randomnumber = random(); and now the user can calll Simple
Random(head);
On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla
naveenshukla...@gmail.com wrote:
random node
--
--
With Best Wishes
From:
Naveen Shukla
IIIT Allahabad
B.Tech IT 4th year
Mob No: 07860896972
E-mail naveenshukla...@gmail.com
--
--
--
Udit Agarwal
B.Tech. ( Information Technology ) , 7th Semester,
Indian Institute of Information Technology
Allahabad - 211012, India
Email : udit...@gmail.com
Mobile: +91-9411656264
--
--
With Best Wishes
From:
Naveen Shukla
IIIT Allahabad
B.Tech IT 4th year
Mob No: 07860896972
E-mail naveenshukla...@gmail.com
--
--
Udit Agarwal
B.Tech. ( Information Technology ) , 7th Semester,
Indian Institute of Information Technology
Allahabad - 211012, India
Email : uditii...@gmail.com
Mobile: +91-9411656264
--
[algogeeks] Skyline extraction
How to extract the skyline from the rectangles ? Given a set of rectangles with x coordinates and height, how to find the skyline ? --
Re: [algogeeks] Linked List question
@Udit: Here is the proof: At step k, node k is selected with probability
1/k. On the (k+1)st step, node k is replaced with probability 1/(k+1). Thus
it is retained with probability 1 - 1/(k+1) = k/(k+1). On subsequent steps,
node k is retained with probabilities (k+1)/(k+2), (k+2)/(k+3), ...,
(n-1)/n. Thus, node k is selected on the kth step and then retained until
the end of the list with probability 1/k * k/(k+1) * (k+1)/(k+2) * ... *
(n-1) / n. Each denominator cancels with the succeeding numerator, so the
product collapses to 1/n.
Dave
On Friday, December 28, 2012 10:46:17 AM UTC-6, Udit Agarwal wrote:
@Dave: U said that the node p returned will be assigned to some kth
node with probability 1/k. then the probability for p to be assigned
to 1,2,3... nodes would be like 1/1, 1/2, 1/3, and so on.. the how is
the node p is assigned with uniform probability.
On Fri, Dec 28, 2012 at 7:35 PM, Dave dave_an...@juno.com javascript:
wrote:
@Sanjeev: Set a pointer p to the first node. Traverse the list. When at
the
kth node, set p to the kth node with probability 1/k. When you reach the
end
of the list, return p, which will point to a random node with uniform
probability.
Dave
On Thursday, December 27, 2012 11:18:20 PM UTC-6, Sanjeev wrote:
i mean the length of the linked list is not known to us.
@udit how can we do this in single traversal ? i think we need to
traverse
the linked list twice in your case.
Please reply if i am wrong ?
On Thu, Dec 27, 2012 at 10:48 PM, Udit Agarwal udit...@gmail.com
wrote:
If the length of the linked is infinite then the above algo would do
the needful.
In case you have a finite length linked list, then you can normalize
the random value using following:
Suppose length of linked list is: l
random number is: r; and r l
then new random number would be: r1 = r%l;
now again use the above algo using new random number r1;
On Thu, Dec 27, 2012 at 4:12 PM, Vineeth vineet...@gmail.com wrote:
You said : Given a linked list of infinite length
On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
naveenshukla...@gmail.com wrote:
But suppose a random number generate a value 5 and your linked list
has only
four elements. In that case what would be the answer ???
On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri
hpre...@gmail.com
wrote:
Well my algo will be Something like this
1 Get a Random number. Perhaps You can have the function like
Randon(List
*head, int Randomnumber)
2 Use the function argument Randomnumber to loop the list.
i.e. for(int count=0;count=Randomnumber;count++ ){
head = head - next;
}
3 print (head-value);
4 return ;
Now as we are using byvalue when we return the value of head
remains
the
same old head value. So everytime we call we are traversing the
same
old
list.
The Random variable can be taken inside the function itself if
the
user
is not taking the random value.
i.e. int Randomnumber = random(); and now the user can calll
Simple
Random(head);
On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla
naveenshukla...@gmail.com wrote:
random node
--
--
With Best Wishes
From:
Naveen Shukla
IIIT Allahabad
B.Tech IT 4th year
Mob No: 07860896972
E-mail naveenshukla...@gmail.com
--
--
--
Udit Agarwal
B.Tech. ( Information Technology ) , 7th Semester,
Indian Institute of Information Technology
Allahabad - 211012, India
Email : udit...@gmail.com
Mobile: +91-9411656264
--
--
With Best Wishes
From:
Naveen Shukla
IIIT Allahabad
B.Tech IT 4th year
Mob No: 07860896972
E-mail naveenshukla...@gmail.com
--
--
Udit Agarwal
B.Tech. ( Information Technology ) , 7th Semester,
Indian Institute of Information Technology
Allahabad - 211012, India
Email : udit...@gmail.com javascript:
Mobile: +91-9411656264
--
