Re: [algogeeks] Microsoft written test question
@shashi: once we have two pointer where anomalies exist, we can exchange
their data value to obtain original BST...
On Wed, Sep 5, 2012 at 12:38 PM, shashi kant shashiski...@gmail.com wrote:
Is it required only to retain the BST property ?? or to retain the
original BST (tree)
*Shashi Kant *
***Think positive and find fuel in failure*
http://thinkndoawesome.blogspot.com/
*System/Software Engineer*
*Hewlett-Packard India Software Operations.
*
On Tue, Sep 4, 2012 at 1:56 PM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
@atul: correctly caught...
here you have to notice that if u get only one violation not second
violation ill the last... then sure the violation is created because of
swapping of previous and current of first violation...
so when you got first violation and put first marker on previous time put
second marker on current...
suppose and the last if you don't get the second violation then 2nd
marker will the current node of first violation...
as in your case when we got first violation at node prev = 20 and current
= 10.. mark first point at 20 and second pointer at 10.. at the last the
2nd pointer does not get change...
i have checked this with other test cases.. this case is coming only when
previous and current are the consecutive nodes(parent and its direct child)
and one of the node is leaf node...
On Tue, Sep 4, 2012 at 1:22 AM, atul anand atul.87fri...@gmail.comwrote:
i guess i missed this part of bharat post :-
/*
If we don't get the violation for the second time .. means both are
side-by-side elements .. swap them ..
*/
i was saying the same.so it will work.
On 9/4/12, atul anand atul.87fri...@gmail.com wrote:
@rahul : Here are the boundary cases need to be taken care of :-
suppose given BST is the following :-
root=allocate(70);
root-right=allocate(75);
root-left=allocate(50);
root-left-left=allocate(20);
root-left-left-right=allocate(25);
root-left-left-left=allocate(10);
root-left-right=allocate(60);
root-left-right-right=allocate(65);
root-left-right-left=allocate(55);
now suppose node(20) and node(10) get swapped
inorder of given tree is :-
20 10 25 50 55 60 65 70 75
now first violation is at node(20)
but you wont get second voilation...because rest is in inc order.
yes , it can be done by taking care of root of that first violation.
On 9/3/12, Rahul Kumar Patle patlerahulku...@gmail.com wrote:
@bharat: +1
i have tried some test cases.. working finely.. @anyone pls verify??
On Mon, Sep 3, 2012 at 11:58 AM, bharat b
bagana.bharatku...@gmail.comwrote:
while doing in-order traversal, we have to check if(prev current)
--
then mark prev element for swapping in the first time violation..
if it happens for the second time..then mark current element for
swapping.
swap both ..
If we don't get the violation for the second time .. means both are
side-by-side elements .. swap them ..
Hope works .. If I miss any case .. correct me
thanks,
On Sun, Sep 2, 2012 at 7:45 PM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
@navin: can u explain ur algorithms in words pls..
On Sun, Sep 2, 2012 at 5:53 PM, Navin Kumar
algorithm.i...@gmail.comwrote:
void correctBST(struct node *root)
{
int flag =0;
static struct node *temp1, *temp2, *temp3, *prev;
static int found;
if(found) return;
if(root) {
correctBST(root-left);
if(!temp1 prev root-data prev-data) {
temp1 = prev;
temp2 = root;
swap((temp1-data), (temp2-data));
flag = 1;
prev = temp1;
}
else if(!temp3 prev root-data prev-data) {
temp3 = root;
swap((temp1-data), (temp2-data));
swap((temp1-data), (temp3-data));
found = 1;
return;
}
if(!flag)
prev = root;
correctBST(root-right);
}
}
On Sun, Sep 2, 2012 at 4:02 PM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
help to solve the following..
Question: Two of the nodes of a BST are swapped. Correct the BST
(taken
from GeekforGeeks http://www.geeksforgeeks.org/archives/23272
2nd
online test 3rd question)
--
Thanks and Regards:
Rahul Kumar
Patle
http://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Indiahttp://www.iitkgp.ac.in/
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
--
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] Microsoft written test question
that what i mentioned finding original BST or a correcting the BST property ... my method will only maintains the BST property... -- 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] Microsoft written test question
Is it required only to retain the BST property ?? or to retain the
original BST (tree)
*Shashi Kant *
***Think positive and find fuel in failure*
http://thinkndoawesome.blogspot.com/
*System/Software Engineer*
*Hewlett-Packard India Software Operations.
*
On Tue, Sep 4, 2012 at 1:56 PM, Rahul Kumar Patle patlerahulku...@gmail.com
wrote:
@atul: correctly caught...
here you have to notice that if u get only one violation not second
violation ill the last... then sure the violation is created because of
swapping of previous and current of first violation...
so when you got first violation and put first marker on previous time put
second marker on current...
suppose and the last if you don't get the second violation then 2nd marker
will the current node of first violation...
as in your case when we got first violation at node prev = 20 and current
= 10.. mark first point at 20 and second pointer at 10.. at the last the
2nd pointer does not get change...
i have checked this with other test cases.. this case is coming only when
previous and current are the consecutive nodes(parent and its direct child)
and one of the node is leaf node...
On Tue, Sep 4, 2012 at 1:22 AM, atul anand atul.87fri...@gmail.comwrote:
i guess i missed this part of bharat post :-
/*
If we don't get the violation for the second time .. means both are
side-by-side elements .. swap them ..
*/
i was saying the same.so it will work.
On 9/4/12, atul anand atul.87fri...@gmail.com wrote:
@rahul : Here are the boundary cases need to be taken care of :-
suppose given BST is the following :-
root=allocate(70);
root-right=allocate(75);
root-left=allocate(50);
root-left-left=allocate(20);
root-left-left-right=allocate(25);
root-left-left-left=allocate(10);
root-left-right=allocate(60);
root-left-right-right=allocate(65);
root-left-right-left=allocate(55);
now suppose node(20) and node(10) get swapped
inorder of given tree is :-
20 10 25 50 55 60 65 70 75
now first violation is at node(20)
but you wont get second voilation...because rest is in inc order.
yes , it can be done by taking care of root of that first violation.
On 9/3/12, Rahul Kumar Patle patlerahulku...@gmail.com wrote:
@bharat: +1
i have tried some test cases.. working finely.. @anyone pls verify??
On Mon, Sep 3, 2012 at 11:58 AM, bharat b
bagana.bharatku...@gmail.comwrote:
while doing in-order traversal, we have to check if(prev current)
--
then mark prev element for swapping in the first time violation..
if it happens for the second time..then mark current element for
swapping.
swap both ..
If we don't get the violation for the second time .. means both are
side-by-side elements .. swap them ..
Hope works .. If I miss any case .. correct me
thanks,
On Sun, Sep 2, 2012 at 7:45 PM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
@navin: can u explain ur algorithms in words pls..
On Sun, Sep 2, 2012 at 5:53 PM, Navin Kumar
algorithm.i...@gmail.comwrote:
void correctBST(struct node *root)
{
int flag =0;
static struct node *temp1, *temp2, *temp3, *prev;
static int found;
if(found) return;
if(root) {
correctBST(root-left);
if(!temp1 prev root-data prev-data) {
temp1 = prev;
temp2 = root;
swap((temp1-data), (temp2-data));
flag = 1;
prev = temp1;
}
else if(!temp3 prev root-data prev-data) {
temp3 = root;
swap((temp1-data), (temp2-data));
swap((temp1-data), (temp3-data));
found = 1;
return;
}
if(!flag)
prev = root;
correctBST(root-right);
}
}
On Sun, Sep 2, 2012 at 4:02 PM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
help to solve the following..
Question: Two of the nodes of a BST are swapped. Correct the BST
(taken
from GeekforGeeks http://www.geeksforgeeks.org/archives/23272
2nd
online test 3rd question)
--
Thanks and Regards:
Rahul Kumar
Patle
http://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Indiahttp://www.iitkgp.ac.in/
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
--
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,
Re: [algogeeks] Microsoft written test question
@Shashi : i dont see any differencebcoz only 2 nodes are swapped ..after correcting it...it shud maintain BST property wich automatically retain original tree -- 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] Microsoft written test question
well in that case there can be simpler ways to do it do an inorder traversal while checking prevcurnext ordering maintained if not then make it in proper order ,although whole tree has to be traversed to fix it. *Shashi Kant * ***Think positive and find fuel in failure* http://thinkndoawesome.blogspot.com/ *System/Software Engineer* *Hewlett-Packard India Software Operations. * On Wed, Sep 5, 2012 at 12:43 PM, atul anand atul.87fri...@gmail.com wrote: @Shashi : i dont see any differencebcoz only 2 nodes are swapped ..after correcting it...it shud maintain BST property wich automatically retain original tree -- 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] Microsoft written test question
@Shashi : please check previous discussion on this thread. On Wed, Sep 5, 2012 at 2:09 PM, shashi kant shashiski...@gmail.com wrote: well in that case there can be simpler ways to do it do an inorder traversal while checking prevcurnext ordering maintained if not then make it in proper order ,although whole tree has to be traversed to fix it. *Shashi Kant * ***Think positive and find fuel in failure* http://thinkndoawesome.blogspot.com/ *System/Software Engineer* *Hewlett-Packard India Software Operations. * On Wed, Sep 5, 2012 at 12:43 PM, atul anand atul.87fri...@gmail.comwrote: @Shashi : i dont see any differencebcoz only 2 nodes are swapped ..after correcting it...it shud maintain BST property wich automatically retain original tree -- 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] Microsoft written test question
@atul: correctly caught...
here you have to notice that if u get only one violation not second
violation ill the last... then sure the violation is created because of
swapping of previous and current of first violation...
so when you got first violation and put first marker on previous time put
second marker on current...
suppose and the last if you don't get the second violation then 2nd marker
will the current node of first violation...
as in your case when we got first violation at node prev = 20 and current =
10.. mark first point at 20 and second pointer at 10.. at the last the 2nd
pointer does not get change...
i have checked this with other test cases.. this case is coming only when
previous and current are the consecutive nodes(parent and its direct child)
and one of the node is leaf node...
On Tue, Sep 4, 2012 at 1:22 AM, atul anand atul.87fri...@gmail.com wrote:
i guess i missed this part of bharat post :-
/*
If we don't get the violation for the second time .. means both are
side-by-side elements .. swap them ..
*/
i was saying the same.so it will work.
On 9/4/12, atul anand atul.87fri...@gmail.com wrote:
@rahul : Here are the boundary cases need to be taken care of :-
suppose given BST is the following :-
root=allocate(70);
root-right=allocate(75);
root-left=allocate(50);
root-left-left=allocate(20);
root-left-left-right=allocate(25);
root-left-left-left=allocate(10);
root-left-right=allocate(60);
root-left-right-right=allocate(65);
root-left-right-left=allocate(55);
now suppose node(20) and node(10) get swapped
inorder of given tree is :-
20 10 25 50 55 60 65 70 75
now first violation is at node(20)
but you wont get second voilation...because rest is in inc order.
yes , it can be done by taking care of root of that first violation.
On 9/3/12, Rahul Kumar Patle patlerahulku...@gmail.com wrote:
@bharat: +1
i have tried some test cases.. working finely.. @anyone pls verify??
On Mon, Sep 3, 2012 at 11:58 AM, bharat b
bagana.bharatku...@gmail.comwrote:
while doing in-order traversal, we have to check if(prev current) --
then mark prev element for swapping in the first time violation..
if it happens for the second time..then mark current element for
swapping.
swap both ..
If we don't get the violation for the second time .. means both are
side-by-side elements .. swap them ..
Hope works .. If I miss any case .. correct me
thanks,
On Sun, Sep 2, 2012 at 7:45 PM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
@navin: can u explain ur algorithms in words pls..
On Sun, Sep 2, 2012 at 5:53 PM, Navin Kumar
algorithm.i...@gmail.comwrote:
void correctBST(struct node *root)
{
int flag =0;
static struct node *temp1, *temp2, *temp3, *prev;
static int found;
if(found) return;
if(root) {
correctBST(root-left);
if(!temp1 prev root-data prev-data) {
temp1 = prev;
temp2 = root;
swap((temp1-data), (temp2-data));
flag = 1;
prev = temp1;
}
else if(!temp3 prev root-data prev-data) {
temp3 = root;
swap((temp1-data), (temp2-data));
swap((temp1-data), (temp3-data));
found = 1;
return;
}
if(!flag)
prev = root;
correctBST(root-right);
}
}
On Sun, Sep 2, 2012 at 4:02 PM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
help to solve the following..
Question: Two of the nodes of a BST are swapped. Correct the BST
(taken
from GeekforGeeks http://www.geeksforgeeks.org/archives/23272 2nd
online test 3rd question)
--
Thanks and Regards:
Rahul Kumar
Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Indiahttp://www.iitkgp.ac.in/
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
--
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 and Regards:
Rahul Kumar
Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Re: [algogeeks] Microsoft written test question
while doing in-order traversal, we have to check if(prev current) --
then mark prev element for swapping in the first time violation..
if it happens for the second time..then mark current element for swapping.
swap both ..
If we don't get the violation for the second time .. means both are
side-by-side elements .. swap them ..
Hope works .. If I miss any case .. correct me
thanks,
On Sun, Sep 2, 2012 at 7:45 PM, Rahul Kumar Patle patlerahulku...@gmail.com
wrote:
@navin: can u explain ur algorithms in words pls..
On Sun, Sep 2, 2012 at 5:53 PM, Navin Kumar algorithm.i...@gmail.comwrote:
void correctBST(struct node *root)
{
int flag =0;
static struct node *temp1, *temp2, *temp3, *prev;
static int found;
if(found) return;
if(root) {
correctBST(root-left);
if(!temp1 prev root-data prev-data) {
temp1 = prev;
temp2 = root;
swap((temp1-data), (temp2-data));
flag = 1;
prev = temp1;
}
else if(!temp3 prev root-data prev-data) {
temp3 = root;
swap((temp1-data), (temp2-data));
swap((temp1-data), (temp3-data));
found = 1;
return;
}
if(!flag)
prev = root;
correctBST(root-right);
}
}
On Sun, Sep 2, 2012 at 4:02 PM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
help to solve the following..
Question: Two of the nodes of a BST are swapped. Correct the BST (taken
from GeekforGeeks http://www.geeksforgeeks.org/archives/23272 2nd
online test 3rd question)
--
Thanks and Regards:
Rahul Kumar
Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Indiahttp://www.iitkgp.ac.in/
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
--
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 and Regards:
Rahul Kumar
Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Indiahttp://www.iitkgp.ac.in/
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
--
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] Microsoft written test question
@bharat: +1
i have tried some test cases.. working finely.. @anyone pls verify??
On Mon, Sep 3, 2012 at 11:58 AM, bharat b bagana.bharatku...@gmail.comwrote:
while doing in-order traversal, we have to check if(prev current) --
then mark prev element for swapping in the first time violation..
if it happens for the second time..then mark current element for swapping.
swap both ..
If we don't get the violation for the second time .. means both are
side-by-side elements .. swap them ..
Hope works .. If I miss any case .. correct me
thanks,
On Sun, Sep 2, 2012 at 7:45 PM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
@navin: can u explain ur algorithms in words pls..
On Sun, Sep 2, 2012 at 5:53 PM, Navin Kumar algorithm.i...@gmail.comwrote:
void correctBST(struct node *root)
{
int flag =0;
static struct node *temp1, *temp2, *temp3, *prev;
static int found;
if(found) return;
if(root) {
correctBST(root-left);
if(!temp1 prev root-data prev-data) {
temp1 = prev;
temp2 = root;
swap((temp1-data), (temp2-data));
flag = 1;
prev = temp1;
}
else if(!temp3 prev root-data prev-data) {
temp3 = root;
swap((temp1-data), (temp2-data));
swap((temp1-data), (temp3-data));
found = 1;
return;
}
if(!flag)
prev = root;
correctBST(root-right);
}
}
On Sun, Sep 2, 2012 at 4:02 PM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
help to solve the following..
Question: Two of the nodes of a BST are swapped. Correct the BST (taken
from GeekforGeeks http://www.geeksforgeeks.org/archives/23272 2nd
online test 3rd question)
--
Thanks and Regards:
Rahul Kumar
Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Indiahttp://www.iitkgp.ac.in/
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
--
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 and Regards:
Rahul Kumar
Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Indiahttp://www.iitkgp.ac.in/
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
--
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 and Regards:
Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Indiahttp://www.iitkgp.ac.in/
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
--
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] Microsoft written test question
@rahul : Here are the boundary cases need to be taken care of :-
suppose given BST is the following :-
root=allocate(70);
root-right=allocate(75);
root-left=allocate(50);
root-left-left=allocate(20);
root-left-left-right=allocate(25);
root-left-left-left=allocate(10);
root-left-right=allocate(60);
root-left-right-right=allocate(65);
root-left-right-left=allocate(55);
now suppose node(20) and node(10) get swapped
inorder of given tree is :-
20 10 25 50 55 60 65 70 75
now first violation is at node(20)
but you wont get second voilation...because rest is in inc order.
yes , it can be done by taking care of root of that first violation.
On 9/3/12, Rahul Kumar Patle patlerahulku...@gmail.com wrote:
@bharat: +1
i have tried some test cases.. working finely.. @anyone pls verify??
On Mon, Sep 3, 2012 at 11:58 AM, bharat b
bagana.bharatku...@gmail.comwrote:
while doing in-order traversal, we have to check if(prev current) --
then mark prev element for swapping in the first time violation..
if it happens for the second time..then mark current element for
swapping.
swap both ..
If we don't get the violation for the second time .. means both are
side-by-side elements .. swap them ..
Hope works .. If I miss any case .. correct me
thanks,
On Sun, Sep 2, 2012 at 7:45 PM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
@navin: can u explain ur algorithms in words pls..
On Sun, Sep 2, 2012 at 5:53 PM, Navin Kumar
algorithm.i...@gmail.comwrote:
void correctBST(struct node *root)
{
int flag =0;
static struct node *temp1, *temp2, *temp3, *prev;
static int found;
if(found) return;
if(root) {
correctBST(root-left);
if(!temp1 prev root-data prev-data) {
temp1 = prev;
temp2 = root;
swap((temp1-data), (temp2-data));
flag = 1;
prev = temp1;
}
else if(!temp3 prev root-data prev-data) {
temp3 = root;
swap((temp1-data), (temp2-data));
swap((temp1-data), (temp3-data));
found = 1;
return;
}
if(!flag)
prev = root;
correctBST(root-right);
}
}
On Sun, Sep 2, 2012 at 4:02 PM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
help to solve the following..
Question: Two of the nodes of a BST are swapped. Correct the BST
(taken
from GeekforGeeks http://www.geeksforgeeks.org/archives/23272 2nd
online test 3rd question)
--
Thanks and Regards:
Rahul Kumar
Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Indiahttp://www.iitkgp.ac.in/
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
--
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 and Regards:
Rahul Kumar
Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Indiahttp://www.iitkgp.ac.in/
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
--
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 and Regards:
Rahul Kumar
Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Indiahttp://www.iitkgp.ac.in/
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
--
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
Re: [algogeeks] Microsoft written test question
i guess i missed this part of bharat post :-
/*
If we don't get the violation for the second time .. means both are
side-by-side elements .. swap them ..
*/
i was saying the same.so it will work.
On 9/4/12, atul anand atul.87fri...@gmail.com wrote:
@rahul : Here are the boundary cases need to be taken care of :-
suppose given BST is the following :-
root=allocate(70);
root-right=allocate(75);
root-left=allocate(50);
root-left-left=allocate(20);
root-left-left-right=allocate(25);
root-left-left-left=allocate(10);
root-left-right=allocate(60);
root-left-right-right=allocate(65);
root-left-right-left=allocate(55);
now suppose node(20) and node(10) get swapped
inorder of given tree is :-
20 10 25 50 55 60 65 70 75
now first violation is at node(20)
but you wont get second voilation...because rest is in inc order.
yes , it can be done by taking care of root of that first violation.
On 9/3/12, Rahul Kumar Patle patlerahulku...@gmail.com wrote:
@bharat: +1
i have tried some test cases.. working finely.. @anyone pls verify??
On Mon, Sep 3, 2012 at 11:58 AM, bharat b
bagana.bharatku...@gmail.comwrote:
while doing in-order traversal, we have to check if(prev current) --
then mark prev element for swapping in the first time violation..
if it happens for the second time..then mark current element for
swapping.
swap both ..
If we don't get the violation for the second time .. means both are
side-by-side elements .. swap them ..
Hope works .. If I miss any case .. correct me
thanks,
On Sun, Sep 2, 2012 at 7:45 PM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
@navin: can u explain ur algorithms in words pls..
On Sun, Sep 2, 2012 at 5:53 PM, Navin Kumar
algorithm.i...@gmail.comwrote:
void correctBST(struct node *root)
{
int flag =0;
static struct node *temp1, *temp2, *temp3, *prev;
static int found;
if(found) return;
if(root) {
correctBST(root-left);
if(!temp1 prev root-data prev-data) {
temp1 = prev;
temp2 = root;
swap((temp1-data), (temp2-data));
flag = 1;
prev = temp1;
}
else if(!temp3 prev root-data prev-data) {
temp3 = root;
swap((temp1-data), (temp2-data));
swap((temp1-data), (temp3-data));
found = 1;
return;
}
if(!flag)
prev = root;
correctBST(root-right);
}
}
On Sun, Sep 2, 2012 at 4:02 PM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
help to solve the following..
Question: Two of the nodes of a BST are swapped. Correct the BST
(taken
from GeekforGeeks http://www.geeksforgeeks.org/archives/23272 2nd
online test 3rd question)
--
Thanks and Regards:
Rahul Kumar
Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Indiahttp://www.iitkgp.ac.in/
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
--
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 and Regards:
Rahul Kumar
Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Indiahttp://www.iitkgp.ac.in/
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
--
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 and Regards:
Rahul Kumar
Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
[algogeeks] Microsoft written test question
help to solve the following.. Question: Two of the nodes of a BST are swapped. Correct the BST (taken from GeekforGeeks http://www.geeksforgeeks.org/archives/23272 2nd online test 3rd question) -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- 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] Microsoft written test question
void correctBST(struct node *root)
{
int flag =0;
static struct node *temp1, *temp2, *temp3, *prev;
static int found;
if(found) return;
if(root) {
correctBST(root-left);
if(!temp1 prev root-data prev-data) {
temp1 = prev;
temp2 = root;
swap((temp1-data), (temp2-data));
flag = 1;
prev = temp1;
}
else if(!temp3 prev root-data prev-data) {
temp3 = root;
swap((temp1-data), (temp2-data));
swap((temp1-data), (temp3-data));
found = 1;
return;
}
if(!flag)
prev = root;
correctBST(root-right);
}
}
On Sun, Sep 2, 2012 at 4:02 PM, Rahul Kumar Patle patlerahulku...@gmail.com
wrote:
help to solve the following..
Question: Two of the nodes of a BST are swapped. Correct the BST (taken
from GeekforGeeks http://www.geeksforgeeks.org/archives/23272 2nd
online test 3rd question)
--
Thanks and Regards:
Rahul Kumar
Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Indiahttp://www.iitkgp.ac.in/
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
--
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] Microsoft written test question
@navin: can u explain ur algorithms in words pls..
On Sun, Sep 2, 2012 at 5:53 PM, Navin Kumar algorithm.i...@gmail.comwrote:
void correctBST(struct node *root)
{
int flag =0;
static struct node *temp1, *temp2, *temp3, *prev;
static int found;
if(found) return;
if(root) {
correctBST(root-left);
if(!temp1 prev root-data prev-data) {
temp1 = prev;
temp2 = root;
swap((temp1-data), (temp2-data));
flag = 1;
prev = temp1;
}
else if(!temp3 prev root-data prev-data) {
temp3 = root;
swap((temp1-data), (temp2-data));
swap((temp1-data), (temp3-data));
found = 1;
return;
}
if(!flag)
prev = root;
correctBST(root-right);
}
}
On Sun, Sep 2, 2012 at 4:02 PM, Rahul Kumar Patle
patlerahulku...@gmail.com wrote:
help to solve the following..
Question: Two of the nodes of a BST are swapped. Correct the BST (taken
from GeekforGeeks http://www.geeksforgeeks.org/archives/23272 2nd
online test 3rd question)
--
Thanks and Regards:
Rahul Kumar
Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Indiahttp://www.iitkgp.ac.in/
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
--
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 and Regards:
Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
Indiahttp://www.iitkgp.ac.in/
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.com
--
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.
