Re: [algogeeks] Re: Amazon Interview Questions
Ans to *Boundary traversal of a tree. Write the code.
*1) you need to for preoder oder for left most tree with flag and post
order traversal for right most tree with flag.
2) the role of flag would be to decide wther to print or not like in case
of left subtree ,flag would be tree as u knw that
in preorder traversal left element would be boundary and once u go
right make it false .. same for right subtree:
Code snippet would look like this :
void printleft (struct node *root, bool flag) {
if (!root) return;
if (flag || (!root-left !root-right)) {
cout root-data;
}
printleft(root-left, true);
printleft(root-right, false);
}
this is preorder for left subtree , do post order for right subtree like :
void printright (struct node *root, bool flag) {
if (!root) return;
printright(root-left, false);
printright(root-right, true);
if (flag || (!root-left !root-right)) cout root-data;
}
*
*let me knw if anything seems confusing.
On Sun, Mar 10, 2013 at 4:59 PM, Nishant Pandey
nishant.bits.me...@gmail.com wrote:
i have few questions regarding ur problems pratik :
1) A tree with only parent pointer, how to find LCA?
Doubt : do u mean only root of the tree is given , i am assuming root
along with two nodes address whose lca need to
find too is given , i am right ?
2) Find top k searched elements from a continuous stream of data.
Doubt : what do u mean by top k search element can u please explain
little bit with exmple.
I would love to post solution for you provided clear my doubts
may i knw which Amazon's round questions are they ?
On Mon, Feb 18, 2013 at 1:28 AM, Tushar tushicom...@gmail.com wrote:
It looks as if you have just pasted some Amazon interview questions on
this forum.
These are pretty common questions.
Try to come up with your own answers.
Do some research on google and previous posts on this forum. You'll get
answers to all of them.
If you have some idea and want to discuss that, then post different posts
for each questions as arun recommended along with your understanding of the
question and your approach.
All the best
On Saturday, 9 February 2013 14:45:35 UTC+5:30, Pratik Mehta wrote:
Hi All,
I need ur help in solving few questions.
Would you please help me out *BY GIVING THE ALGORITHM AND THE LOGIC
BEHIND IT and it's DEEP EXPLANATION IF POSSIBLE?*
*
*
*a. Kadane’s Algo.*
*
*
*b. Linked-list intersection point.*
*
[A tree with only parent pointer, how to find LCA?]
*
*
*
*
c. Design a stack which can perform findMax in O(1).
*
*
*
*d. Set of stocks for each day have been given. Need to find the days
on which I buy and sell share to earn max profit, alongwith finding the max
profit.*
*
e. Find top k searched elements from a continuous stream of data.
*
*
*
*f. Given a linked-list and 2 integers k m. Reverse the linked-list
till k elements and then traverse till m elements and repeat.*
*Write production quality code.*
*
*
*g. An array of elements have been given. Find for each element, first
max element to its right.*
*
*
*h. Boundary traversal of a tree. Write the code.*
Please help me out...
Thanks in advance...
Thanks Regards,
Pratik Mayur Mehta.
--
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.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Amazon Interview Questions
i have few questions regarding ur problems pratik : 1) A tree with only parent pointer, how to find LCA? Doubt : do u mean only root of the tree is given , i am assuming root along with two nodes address whose lca need to find too is given , i am right ? 2) Find top k searched elements from a continuous stream of data. Doubt : what do u mean by top k search element can u please explain little bit with exmple. I would love to post solution for you provided clear my doubts may i knw which Amazon's round questions are they ? On Mon, Feb 18, 2013 at 1:28 AM, Tushar tushicom...@gmail.com wrote: It looks as if you have just pasted some Amazon interview questions on this forum. These are pretty common questions. Try to come up with your own answers. Do some research on google and previous posts on this forum. You'll get answers to all of them. If you have some idea and want to discuss that, then post different posts for each questions as arun recommended along with your understanding of the question and your approach. All the best On Saturday, 9 February 2013 14:45:35 UTC+5:30, Pratik Mehta wrote: Hi All, I need ur help in solving few questions. Would you please help me out *BY GIVING THE ALGORITHM AND THE LOGIC BEHIND IT and it's DEEP EXPLANATION IF POSSIBLE?* * * *a. Kadane’s Algo.* * * *b. Linked-list intersection point.* * [A tree with only parent pointer, how to find LCA?] * * * * c. Design a stack which can perform findMax in O(1). * * * *d. Set of stocks for each day have been given. Need to find the days on which I buy and sell share to earn max profit, alongwith finding the max profit.* * e. Find top k searched elements from a continuous stream of data. * * * *f. Given a linked-list and 2 integers k m. Reverse the linked-list till k elements and then traverse till m elements and repeat.* *Write production quality code.* * * *g. An array of elements have been given. Find for each element, first max element to its right.* * * *h. Boundary traversal of a tree. Write the code.* Please help me out... Thanks in advance... Thanks Regards, Pratik Mayur Mehta. -- 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. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Amazon Interview Questions
these questions were asked for software dev. in amazon ? which round .
looks like straight easy questions...
On Sun, Mar 10, 2013 at 5:58 PM, Nishant Pandey
nishant.bits.me...@gmail.com wrote:
Ans to *Boundary traversal of a tree. Write the code.
*1) you need to for preoder oder for left most tree with flag and post
order traversal for right most tree with flag.
2) the role of flag would be to decide wther to print or not like in case
of left subtree ,flag would be tree as u knw that
in preorder traversal left element would be boundary and once u go
right make it false .. same for right subtree:
Code snippet would look like this :
void printleft (struct node *root, bool flag) {
if (!root) return;
if (flag || (!root-left !root-right)) {
cout root-data;
}
printleft(root-left, true);
printleft(root-right, false);
}
this is preorder for left subtree , do post order for right subtree like :
void printright (struct node *root, bool flag) {
if (!root) return;
printright(root-left, false);
printright(root-right, true);
if (flag || (!root-left !root-right)) cout root-data;
}
*
*let me knw if anything seems confusing.
On Sun, Mar 10, 2013 at 4:59 PM, Nishant Pandey
nishant.bits.me...@gmail.com wrote:
i have few questions regarding ur problems pratik :
1) A tree with only parent pointer, how to find LCA?
Doubt : do u mean only root of the tree is given , i am assuming root
along with two nodes address whose lca need to
find too is given , i am right ?
2) Find top k searched elements from a continuous stream of data.
Doubt : what do u mean by top k search element can u please explain
little bit with exmple.
I would love to post solution for you provided clear my doubts
may i knw which Amazon's round questions are they ?
On Mon, Feb 18, 2013 at 1:28 AM, Tushar tushicom...@gmail.com wrote:
It looks as if you have just pasted some Amazon interview questions on
this forum.
These are pretty common questions.
Try to come up with your own answers.
Do some research on google and previous posts on this forum. You'll get
answers to all of them.
If you have some idea and want to discuss that, then post different
posts for each questions as arun recommended along with your understanding
of the question and your approach.
All the best
On Saturday, 9 February 2013 14:45:35 UTC+5:30, Pratik Mehta wrote:
Hi All,
I need ur help in solving few questions.
Would you please help me out *BY GIVING THE ALGORITHM AND THE LOGIC
BEHIND IT and it's DEEP EXPLANATION IF POSSIBLE?*
*
*
*a. Kadane’s Algo.*
*
*
*b. Linked-list intersection point.*
*
[A tree with only parent pointer, how to find LCA?]
*
*
*
*
c. Design a stack which can perform findMax in O(1).
*
*
*
*d. Set of stocks for each day have been given. Need to find the days
on which I buy and sell share to earn max profit, alongwith finding the max
profit.*
*
e. Find top k searched elements from a continuous stream of data.
*
*
*
*f. Given a linked-list and 2 integers k m. Reverse the linked-list
till k elements and then traverse till m elements and repeat.*
*Write production quality code.*
*
*
*g. An array of elements have been given. Find for each element, first
max element to its right.*
*
*
*h. Boundary traversal of a tree. Write the code.*
Please help me out...
Thanks in advance...
Thanks Regards,
Pratik Mayur Mehta.
--
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.
For more options, visit https://groups.google.com/groups/opt_out.
--
Rohit Jangid
Graduate
Deptt. of Computer Engineering
NSIT, Delhi University, India
--
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.
Re: [algogeeks] Re: amazon interview questions
Hassan geke should not be a valid string. The question states which have the same substring following it so here e follows e. There is no precondition that it has to follow immediate. Utsav: can you clarify? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:32 PM, Hassan Monfared hmonfa...@gmail.comwrote: yes It's valid, cuz it doesn't have any repeated substring next together On Tue, Jun 5, 2012 at 7:08 PM, Lomash Goyal lomesh.go...@gmail.comwrote: is geke is a invalid strng? On Tue, Jun 5, 2012 at 12:17 PM, Hassan Monfared hmonfa...@gmail.comwrote: Ashish: the algorithm passes over string and check if there is any substring with len=1 is repeated or not. if not, tries for substring with len 2,... and so on. max length of substring which can be repeated can be at most N/2. Regards, On Tue, Jun 5, 2012 at 10:48 AM, Ashish Goel ashg...@gmail.com wrote: The problem suggests that a character can't be more than once present and thereby it can be done by just having s bitmap and if a char repeats, any longer repeating substring will have those char repeated atleast twice, hence O(n) solution. Also, Hasaan: how is your algo O(n2) for for-while-for chain? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:42 AM, Ashish Goel ashg...@gmail.com wrote: Hassan, can you explain your algo? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared hmonfa...@gmail.comwrote: for -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Lomash Goyal * * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon interview questions
nope geke is valid string.. here is the link from where question was taken http://geeksforgeeks.org/forum/topic/amazon-interview-question-password-checker On Wed, Jun 6, 2012 at 11:44 AM, Ashish Goel ashg...@gmail.com wrote: Hassan geke should not be a valid string. The question states which have the same substring following it so here e follows e. There is no precondition that it has to follow immediate. Utsav: can you clarify? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:32 PM, Hassan Monfared hmonfa...@gmail.comwrote: yes It's valid, cuz it doesn't have any repeated substring next together On Tue, Jun 5, 2012 at 7:08 PM, Lomash Goyal lomesh.go...@gmail.comwrote: is geke is a invalid strng? On Tue, Jun 5, 2012 at 12:17 PM, Hassan Monfared hmonfa...@gmail.comwrote: Ashish: the algorithm passes over string and check if there is any substring with len=1 is repeated or not. if not, tries for substring with len 2,... and so on. max length of substring which can be repeated can be at most N/2. Regards, On Tue, Jun 5, 2012 at 10:48 AM, Ashish Goel ashg...@gmail.com wrote: The problem suggests that a character can't be more than once present and thereby it can be done by just having s bitmap and if a char repeats, any longer repeating substring will have those char repeated atleast twice, hence O(n) solution. Also, Hasaan: how is your algo O(n2) for for-while-for chain? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:42 AM, Ashish Goel ashg...@gmail.comwrote: Hassan, can you explain your algo? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared hmonfa...@gmail.com wrote: for -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Lomash Goyal * * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon interview questions
geke is valid. BTW if you changeif(i=len) toif(i0) my code outputs geke is invalid.( what you desired) if geke is invalid regarding to the question, then you can achieve the answer in nLogn by sorting strings :s[0..n-1], s[1..n-1],s[n-1..n-1] and comparing adjacent members. Regards On Wed, Jun 6, 2012 at 11:52 AM, atul anand atul.87fri...@gmail.com wrote: nope geke is valid string.. here is the link from where question was taken http://geeksforgeeks.org/forum/topic/amazon-interview-question-password-checker On Wed, Jun 6, 2012 at 11:44 AM, Ashish Goel ashg...@gmail.com wrote: Hassan geke should not be a valid string. The question states which have the same substring following it so here e follows e. There is no precondition that it has to follow immediate. Utsav: can you clarify? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:32 PM, Hassan Monfared hmonfa...@gmail.comwrote: yes It's valid, cuz it doesn't have any repeated substring next together On Tue, Jun 5, 2012 at 7:08 PM, Lomash Goyal lomesh.go...@gmail.comwrote: is geke is a invalid strng? On Tue, Jun 5, 2012 at 12:17 PM, Hassan Monfared hmonfa...@gmail.comwrote: Ashish: the algorithm passes over string and check if there is any substring with len=1 is repeated or not. if not, tries for substring with len 2,... and so on. max length of substring which can be repeated can be at most N/2. Regards, On Tue, Jun 5, 2012 at 10:48 AM, Ashish Goel ashg...@gmail.comwrote: The problem suggests that a character can't be more than once present and thereby it can be done by just having s bitmap and if a char repeats, any longer repeating substring will have those char repeated atleast twice, hence O(n) solution. Also, Hasaan: how is your algo O(n2) for for-while-for chain? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:42 AM, Ashish Goel ashg...@gmail.comwrote: Hassan, can you explain your algo? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared hmonfa...@gmail.com wrote: for -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Lomash Goyal * * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon interview questions
@ashish:- geke is valid as repeated substrings should be immediate. On Wed, Jun 6, 2012 at 1:44 PM, Hassan Monfared hmonfa...@gmail.com wrote: geke is valid. BTW if you changeif(i=len) toif(i0) my code outputs geke is invalid.( what you desired) if geke is invalid regarding to the question, then you can achieve the answer in nLogn by sorting strings :s[0..n-1], s[1..n-1],s[n-1..n-1] and comparing adjacent members. Regards On Wed, Jun 6, 2012 at 11:52 AM, atul anand atul.87fri...@gmail.comwrote: nope geke is valid string.. here is the link from where question was taken http://geeksforgeeks.org/forum/topic/amazon-interview-question-password-checker On Wed, Jun 6, 2012 at 11:44 AM, Ashish Goel ashg...@gmail.com wrote: Hassan geke should not be a valid string. The question states which have the same substring following it so here e follows e. There is no precondition that it has to follow immediate. Utsav: can you clarify? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:32 PM, Hassan Monfared hmonfa...@gmail.comwrote: yes It's valid, cuz it doesn't have any repeated substring next together On Tue, Jun 5, 2012 at 7:08 PM, Lomash Goyal lomesh.go...@gmail.comwrote: is geke is a invalid strng? On Tue, Jun 5, 2012 at 12:17 PM, Hassan Monfared hmonfa...@gmail.comwrote: Ashish: the algorithm passes over string and check if there is any substring with len=1 is repeated or not. if not, tries for substring with len 2,... and so on. max length of substring which can be repeated can be at most N/2. Regards, On Tue, Jun 5, 2012 at 10:48 AM, Ashish Goel ashg...@gmail.comwrote: The problem suggests that a character can't be more than once present and thereby it can be done by just having s bitmap and if a char repeats, any longer repeating substring will have those char repeated atleast twice, hence O(n) solution. Also, Hasaan: how is your algo O(n2) for for-while-for chain? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:42 AM, Ashish Goel ashg...@gmail.comwrote: Hassan, can you explain your algo? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared hmonfa...@gmail.com wrote: for -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Lomash Goyal * * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *DARPAN BAWEJA* *3rd year, I.T* *MNNIT Allahabad* -- You received
Re: [algogeeks] Re: amazon interview questions
Thanks, my approach prepare a multimap of charcters and their positions by walking over the string. ashishis if is give string the multimap will have a-0 s-1,4,7 h-2,5 i-3,6 now for every character while walkingover the given string again, check from its multimap, if it is repeated, if not continue to next char. but if it is for all possible differences w.r.t this position, find the repeated string eg for s the values are 4-1=3 and 7-1=6 so if the string repeats than the next 3-1 or 6-1 chars should also have the diff exactly the same the next tow chars are h and i for h current pos is 2 and the diff is 5-2=3 which is good for i current pos is 3 and the diff is 6-3=3, hence shi is indeed a repeating string immediately and hence it is not a valid string. Had it not matched, we would have started for string of length 6 starting at a[7]. hope this helps. But this is not O(n) algo. O(n2) actually in worst case. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jun 6, 2012 at 12:52 PM, atul anand atul.87fri...@gmail.com wrote: nope geke is valid string.. here is the link from where question was taken http://geeksforgeeks.org/forum/topic/amazon-interview-question-password-checker On Wed, Jun 6, 2012 at 11:44 AM, Ashish Goel ashg...@gmail.com wrote: Hassan geke should not be a valid string. The question states which have the same substring following it so here e follows e. There is no precondition that it has to follow immediate. Utsav: can you clarify? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:32 PM, Hassan Monfared hmonfa...@gmail.comwrote: yes It's valid, cuz it doesn't have any repeated substring next together On Tue, Jun 5, 2012 at 7:08 PM, Lomash Goyal lomesh.go...@gmail.comwrote: is geke is a invalid strng? On Tue, Jun 5, 2012 at 12:17 PM, Hassan Monfared hmonfa...@gmail.comwrote: Ashish: the algorithm passes over string and check if there is any substring with len=1 is repeated or not. if not, tries for substring with len 2,... and so on. max length of substring which can be repeated can be at most N/2. Regards, On Tue, Jun 5, 2012 at 10:48 AM, Ashish Goel ashg...@gmail.comwrote: The problem suggests that a character can't be more than once present and thereby it can be done by just having s bitmap and if a char repeats, any longer repeating substring will have those char repeated atleast twice, hence O(n) solution. Also, Hasaan: how is your algo O(n2) for for-while-for chain? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:42 AM, Ashish Goel ashg...@gmail.comwrote: Hassan, can you explain your algo? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared hmonfa...@gmail.com wrote: for -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Lomash Goyal * * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this
Re: [algogeeks] Re: amazon interview questions
*tree substrings*
tree--|---mississippim .. mississippi
|
|---i--|---ssi--|---ssippi i .. ississippi
| | |
| | |---ppi issip,issipp,issippi
| |
| |---ppiip, ipp, ippi
|
|---s--|---si--|---ssippis .. ssissippi
| ||
| ||---ppi ssip, ssipp, ssippi
| |
| |---i--|---ssippi si .. sissippi
| |
| |---ppisip, sipp, sippi
|
|---p--|---pi p, pp, ppi
|
|---i p, pi
*--- Suffix Tree for mississippi ---*
in this example, any bifurcation implies that the substring is repeated(eg
i, s, ss, si, p, issi) and looks like this problem can be done while
forming the suffix trie
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Jun 5, 2012 at 12:28 AM, Abhishek Sharma abhi120...@gmail.comwrote:
I think it can be done by modifying the h-array and by making some changes
in KMP-algorithm
On Mon, Jun 4, 2012 at 9:35 AM, Jeevitesh jeeviteshshekha...@gmail.comwrote:
i have not implemented it but i can you an idea how to approach it.
Go to Each suffix in suffix or suffix array(I would prefer suffix array
as it is easier) traverse the each suffix till you encounter the first
letter of the suffix you are traversing and check to see this suppose i is
the index you found out the starting letter then check
s.substring(0,i)==s.substring(i,2i).
I hope you get the idea.
On Mon, Jun 4, 2012 at 9:14 AM, utsav sharma utsav.sharm...@gmail.comwrote:
@jeevitesh :- yes i am also thinking of suffix tree,
but i am facing problem in implementing it. did you implement it ??
On Mon, Jun 4, 2012 at 9:11 AM, utsav sharma
utsav.sharm...@gmail.comwrote:
@hassan :- it will not work for many strings as you are checking from
the mid of strings. try out ababcdef,aabc.
@atul :- it should be done in O(n).
On Sun, Jun 3, 2012 at 11:54 PM, Hassan Monfared
hmonfa...@gmail.comwrote:
yes it's not valid
On Sun, Jun 3, 2012 at 5:36 PM, anugrah anugrah.agra...@gmail.comwrote:
So any string with two same characters is not valid??
for example :
GEEK has E followed by E.
So GEEK is also invalid?
On Jun 3, 1:49 pm, Hassan Monfared hmonfa...@gmail.com wrote:
bool IsValid(string s)
{
for(int len=0;lens.len/2;len++)
{
int start1=0,start2=len+1;
while(start2s.size())
{
for(int i=0;ilen start2+is.size()
s[start1+i]=s[start2+i];i++);
if(i==len)
return false; //not valid
start1++;
start2++;
}
}
return true; // valid
}
On Sun, Jun 3, 2012 at 12:52 PM, atul anand
atul.87fri...@gmail.com wrote:
can be done with O(n^2) time complexity..
can it be done with O(n) complexity ???
On 6/3/12, utsav sharma utsav.sharm...@gmail.com wrote:
given a string tell wether it is valid or not.
string is valid if there is no substring which have the same
substring
following it.
these strings are not valid:- stringstring,geek123123rt,
abcadabcad,strngstingstrngsting
--
You received this message because you are subscribed to the
Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the
Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
Re: [algogeeks] Re: amazon interview questions
Hassan, can you explain your algo? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared hmonfa...@gmail.comwrote: for -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon interview questions
The problem suggests that a character can't be more than once present and thereby it can be done by just having s bitmap and if a char repeats, any longer repeating substring will have those char repeated atleast twice, hence O(n) solution. Also, Hasaan: how is your algo O(n2) for for-while-for chain? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:42 AM, Ashish Goel ashg...@gmail.com wrote: Hassan, can you explain your algo? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared hmonfa...@gmail.comwrote: for -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon interview questions
Ashish: the algorithm passes over string and check if there is any substring with len=1 is repeated or not. if not, tries for substring with len 2,... and so on. max length of substring which can be repeated can be at most N/2. Regards, On Tue, Jun 5, 2012 at 10:48 AM, Ashish Goel ashg...@gmail.com wrote: The problem suggests that a character can't be more than once present and thereby it can be done by just having s bitmap and if a char repeats, any longer repeating substring will have those char repeated atleast twice, hence O(n) solution. Also, Hasaan: how is your algo O(n2) for for-while-for chain? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:42 AM, Ashish Goel ashg...@gmail.com wrote: Hassan, can you explain your algo? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared hmonfa...@gmail.comwrote: for -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon interview questions
is geke is a invalid strng? On Tue, Jun 5, 2012 at 12:17 PM, Hassan Monfared hmonfa...@gmail.comwrote: Ashish: the algorithm passes over string and check if there is any substring with len=1 is repeated or not. if not, tries for substring with len 2,... and so on. max length of substring which can be repeated can be at most N/2. Regards, On Tue, Jun 5, 2012 at 10:48 AM, Ashish Goel ashg...@gmail.com wrote: The problem suggests that a character can't be more than once present and thereby it can be done by just having s bitmap and if a char repeats, any longer repeating substring will have those char repeated atleast twice, hence O(n) solution. Also, Hasaan: how is your algo O(n2) for for-while-for chain? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:42 AM, Ashish Goel ashg...@gmail.com wrote: Hassan, can you explain your algo? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared hmonfa...@gmail.comwrote: for -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Lomash Goyal * * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon interview questions
yes It's valid, cuz it doesn't have any repeated substring next together On Tue, Jun 5, 2012 at 7:08 PM, Lomash Goyal lomesh.go...@gmail.com wrote: is geke is a invalid strng? On Tue, Jun 5, 2012 at 12:17 PM, Hassan Monfared hmonfa...@gmail.comwrote: Ashish: the algorithm passes over string and check if there is any substring with len=1 is repeated or not. if not, tries for substring with len 2,... and so on. max length of substring which can be repeated can be at most N/2. Regards, On Tue, Jun 5, 2012 at 10:48 AM, Ashish Goel ashg...@gmail.com wrote: The problem suggests that a character can't be more than once present and thereby it can be done by just having s bitmap and if a char repeats, any longer repeating substring will have those char repeated atleast twice, hence O(n) solution. Also, Hasaan: how is your algo O(n2) for for-while-for chain? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jun 5, 2012 at 11:42 AM, Ashish Goel ashg...@gmail.com wrote: Hassan, can you explain your algo? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared hmonfa...@gmail.comwrote: for -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Lomash Goyal * * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon interview questions
@hasan :-ohhh sorry, i didn't see the outer loop
yeah, it works but it is O(n^2), required solution is of O(n).
On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared hmonfa...@gmail.comwrote:
utsav: It works fine, I did little bug fixing on boundaries as here goes :
bool IsValid(string s)
{
for(int len=1;len=s.size()/2;len++)
{
int start1=0,start2=len;
while(start2s.size())
{
int i=0;
for(;ilen start2+is.size() s[start1+i]==s[start2+i];i++);
if(i=len)
return false; //not valid
start1++;
start2++;
}
}
return true; // valid
}
It works for both input you provided. :)
On Mon, Jun 4, 2012 at 8:14 AM, utsav sharma utsav.sharm...@gmail.comwrote:
@jeevitesh :- yes i am also thinking of suffix tree,
but i am facing problem in implementing it. did you implement it ??
On Mon, Jun 4, 2012 at 9:11 AM, utsav sharma utsav.sharm...@gmail.comwrote:
@hassan :- it will not work for many strings as you are checking from
the mid of strings. try out ababcdef,aabc.
@atul :- it should be done in O(n).
On Sun, Jun 3, 2012 at 11:54 PM, Hassan Monfared hmonfa...@gmail.comwrote:
yes it's not valid
On Sun, Jun 3, 2012 at 5:36 PM, anugrah anugrah.agra...@gmail.comwrote:
So any string with two same characters is not valid??
for example :
GEEK has E followed by E.
So GEEK is also invalid?
On Jun 3, 1:49 pm, Hassan Monfared hmonfa...@gmail.com wrote:
bool IsValid(string s)
{
for(int len=0;lens.len/2;len++)
{
int start1=0,start2=len+1;
while(start2s.size())
{
for(int i=0;ilen start2+is.size()
s[start1+i]=s[start2+i];i++);
if(i==len)
return false; //not valid
start1++;
start2++;
}
}
return true; // valid
}
On Sun, Jun 3, 2012 at 12:52 PM, atul anand atul.87fri...@gmail.com
wrote:
can be done with O(n^2) time complexity..
can it be done with O(n) complexity ???
On 6/3/12, utsav sharma utsav.sharm...@gmail.com wrote:
given a string tell wether it is valid or not.
string is valid if there is no substring which have the same
substring
following it.
these strings are not valid:- stringstring,geek123123rt,
abcadabcad,strngstingstrngsting
--
You received this message because you are subscribed to the
Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Utsav Sharma,
NIT Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon interview questions
i have not implemented it but i can you an idea how to approach it.
Go to Each suffix in suffix or suffix array(I would prefer suffix array as
it is easier) traverse the each suffix till you encounter the first letter
of the suffix you are traversing and check to see this suppose i is the
index you found out the starting letter then check
s.substring(0,i)==s.substring(i,2i).
I hope you get the idea.
On Mon, Jun 4, 2012 at 9:14 AM, utsav sharma utsav.sharm...@gmail.comwrote:
@jeevitesh :- yes i am also thinking of suffix tree,
but i am facing problem in implementing it. did you implement it ??
On Mon, Jun 4, 2012 at 9:11 AM, utsav sharma utsav.sharm...@gmail.comwrote:
@hassan :- it will not work for many strings as you are checking from the
mid of strings. try out ababcdef,aabc.
@atul :- it should be done in O(n).
On Sun, Jun 3, 2012 at 11:54 PM, Hassan Monfared hmonfa...@gmail.comwrote:
yes it's not valid
On Sun, Jun 3, 2012 at 5:36 PM, anugrah anugrah.agra...@gmail.comwrote:
So any string with two same characters is not valid??
for example :
GEEK has E followed by E.
So GEEK is also invalid?
On Jun 3, 1:49 pm, Hassan Monfared hmonfa...@gmail.com wrote:
bool IsValid(string s)
{
for(int len=0;lens.len/2;len++)
{
int start1=0,start2=len+1;
while(start2s.size())
{
for(int i=0;ilen start2+is.size()
s[start1+i]=s[start2+i];i++);
if(i==len)
return false; //not valid
start1++;
start2++;
}
}
return true; // valid
}
On Sun, Jun 3, 2012 at 12:52 PM, atul anand atul.87fri...@gmail.com
wrote:
can be done with O(n^2) time complexity..
can it be done with O(n) complexity ???
On 6/3/12, utsav sharma utsav.sharm...@gmail.com wrote:
given a string tell wether it is valid or not.
string is valid if there is no substring which have the same
substring
following it.
these strings are not valid:- stringstring,geek123123rt,
abcadabcad,strngstingstrngsting
--
You received this message because you are subscribed to the
Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Thanks,
Jeevitesh Shekhar Singh.*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon interview questions
I think it can be done by modifying the h-array and by making some changes
in KMP-algorithm
On Mon, Jun 4, 2012 at 9:35 AM, Jeevitesh jeeviteshshekha...@gmail.comwrote:
i have not implemented it but i can you an idea how to approach it.
Go to Each suffix in suffix or suffix array(I would prefer suffix array as
it is easier) traverse the each suffix till you encounter the first letter
of the suffix you are traversing and check to see this suppose i is the
index you found out the starting letter then check
s.substring(0,i)==s.substring(i,2i).
I hope you get the idea.
On Mon, Jun 4, 2012 at 9:14 AM, utsav sharma utsav.sharm...@gmail.comwrote:
@jeevitesh :- yes i am also thinking of suffix tree,
but i am facing problem in implementing it. did you implement it ??
On Mon, Jun 4, 2012 at 9:11 AM, utsav sharma utsav.sharm...@gmail.comwrote:
@hassan :- it will not work for many strings as you are checking from
the mid of strings. try out ababcdef,aabc.
@atul :- it should be done in O(n).
On Sun, Jun 3, 2012 at 11:54 PM, Hassan Monfared hmonfa...@gmail.comwrote:
yes it's not valid
On Sun, Jun 3, 2012 at 5:36 PM, anugrah anugrah.agra...@gmail.comwrote:
So any string with two same characters is not valid??
for example :
GEEK has E followed by E.
So GEEK is also invalid?
On Jun 3, 1:49 pm, Hassan Monfared hmonfa...@gmail.com wrote:
bool IsValid(string s)
{
for(int len=0;lens.len/2;len++)
{
int start1=0,start2=len+1;
while(start2s.size())
{
for(int i=0;ilen start2+is.size()
s[start1+i]=s[start2+i];i++);
if(i==len)
return false; //not valid
start1++;
start2++;
}
}
return true; // valid
}
On Sun, Jun 3, 2012 at 12:52 PM, atul anand atul.87fri...@gmail.com
wrote:
can be done with O(n^2) time complexity..
can it be done with O(n) complexity ???
On 6/3/12, utsav sharma utsav.sharm...@gmail.com wrote:
given a string tell wether it is valid or not.
string is valid if there is no substring which have the same
substring
following it.
these strings are not valid:- stringstring,geek123123rt,
abcadabcad,strngstingstrngsting
--
You received this message because you are subscribed to the
Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Thanks,
Jeevitesh Shekhar Singh.*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Abhishek Sharma
Under-Graduate Student,
PEC University of Technology
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon interview questions
yes it's not valid
On Sun, Jun 3, 2012 at 5:36 PM, anugrah anugrah.agra...@gmail.com wrote:
So any string with two same characters is not valid??
for example :
GEEK has E followed by E.
So GEEK is also invalid?
On Jun 3, 1:49 pm, Hassan Monfared hmonfa...@gmail.com wrote:
bool IsValid(string s)
{
for(int len=0;lens.len/2;len++)
{
int start1=0,start2=len+1;
while(start2s.size())
{
for(int i=0;ilen start2+is.size()
s[start1+i]=s[start2+i];i++);
if(i==len)
return false; //not valid
start1++;
start2++;
}
}
return true; // valid
}
On Sun, Jun 3, 2012 at 12:52 PM, atul anand atul.87fri...@gmail.com
wrote:
can be done with O(n^2) time complexity..
can it be done with O(n) complexity ???
On 6/3/12, utsav sharma utsav.sharm...@gmail.com wrote:
given a string tell wether it is valid or not.
string is valid if there is no substring which have the same
substring
following it.
these strings are not valid:- stringstring,geek123123rt,
abcadabcad,strngstingstrngsting
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon interview questions
@hassan :- it will not work for many strings as you are checking from the
mid of strings. try out ababcdef,aabc.
@atul :- it should be done in O(n).
On Sun, Jun 3, 2012 at 11:54 PM, Hassan Monfared hmonfa...@gmail.comwrote:
yes it's not valid
On Sun, Jun 3, 2012 at 5:36 PM, anugrah anugrah.agra...@gmail.com wrote:
So any string with two same characters is not valid??
for example :
GEEK has E followed by E.
So GEEK is also invalid?
On Jun 3, 1:49 pm, Hassan Monfared hmonfa...@gmail.com wrote:
bool IsValid(string s)
{
for(int len=0;lens.len/2;len++)
{
int start1=0,start2=len+1;
while(start2s.size())
{
for(int i=0;ilen start2+is.size()
s[start1+i]=s[start2+i];i++);
if(i==len)
return false; //not valid
start1++;
start2++;
}
}
return true; // valid
}
On Sun, Jun 3, 2012 at 12:52 PM, atul anand atul.87fri...@gmail.com
wrote:
can be done with O(n^2) time complexity..
can it be done with O(n) complexity ???
On 6/3/12, utsav sharma utsav.sharm...@gmail.com wrote:
given a string tell wether it is valid or not.
string is valid if there is no substring which have the same
substring
following it.
these strings are not valid:- stringstring,geek123123rt,
abcadabcad,strngstingstrngsting
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon interview questions
@jeevitesh :- yes i am also thinking of suffix tree,
but i am facing problem in implementing it. did you implement it ??
On Mon, Jun 4, 2012 at 9:11 AM, utsav sharma utsav.sharm...@gmail.comwrote:
@hassan :- it will not work for many strings as you are checking from the
mid of strings. try out ababcdef,aabc.
@atul :- it should be done in O(n).
On Sun, Jun 3, 2012 at 11:54 PM, Hassan Monfared hmonfa...@gmail.comwrote:
yes it's not valid
On Sun, Jun 3, 2012 at 5:36 PM, anugrah anugrah.agra...@gmail.comwrote:
So any string with two same characters is not valid??
for example :
GEEK has E followed by E.
So GEEK is also invalid?
On Jun 3, 1:49 pm, Hassan Monfared hmonfa...@gmail.com wrote:
bool IsValid(string s)
{
for(int len=0;lens.len/2;len++)
{
int start1=0,start2=len+1;
while(start2s.size())
{
for(int i=0;ilen start2+is.size()
s[start1+i]=s[start2+i];i++);
if(i==len)
return false; //not valid
start1++;
start2++;
}
}
return true; // valid
}
On Sun, Jun 3, 2012 at 12:52 PM, atul anand atul.87fri...@gmail.com
wrote:
can be done with O(n^2) time complexity..
can it be done with O(n) complexity ???
On 6/3/12, utsav sharma utsav.sharm...@gmail.com wrote:
given a string tell wether it is valid or not.
string is valid if there is no substring which have the same
substring
following it.
these strings are not valid:- stringstring,geek123123rt,
abcadabcad,strngstingstrngsting
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: amazon interview questions
utsav: It works fine, I did little bug fixing on boundaries as here goes :
bool IsValid(string s)
{
for(int len=1;len=s.size()/2;len++)
{
int start1=0,start2=len;
while(start2s.size())
{
int i=0;
for(;ilen start2+is.size() s[start1+i]==s[start2+i];i++);
if(i=len)
return false; //not valid
start1++;
start2++;
}
}
return true; // valid
}
It works for both input you provided. :)
On Mon, Jun 4, 2012 at 8:14 AM, utsav sharma utsav.sharm...@gmail.comwrote:
@jeevitesh :- yes i am also thinking of suffix tree,
but i am facing problem in implementing it. did you implement it ??
On Mon, Jun 4, 2012 at 9:11 AM, utsav sharma utsav.sharm...@gmail.comwrote:
@hassan :- it will not work for many strings as you are checking from the
mid of strings. try out ababcdef,aabc.
@atul :- it should be done in O(n).
On Sun, Jun 3, 2012 at 11:54 PM, Hassan Monfared hmonfa...@gmail.comwrote:
yes it's not valid
On Sun, Jun 3, 2012 at 5:36 PM, anugrah anugrah.agra...@gmail.comwrote:
So any string with two same characters is not valid??
for example :
GEEK has E followed by E.
So GEEK is also invalid?
On Jun 3, 1:49 pm, Hassan Monfared hmonfa...@gmail.com wrote:
bool IsValid(string s)
{
for(int len=0;lens.len/2;len++)
{
int start1=0,start2=len+1;
while(start2s.size())
{
for(int i=0;ilen start2+is.size()
s[start1+i]=s[start2+i];i++);
if(i==len)
return false; //not valid
start1++;
start2++;
}
}
return true; // valid
}
On Sun, Jun 3, 2012 at 12:52 PM, atul anand atul.87fri...@gmail.com
wrote:
can be done with O(n^2) time complexity..
can it be done with O(n) complexity ???
On 6/3/12, utsav sharma utsav.sharm...@gmail.com wrote:
given a string tell wether it is valid or not.
string is valid if there is no substring which have the same
substring
following it.
these strings are not valid:- stringstring,geek123123rt,
abcadabcad,strngstingstrngsting
--
You received this message because you are subscribed to the
Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
