[algogeeks] Re: Amazon Question
have a look http://amnwidfrenz-thinkalways.blogspot.in/2012/09/string- reduction.html -- 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 Question
10 4 5 2 7 6 11 1 39 8 12 13 14 15 For this the cousins of 1 should be 9 8 12 13 14 15 how then can it be a 2 pass algorithm... we should also consider great grandparent as in this case ... Correct me if I m wrong!! On Tuesday, 19 April 2011 05:33:26 UTC+5:30, ashgoel wrote: This essentially becomes a two pass algo first find the parent and grand parent and find children of all the siblings of the parent Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Apr 14, 2011 at 9:53 AM, Dave dave_and_da...@juno.com wrote: @Priya: Assuming that cousins means first cousins, then cousins have a common grandparent but different parents. Other people on the same level would not be first cousins. The algorithm is to go up two levels (to the grandparent) and descend to the other child (to an aunt or uncle). The children of that node are the cousins. Dave On Apr 13, 11:13 pm, priya mehta priya.mehta...@gmail.com wrote: i hope all the cousins means all the nodes on the same level, so it should be done using level order traversal. On Thu, Apr 14, 2011 at 8:38 AM, sravanreddy001 sravanreddy...@gmail.comwrote: Yes, this is correct, and to move the data in the array, its simple, just do a traverse and populate the array.. another way is to put data into queue and putting only one level of data at a time, this reduces the space consumption but... only by half... -- 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.- Hide quoted text - - Show quoted text - -- 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. On Tuesday, 19 April 2011 05:33:26 UTC+5:30, ashgoel wrote: This essentially becomes a two pass algo first find the parent and grand parent and find children of all the siblings of the parent Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Apr 14, 2011 at 9:53 AM, Dave dave_and_da...@juno.com wrote: @Priya: Assuming that cousins means first cousins, then cousins have a common grandparent but different parents. Other people on the same level would not be first cousins. The algorithm is to go up two levels (to the grandparent) and descend to the other child (to an aunt or uncle). The children of that node are the cousins. Dave On Apr 13, 11:13 pm, priya mehta priya.mehta...@gmail.com wrote: i hope all the cousins means all the nodes on the same level, so it should be done using level order traversal. On Thu, Apr 14, 2011 at 8:38 AM, sravanreddy001 sravanreddy...@gmail.comwrote: Yes, this is correct, and to move the data in the array, its simple, just do a traverse and populate the array.. another way is to put data into queue and putting only one level of data at a time, this reduces the space consumption but... only by half... -- 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.- Hide quoted text - - Show quoted text - -- 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. On Tuesday, 19 April 2011 05:33:26 UTC+5:30, ashgoel wrote: This essentially becomes a two pass algo first find the parent and grand parent and find children of all the siblings of the parent Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Apr 14, 2011 at 9:53 AM, Dave dave_and_da...@juno.com wrote: @Priya: Assuming that cousins means first cousins, then cousins have a common grandparent but different parents. Other people on the same level would not be first cousins. The algorithm is to go up two levels (to the
Re: [algogeeks] Re: Amazon Question
For this the cousins of 1 should be 9 8 12 13 14 15 how then can it be a 2 pass algorithm... we should also consider great grandparent as in this case ... Correct me if I m wrong!! the first cousins are 9,8 not 12,13...otherwise the question becomes really simple :) Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, May 21, 2012 at 12:54 PM, sivaviknesh sivavikne...@gmail.comwrote: For this the cousins of 1 should be 9 8 12 13 14 15 how then can it be a 2 pass algorithm... we should also consider great grandparent as in this case ... Correct me if I m wrong!! -- 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 Question
bool firstCousins(struct node * pRoot, struct node *pThis, (struct node*)[]
path, int pos, vectorint firstCousins)
{
if ((!pThis) || (!pRoot)) return false;
if (pRoot-data!=pThis-data) {
path[pos] = pRoot;
if (!findCousins(pRoot-left, pThis, path, pos+1, firstCousins))
return findCousins(pRoot-left, pThis, path, pos+1, firstCousins);
}
if (pos2) return false; //this node is at level 0 or level 1
struct node* pGP = path[pos-2];
struct node *pParent = path[pos-1];
struct node *pUncle = NULL;
if (pParent == pGP-left)
{
pUncle = pGP-right;
}else pUncle = pGP-left;
if (pUncle-left) firstCousins.add(pUncle-left-data);
if (pUncle-right) firstCousins.add(pUncle-right-data);
return true;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, May 21, 2012 at 5:41 PM, Ashish Goel ashg...@gmail.com wrote:
For this the cousins of 1 should be 9 8 12 13 14 15 how
then can it be a 2 pass algorithm... we should also consider great
grandparent as in this case ... Correct me if I m wrong!!
the first cousins are 9,8 not 12,13...otherwise the question becomes
really simple :)
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, May 21, 2012 at 12:54 PM, sivaviknesh sivavikne...@gmail.comwrote:
For this the cousins of 1 should be 9 8 12 13 14 15 how
then can it be a 2 pass algorithm... we should also consider great
grandparent as in this case ... Correct me if I m wrong!!
--
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 Question
Shouldn't having 2 queues one storing the node and other corresponding
level should be sufficient and do level order traversal?
-mithun
On Mon, May 21, 2012 at 5:54 PM, Ashish Goel ashg...@gmail.com wrote:
bool firstCousins(struct node * pRoot, struct node *pThis, (struct
node*)[] path, int pos, vectorint firstCousins)
{
if ((!pThis) || (!pRoot)) return false;
if (pRoot-data!=pThis-data) {
path[pos] = pRoot;
if (!findCousins(pRoot-left, pThis, path, pos+1, firstCousins))
return findCousins(pRoot-left, pThis, path, pos+1, firstCousins);
}
if (pos2) return false; //this node is at level 0 or level 1
struct node* pGP = path[pos-2];
struct node *pParent = path[pos-1];
struct node *pUncle = NULL;
if (pParent == pGP-left)
{
pUncle = pGP-right;
}else pUncle = pGP-left;
if (pUncle-left) firstCousins.add(pUncle-left-data);
if (pUncle-right) firstCousins.add(pUncle-right-data);
return true;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, May 21, 2012 at 5:41 PM, Ashish Goel ashg...@gmail.com wrote:
For this the cousins of 1 should be 9 8 12 13 14 15 how
then can it be a 2 pass algorithm... we should also consider great
grandparent as in this case ... Correct me if I m wrong!!
the first cousins are 9,8 not 12,13...otherwise the question becomes
really simple :)
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, May 21, 2012 at 12:54 PM, sivaviknesh sivavikne...@gmail.comwrote:
For this the cousins of 1 should be 9 8 12 13 14 15 how
then can it be a 2 pass algorithm... we should also consider great
grandparent as in this case ... Correct me if I m wrong!!
--
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 Question
//considering node who's cousins need to be find as start..
node * a[10];
while(root!=start)
{
a[i]=root;
i++;
if(root-data start-data)
root=root-left;
else
root=root-right;
}//we can do this using recursion
node *grand=a[i-2];
if(start-data grand-data)
print(grand-left-left-data,gramd-left-right-data)
else
print...
I may be wrong I am new to coding..
On Monday, 21 May 2012 21:44:56 UTC+5:30, mithun wrote:
Shouldn't having 2 queues one storing the node and other corresponding
level should be sufficient and do level order traversal?
-mithun
On Mon, May 21, 2012 at 5:54 PM, Ashish Goel ashg...@gmail.com wrote:
bool firstCousins(struct node * pRoot, struct node *pThis, (struct
node*)[] path, int pos, vectorint firstCousins)
{
if ((!pThis) || (!pRoot)) return false;
if (pRoot-data!=pThis-data) {
path[pos] = pRoot;
if (!findCousins(pRoot-left, pThis, path, pos+1, firstCousins))
return findCousins(pRoot-left, pThis, path, pos+1, firstCousins);
}
if (pos2) return false; //this node is at level 0 or level 1
struct node* pGP = path[pos-2];
struct node *pParent = path[pos-1];
struct node *pUncle = NULL;
if (pParent == pGP-left)
{
pUncle = pGP-right;
}else pUncle = pGP-left;
if (pUncle-left) firstCousins.add(pUncle-left-data);
if (pUncle-right) firstCousins.add(pUncle-right-data);
return true;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, May 21, 2012 at 5:41 PM, Ashish Goel ashg...@gmail.com wrote:
For this the cousins of 1 should be 9 8 12 13 14 15 how
then can it be a 2 pass algorithm... we should also consider great
grandparent as in this case ... Correct me if I m wrong!!
the first cousins are 9,8 not 12,13...otherwise the question becomes
really simple :)
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, May 21, 2012 at 12:54 PM, sivaviknesh sivavikne...@gmail.comwrote:
For this the cousins of 1 should be 9 8 12 13 14 15
how then can it be a 2 pass algorithm... we should also consider great
grandparent as in this case ... Correct me if I m wrong!!
--
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 view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/qqG_yzwRUhgJ.
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.
[algogeeks] Re: Amazon question
I think this works and the complexity is O(sqrt(n))
#includecmath
#includecstdio
#includeiostream
#includecstring
#includecstdlib
using namespace std;
# define INFY 17
int main()
{
int n, i, j;
int val, minDiv, minDis;
while(1)
{
cin n;
minDis = INFY;
for (i = n; i = n+2; i++)
{
for (j = 1; j*j = i; j++)
{
if (i % j == 0minDis (i/j - j) )
{
minDis = i/j - j;
minDiv = j;
val = i;
}
}
}
coutval minDiv val/minDivendl;
}
//system(pause);
return 0;
}
On Mar 22, 10:34 am, atul anand atul.87fri...@gmail.com wrote:
@Rujin : mathematically point 2.2 seems straight forward but can we achieve
value of x and y with an algo whose complexity wud be O(sqrt(E)) ??
On Wed, Mar 21, 2012 at 2:37 PM, Rujin Cao drizzle...@gmail.com wrote:
One possible way is:
1) Put the three candidate number together into an array [n, n + 1, n + 2]
2) Iterate each element *E* in that array and test whether *E* is a prime
number
2.1) If it is, there will be only one way to find the two numbers
product to be *E*, i.e. {x = 1, y = E} OR {x = E, y = 1}, so the result
is E - 1
2.2) Otherwise, we should choose x and y that are closest to the
sqrt of *E*, which is quite straight forward.
E.g. 72 = 8 * 9 and 72 = 2 * 36 (2 8 and 36 9, so |9
- 8| |36 - 2|)
So total time complexity is O(sqrt(E)).
--
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 question
+1 @ anurag's solution.agree with O(sqrt(n)) complexity.
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Thu, Mar 22, 2012 at 11:42 AM, Anurag Gupta anurag.gupta...@gmail.comwrote:
I think this works and the complexity is O(sqrt(n))
#includecmath
#includecstdio
#includeiostream
#includecstring
#includecstdlib
using namespace std;
# define INFY 17
int main()
{
int n, i, j;
int val, minDiv, minDis;
while(1)
{
cin n;
minDis = INFY;
for (i = n; i = n+2; i++)
{
for (j = 1; j*j = i; j++)
{
if (i % j == 0minDis (i/j - j) )
{
minDis = i/j - j;
minDiv = j;
val = i;
}
}
}
coutval minDiv val/minDivendl;
}
//system(pause);
return 0;
}
On Mar 22, 10:34 am, atul anand atul.87fri...@gmail.com wrote:
@Rujin : mathematically point 2.2 seems straight forward but can we
achieve
value of x and y with an algo whose complexity wud be O(sqrt(E)) ??
On Wed, Mar 21, 2012 at 2:37 PM, Rujin Cao drizzle...@gmail.com wrote:
One possible way is:
1) Put the three candidate number together into an array [n, n + 1, n
+ 2]
2) Iterate each element *E* in that array and test whether *E* is a
prime
number
2.1) If it is, there will be only one way to find the two
numbers
product to be *E*, i.e. {x = 1, y = E} OR {x = E, y = 1}, so the
result
is E - 1
2.2) Otherwise, we should choose x and y that are closest to the
sqrt of *E*, which is quite straight forward.
E.g. 72 = 8 * 9 and 72 = 2 * 36 (2 8 and 36 9, so
|9
- 8| |36 - 2|)
So total time complexity is O(sqrt(E)).
--
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.
[algogeeks] Re: Amazon Question
seems like quesion of permutation, it will take all the permutation to check which one can lead to answer, there will be always be more than one solution complexity ((n-1)!) anyone for better solution ?? On Nov 12, 4:27 pm, surender sanke surend...@gmail.com wrote: @myself if number of distinct characters are equal then its final string size is 2. else there are more repeated characters other than distinct characters then its 1 correct me !!! surender On Sat, Nov 12, 2011 at 4:46 PM, surender sanke surend...@gmail.com wrote: All distinct combinations will result in string size of 2 + rest repeated characters eg abcabcabc -aabbcc-abc-aa or bb or cc surender On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me thesnoop...@gmail.com wrote: Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly? -- 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 Question
The Complexity of my solution is of Order n . At most I Traverse the whole string twice .. On Sat, Nov 12, 2011 at 8:29 PM, vikas vikas.rastogi2...@gmail.com wrote: seems like quesion of permutation, it will take all the permutation to check which one can lead to answer, there will be always be more than one solution complexity ((n-1)!) anyone for better solution ?? On Nov 12, 4:27 pm, surender sanke surend...@gmail.com wrote: @myself if number of distinct characters are equal then its final string size is 2. else there are more repeated characters other than distinct characters then its 1 correct me !!! surender On Sat, Nov 12, 2011 at 4:46 PM, surender sanke surend...@gmail.com wrote: All distinct combinations will result in string size of 2 + rest repeated characters eg abcabcabc -aabbcc-abc-aa or bb or cc surender On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me thesnoop...@gmail.com wrote: Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly? -- 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 Question
Well it aint O(n) ..:P ...The erase part will be complex and will take shifting string parts . So complexity will be O(n^2) for str.erase operation On Sat, Nov 12, 2011 at 8:34 PM, Ankur Garg ankurga...@gmail.com wrote: The Complexity of my solution is of Order n . At most I Traverse the whole string twice .. On Sat, Nov 12, 2011 at 8:29 PM, vikas vikas.rastogi2...@gmail.comwrote: seems like quesion of permutation, it will take all the permutation to check which one can lead to answer, there will be always be more than one solution complexity ((n-1)!) anyone for better solution ?? On Nov 12, 4:27 pm, surender sanke surend...@gmail.com wrote: @myself if number of distinct characters are equal then its final string size is 2. else there are more repeated characters other than distinct characters then its 1 correct me !!! surender On Sat, Nov 12, 2011 at 4:46 PM, surender sanke surend...@gmail.com wrote: All distinct combinations will result in string size of 2 + rest repeated characters eg abcabcabc -aabbcc-abc-aa or bb or cc surender On Sat, Nov 12, 2011 at 4:24 PM, Snoopy Me thesnoop...@gmail.com wrote: Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly? -- 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 question
@sagar for one time u r taking the return value of newly created process and for other time u r taking return value of parentir it right?? -- 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.
[algogeeks] Re: amazon question
But the o/p at
http://ideone.com/zKZuS
seems to be different than what one is getting from parent child tree
On Aug 8, 10:41 am, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
what will be the o/p of the following program:
main()
{
int ret;
ret=fork();
ret=fork();
ret=fork();
ret=fork();
if(!ret)
printf(one);
else
printf(two);
}
--
Regards,
Kamakshi
kamakshi...@gmail.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] Re: Amazon question
instead of that find sum of first n natural number sum ie (n(n+1))/2.;say NSum then find the sum of all elements of the array . say ASum ASUm - NSum = result (no repeated twice). On Fri, Aug 19, 2011 at 7:30 PM, Sanjay Rajpal tosanjayraj...@gmail.comwrote: :) *Regards Sanju Happy to Help :)* -- 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 question
Hi folks, I just thought since the range of the numbers is not known so can go this way; 1.We can find the max number in the array in o(n)=MAX say 2.Then (MAX(MAX+1))/2-sum(a[1n]) of given array=S=(a1+a2+.+an)-R 3. MAX!/prod(a[1...n])=P=(a1*a2*..*an)/R where a1,a2..an are the nos apart from nos in the array execpt the repeated number R from 1MAX 4.AM=GM we know this... (a1+a2+an)/n = pow((a1*a2*.an),1/n) = k1+R/n = pow((k2*R),1/n) I think computer is good enough to find R ... Please correct me if i am wrong cheers JAGANNATH On Sat, Aug 20, 2011 at 5:12 PM, aditya kumar aditya.kumar130...@gmail.comwrote: instead of that find sum of first n natural number sum ie (n(n+1))/2.;say NSum then find the sum of all elements of the array . say ASum ASUm - NSum = result (no repeated twice). On Fri, Aug 19, 2011 at 7:30 PM, Sanjay Rajpal tosanjayraj...@gmail.comwrote: :) *Regards Sanju Happy to Help :)* -- 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 question
But let us think in more general case let us say that numbers are 1 4 77 88 90 88 Then How to do it??? On Fri, Aug 19, 2011 at 5:01 PM, Sanjay Rajpal tosanjayraj...@gmail.comwrote: Yes this is the restriction and in assumption I have cleared it . *Regards Sanju Happy to Help :)* On Fri, Aug 19, 2011 at 3:33 AM, monty 1987 1986mo...@gmail.com wrote: @Sanju I think there exists a restriction in your approach that all numbers between 1and n has to be present in the array. Thanks Soumitra On Fri, Aug 19, 2011 at 9:53 AM, Sanjay Rajpal tosanjayraj...@gmail.comwrote: In the first loop, numbers are the numbers in the given array but in the second loop, numbers are just natural numbers. I forgot to mention as people may get confused. *Regards Sanju Happy to Help :)* -- 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 question
Sorting can be used i.e. O(nlogn). Since O(1) space constraint is there, so hashing can't be used. *Regards Sanju Happy to Help :)* On Fri, Aug 19, 2011 at 4:36 AM, monty 1987 1986mo...@gmail.com wrote: But let us think in more general case let us say that numbers are 1 4 77 88 90 88 Then How to do it??? On Fri, Aug 19, 2011 at 5:01 PM, Sanjay Rajpal tosanjayraj...@gmail.comwrote: Yes this is the restriction and in assumption I have cleared it . *Regards Sanju Happy to Help :)* On Fri, Aug 19, 2011 at 3:33 AM, monty 1987 1986mo...@gmail.com wrote: @Sanju I think there exists a restriction in your approach that all numbers between 1and n has to be present in the array. Thanks Soumitra On Fri, Aug 19, 2011 at 9:53 AM, Sanjay Rajpal tosanjayraj...@gmail.com wrote: In the first loop, numbers are the numbers in the given array but in the second loop, numbers are just natural numbers. I forgot to mention as people may get confused. *Regards Sanju Happy to Help :)* -- 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 question
@sanjay: Why doesn't your algo work if the nos are not in the range 1-n?? -- 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 question
acc to your logic, it should be 1^2^3^4^5^5^6 which is 1^2^3^4^6 (5^5 is zero) now when you XOR this with the given array, the result will again be 0. -- 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 question
You did not get my point, second time you have to XOR with Natural numbers, not with original array. Check out my post again :) After u calculated 1^2^3^4^6,let this be Res. XOR this result with Res^1^2^3^4^5^6. Now you got the point ? *Regards Sanju Happy to Help :)* On Fri, Aug 19, 2011 at 6:46 AM, priya ramesh love.for.programm...@gmail.com wrote: acc to your logic, it should be 1^2^3^4^5^5^6 which is 1^2^3^4^6 (5^5 is zero) now when you XOR this with the given array, the result will again be 0. -- 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 question
Oh yes yes i got it now!! I missed that point! -- 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 question
:) *Regards Sanju Happy to Help :)* -- 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.
[algogeeks] Re: Amazon Question
bitset would work i guess On Aug 18, 7:10 pm, hary rathor harry.rat...@gmail.com wrote: bitset is best . require only 32 time less then require in hash table . -- 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 Question
use (dynamic/ infinite)array initial the array with -1.
insert(int a)
{
array[a]=a;
}
delete(int a)
{
array[a]=-1;
}
..
Thank you,
Siddharam
On Thu, Aug 18, 2011 at 7:54 PM, DheerajSharma
dheerajsharma1...@gmail.comwrote:
bitset would work i guess
On Aug 18, 7:10 pm, hary rathor harry.rat...@gmail.com wrote:
bitset is best . require only 32 time less then require in hash table .
--
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.
[algogeeks] Re: Amazon question
#!/usr/bin/ruby -w
#array of unsorted positive integers
# find the [only] one that is duplicated
arr= [97,2,54,26,67,12,1,19,44,4,29,36,67,14,93,22,39,89]
h = Hash.new(0)
arr.each {|n|
h[n]+=1
(puts n; break) if h[n]==2
}
#output
#67
I hope this meets the requirements ;P
On Aug 18, 3:15 pm, *$* gopi.komand...@gmail.com wrote:
How to find duplicate element (only one element is repeated) from an array
of unsorted positive integers..
time complexity .. O(n)
space .. o(1).
--
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 question
I think we are using hash , which is like extra spaace , but as per the
question , O(s) = 1.
Thx,
--Gopi
On Fri, Aug 19, 2011 at 2:15 AM, icy` vipe...@gmail.com wrote:
#!/usr/bin/ruby -w
#array of unsorted positive integers
# find the [only] one that is duplicated
arr= [97,2,54,26,67,12,1,19,44,4,29,36,67,14,93,22,39,89]
h = Hash.new(0)
arr.each {|n|
h[n]+=1
(puts n; break) if h[n]==2
}
#output
#67
I hope this meets the requirements ;P
On Aug 18, 3:15 pm, *$* gopi.komand...@gmail.com wrote:
How to find duplicate element (only one element is repeated) from an
array
of unsorted positive integers..
time complexity .. O(n)
space .. o(1).
--
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.
--
Thx,
--Gopi
--
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 question
The element is repeated only once or can be repeated k number of times??
On Fri, Aug 19, 2011 at 7:50 AM, *$* gopi.komand...@gmail.com wrote:
I think we are using hash , which is like extra spaace , but as per the
question , O(s) = 1.
Thx,
--Gopi
On Fri, Aug 19, 2011 at 2:15 AM, icy` vipe...@gmail.com wrote:
#!/usr/bin/ruby -w
#array of unsorted positive integers
# find the [only] one that is duplicated
arr= [97,2,54,26,67,12,1,19,44,4,29,36,67,14,93,22,39,89]
h = Hash.new(0)
arr.each {|n|
h[n]+=1
(puts n; break) if h[n]==2
}
#output
#67
I hope this meets the requirements ;P
On Aug 18, 3:15 pm, *$* gopi.komand...@gmail.com wrote:
How to find duplicate element (only one element is repeated) from an
array
of unsorted positive integers..
time complexity .. O(n)
space .. o(1).
--
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.
--
Thx,
--Gopi
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT 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 question
only once
On Fri, Aug 19, 2011 at 7:57 AM, saurabh singh saurab...@gmail.com wrote:
The element is repeated only once or can be repeated k number of times??
On Fri, Aug 19, 2011 at 7:50 AM, *$* gopi.komand...@gmail.com wrote:
I think we are using hash , which is like extra spaace , but as per the
question , O(s) = 1.
Thx,
--Gopi
On Fri, Aug 19, 2011 at 2:15 AM, icy` vipe...@gmail.com wrote:
#!/usr/bin/ruby -w
#array of unsorted positive integers
# find the [only] one that is duplicated
arr= [97,2,54,26,67,12,1,19,44,4,29,36,67,14,93,22,39,89]
h = Hash.new(0)
arr.each {|n|
h[n]+=1
(puts n; break) if h[n]==2
}
#output
#67
I hope this meets the requirements ;P
On Aug 18, 3:15 pm, *$* gopi.komand...@gmail.com wrote:
How to find duplicate element (only one element is repeated) from an
array
of unsorted positive integers..
time complexity .. O(n)
space .. o(1).
--
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.
--
Thx,
--Gopi
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT 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.
--
Thx,
--Gopi
--
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 question
O(1) space means constant space. It doesn't mean you can't use extra space.
Refer here:
http://stackoverflow.com/questions/2219109/what-does-this-mean-on-steps-and-o1-space
According to the question you can definitely use a Hash Table for keeping
hit record, as it will be a constant space (provided the range of numbers is
known).
In case the range of numbers is not known, BST will be close answer. Since
only one element will be repeating, the process of making the BST can be
stopped when the first repeating element is caught. BUT, this will be O(n)
space, as the number of nodes in BST will be n-1 in worst case.
On 19 August 2011 07:59, *$* gopi.komand...@gmail.com wrote:
only once
On Fri, Aug 19, 2011 at 7:57 AM, saurabh singh saurab...@gmail.comwrote:
The element is repeated only once or can be repeated k number of times??
On Fri, Aug 19, 2011 at 7:50 AM, *$* gopi.komand...@gmail.com wrote:
I think we are using hash , which is like extra spaace , but as per the
question , O(s) = 1.
Thx,
--Gopi
On Fri, Aug 19, 2011 at 2:15 AM, icy` vipe...@gmail.com wrote:
#!/usr/bin/ruby -w
#array of unsorted positive integers
# find the [only] one that is duplicated
arr= [97,2,54,26,67,12,1,19,44,4,29,36,67,14,93,22,39,89]
h = Hash.new(0)
arr.each {|n|
h[n]+=1
(puts n; break) if h[n]==2
}
#output
#67
I hope this meets the requirements ;P
On Aug 18, 3:15 pm, *$* gopi.komand...@gmail.com wrote:
How to find duplicate element (only one element is repeated) from an
array
of unsorted positive integers..
time complexity .. O(n)
space .. o(1).
--
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.
--
Thx,
--Gopi
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT 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.
--
Thx,
--Gopi
--
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.
--
___
Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
--
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 question
true. I agree , we can use additional memory which will be constant
irrespective of counjt of elements.
But using an hash wont be a constant memory as input can keep on varying.
Thx,
--Gopi
On Fri, Aug 19, 2011 at 8:16 AM, Dipankar Patro dip10c...@gmail.com wrote:
O(1) space means constant space. It doesn't mean you can't use extra space.
Refer here:
http://stackoverflow.com/questions/2219109/what-does-this-mean-on-steps-and-o1-space
According to the question you can definitely use a Hash Table for keeping
hit record, as it will be a constant space (provided the range of numbers is
known).
In case the range of numbers is not known, BST will be close answer. Since
only one element will be repeating, the process of making the BST can be
stopped when the first repeating element is caught. BUT, this will be O(n)
space, as the number of nodes in BST will be n-1 in worst case.
On 19 August 2011 07:59, *$* gopi.komand...@gmail.com wrote:
only once
On Fri, Aug 19, 2011 at 7:57 AM, saurabh singh saurab...@gmail.comwrote:
The element is repeated only once or can be repeated k number of times??
On Fri, Aug 19, 2011 at 7:50 AM, *$* gopi.komand...@gmail.com wrote:
I think we are using hash , which is like extra spaace , but as per the
question , O(s) = 1.
Thx,
--Gopi
On Fri, Aug 19, 2011 at 2:15 AM, icy` vipe...@gmail.com wrote:
#!/usr/bin/ruby -w
#array of unsorted positive integers
# find the [only] one that is duplicated
arr= [97,2,54,26,67,12,1,19,44,4,29,36,67,14,93,22,39,89]
h = Hash.new(0)
arr.each {|n|
h[n]+=1
(puts n; break) if h[n]==2
}
#output
#67
I hope this meets the requirements ;P
On Aug 18, 3:15 pm, *$* gopi.komand...@gmail.com wrote:
How to find duplicate element (only one element is repeated) from an
array
of unsorted positive integers..
time complexity .. O(n)
space .. o(1).
--
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.
--
Thx,
--Gopi
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT 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.
--
Thx,
--Gopi
--
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.
--
___
Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
--
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.
--
Thx,
--Gopi
--
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 question
hash map is the solution provided the elements lie in a predefined range..
On Fri, Aug 19, 2011 at 8:46 AM, *$* gopi.komand...@gmail.com wrote:
true. I agree , we can use additional memory which will be constant
irrespective of counjt of elements.
But using an hash wont be a constant memory as input can keep on varying.
Thx,
--Gopi
On Fri, Aug 19, 2011 at 8:16 AM, Dipankar Patro dip10c...@gmail.comwrote:
O(1) space means constant space. It doesn't mean you can't use extra
space.
Refer here:
http://stackoverflow.com/questions/2219109/what-does-this-mean-on-steps-and-o1-space
According to the question you can definitely use a Hash Table for keeping
hit record, as it will be a constant space (provided the range of numbers is
known).
In case the range of numbers is not known, BST will be close answer. Since
only one element will be repeating, the process of making the BST can be
stopped when the first repeating element is caught. BUT, this will be O(n)
space, as the number of nodes in BST will be n-1 in worst case.
On 19 August 2011 07:59, *$* gopi.komand...@gmail.com wrote:
only once
On Fri, Aug 19, 2011 at 7:57 AM, saurabh singh saurab...@gmail.comwrote:
The element is repeated only once or can be repeated k number of times??
On Fri, Aug 19, 2011 at 7:50 AM, *$* gopi.komand...@gmail.com wrote:
I think we are using hash , which is like extra spaace , but as per the
question , O(s) = 1.
Thx,
--Gopi
On Fri, Aug 19, 2011 at 2:15 AM, icy` vipe...@gmail.com wrote:
#!/usr/bin/ruby -w
#array of unsorted positive integers
# find the [only] one that is duplicated
arr= [97,2,54,26,67,12,1,19,44,4,29,36,67,14,93,22,39,89]
h = Hash.new(0)
arr.each {|n|
h[n]+=1
(puts n; break) if h[n]==2
}
#output
#67
I hope this meets the requirements ;P
On Aug 18, 3:15 pm, *$* gopi.komand...@gmail.com wrote:
How to find duplicate element (only one element is repeated) from an
array
of unsorted positive integers..
time complexity .. O(n)
space .. o(1).
--
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.
--
Thx,
--Gopi
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT 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.
--
Thx,
--Gopi
--
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.
--
___
Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
--
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.
--
Thx,
--Gopi
--
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.
--
*Dheeraj Sharma*
Comp Engg.
NIT Kurukshetra
+91 8950264227
--
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 question
yes , but that constraint is not provided by the interviewer , hence ,
solution of hash is not acceptable
On Fri, Aug 19, 2011 at 8:58 AM, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
hash map is the solution provided the elements lie in a predefined range..
On Fri, Aug 19, 2011 at 8:46 AM, *$* gopi.komand...@gmail.com wrote:
true. I agree , we can use additional memory which will be constant
irrespective of counjt of elements.
But using an hash wont be a constant memory as input can keep on varying.
Thx,
--Gopi
On Fri, Aug 19, 2011 at 8:16 AM, Dipankar Patro dip10c...@gmail.comwrote:
O(1) space means constant space. It doesn't mean you can't use extra
space.
Refer here:
http://stackoverflow.com/questions/2219109/what-does-this-mean-on-steps-and-o1-space
According to the question you can definitely use a Hash Table for keeping
hit record, as it will be a constant space (provided the range of numbers is
known).
In case the range of numbers is not known, BST will be close answer.
Since only one element will be repeating, the process of making the BST can
be stopped when the first repeating element is caught. BUT, this will be
O(n) space, as the number of nodes in BST will be n-1 in worst case.
On 19 August 2011 07:59, *$* gopi.komand...@gmail.com wrote:
only once
On Fri, Aug 19, 2011 at 7:57 AM, saurabh singh saurab...@gmail.comwrote:
The element is repeated only once or can be repeated k number of
times??
On Fri, Aug 19, 2011 at 7:50 AM, *$* gopi.komand...@gmail.com wrote:
I think we are using hash , which is like extra spaace , but as per
the question , O(s) = 1.
Thx,
--Gopi
On Fri, Aug 19, 2011 at 2:15 AM, icy` vipe...@gmail.com wrote:
#!/usr/bin/ruby -w
#array of unsorted positive integers
# find the [only] one that is duplicated
arr= [97,2,54,26,67,12,1,19,44,4,29,36,67,14,93,22,39,89]
h = Hash.new(0)
arr.each {|n|
h[n]+=1
(puts n; break) if h[n]==2
}
#output
#67
I hope this meets the requirements ;P
On Aug 18, 3:15 pm, *$* gopi.komand...@gmail.com wrote:
How to find duplicate element (only one element is repeated) from
an array
of unsorted positive integers..
time complexity .. O(n)
space .. o(1).
--
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.
--
Thx,
--Gopi
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT 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.
--
Thx,
--Gopi
--
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.
--
___
Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
--
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.
--
Thx,
--Gopi
--
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.
--
*Dheeraj Sharma*
Comp Engg.
NIT Kurukshetra
+91 8950264227
--
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.
Re: [algogeeks] Re: Amazon question
In the first loop, numbers are the numbers in the given array but in the second loop, numbers are just natural numbers. I forgot to mention as people may get confused. *Regards Sanju Happy to Help :)* -- 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 question.
@Dave How is the complexity O(n^2logn) .. Can you please tell I believe there cant be solution better than O(n^2) unless u use FFT which again is out of scope , at least for me :) Regards Ankur 2011/8/11 Samba Ganapavarapu sambasiv...@gmail.com Can we find any alg. which runs faster than O(n^2) using these 2 axioms ? 2011/8/10 Amethy hobby news...@gmail.com it also like Pythagorean theorem; so the a[k] also with the value where a[j]-a[i]a[k]a[i]+a[j] and a[k]a[j]=a[i]; On 8月9日, 下午10时43分, Samba Ganapavarapu sambasiv...@gmail.com wrote: We have an array of integers, we need to find the element a[i],a[j] and a[k] values where.. a[i]^2 + a[k]^2 = a[k] ^2 what would be the fast algorithm to find ? - Samba -- 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 question.
Can we find any alg. which runs faster than O(n^2) using these 2 axioms ? 2011/8/10 Amethy hobby news...@gmail.com it also like Pythagorean theorem; so the a[k] also with the value where a[j]-a[i]a[k]a[i]+a[j] and a[k]a[j]=a[i]; On 8月9日, 下午10时43分, Samba Ganapavarapu sambasiv...@gmail.com wrote: We have an array of integers, we need to find the element a[i],a[j] and a[k] values where.. a[i]^2 + a[k]^2 = a[k] ^2 what would be the fast algorithm to find ? - Samba -- 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 question.
@Ankit Sambyal: Agree with ankuj...TC of your solution is O(nlogn) and not O(n^2)... -- 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 question.
@kunal, anuj : step 2 of my algo takes O(n^2). So how can the TC be O(nlogn) -- 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 question.
@Ankit: Ohh Sorry..I didnt actually read the question properly.. I didnt see we have to check for sum which must be another element in the array not some user provided constant value..I mis-understood it with sum upto k problem which can be solved on sorted array in O(n)... thats why gave a wrong comment...my Bad.. -- 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 question.
After squaring all the elements up and sorting them, couldn't we just do a binary search on the array.. so the TC would be O(nlogn)... On Wed, Aug 10, 2011 at 1:18 PM, Kunal Patil kp101...@gmail.com wrote: @Ankit: Ohh Sorry..I didnt actually read the question properly.. I didnt see we have to check for sum which must be another element in the array not some user provided constant value..I mis-understood it with sum upto k problem which can be solved on sorted array in O(n)... thats why gave a wrong comment...my Bad.. -- 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, Dinoj -- 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.
[algogeeks] Re: Amazon question.
@Dinoja: No. You can only binary search for 1 thing, so you would have to choose two elements and then search for the third. Thus, the order would be O(n^2 log n). Dave On Aug 10, 6:11 pm, Dinoja Padmanabhan dino...@gmail.com wrote: After squaring all the elements up and sorting them, couldn't we just do a binary search on the array.. so the TC would be O(nlogn)... On Wed, Aug 10, 2011 at 1:18 PM, Kunal Patil kp101...@gmail.com wrote: @Ankit: Ohh Sorry..I didnt actually read the question properly.. I didnt see we have to check for sum which must be another element in the array not some user provided constant value..I mis-understood it with sum upto k problem which can be solved on sorted array in O(n)... thats why gave a wrong comment...my Bad.. -- 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, Dinoj -- 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.
[algogeeks] Re: Amazon question.
it also like Pythagorean theorem; so the a[k] also with the value where a[j]-a[i]a[k]a[i]+a[j] and a[k]a[j]=a[i]; On 8月9日, 下午10时43分, Samba Ganapavarapu sambasiv...@gmail.com wrote: We have an array of integers, we need to find the element a[i],a[j] and a[k] values where.. a[i]^2 + a[k]^2 = a[k] ^2 what would be the fast algorithm to find ? - Samba -- 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.
[algogeeks] Re: Amazon question.
How is the time O(n^2).It is O(nlgn)
On Aug 9, 7:53 pm, ankit sambyal ankitsamb...@gmail.com wrote:
1. Square each element of the array and then sort it---O(nlogn)
2. for(i=0;i(size-3);i++)
{
j=i+1; k=size-1;
while(jk)
{
if(a[[i] + a[j] == a[k])
printf(\n%d %d %d,sqrt(a[i]),sqrt(a[j]),sqrt(a[k]));
else if(a[i] + a[j] a[k])
j++;
else
k--;
}
}O(n^2)
Time O(n^2)
--
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.
[algogeeks] Re: amazon question
can anyone explain how it's working i didn't get it???
On Aug 7, 10:49 pm, Shachindra A C sachindr...@gmail.com wrote:
8 one's and 8 two's. The order in which they get printed might vary.
On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
what will be the o/p of the following program:
main()
{
int ret;
ret=fork();
ret=fork();
ret=fork();
ret=fork();
if(!ret)
printf(one);
else
printf(two);
}
--
Regards,
Kamakshi
kamakshi...@gmail.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.
--
Regards,
Shachindra A C
--
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.
[algogeeks] Re: amazon question
get it..!! :) :)
On Aug 7, 10:49 pm, Shachindra A C sachindr...@gmail.com wrote:
8 one's and 8 two's. The order in which they get printed might vary.
On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
what will be the o/p of the following program:
main()
{
int ret;
ret=fork();
ret=fork();
ret=fork();
ret=fork();
if(!ret)
printf(one);
else
printf(two);
}
--
Regards,
Kamakshi
kamakshi...@gmail.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.
--
Regards,
Shachindra A C
--
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 question
then please elaborate?
On Mon, Aug 8, 2011 at 12:34 PM, Pradex pradam.prad...@gmail.com wrote:
get it..!! :) :)
On Aug 7, 10:49 pm, Shachindra A C sachindr...@gmail.com wrote:
8 one's and 8 two's. The order in which they get printed might vary.
On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
what will be the o/p of the following program:
main()
{
int ret;
ret=fork();
ret=fork();
ret=fork();
ret=fork();
if(!ret)
printf(one);
else
printf(two);
}
--
Regards,
Kamakshi
kamakshi...@gmail.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.
--
Regards,
Shachindra A C
--
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,
Kamakshi
kamakshi...@gmail.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] Re: amazon question
When Process executed fork(). It create the Same Structure as the main
process.The only difference is the return value of the child fork process is
0 and that of parent is the PID of its Child process.
Now you can draw the pictorial representation of the fork processes during
the execution and its corresponding values.
On Mon, Aug 8, 2011 at 12:49 PM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
then please elaborate?
On Mon, Aug 8, 2011 at 12:34 PM, Pradex pradam.prad...@gmail.com wrote:
get it..!! :) :)
On Aug 7, 10:49 pm, Shachindra A C sachindr...@gmail.com wrote:
8 one's and 8 two's. The order in which they get printed might vary.
On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
what will be the o/p of the following program:
main()
{
int ret;
ret=fork();
ret=fork();
ret=fork();
ret=fork();
if(!ret)
printf(one);
else
printf(two);
}
--
Regards,
Kamakshi
kamakshi...@gmail.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.
--
Regards,
Shachindra A C
--
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,
Kamakshi
kamakshi...@gmail.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] Re: amazon question
At the point of execution of the 4th fork(), there are 8 processes i.e, the
4th fork will get executed 8 times. The final value of ret will depend on
this fork. the fork will return 0 in the 8 child processes created and
returns pid of the child in the parent processes.
On Mon, Aug 8, 2011 at 12:49 PM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
then please elaborate?
On Mon, Aug 8, 2011 at 12:34 PM, Pradex pradam.prad...@gmail.com wrote:
get it..!! :) :)
On Aug 7, 10:49 pm, Shachindra A C sachindr...@gmail.com wrote:
8 one's and 8 two's. The order in which they get printed might vary.
On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
what will be the o/p of the following program:
main()
{
int ret;
ret=fork();
ret=fork();
ret=fork();
ret=fork();
if(!ret)
printf(one);
else
printf(two);
}
--
Regards,
Kamakshi
kamakshi...@gmail.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.
--
Regards,
Shachindra A C
--
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,
Kamakshi
kamakshi...@gmail.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.
--
Regards,
Shachindra A C
--
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 question
lets label your forks :-
main()
{
int ret;
ret=fork(); -- 1
ret=fork(); -- 2
ret=fork(); --- 3
ret=fork(); --- 4
if(!ret)
printf(one);
else
printf(two);
}
Now
original main() is suppose named M
then after encountering fork() 1st then
M
/ \
/\
/\
M C1
now after fork() -2
M
/ \
/\
/\
M C1
/
\ /\
M C2C1 C3
after fork()- 4
it will be
M
C1C2 C3.. C15
now we have half of them include main() have ret!=0 and
rest of them ret=0
i hope its clear now...
On Mon, Aug 8, 2011 at 12:53 PM, Shachindra A C sachindr...@gmail.comwrote:
At the point of execution of the 4th fork(), there are 8 processes i.e, the
4th fork will get executed 8 times. The final value of ret will depend on
this fork. the fork will return 0 in the 8 child processes created and
returns pid of the child in the parent processes.
On Mon, Aug 8, 2011 at 12:49 PM, Kamakshii Aggarwal kamakshi...@gmail.com
wrote:
then please elaborate?
On Mon, Aug 8, 2011 at 12:34 PM, Pradex pradam.prad...@gmail.com wrote:
get it..!! :) :)
On Aug 7, 10:49 pm, Shachindra A C sachindr...@gmail.com wrote:
8 one's and 8 two's. The order in which they get printed might vary.
On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
what will be the o/p of the following program:
main()
{
int ret;
ret=fork();
ret=fork();
ret=fork();
ret=fork();
if(!ret)
printf(one);
else
printf(two);
}
--
Regards,
Kamakshi
kamakshi...@gmail.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.
--
Regards,
Shachindra A C
--
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,
Kamakshi
kamakshi...@gmail.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.
--
Regards,
Shachindra A C
--
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
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
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 question
ok ..thanks sagar..:)
On Mon, Aug 8, 2011 at 6:42 PM, sagar pareek sagarpar...@gmail.com wrote:
lets label your forks :-
main()
{
int ret;
ret=fork(); -- 1
ret=fork(); -- 2
ret=fork(); --- 3
ret=fork(); --- 4
if(!ret)
printf(one);
else
printf(two);
}
Now
original main() is suppose named M
then after encountering fork() 1st then
M
/ \
/\
/\
M C1
now after fork() -2
M
/ \
/\
/\
M C1
/ \ /\
M C2C1 C3
after fork()- 4
it will be
M
C1C2 C3.. C15
now we have half of them include main() have ret!=0 and
rest of them ret=0
i hope its clear now...
On Mon, Aug 8, 2011 at 12:53 PM, Shachindra A C sachindr...@gmail.comwrote:
At the point of execution of the 4th fork(), there are 8 processes i.e,
the 4th fork will get executed 8 times. The final value of ret will depend
on this fork. the fork will return 0 in the 8 child processes created and
returns pid of the child in the parent processes.
On Mon, Aug 8, 2011 at 12:49 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
then please elaborate?
On Mon, Aug 8, 2011 at 12:34 PM, Pradex pradam.prad...@gmail.comwrote:
get it..!! :) :)
On Aug 7, 10:49 pm, Shachindra A C sachindr...@gmail.com wrote:
8 one's and 8 two's. The order in which they get printed might vary.
On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
what will be the o/p of the following program:
main()
{
int ret;
ret=fork();
ret=fork();
ret=fork();
ret=fork();
if(!ret)
printf(one);
else
printf(two);
}
--
Regards,
Kamakshi
kamakshi...@gmail.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.
--
Regards,
Shachindra A C
--
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,
Kamakshi
kamakshi...@gmail.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.
--
Regards,
Shachindra A C
--
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
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
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.
--
Regards,
Kamakshi
kamakshi...@gmail.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] Re: amazon question
@ sagar: wat wud be the order? as in all 8 frst wud return non zero and rest
0 or wat?
On Mon, Aug 8, 2011 at 6:50 PM, Kamakshii Aggarwal kamakshi...@gmail.comwrote:
ok ..thanks sagar..:)
On Mon, Aug 8, 2011 at 6:42 PM, sagar pareek sagarpar...@gmail.comwrote:
lets label your forks :-
main()
{
int ret;
ret=fork(); -- 1
ret=fork(); -- 2
ret=fork(); --- 3
ret=fork(); --- 4
if(!ret)
printf(one);
else
printf(two);
}
Now
original main() is suppose named M
then after encountering fork() 1st then
M
/ \
/\
/\
M C1
now after fork() -2
M
/ \
/\
/\
M C1
/ \ /\
M C2C1 C3
after fork()- 4
it will be
M
C1C2 C3.. C15
now we have half of them include main() have ret!=0 and
rest of them ret=0
i hope its clear now...
On Mon, Aug 8, 2011 at 12:53 PM, Shachindra A C sachindr...@gmail.comwrote:
At the point of execution of the 4th fork(), there are 8 processes i.e,
the 4th fork will get executed 8 times. The final value of ret will depend
on this fork. the fork will return 0 in the 8 child processes created and
returns pid of the child in the parent processes.
On Mon, Aug 8, 2011 at 12:49 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
then please elaborate?
On Mon, Aug 8, 2011 at 12:34 PM, Pradex pradam.prad...@gmail.comwrote:
get it..!! :) :)
On Aug 7, 10:49 pm, Shachindra A C sachindr...@gmail.com wrote:
8 one's and 8 two's. The order in which they get printed might vary.
On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
what will be the o/p of the following program:
main()
{
int ret;
ret=fork();
ret=fork();
ret=fork();
ret=fork();
if(!ret)
printf(one);
else
printf(two);
}
--
Regards,
Kamakshi
kamakshi...@gmail.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.
--
Regards,
Shachindra A C
--
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,
Kamakshi
kamakshi...@gmail.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.
--
Regards,
Shachindra A C
--
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
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
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.
--
Regards,
Kamakshi
kamakshi...@gmail.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.
--
Aditi Garg
Undergraduate Student
Electronics Communication Divison
NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
Sector 3, Dwarka
New Delhi
--
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
Re: [algogeeks] Re: amazon question
M
/ \
/\
/\
/ \
/ \
/ \
/ \
M
C1
/ \
/\
/
\ / \
/
\ /\
/
\ / \
M C2
C1 C3
/ \
/ \ / \ / \
/\
/ \/ \
/\
M C4C2
C5 C1C6 C3 C7
/\ /\/
\/ \/ \ / \ /
\ / \
M C8 C4 C9 C2 C10 C5 C11 C1 C12
C6 C13 C4 C14 C7 C15
M C4 C2 C5 C1 C6 C3 C7 (one level upper will have ret0 and rest will have
ret =0
Just think ur self how any process and its child have pid==0 ???
I hope its clear now...
On Mon, Aug 8, 2011 at 8:05 PM, aditi garg aditi.garg.6...@gmail.comwrote:
@ sagar: wat wud be the order? as in all 8 frst wud return non zero and
rest 0 or wat?
On Mon, Aug 8, 2011 at 6:50 PM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
ok ..thanks sagar..:)
On Mon, Aug 8, 2011 at 6:42 PM, sagar pareek sagarpar...@gmail.comwrote:
lets label your forks :-
main()
{
int ret;
ret=fork(); -- 1
ret=fork(); -- 2
ret=fork(); --- 3
ret=fork(); --- 4
if(!ret)
printf(one);
else
printf(two);
}
Now
original main() is suppose named M
then after encountering fork() 1st then
M
/ \
/\
/\
M C1
now after fork() -2
M
/ \
/\
/\
M C1
/ \ /\
M C2C1 C3
after fork()- 4
it will be
M
C1C2 C3.. C15
now we have half of them include main() have ret!=0
and rest of them ret=0
i hope its clear now...
On Mon, Aug 8, 2011 at 12:53 PM, Shachindra A C
sachindr...@gmail.comwrote:
At the point of execution of the 4th fork(), there are 8 processes i.e,
the 4th fork will get executed 8 times. The final value of ret will depend
on this fork. the fork will return 0 in the 8 child processes created and
returns pid of the child in the parent processes.
On Mon, Aug 8, 2011 at 12:49 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
then please elaborate?
On Mon, Aug 8, 2011 at 12:34 PM, Pradex pradam.prad...@gmail.comwrote:
get it..!! :) :)
On Aug 7, 10:49 pm, Shachindra A C sachindr...@gmail.com wrote:
8 one's and 8 two's. The order in which they get printed might vary.
On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
what will be the o/p of the following program:
main()
{
int ret;
ret=fork();
ret=fork();
ret=fork();
ret=fork();
if(!ret)
printf(one);
else
printf(two);
}
--
Regards,
Kamakshi
kamakshi...@gmail.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.
--
Regards,
Shachindra A C
--
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,
Kamakshi
kamakshi...@gmail.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
Re: [algogeeks] Re: amazon question
i was asking about the order in printfso it wud be like 8times one and
then 8 times two?
On Mon, Aug 8, 2011 at 8:23 PM, sagar pareek sagarpar...@gmail.com wrote:
M
/ \
/\
/\
/ \
/ \
/ \
/ \
M
C1
/ \
/\
/
\ / \
/
\ /\
/
\ / \
M C2
C1 C3
/ \
/ \ / \ / \
/\
/ \/ \
/\
M C4C2
C5 C1C6 C3 C7
/\ /\/
\/ \/ \ / \ /
\ / \
M C8 C4 C9 C2 C10 C5 C11 C1 C12
C6 C13 C4 C14 C7 C15
M C4 C2 C5 C1 C6 C3 C7 (one level upper will have ret0 and rest will
have ret =0
Just think ur self how any process and its child have pid==0 ???
I hope its clear now...
On Mon, Aug 8, 2011 at 8:05 PM, aditi garg aditi.garg.6...@gmail.comwrote:
@ sagar: wat wud be the order? as in all 8 frst wud return non zero and
rest 0 or wat?
On Mon, Aug 8, 2011 at 6:50 PM, Kamakshii Aggarwal kamakshi...@gmail.com
wrote:
ok ..thanks sagar..:)
On Mon, Aug 8, 2011 at 6:42 PM, sagar pareek sagarpar...@gmail.comwrote:
lets label your forks :-
main()
{
int ret;
ret=fork(); -- 1
ret=fork(); -- 2
ret=fork(); --- 3
ret=fork(); --- 4
if(!ret)
printf(one);
else
printf(two);
}
Now
original main() is suppose named M
then after encountering fork() 1st then
M
/ \
/\
/\
M C1
now after fork() -2
M
/ \
/\
/\
M C1
/ \ /\
M C2C1 C3
after fork()- 4
it will be
M
C1C2 C3.. C15
now we have half of them include main() have ret!=0
and rest of them ret=0
i hope its clear now...
On Mon, Aug 8, 2011 at 12:53 PM, Shachindra A C
sachindr...@gmail.comwrote:
At the point of execution of the 4th fork(), there are 8 processes i.e,
the 4th fork will get executed 8 times. The final value of ret will depend
on this fork. the fork will return 0 in the 8 child processes created and
returns pid of the child in the parent processes.
On Mon, Aug 8, 2011 at 12:49 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
then please elaborate?
On Mon, Aug 8, 2011 at 12:34 PM, Pradex pradam.prad...@gmail.comwrote:
get it..!! :) :)
On Aug 7, 10:49 pm, Shachindra A C sachindr...@gmail.com wrote:
8 one's and 8 two's. The order in which they get printed might
vary.
On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
what will be the o/p of the following program:
main()
{
int ret;
ret=fork();
ret=fork();
ret=fork();
ret=fork();
if(!ret)
printf(one);
else
printf(two);
}
--
Regards,
Kamakshi
kamakshi...@gmail.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.
--
Regards,
Shachindra A C
--
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,
Kamakshi
Re: [algogeeks] Re: amazon question
no it'll vary as the PID will vary from parent to child.
On Mon, Aug 8, 2011 at 8:05 AM, aditi garg aditi.garg.6...@gmail.comwrote:
i was asking about the order in printfso it wud be like 8times one and
then 8 times two?
On Mon, Aug 8, 2011 at 8:23 PM, sagar pareek sagarpar...@gmail.comwrote:
M
/ \
/\
/\
/ \
/ \
/ \
/ \
M
C1
/ \
/\
/
\ / \
/
\ /\
/
\ / \
M
C2 C1 C3
/ \
/ \ / \ / \
/\
/ \/ \
/\
M C4C2
C5 C1C6 C3 C7
/\ /\/
\/ \/ \ / \ /
\ / \
M C8 C4 C9 C2 C10 C5 C11 C1
C12 C6 C13 C4 C14 C7 C15
M C4 C2 C5 C1 C6 C3 C7 (one level upper will have ret0 and rest will
have ret =0
Just think ur self how any process and its child have pid==0 ???
I hope its clear now...
On Mon, Aug 8, 2011 at 8:05 PM, aditi garg aditi.garg.6...@gmail.comwrote:
@ sagar: wat wud be the order? as in all 8 frst wud return non zero and
rest 0 or wat?
On Mon, Aug 8, 2011 at 6:50 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
ok ..thanks sagar..:)
On Mon, Aug 8, 2011 at 6:42 PM, sagar pareek sagarpar...@gmail.comwrote:
lets label your forks :-
main()
{
int ret;
ret=fork(); -- 1
ret=fork(); -- 2
ret=fork(); --- 3
ret=fork(); --- 4
if(!ret)
printf(one);
else
printf(two);
}
Now
original main() is suppose named M
then after encountering fork() 1st then
M
/ \
/\
/\
M C1
now after fork() -2
M
/ \
/\
/\
M C1
/ \ /\
M C2C1 C3
after fork()- 4
it will be
M C1C2 C3.. C15
now we have half of them include main() have ret!=0
and rest of them ret=0
i hope its clear now...
On Mon, Aug 8, 2011 at 12:53 PM, Shachindra A C sachindr...@gmail.com
wrote:
At the point of execution of the 4th fork(), there are 8 processes
i.e, the 4th fork will get executed 8 times. The final value of ret will
depend on this fork. the fork will return 0 in the 8 child processes
created
and returns pid of the child in the parent processes.
On Mon, Aug 8, 2011 at 12:49 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
then please elaborate?
On Mon, Aug 8, 2011 at 12:34 PM, Pradex pradam.prad...@gmail.comwrote:
get it..!! :) :)
On Aug 7, 10:49 pm, Shachindra A C sachindr...@gmail.com wrote:
8 one's and 8 two's. The order in which they get printed might
vary.
On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
what will be the o/p of the following program:
main()
{
int ret;
ret=fork();
ret=fork();
ret=fork();
ret=fork();
if(!ret)
printf(one);
else
printf(two);
}
--
Regards,
Kamakshi
kamakshi...@gmail.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.
--
Regards,
Shachindra A C
--
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
Re: [algogeeks] Re: amazon question
@aditi
nope... it will run in parallel...so order is not fix
On Mon, Aug 8, 2011 at 8:48 PM, Pradeep Mishra pradam.prad...@gmail.comwrote:
no it'll vary as the PID will vary from parent to child.
On Mon, Aug 8, 2011 at 8:05 AM, aditi garg aditi.garg.6...@gmail.comwrote:
i was asking about the order in printfso it wud be like 8times one
and then 8 times two?
On Mon, Aug 8, 2011 at 8:23 PM, sagar pareek sagarpar...@gmail.comwrote:
M
/ \
/\
/\
/ \
/ \
/ \
/ \
M
C1
/ \
/\
/
\ / \
/
\ /\
/
\ / \
M
C2 C1 C3
/ \
/ \ / \ / \
/\
/ \/ \
/\
M C4
C2 C5 C1C6 C3 C7
/\ /\/
\/ \/ \ / \ /
\ / \
M C8 C4 C9 C2 C10 C5 C11 C1
C12 C6 C13 C4 C14 C7 C15
M C4 C2 C5 C1 C6 C3 C7 (one level upper will have ret0 and rest will
have ret =0
Just think ur self how any process and its child have pid==0 ???
I hope its clear now...
On Mon, Aug 8, 2011 at 8:05 PM, aditi garg aditi.garg.6...@gmail.comwrote:
@ sagar: wat wud be the order? as in all 8 frst wud return non zero and
rest 0 or wat?
On Mon, Aug 8, 2011 at 6:50 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
ok ..thanks sagar..:)
On Mon, Aug 8, 2011 at 6:42 PM, sagar pareek sagarpar...@gmail.comwrote:
lets label your forks :-
main()
{
int ret;
ret=fork(); -- 1
ret=fork(); -- 2
ret=fork(); --- 3
ret=fork(); --- 4
if(!ret)
printf(one);
else
printf(two);
}
Now
original main() is suppose named M
then after encountering fork() 1st then
M
/ \
/\
/\
M C1
now after fork() -2
M
/ \
/\
/\
M C1
/ \ /\
M C2C1 C3
after fork()- 4
it will be
M C1C2 C3.. C15
now we have half of them include main() have ret!=0
and rest of them ret=0
i hope its clear now...
On Mon, Aug 8, 2011 at 12:53 PM, Shachindra A C
sachindr...@gmail.com wrote:
At the point of execution of the 4th fork(), there are 8 processes
i.e, the 4th fork will get executed 8 times. The final value of ret will
depend on this fork. the fork will return 0 in the 8 child processes
created
and returns pid of the child in the parent processes.
On Mon, Aug 8, 2011 at 12:49 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
then please elaborate?
On Mon, Aug 8, 2011 at 12:34 PM, Pradex
pradam.prad...@gmail.comwrote:
get it..!! :) :)
On Aug 7, 10:49 pm, Shachindra A C sachindr...@gmail.com wrote:
8 one's and 8 two's. The order in which they get printed might
vary.
On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
what will be the o/p of the following program:
main()
{
int ret;
ret=fork();
ret=fork();
ret=fork();
ret=fork();
if(!ret)
printf(one);
else
printf(two);
}
--
Regards,
Kamakshi
kamakshi...@gmail.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.
--
Regards,
Shachindra A C
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to
Re: [algogeeks] Re: amazon question
@sagar thanx :)
On Mon, Aug 8, 2011 at 9:01 PM, sagar pareek sagarpar...@gmail.com wrote:
@aditi
nope... it will run in parallel...so order is not fix
On Mon, Aug 8, 2011 at 8:48 PM, Pradeep Mishra
pradam.prad...@gmail.comwrote:
no it'll vary as the PID will vary from parent to child.
On Mon, Aug 8, 2011 at 8:05 AM, aditi garg aditi.garg.6...@gmail.comwrote:
i was asking about the order in printfso it wud be like 8times one
and then 8 times two?
On Mon, Aug 8, 2011 at 8:23 PM, sagar pareek sagarpar...@gmail.comwrote:
M
/ \
/\
/\
/ \
/ \
/ \
/ \
M
C1
/ \
/\
/
\ / \
/
\ /\
/
\ / \
M
C2 C1 C3
/ \
/ \ / \ /
\
/\
/ \/ \
/\
M C4
C2 C5 C1C6 C3 C7
/\ /\/
\/ \/ \ / \ /
\ / \
M C8 C4 C9 C2 C10 C5 C11 C1
C12 C6 C13 C4 C14 C7 C15
M C4 C2 C5 C1 C6 C3 C7 (one level upper will have ret0 and rest will
have ret =0
Just think ur self how any process and its child have pid==0 ???
I hope its clear now...
On Mon, Aug 8, 2011 at 8:05 PM, aditi garg
aditi.garg.6...@gmail.comwrote:
@ sagar: wat wud be the order? as in all 8 frst wud return non zero and
rest 0 or wat?
On Mon, Aug 8, 2011 at 6:50 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
ok ..thanks sagar..:)
On Mon, Aug 8, 2011 at 6:42 PM, sagar pareek
sagarpar...@gmail.comwrote:
lets label your forks :-
main()
{
int ret;
ret=fork(); -- 1
ret=fork(); -- 2
ret=fork(); --- 3
ret=fork(); --- 4
if(!ret)
printf(one);
else
printf(two);
}
Now
original main() is suppose named M
then after encountering fork() 1st then
M
/ \
/\
/\
M C1
now after fork() -2
M
/ \
/\
/\
M C1
/ \ /\
M C2C1 C3
after fork()- 4
it will be
M C1C2 C3.. C15
now we have half of them include main() have
ret!=0 and rest of them ret=0
i hope its clear now...
On Mon, Aug 8, 2011 at 12:53 PM, Shachindra A C
sachindr...@gmail.com wrote:
At the point of execution of the 4th fork(), there are 8 processes
i.e, the 4th fork will get executed 8 times. The final value of ret
will
depend on this fork. the fork will return 0 in the 8 child processes
created
and returns pid of the child in the parent processes.
On Mon, Aug 8, 2011 at 12:49 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
then please elaborate?
On Mon, Aug 8, 2011 at 12:34 PM, Pradex
pradam.prad...@gmail.comwrote:
get it..!! :) :)
On Aug 7, 10:49 pm, Shachindra A C sachindr...@gmail.com wrote:
8 one's and 8 two's. The order in which they get printed might
vary.
On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
what will be the o/p of the following program:
main()
{
int ret;
ret=fork();
ret=fork();
ret=fork();
ret=fork();
if(!ret)
printf(one);
else
printf(two);
}
--
Regards,
Kamakshi
kamakshi...@gmail.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.
--
Regards,
Shachindra A C
--
You received this message because you are subscribed
Re: [algogeeks] Re: amazon question
@sagar: i think order has to be fixed...in amazon they gave us four
options
but i dnt remember them now...
On Mon, Aug 8, 2011 at 10:05 PM, aditi garg aditi.garg.6...@gmail.comwrote:
@sagar thanx :)
On Mon, Aug 8, 2011 at 9:01 PM, sagar pareek sagarpar...@gmail.comwrote:
@aditi
nope... it will run in parallel...so order is not fix
On Mon, Aug 8, 2011 at 8:48 PM, Pradeep Mishra
pradam.prad...@gmail.comwrote:
no it'll vary as the PID will vary from parent to child.
On Mon, Aug 8, 2011 at 8:05 AM, aditi garg aditi.garg.6...@gmail.comwrote:
i was asking about the order in printfso it wud be like 8times one
and then 8 times two?
On Mon, Aug 8, 2011 at 8:23 PM, sagar pareek sagarpar...@gmail.comwrote:
M
/ \
/\
/\
/ \
/ \
/ \
/ \
M
C1
/ \
/\
/
\ / \
/
\ /\
/
\ / \
M
C2 C1 C3
/ \
/ \ / \ /
\
/\
/ \/ \
/\
M C4
C2 C5 C1C6 C3 C7
/\ /\/
\/ \/ \ / \ /
\ / \
M C8 C4 C9 C2 C10 C5 C11 C1
C12 C6 C13 C4 C14 C7 C15
M C4 C2 C5 C1 C6 C3 C7 (one level upper will have ret0 and rest will
have ret =0
Just think ur self how any process and its child have pid==0 ???
I hope its clear now...
On Mon, Aug 8, 2011 at 8:05 PM, aditi garg
aditi.garg.6...@gmail.comwrote:
@ sagar: wat wud be the order? as in all 8 frst wud return non zero
and rest 0 or wat?
On Mon, Aug 8, 2011 at 6:50 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
ok ..thanks sagar..:)
On Mon, Aug 8, 2011 at 6:42 PM, sagar pareek
sagarpar...@gmail.comwrote:
lets label your forks :-
main()
{
int ret;
ret=fork(); -- 1
ret=fork(); -- 2
ret=fork(); --- 3
ret=fork(); --- 4
if(!ret)
printf(one);
else
printf(two);
}
Now
original main() is suppose named M
then after encountering fork() 1st then
M
/ \
/\
/\
M C1
now after fork() -2
M
/ \
/\
/\
M C1
/ \ /\
M C2C1 C3
after fork()- 4
it will be
M C1C2 C3.. C15
now we have half of them include main() have
ret!=0 and rest of them ret=0
i hope its clear now...
On Mon, Aug 8, 2011 at 12:53 PM, Shachindra A C
sachindr...@gmail.com wrote:
At the point of execution of the 4th fork(), there are 8 processes
i.e, the 4th fork will get executed 8 times. The final value of ret
will
depend on this fork. the fork will return 0 in the 8 child processes
created
and returns pid of the child in the parent processes.
On Mon, Aug 8, 2011 at 12:49 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
then please elaborate?
On Mon, Aug 8, 2011 at 12:34 PM, Pradex pradam.prad...@gmail.com
wrote:
get it..!! :) :)
On Aug 7, 10:49 pm, Shachindra A C sachindr...@gmail.com
wrote:
8 one's and 8 two's. The order in which they get printed might
vary.
On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
what will be the o/p of the following program:
main()
{
int ret;
ret=fork();
ret=fork();
ret=fork();
ret=fork();
if(!ret)
printf(one);
else
printf(two);
}
--
Regards,
Kamakshi
kamakshi...@gmail.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
Re: [algogeeks] Re: amazon question
@kamaskshi:
The order of execution of the processes cant be in user hands.It is a
scheduling aspect.So we cant expect the peculiar order.
On 8 August 2011 22:10, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
@sagar: i think order has to be fixed...in amazon they gave us four
options
but i dnt remember them now...
On Mon, Aug 8, 2011 at 10:05 PM, aditi garg aditi.garg.6...@gmail.comwrote:
@sagar thanx :)
On Mon, Aug 8, 2011 at 9:01 PM, sagar pareek sagarpar...@gmail.comwrote:
@aditi
nope... it will run in parallel...so order is not fix
On Mon, Aug 8, 2011 at 8:48 PM, Pradeep Mishra pradam.prad...@gmail.com
wrote:
no it'll vary as the PID will vary from parent to child.
On Mon, Aug 8, 2011 at 8:05 AM, aditi garg
aditi.garg.6...@gmail.comwrote:
i was asking about the order in printfso it wud be like 8times one
and then 8 times two?
On Mon, Aug 8, 2011 at 8:23 PM, sagar pareek sagarpar...@gmail.comwrote:
M
/ \
/\
/\
/ \
/ \
/ \
/ \
M
C1
/ \
/\
/
\ / \
/
\ /\
/ \
/ \
M
C2 C1 C3
/ \
/ \ / \ /
\
/\
/ \/ \
/\
M C4
C2 C5 C1C6 C3 C7
/\ /\/
\/ \/ \ / \ /
\ / \
M C8 C4 C9 C2 C10 C5 C11 C1
C12 C6 C13 C4 C14 C7 C15
M C4 C2 C5 C1 C6 C3 C7 (one level upper will have ret0 and rest
will have ret =0
Just think ur self how any process and its child have pid==0 ???
I hope its clear now...
On Mon, Aug 8, 2011 at 8:05 PM, aditi garg aditi.garg.6...@gmail.com
wrote:
@ sagar: wat wud be the order? as in all 8 frst wud return non zero
and rest 0 or wat?
On Mon, Aug 8, 2011 at 6:50 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
ok ..thanks sagar..:)
On Mon, Aug 8, 2011 at 6:42 PM, sagar pareek sagarpar...@gmail.com
wrote:
lets label your forks :-
main()
{
int ret;
ret=fork(); -- 1
ret=fork(); -- 2
ret=fork(); --- 3
ret=fork(); --- 4
if(!ret)
printf(one);
else
printf(two);
}
Now
original main() is suppose named M
then after encountering fork() 1st then
M
/ \
/\
/\
M C1
now after fork() -2
M
/ \
/\
/\
M C1
/ \ /\
M C2C1 C3
after fork()- 4
it will be
M C1C2 C3.. C15
now we have half of them include main() have
ret!=0 and rest of them ret=0
i hope its clear now...
On Mon, Aug 8, 2011 at 12:53 PM, Shachindra A C
sachindr...@gmail.com wrote:
At the point of execution of the 4th fork(), there are 8 processes
i.e, the 4th fork will get executed 8 times. The final value of ret
will
depend on this fork. the fork will return 0 in the 8 child processes
created
and returns pid of the child in the parent processes.
On Mon, Aug 8, 2011 at 12:49 PM, Kamakshii Aggarwal
kamakshi...@gmail.com wrote:
then please elaborate?
On Mon, Aug 8, 2011 at 12:34 PM, Pradex
pradam.prad...@gmail.com wrote:
get it..!! :) :)
On Aug 7, 10:49 pm, Shachindra A C sachindr...@gmail.com
wrote:
8 one's and 8 two's. The order in which they get printed might
vary.
On Mon, Aug 8, 2011 at 11:11 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
what will be the o/p of the following program:
main()
{
int ret;
ret=fork();
ret=fork();
ret=fork();
ret=fork();
if(!ret)
printf(one);
else
printf(two);
}
--
Regards,
Kamakshi
kamakshi...@gmail.com
--
You received this message because you are subscribed to the
Google Groups
Re: [algogeeks] Re: amazon question
the order of printfs depend on the scheduling algorithms which OS is following and can't be predicted -- 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 question
@ankit:i feel you are right!!! Thank you, Siddharam On Mon, Aug 8, 2011 at 10:56 PM, ankit sambyal ankitsamb...@gmail.comwrote: the order of printfs depend on the scheduling algorithms which OS is following and can't be predicted -- 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 Question
@shiva viknesh
this is a different Question...
@saurabh
how is nlgn possible, total no of possible substrings are n^2
this is the O(n^2) solutionOn Wed, Jul 27, 2011 at 8:09 AM, saurabh singh
for(int l = 0; l len; l++){
for(int i = 0; i len-l; i++){
int j = i+l;
char temp = s[j+1];
s[j+1] = 0;
printf(%s\n, s+i);
s[j+1] = temp;
}
}
saurab...@gmail.com wrote:
using suffix tree this can be done in o(nlogn) though will take extra space.
On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh sivavikne...@gmail.com wrote:
http://geeksforgeeks.org/?p=767
On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote:
how?
On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com wrote:
@vivin : Suffix trees are memory intensive..
This problem can be solved just by running 2 nested loops in O(1)
space and O(n^2) time
--
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 Pratima :)
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT 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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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 Question
@sunny
consider *uncompressed* suffix tree, even with distinct elements maximum
number of nodes with string length n formed will be 2n.
once suffix tree is constructed, needs to traverse in dfs order appending
the node found on the way.
total complexity would be O(construction of suffix tree ) + O(traverse
time).
surender
On Wed, Jul 27, 2011 at 12:00 PM, sunny agrawal sunny816.i...@gmail.comwrote:
@shiva viknesh
this is a different Question...
@saurabh
how is nlgn possible, total no of possible substrings are n^2
this is the O(n^2) solutionOn Wed, Jul 27, 2011 at 8:09 AM, saurabh singh
for(int l = 0; l len; l++){
for(int i = 0; i len-l; i++){
int j = i+l;
char temp = s[j+1];
s[j+1] = 0;
printf(%s\n, s+i);
s[j+1] = temp;
}
}
saurab...@gmail.com wrote:
using suffix tree this can be done in o(nlogn) though will take extra
space.
On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh sivavikne...@gmail.com
wrote:
http://geeksforgeeks.org/?p=767
On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote:
how?
On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com wrote:
@vivin : Suffix trees are memory intensive..
This problem can be solved just by running 2 nested loops in O(1)
space and O(n^2) time
--
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 Pratima :)
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT 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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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 Question
But still Printing O(N^2) substrings will take O(N^2) time isn't it ?
On Wed, Jul 27, 2011 at 12:39 PM, surender sanke surend...@gmail.comwrote:
@sunny
consider *uncompressed* suffix tree, even with distinct elements maximum
number of nodes with string length n formed will be 2n.
once suffix tree is constructed, needs to traverse in dfs order appending
the node found on the way.
total complexity would be O(construction of suffix tree ) + O(traverse
time).
surender
On Wed, Jul 27, 2011 at 12:00 PM, sunny agrawal
sunny816.i...@gmail.comwrote:
@shiva viknesh
this is a different Question...
@saurabh
how is nlgn possible, total no of possible substrings are n^2
this is the O(n^2) solutionOn Wed, Jul 27, 2011 at 8:09 AM, saurabh singh
for(int l = 0; l len; l++){
for(int i = 0; i len-l; i++){
int j = i+l;
char temp = s[j+1];
s[j+1] = 0;
printf(%s\n, s+i);
s[j+1] = temp;
}
}
saurab...@gmail.com wrote:
using suffix tree this can be done in o(nlogn) though will take extra
space.
On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh sivavikne...@gmail.com
wrote:
http://geeksforgeeks.org/?p=767
On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote:
how?
On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com wrote:
@vivin : Suffix trees are memory intensive..
This problem can be solved just by running 2 nested loops in O(1)
space and O(n^2) time
--
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 Pratima :)
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT 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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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 Question
*
/ \\
a bc
/\
b c
/
c
prints *a*
comes to b, appends a with bprints *ab*
comes to c ,appends ab with c prints *abc*
starts with new child
prints *b*
prints *bc*
prints *c*
surender
On Wed, Jul 27, 2011 at 12:46 PM, sunny agrawal sunny816.i...@gmail.comwrote:
But still Printing O(N^2) substrings will take O(N^2) time isn't it ?
On Wed, Jul 27, 2011 at 12:39 PM, surender sanke surend...@gmail.comwrote:
@sunny
consider *uncompressed* suffix tree, even with distinct elements maximum
number of nodes with string length n formed will be 2n.
once suffix tree is constructed, needs to traverse in dfs order appending
the node found on the way.
total complexity would be O(construction of suffix tree ) + O(traverse
time).
surender
On Wed, Jul 27, 2011 at 12:00 PM, sunny agrawal
sunny816.i...@gmail.comwrote:
@shiva viknesh
this is a different Question...
@saurabh
how is nlgn possible, total no of possible substrings are n^2
this is the O(n^2) solutionOn Wed, Jul 27, 2011 at 8:09 AM, saurabh singh
for(int l = 0; l len; l++){
for(int i = 0; i len-l; i++){
int j = i+l;
char temp = s[j+1];
s[j+1] = 0;
printf(%s\n, s+i);
s[j+1] = temp;
}
}
saurab...@gmail.com wrote:
using suffix tree this can be done in o(nlogn) though will take extra
space.
On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh sivavikne...@gmail.com
wrote:
http://geeksforgeeks.org/?p=767
On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote:
how?
On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com
wrote:
@vivin : Suffix trees are memory intensive..
This problem can be solved just by running 2 nested loops in O(1)
space and O(n^2) time
--
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 Pratima :)
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT 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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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 Question
i don't find difference between your suffix tree approach and my simple
O(N^2) method
in both cases printf statement will be executed O(N^2) times
and in Suffix Tree approach will take some extra time of construction of
tree and extra space too !
On Wed, Jul 27, 2011 at 1:45 PM, surender sanke surend...@gmail.com wrote:
*
/ \\
a bc
/\
b c
/
c
prints *a*
comes to b, appends a with bprints *ab*
comes to c ,appends ab with c prints *abc*
starts with new child
prints *b*
prints *bc*
prints *c*
surender
On Wed, Jul 27, 2011 at 12:46 PM, sunny agrawal
sunny816.i...@gmail.comwrote:
But still Printing O(N^2) substrings will take O(N^2) time isn't it ?
On Wed, Jul 27, 2011 at 12:39 PM, surender sanke surend...@gmail.comwrote:
@sunny
consider *uncompressed* suffix tree, even with distinct elements maximum
number of nodes with string length n formed will be 2n.
once suffix tree is constructed, needs to traverse in dfs order
appending the node found on the way.
total complexity would be O(construction of suffix tree ) + O(traverse
time).
surender
On Wed, Jul 27, 2011 at 12:00 PM, sunny agrawal sunny816.i...@gmail.com
wrote:
@shiva viknesh
this is a different Question...
@saurabh
how is nlgn possible, total no of possible substrings are n^2
this is the O(n^2) solutionOn Wed, Jul 27, 2011 at 8:09 AM, saurabh
singh
for(int l = 0; l len; l++){
for(int i = 0; i len-l; i++){
int j = i+l;
char temp = s[j+1];
s[j+1] = 0;
printf(%s\n, s+i);
s[j+1] = temp;
}
}
saurab...@gmail.com wrote:
using suffix tree this can be done in o(nlogn) though will take extra
space.
On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh
sivavikne...@gmail.com wrote:
http://geeksforgeeks.org/?p=767
On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote:
how?
On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com
wrote:
@vivin : Suffix trees are memory intensive..
This problem can be solved just by running 2 nested loops in O(1)
space and O(n^2) time
--
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 Pratima :)
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT 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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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
Re: [algogeeks] Re: Amazon Question
@ sunny , ur right!!
surender
On Wed, Jul 27, 2011 at 1:58 PM, sunny agrawal sunny816.i...@gmail.comwrote:
i don't find difference between your suffix tree approach and my simple
O(N^2) method
in both cases printf statement will be executed O(N^2) times
and in Suffix Tree approach will take some extra time of construction of
tree and extra space too !
On Wed, Jul 27, 2011 at 1:45 PM, surender sanke surend...@gmail.comwrote:
*
/ \\
a bc
/\
b c
/
c
prints *a*
comes to b, appends a with bprints *ab*
comes to c ,appends ab with c prints *abc*
starts with new child
prints *b*
prints *bc*
prints *c*
surender
On Wed, Jul 27, 2011 at 12:46 PM, sunny agrawal
sunny816.i...@gmail.comwrote:
But still Printing O(N^2) substrings will take O(N^2) time isn't it ?
On Wed, Jul 27, 2011 at 12:39 PM, surender sanke surend...@gmail.comwrote:
@sunny
consider *uncompressed* suffix tree, even with distinct elements
maximum number of nodes with string length n formed will be 2n.
once suffix tree is constructed, needs to traverse in dfs order
appending the node found on the way.
total complexity would be O(construction of suffix tree ) + O(traverse
time).
surender
On Wed, Jul 27, 2011 at 12:00 PM, sunny agrawal
sunny816.i...@gmail.com wrote:
@shiva viknesh
this is a different Question...
@saurabh
how is nlgn possible, total no of possible substrings are n^2
this is the O(n^2) solutionOn Wed, Jul 27, 2011 at 8:09 AM, saurabh
singh
for(int l = 0; l len; l++){
for(int i = 0; i len-l; i++){
int j = i+l;
char temp = s[j+1];
s[j+1] = 0;
printf(%s\n, s+i);
s[j+1] = temp;
}
}
saurab...@gmail.com wrote:
using suffix tree this can be done in o(nlogn) though will take extra
space.
On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh
sivavikne...@gmail.com wrote:
http://geeksforgeeks.org/?p=767
On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote:
how?
On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com
wrote:
@vivin : Suffix trees are memory intensive..
This problem can be solved just by running 2 nested loops in
O(1)
space and O(n^2) time
--
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 Pratima :)
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT 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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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] Re: Amazon Question
hmm o(nlogn) was for constructing the tree.Btw sorry for being unclear.
The best solution is the obvious one in this case.
On Wed, Jul 27, 2011 at 2:10 PM, surender sanke surend...@gmail.com wrote:
@ sunny , ur right!!
surender
On Wed, Jul 27, 2011 at 1:58 PM, sunny agrawal sunny816.i...@gmail.comwrote:
i don't find difference between your suffix tree approach and my simple
O(N^2) method
in both cases printf statement will be executed O(N^2) times
and in Suffix Tree approach will take some extra time of construction of
tree and extra space too !
On Wed, Jul 27, 2011 at 1:45 PM, surender sanke surend...@gmail.comwrote:
*
/ \\
a bc
/\
b c
/
c
prints *a*
comes to b, appends a with bprints *ab*
comes to c ,appends ab with c prints *abc*
starts with new child
prints *b*
prints *bc*
prints *c*
surender
On Wed, Jul 27, 2011 at 12:46 PM, sunny agrawal sunny816.i...@gmail.com
wrote:
But still Printing O(N^2) substrings will take O(N^2) time isn't it ?
On Wed, Jul 27, 2011 at 12:39 PM, surender sanke
surend...@gmail.comwrote:
@sunny
consider *uncompressed* suffix tree, even with distinct elements
maximum number of nodes with string length n formed will be 2n.
once suffix tree is constructed, needs to traverse in dfs order
appending the node found on the way.
total complexity would be O(construction of suffix tree ) + O(traverse
time).
surender
On Wed, Jul 27, 2011 at 12:00 PM, sunny agrawal
sunny816.i...@gmail.com wrote:
@shiva viknesh
this is a different Question...
@saurabh
how is nlgn possible, total no of possible substrings are n^2
this is the O(n^2) solutionOn Wed, Jul 27, 2011 at 8:09 AM, saurabh
singh
for(int l = 0; l len; l++){
for(int i = 0; i len-l; i++){
int j = i+l;
char temp = s[j+1];
s[j+1] = 0;
printf(%s\n, s+i);
s[j+1] = temp;
}
}
saurab...@gmail.com wrote:
using suffix tree this can be done in o(nlogn) though will take
extra space.
On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh
sivavikne...@gmail.com wrote:
http://geeksforgeeks.org/?p=767
On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote:
how?
On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com
wrote:
@vivin : Suffix trees are memory intensive..
This problem can be solved just by running 2 nested loops in
O(1)
space and O(n^2) time
--
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 Pratima :)
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT 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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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 Question
in the above example y ac is not included in the substring?
On Wed, Jul 27, 2011 at 3:45 PM, saurabh singh saurab...@gmail.com wrote:
hmm o(nlogn) was for constructing the tree.Btw sorry for being unclear.
The best solution is the obvious one in this case.
On Wed, Jul 27, 2011 at 2:10 PM, surender sanke surend...@gmail.comwrote:
@ sunny , ur right!!
surender
On Wed, Jul 27, 2011 at 1:58 PM, sunny agrawal
sunny816.i...@gmail.comwrote:
i don't find difference between your suffix tree approach and my simple
O(N^2) method
in both cases printf statement will be executed O(N^2) times
and in Suffix Tree approach will take some extra time of construction of
tree and extra space too !
On Wed, Jul 27, 2011 at 1:45 PM, surender sanke surend...@gmail.comwrote:
*
/ \\
a bc
/\
b c
/
c
prints *a*
comes to b, appends a with bprints *ab*
comes to c ,appends ab with c prints *abc*
starts with new child
prints *b*
prints *bc*
prints *c*
surender
On Wed, Jul 27, 2011 at 12:46 PM, sunny agrawal
sunny816.i...@gmail.com wrote:
But still Printing O(N^2) substrings will take O(N^2) time isn't it ?
On Wed, Jul 27, 2011 at 12:39 PM, surender sanke
surend...@gmail.comwrote:
@sunny
consider *uncompressed* suffix tree, even with distinct elements
maximum number of nodes with string length n formed will be 2n.
once suffix tree is constructed, needs to traverse in dfs order
appending the node found on the way.
total complexity would be O(construction of suffix tree ) + O(traverse
time).
surender
On Wed, Jul 27, 2011 at 12:00 PM, sunny agrawal
sunny816.i...@gmail.com wrote:
@shiva viknesh
this is a different Question...
@saurabh
how is nlgn possible, total no of possible substrings are n^2
this is the O(n^2) solutionOn Wed, Jul 27, 2011 at 8:09 AM, saurabh
singh
for(int l = 0; l len; l++){
for(int i = 0; i len-l; i++){
int j = i+l;
char temp = s[j+1];
s[j+1] = 0;
printf(%s\n, s+i);
s[j+1] = temp;
}
}
saurab...@gmail.com wrote:
using suffix tree this can be done in o(nlogn) though will take
extra space.
On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh
sivavikne...@gmail.com wrote:
http://geeksforgeeks.org/?p=767
On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote:
how?
On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com
wrote:
@vivin : Suffix trees are memory intensive..
This problem can be solved just by running 2 nested loops in
O(1)
space and O(n^2) time
--
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 Pratima :)
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT 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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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] Re: Amazon Question
The following code can be used to generate permutations of the string.. but
still some bugs are there like to avoid already printed char etc.. however
logic will be similar..
order will be less that n^2
// stringPermutration.cpp : Defines the entry point for the console
application.
//
#include stdafx.h
#includestdio.h
#includestring.h
#includestring
#includeiostream
using namespace std;
using namespace std;
void Permutate(int pos,char *prefix,char *str,char *src)
{
char *prefix1,*str1,*src1;
prefix1 = new char[20];
memset(prefix1,0,20);
str1 = new char[20];
memset(str1,0,20);
src1 = new char[20];
memset(src1,0,20);
if(pos = strlen(src))
return;
if(strlen(str)!=0)
{
strcpy(prefix1,prefix);
strcpy(str1,str);
strcpy(src1,src);
prefix1[strlen(prefix1)]=str1[0];
prefix1[strlen(prefix1)+1]='\0';
for(int i=0;istrlen(str1);i++)
{
str1[i]=str1[i+1];
}
}
else
{
int j;
int pos1=pos+1;
for(int i=pos1,j=0;jstrlen(src);)
{
str[j]=src[(i+j)%strlen(src)];
j++;
//i++;
}
strcpy(prefix1,);
strcpy(str1,str);
pos++;
}
strcpy(prefix,prefix1);
strcpy(str,str1);
Permutate(pos,prefix,str,src);
for(int x=0;xstrlen(str1);x++)
{
printf(\n %s,prefix1);
printf(%c,str1[x]);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
char *str = new char[20];
char *remaining = new char[20];
memset(str,0,20);
memset(remaining,0,20);
strcpy(str,abcd);
strcpy(remaining,str);
char *prefix = new char[20];
memset(prefix,0,20);
Permutate(0,prefix,remaining,str);
return 0;
}
Thx,
--Gopi
On Thu, Jul 28, 2011 at 12:30 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
in the above example y ac is not included in the substring?
On Wed, Jul 27, 2011 at 3:45 PM, saurabh singh saurab...@gmail.comwrote:
hmm o(nlogn) was for constructing the tree.Btw sorry for being unclear.
The best solution is the obvious one in this case.
On Wed, Jul 27, 2011 at 2:10 PM, surender sanke surend...@gmail.comwrote:
@ sunny , ur right!!
surender
On Wed, Jul 27, 2011 at 1:58 PM, sunny agrawal
sunny816.i...@gmail.comwrote:
i don't find difference between your suffix tree approach and my simple
O(N^2) method
in both cases printf statement will be executed O(N^2) times
and in Suffix Tree approach will take some extra time of construction of
tree and extra space too !
On Wed, Jul 27, 2011 at 1:45 PM, surender sanke surend...@gmail.comwrote:
*
/ \\
a bc
/\
b c
/
c
prints *a*
comes to b, appends a with bprints *ab*
comes to c ,appends ab with c prints *abc*
starts with new child
prints *b*
prints *bc*
prints *c*
surender
On Wed, Jul 27, 2011 at 12:46 PM, sunny agrawal
sunny816.i...@gmail.com wrote:
But still Printing O(N^2) substrings will take O(N^2) time isn't it ?
On Wed, Jul 27, 2011 at 12:39 PM, surender sanke surend...@gmail.com
wrote:
@sunny
consider *uncompressed* suffix tree, even with distinct elements
maximum number of nodes with string length n formed will be 2n.
once suffix tree is constructed, needs to traverse in dfs order
appending the node found on the way.
total complexity would be O(construction of suffix tree ) +
O(traverse time).
surender
On Wed, Jul 27, 2011 at 12:00 PM, sunny agrawal
sunny816.i...@gmail.com wrote:
@shiva viknesh
this is a different Question...
@saurabh
how is nlgn possible, total no of possible substrings are n^2
this is the O(n^2) solutionOn Wed, Jul 27, 2011 at 8:09 AM, saurabh
singh
for(int l = 0; l len; l++){
for(int i = 0; i len-l; i++){
int j = i+l;
char temp = s[j+1];
s[j+1] = 0;
printf(%s\n, s+i);
s[j+1] = temp;
}
}
saurab...@gmail.com wrote:
using suffix tree this can be done in o(nlogn) though will take
extra space.
On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh
sivavikne...@gmail.com wrote:
http://geeksforgeeks.org/?p=767
On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote:
how?
On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com
wrote:
@vivin : Suffix trees are memory intensive..
This problem can be solved just by running 2 nested loops in
O(1)
space and O(n^2) time
--
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 Pratima :)
[algogeeks] Re: Amazon Question
http://en.wikipedia.org/wiki/Substring
ac should be a subsequence and not substring.
On Jul 28, 12:00 am, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
in the above example y ac is not included in the substring?
On Wed, Jul 27, 2011 at 3:45 PM, saurabh singh saurab...@gmail.com wrote:
hmm o(nlogn) was for constructing the tree.Btw sorry for being unclear.
The best solution is the obvious one in this case.
On Wed, Jul 27, 2011 at 2:10 PM, surender sanke surend...@gmail.comwrote:
@ sunny , ur right!!
surender
On Wed, Jul 27, 2011 at 1:58 PM, sunny agrawal
sunny816.i...@gmail.comwrote:
i don't find difference between your suffix tree approach and my simple
O(N^2) method
in both cases printf statement will be executed O(N^2) times
and in Suffix Tree approach will take some extra time of construction of
tree and extra space too !
On Wed, Jul 27, 2011 at 1:45 PM, surender sanke
surend...@gmail.comwrote:
*
/ \ \
a b c
/ \
b c
/
c
prints *a*
comes to b, appends a with b prints *ab*
comes to c ,appends ab with c prints *abc*
starts with new child
prints *b*
prints *bc*
prints *c*
surender
On Wed, Jul 27, 2011 at 12:46 PM, sunny agrawal
sunny816.i...@gmail.com wrote:
But still Printing O(N^2) substrings will take O(N^2) time isn't it ?
On Wed, Jul 27, 2011 at 12:39 PM, surender sanke
surend...@gmail.comwrote:
@sunny
consider *uncompressed* suffix tree, even with distinct elements
maximum number of nodes with string length n formed will be 2n.
once suffix tree is constructed, needs to traverse in dfs order
appending the node found on the way.
total complexity would be O(construction of suffix tree ) + O(traverse
time).
surender
On Wed, Jul 27, 2011 at 12:00 PM, sunny agrawal
sunny816.i...@gmail.com wrote:
@shiva viknesh
this is a different Question...
@saurabh
how is nlgn possible, total no of possible substrings are n^2
this is the O(n^2) solutionOn Wed, Jul 27, 2011 at 8:09 AM, saurabh
singh
for(int l = 0; l len; l++){
for(int i = 0; i len-l; i++){
int j = i+l;
char temp = s[j+1];
s[j+1] = 0;
printf(%s\n, s+i);
s[j+1] = temp;
}
}
saurab...@gmail.com wrote:
using suffix tree this can be done in o(nlogn) though will take
extra space.
On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh
sivavikne...@gmail.com wrote:
http://geeksforgeeks.org/?p=767
On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote:
how?
On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com
wrote:
@vivin : Suffix trees are memory intensive..
This problem can be solved just by running 2 nested loops in
O(1)
space and O(n^2) time
--
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 Pratima :)
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT 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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
[algogeeks] Re: Amazon Question
#include cstdio
#include cstring
using namespace std;
const int MX = 1000;
char str[MX], sol[MX];
bool seen[MX] = {0};
void print(int n, int k=0) {
if(k==n) {
sol[n] = 0; printf(%s\n, sol);
return;
}
for(int i = 0; i n; i++) {
if(!seen[i]) {
sol[k] = str[i];
seen[i] = 1; print(n, k+1); seen[i] = 0;
}
}
}
int main() {
scanf(%s, str);
print(strlen(str));
}
On Jul 28, 12:03 am, *$* gopi.komand...@gmail.com wrote:
The following code can be used to generate permutations of the string.. but
still some bugs are there like to avoid already printed char etc.. however
logic will be similar..
order will be less that n^2
// stringPermutration.cpp : Defines the entry point for the console
application.
//
#include stdafx.h
#includestdio.h
#includestring.h
#includestring
#includeiostream
using namespace std;
using namespace std;
void Permutate(int pos,char *prefix,char *str,char *src)
{
char *prefix1,*str1,*src1;
prefix1 = new char[20];
memset(prefix1,0,20);
str1 = new char[20];
memset(str1,0,20);
src1 = new char[20];
memset(src1,0,20);
if(pos = strlen(src))
return;
if(strlen(str)!=0)
{
strcpy(prefix1,prefix);
strcpy(str1,str);
strcpy(src1,src);
prefix1[strlen(prefix1)]=str1[0];
prefix1[strlen(prefix1)+1]='\0';
for(int i=0;istrlen(str1);i++)
{
str1[i]=str1[i+1];
}
}
else
{
int j;
int pos1=pos+1;
for(int i=pos1,j=0;jstrlen(src);)
{
str[j]=src[(i+j)%strlen(src)];
j++;
//i++;
}
strcpy(prefix1,);
strcpy(str1,str);
pos++;
}
strcpy(prefix,prefix1);
strcpy(str,str1);
Permutate(pos,prefix,str,src);
for(int x=0;xstrlen(str1);x++)
{
printf(\n %s,prefix1);
printf(%c,str1[x]);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
char *str = new char[20];
char *remaining = new char[20];
memset(str,0,20);
memset(remaining,0,20);
strcpy(str,abcd);
strcpy(remaining,str);
char *prefix = new char[20];
memset(prefix,0,20);
Permutate(0,prefix,remaining,str);
return 0;
}
Thx,
--Gopi
On Thu, Jul 28, 2011 at 12:30 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
in the above example y ac is not included in the substring?
On Wed, Jul 27, 2011 at 3:45 PM, saurabh singh saurab...@gmail.comwrote:
hmm o(nlogn) was for constructing the tree.Btw sorry for being unclear.
The best solution is the obvious one in this case.
On Wed, Jul 27, 2011 at 2:10 PM, surender sanke surend...@gmail.comwrote:
@ sunny , ur right!!
surender
On Wed, Jul 27, 2011 at 1:58 PM, sunny agrawal
sunny816.i...@gmail.comwrote:
i don't find difference between your suffix tree approach and my simple
O(N^2) method
in both cases printf statement will be executed O(N^2) times
and in Suffix Tree approach will take some extra time of construction of
tree and extra space too !
On Wed, Jul 27, 2011 at 1:45 PM, surender sanke
surend...@gmail.comwrote:
*
/ \ \
a b c
/ \
b c
/
c
prints *a*
comes to b, appends a with b prints *ab*
comes to c ,appends ab with c prints *abc*
starts with new child
prints *b*
prints *bc*
prints *c*
surender
On Wed, Jul 27, 2011 at 12:46 PM, sunny agrawal
sunny816.i...@gmail.com wrote:
But still Printing O(N^2) substrings will take O(N^2) time isn't it ?
On Wed, Jul 27, 2011 at 12:39 PM, surender sanke surend...@gmail.com
wrote:
@sunny
consider *uncompressed* suffix tree, even with distinct elements
maximum number of nodes with string length n formed will be 2n.
once suffix tree is constructed, needs to traverse in dfs order
appending the node found on the way.
total complexity would be O(construction of suffix tree ) +
O(traverse time).
surender
On Wed, Jul 27, 2011 at 12:00 PM, sunny agrawal
sunny816.i...@gmail.com wrote:
@shiva viknesh
this is a different Question...
@saurabh
how is nlgn possible, total no of possible substrings are n^2
this is the O(n^2) solutionOn Wed, Jul 27, 2011 at 8:09 AM, saurabh
singh
for(int l = 0; l len; l++){
for(int i = 0; i len-l; i++){
int j = i+l;
char temp = s[j+1];
s[j+1] = 0;
printf(%s\n, s+i);
s[j+1] = temp;
}
}
saurab...@gmail.com wrote:
using suffix tree this can be done in o(nlogn) though will take
extra space.
On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh
sivavikne...@gmail.com wrote:
http://geeksforgeeks.org/?p=767
On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote:
[algogeeks] Re: Amazon Question
suffix tree can be used print all the nodes...u ll get every
substring ..!!
On Jul 26, 8:51 pm, Ankur Garg ankurga...@gmail.com wrote:
Hey Guys
Can we use KMP Algorithm here to generate permutations...May be a bit
modification is req
On Tue, Jul 26, 2011 at 9:07 PM, keyan karthi
keyankarthi1...@gmail.comwrote:
oops .. permutation pardon me guys !!!
On 7/26/11, keyan karthi keyankarthi1...@gmail.com wrote:
@kavitha: u can use back tracking to print all the substring for a
string .. pseudo code should look some thing like this:
void next_perm(string st,int pos)
{
if(pos==length)
{
coutst;
return;
}
for(int i=pos;ilength;i++)
{
swap(st,i,pos);
next_perm(st,i+1);
swap(st,i,pos);
}
}
On 7/26/11, ankit sambyal ankitsamb...@gmail.com wrote:
@Swetha :Number of possible sub strings of a string of length n is of
the order of n^2.
So, there can,t be a better solution than O(n^2)
--
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 Question
@vivin : Suffix trees are memory intensive.. This problem can be solved just by running 2 nested loops in O(1) space and O(n^2) time -- 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 Question
how? On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com wrote: @vivin : Suffix trees are memory intensive.. This problem can be solved just by running 2 nested loops in O(1) space and O(n^2) time -- 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 Pratima :) -- 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.
[algogeeks] Re: Amazon Question
http://geeksforgeeks.org/?p=767 On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote: how? On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com wrote: @vivin : Suffix trees are memory intensive.. This problem can be solved just by running 2 nested loops in O(1) space and O(n^2) time -- 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 Pratima :) -- 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 Question
using suffix tree this can be done in o(nlogn) though will take extra space. On Wed, Jul 27, 2011 at 12:47 AM, siva viknesh sivavikne...@gmail.comwrote: http://geeksforgeeks.org/?p=767 On Jul 26, 11:49 pm, Pratz mary pratima.m...@gmail.com wrote: how? On 26 July 2011 23:18, ankit sambyal ankitsamb...@gmail.com wrote: @vivin : Suffix trees are memory intensive.. This problem can be solved just by running 2 nested loops in O(1) space and O(n^2) time -- 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 Pratima :) -- 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. -- Saurabh Singh B.Tech (Computer Science) MNNIT 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 Question
This essentially becomes a two pass algo first find the parent and grand parent and find children of all the siblings of the parent Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Apr 14, 2011 at 9:53 AM, Dave dave_and_da...@juno.com wrote: @Priya: Assuming that cousins means first cousins, then cousins have a common grandparent but different parents. Other people on the same level would not be first cousins. The algorithm is to go up two levels (to the grandparent) and descend to the other child (to an aunt or uncle). The children of that node are the cousins. Dave On Apr 13, 11:13 pm, priya mehta priya.mehta...@gmail.com wrote: i hope all the cousins means all the nodes on the same level, so it should be done using level order traversal. On Thu, Apr 14, 2011 at 8:38 AM, sravanreddy001 sravanreddy...@gmail.comwrote: Yes, this is correct, and to move the data in the array, its simple, just do a traverse and populate the array.. another way is to put data into queue and putting only one level of data at a time, this reduces the space consumption but... only by half... -- 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.- Hide quoted text - - Show quoted text - -- 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.
[algogeeks] Re: Amazon Question
@Priya: Assuming that cousins means first cousins, then cousins have a common grandparent but different parents. Other people on the same level would not be first cousins. The algorithm is to go up two levels (to the grandparent) and descend to the other child (to an aunt or uncle). The children of that node are the cousins. Dave On Apr 13, 11:13 pm, priya mehta priya.mehta...@gmail.com wrote: i hope all the cousins means all the nodes on the same level, so it should be done using level order traversal. On Thu, Apr 14, 2011 at 8:38 AM, sravanreddy001 sravanreddy...@gmail.comwrote: Yes, this is correct, and to move the data in the array, its simple, just do a traverse and populate the array.. another way is to put data into queue and putting only one level of data at a time, this reduces the space consumption but... only by half... -- 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.- Hide quoted text - - Show quoted text - -- 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 Question
@Dave i understood it thanks :) On Thu, Apr 14, 2011 at 9:53 AM, Dave dave_and_da...@juno.com wrote: @Priya: Assuming that cousins means first cousins, then cousins have a common grandparent but different parents. Other people on the same level would not be first cousins. The algorithm is to go up two levels (to the grandparent) and descend to the other child (to an aunt or uncle). The children of that node are the cousins. Dave On Apr 13, 11:13 pm, priya mehta priya.mehta...@gmail.com wrote: i hope all the cousins means all the nodes on the same level, so it should be done using level order traversal. On Thu, Apr 14, 2011 at 8:38 AM, sravanreddy001 sravanreddy...@gmail.comwrote: Yes, this is correct, and to move the data in the array, its simple, just do a traverse and populate the array.. another way is to put data into queue and putting only one level of data at a time, this reduces the space consumption but... only by half... -- 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.- Hide quoted text - - Show quoted text - -- 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.
[algogeeks] Re: Amazon Question
take an example
3 3 3 5 5 5 7 8
I think this would fail
On Mar 3, 8:22 pm, Ankit Sinha akki12...@gmail.com wrote:
It is funny but right input is as mentioned earlier to rahul. 0,2,3,8,
10, 12, 14., 15 :).. Sorry for unnecessarily flooding your mail
accounts. Please ignore previous post
thanks,
ankit!!
On Thu, Mar 3, 2011 at 8:15 PM, rajul jain rajuljain...@gmail.com wrote:
i think he is wrong bcoz this array in not sorted one.
so solution of Ankit is right.
On Thu, Mar 3, 2011 at 7:33 PM, nishaanth nishaant...@gmail.com wrote:
Ignore the previous post..there is a small error in the code..
@Ankit..your algm is O(n)...you should split the problem size to n/2 at
every stage...rather you are again computing both the subarrays..
Here is the correct code...
int BsearchElemEqualIndex (int *a, int start, int end)
{
int mid = (((end - start) 1) + start);
if (a[mid] == mid)
return a[mid];
else if (a[mid] != mid)
{
if (mid == start || mid == end)
{
return -1;
}
else
{
if(a[mid] mid )
BsearchElemEqualIndex (a, start, mid);
else
BsearchElemEqualIndex (a, mid + 1, end);
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[SIZE] = {5,9,3,8,1,2,6,7};
int x = BsearchElemEqualIndex (a, 0, SIZE);
printf (%d, x);
system (PAUSE);
return 0;
}
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
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 Question
he already pointed out that there are no repetations..!!
On Thu, Mar 3, 2011 at 9:40 PM, Vipin Agrawal vipin.iitr@gmail.comwrote:
take an example
3 3 3 5 5 5 7 8
I think this would fail
On Mar 3, 8:22 pm, Ankit Sinha akki12...@gmail.com wrote:
It is funny but right input is as mentioned earlier to rahul. 0,2,3,8,
10, 12, 14., 15 :).. Sorry for unnecessarily flooding your mail
accounts. Please ignore previous post
thanks,
ankit!!
On Thu, Mar 3, 2011 at 8:15 PM, rajul jain rajuljain...@gmail.com
wrote:
i think he is wrong bcoz this array in not sorted one.
so solution of Ankit is right.
On Thu, Mar 3, 2011 at 7:33 PM, nishaanth nishaant...@gmail.com
wrote:
Ignore the previous post..there is a small error in the code..
@Ankit..your algm is O(n)...you should split the problem size to n/2
at
every stage...rather you are again computing both the subarrays..
Here is the correct code...
int BsearchElemEqualIndex (int *a, int start, int end)
{
int mid = (((end - start) 1) + start);
if (a[mid] == mid)
return a[mid];
else if (a[mid] != mid)
{
if (mid == start || mid == end)
{
return -1;
}
else
{
if(a[mid] mid )
BsearchElemEqualIndex (a, start, mid);
else
BsearchElemEqualIndex (a, mid + 1, end);
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[SIZE] = {5,9,3,8,1,2,6,7};
int x = BsearchElemEqualIndex (a, 0, SIZE);
printf (%d, x);
system (PAUSE);
return 0;
}
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
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 Question
@Gunjani made a mistake...u r right...but there is one more hidden
assumption that the numbers are positive integers.
On Thu, Mar 3, 2011 at 10:57 PM, sukhmeet singh sukhmeet2...@gmail.comwrote:
he already pointed out that there are no repetations..!!
On Thu, Mar 3, 2011 at 9:40 PM, Vipin Agrawal vipin.iitr@gmail.comwrote:
take an example
3 3 3 5 5 5 7 8
I think this would fail
On Mar 3, 8:22 pm, Ankit Sinha akki12...@gmail.com wrote:
It is funny but right input is as mentioned earlier to rahul. 0,2,3,8,
10, 12, 14., 15 :).. Sorry for unnecessarily flooding your mail
accounts. Please ignore previous post
thanks,
ankit!!
On Thu, Mar 3, 2011 at 8:15 PM, rajul jain rajuljain...@gmail.com
wrote:
i think he is wrong bcoz this array in not sorted one.
so solution of Ankit is right.
On Thu, Mar 3, 2011 at 7:33 PM, nishaanth nishaant...@gmail.com
wrote:
Ignore the previous post..there is a small error in the code..
@Ankit..your algm is O(n)...you should split the problem size to n/2
at
every stage...rather you are again computing both the subarrays..
Here is the correct code...
int BsearchElemEqualIndex (int *a, int start, int end)
{
int mid = (((end - start) 1) + start);
if (a[mid] == mid)
return a[mid];
else if (a[mid] != mid)
{
if (mid == start || mid == end)
{
return -1;
}
else
{
if(a[mid] mid )
BsearchElemEqualIndex (a, start, mid);
else
BsearchElemEqualIndex (a, mid + 1, end);
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[SIZE] = {5,9,3,8,1,2,6,7};
int x = BsearchElemEqualIndex (a, 0, SIZE);
printf (%d, x);
system (PAUSE);
return 0;
}
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
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.
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
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 Question
And Integers too :P
On Fri, Mar 4, 2011 at 12:03 AM, nishaanth nishaant...@gmail.com wrote:
@Gunjani made a mistake...u r right...but there is one more hidden
assumption that the numbers are positive integers.
On Thu, Mar 3, 2011 at 10:57 PM, sukhmeet singh sukhmeet2...@gmail.comwrote:
he already pointed out that there are no repetations..!!
On Thu, Mar 3, 2011 at 9:40 PM, Vipin Agrawal
vipin.iitr@gmail.comwrote:
take an example
3 3 3 5 5 5 7 8
I think this would fail
On Mar 3, 8:22 pm, Ankit Sinha akki12...@gmail.com wrote:
It is funny but right input is as mentioned earlier to rahul. 0,2,3,8,
10, 12, 14., 15 :).. Sorry for unnecessarily flooding your mail
accounts. Please ignore previous post
thanks,
ankit!!
On Thu, Mar 3, 2011 at 8:15 PM, rajul jain rajuljain...@gmail.com
wrote:
i think he is wrong bcoz this array in not sorted one.
so solution of Ankit is right.
On Thu, Mar 3, 2011 at 7:33 PM, nishaanth nishaant...@gmail.com
wrote:
Ignore the previous post..there is a small error in the code..
@Ankit..your algm is O(n)...you should split the problem size to n/2
at
every stage...rather you are again computing both the subarrays..
Here is the correct code...
int BsearchElemEqualIndex (int *a, int start, int end)
{
int mid = (((end - start) 1) + start);
if (a[mid] == mid)
return a[mid];
else if (a[mid] != mid)
{
if (mid == start || mid == end)
{
return -1;
}
else
{
if(a[mid] mid )
BsearchElemEqualIndex (a, start, mid);
else
BsearchElemEqualIndex (a, mid + 1, end);
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[SIZE] = {5,9,3,8,1,2,6,7};
int x = BsearchElemEqualIndex (a, 0, SIZE);
printf (%d, x);
system (PAUSE);
return 0;
}
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
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.
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
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
Gunjan Sharma
Chairman IEEE Students Chapter IIT Roorkee
B.Tech IV year CSE
Contact No- +91 9997767077
--
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.
[algogeeks] Re: amazon question
@jalaj dude..its not d problem u can convert string ti tree easily First Check Out Solution i have posted Thank Regards Shashank Mani The best way to escape from a problem is to solve it -- 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.
[algogeeks] Re: amazon question
can u explain what is meant by binary tree as a mirror strucrure ? is it like all left and right subtrees in tree should be mirror image of each other.. if that is the case then (A (B (C)), D(E))) should be (A (B (C)), D(,E))) means if C is the left child of B then E should be the right child of D On Feb 6, 3:34 pm, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: Write a function to check whether the Binary Tree is mirror structure. True (A (B (C,D), E( F,G))) or (A (B (C)), D(E))) False (A (B)) or (A (B,C(D,E))) -- tree is represented in string form as given above With Regards, *Jalaj Jaiswal* (+919019947895) Final Year Undergraduate, IIIT 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.
[algogeeks] Re: amazon question
Correct representation of tree in string format is (root Left sub tree,right sub tree) and if Left sub tree is NULL then it is (root,right sub tree) so as differentiate b/w case 1. when B is left child of A (A (B)) 2. or B is right child of A(A,(B)) On Feb 6, 3:34 pm, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: Write a function to check whether the Binary Tree is mirror structure. True (A (B (C,D), E( F,G))) or (A (B (C)), D(E))) False (A (B)) or (A (B,C(D,E))) -- tree is represented in string form as given above With Regards, *Jalaj Jaiswal* (+919019947895) Final Year Undergraduate, IIIT 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 question
hi,
I think we can use a stack here...
start from left of string(0 to n)
till we don't get a ')' we will keep on pushin the elements on the
stack...
if we encounter a '0' we will pop elements till ')' if this count is 2
everytime except the last time then this is a mirror tree else not
i think this algorithm should work...
Thanks and regards,
Gajendra Dadheech
Software Engineer-I (RD)
MediaTek India Technology
Work: 120-4343900(Ext. 276)
Mobile: +91-9540646145
-
Be the change you want to see in the world -Mohandas Gandhi
On Sun, Feb 6, 2011 at 9:41 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote:
@ bittu and bharath
the tree is given in form of string
On Sun, Feb 6, 2011 at 6:55 PM, Bharath M R catchmrbhar...@gmail.comwrote:
bool visit(node temp1, node temp2)
{
if(temp1.left==null temp2.right==null)
return true;
else if((temp1.left==null temp2.right!=null) || (temp1.left!=null
temp2.right==null))
return false;
else
return visit(temp1.left,temp2.right);
-- do the same for temp1.right and temp2.left
}
Just check whether root. left and root.right are not null and pass it the
visit function.
--
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.
--
With Regards,
*Jalaj Jaiswal* (+919019947895)
Final Year Undergraduate,
IIIT 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.
--
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.
[algogeeks] Re: amazon question
@jalal hi You Can Use This algorithm to construct the Mirror tree (1) Call Mirror for left-subtreei.e., Mirror(left-subtree) (2) Call Mirror for right-subtree i.e., Mirror(left-subtree) (3) Swap left and right subtrees. temp = left-subtree left-subtree = right-subtree right-subtree = temp then compare inorder traversal of two tree if they are in reverse order then they are Mirror Tree else not one can easily visualize it You Can Find Out The Code here slightly modification need in this because i put it here in hurry 1 Longer better explantion http://codepad.org/aKoC2EyK 2. shorter version http://codepad.org/e7V1CjuY Might have some bugs Thanks Regards Shashank Mani The Best Way to Escape from the problem is to solve it -- 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.
[algogeeks] Re: Amazon Question
Here is working Code
//code is very simple from understanding points of view
//we can solved the problem dynamically or more efficiently but i
posted the solution by taking every things statically ..but its
working what question asked.for
#includestdio.h
#includeconio.h
int main()
{
int a[5]={1,2,3,4,5};
int b[10]={6,7,8,9,10};
int i=0,j=0,x=5,y=5;;
int t=5; //temp which pints to location in array b after 5 elements
while((ix) (jy))
{
if(a[i]=b[j])
{
b[t]=b[j];
b[j]=a[i];
i++;
j++;
}
else
{
b[t]=a[i];
printf(%d ,b[t]);
b[i]=b[j];
j++;
i++;
}
t++;
}
for(i=0;i10;i++)
{
printf(%d\t,b[i]);
}
getch();
return 0;
}
Thanks Regards
Shashank The best way to escape from a problem is to solve it.
--
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 Question
Looks good. I concede that it works for a Binary Search Tree.
On Sat, Jan 29, 2011 at 1:35 AM, Ritu Garg ritugarg.c...@gmail.com wrote:
@nphard,see the following approach carefully to know *if right pointer is
pointing to right child or in order successor*
*
*Q = node-right
IF (Q is not NULL)
{
/*Determine if Q is node's right child or successor*/
/*Q is inorder successor of node*/
IF (Q-left == node OR Q-left-val node-val)
{
}
/*Q is the right child of node*/
ELSE IF (Q-left == NULL or Q-left-val node-right)
{
}
}
1. Q-left is smaller than or equal to node if Q is Inorder Successor of
node
2. Q-left is either NULL or Q-left is greater than node if Q is right
child of node
*
*Hence* in order traversal of right threaded BST without flag* is possible
On Fri, Jan 28, 2011 at 9:40 AM, nphard nphard nphard.nph...@gmail.comwrote:
Not correct. You cannot assume that the right node always points to the
successor. If you do that, your traversal will be affected. Consider that
when you reach a node B from the right pointer of its parent A, you traverse
that subtree rooted at B in normal inorder. However, when you reach B from
its inorder predecessor C, you should have the knowledge that you have
visited that node's left subtree and should not visit again (which is only
known if you have the information that you are reaching that node through a
thread).
On Thu, Jan 27, 2011 at 10:57 PM, Ritu Garg ritugarg.c...@gmail.comwrote:
@nphard
ideally,a flag is required in right threaded tree to distinguish whether
right child is a pointer to inorder successor or to right child.Even we can
do without flag assuming that there ll be no further insertions taking
place in tree and no other traversal is required.
here we suppose that right pointer always gives the successor..
The solution to get the linear inorder traversal is just tailored for a
situation where there is no extra space,not even for stack!!!
On Fri, Jan 28, 2011 at 5:42 AM, nphard nphard
nphard.nph...@gmail.comwrote:
@Ritu - Do you realize that you cannot just convert a given binary tree
into right-threaded binary tree? You need at least 1 bit information at
each
node to specify whether the right pointer of that node is a regular pointer
or pointer to the inorder successor. This is because traversal is done
differently when you arrive at a node through its inorder predecessor.
On Thu, Jan 27, 2011 at 7:22 AM, Ritu Garg
ritugarg.c...@gmail.comwrote:
solution is not too hard to understand!!
1. [quote] For every none leaf node , go to the last node in it's left
subtree and mark the right child of that node as x [\quote]. How are
we going to refer to the right child now ??We have removed it's
reference now !!
last node in left sub tree of any node always have right pointer as
NULL because this is the last node
2. It is to be repeated for every node except the non leaf nodes . This
will take O(n*n) time in worst case , say a leftist tree with only
left pointers . root makes n-1 traversals , root's left subtree's root
makes n-2 , and so on.
i said that it ll take O(n) time for well balanced tree.
for a node at height h ,it takes O(h) to fill this node as successor of
some other node.if combined for all sum(O(h)) h=1 to lg n ..total time ll
come as O(n)
3. Take the case below .
1
2 3
1 1.5 2.5 4
for node 2 , you will go to 1 , which is the successor of 2 , you make
2-right=1 but what about node 1.5 ???
same is the case with node 3 ... 3-right=2.5 . How will we refer to 4
now ??
when you ll process node 1,it ll be filled in as right child of 1.5
there is no successor for 4.
In Brief
1. Convert the tree to right threaded binary tree.means all right
children point to their successors.
it ll take no additional space.ll take O(n) time if tree is well
balanced
2. Do inorder traversal to find ith element without using extra space
because succssor of each node is pointed by right child.
i hope you got it now!!
On Wed, Jan 26, 2011 at 5:31 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
I don't seem to understand ur solution .
[quote] For every none leaf node , go to the last node in it's left
subtree and mark the right child of that node as x [\quote]. How are
we going to refer to the right child now ??We have removed it's
reference now !!
It is to be repeated for every node except the non leaf nodes . This
will take O(n*n) time in worst case , say a leftist tree with only
left pointers . root makes n-1 traversals , root's left subtree's root
makes n-2 , and so on.
Go to the largest node in the left subtree .This means go to the left
subtree and keep on going to the right until it becomes null , in
which case , you make y-right as x . This means effectively , that y
is the predecessor of x , in the tree .
Re: [algogeeks] Re: Amazon Question
Yes,it works for binary search tree only
On Sat, Jan 29, 2011 at 2:22 PM, nphard nphard nphard.nph...@gmail.comwrote:
Looks good. I concede that it works for a Binary Search Tree.
On Sat, Jan 29, 2011 at 1:35 AM, Ritu Garg ritugarg.c...@gmail.comwrote:
@nphard,see the following approach carefully to know *if right pointer is
pointing to right child or in order successor*
*
*Q = node-right
IF (Q is not NULL)
{
/*Determine if Q is node's right child or successor*/
/*Q is inorder successor of node*/
IF (Q-left == node OR Q-left-val node-val)
{
}
/*Q is the right child of node*/
ELSE IF (Q-left == NULL or Q-left-val node-right)
{
}
}
1. Q-left is smaller than or equal to node if Q is Inorder Successor of
node
2. Q-left is either NULL or Q-left is greater than node if Q is right
child of node
*
*Hence* in order traversal of right threaded BST without flag* is
possible
On Fri, Jan 28, 2011 at 9:40 AM, nphard nphard
nphard.nph...@gmail.comwrote:
Not correct. You cannot assume that the right node always points to the
successor. If you do that, your traversal will be affected. Consider that
when you reach a node B from the right pointer of its parent A, you traverse
that subtree rooted at B in normal inorder. However, when you reach B from
its inorder predecessor C, you should have the knowledge that you have
visited that node's left subtree and should not visit again (which is only
known if you have the information that you are reaching that node through a
thread).
On Thu, Jan 27, 2011 at 10:57 PM, Ritu Garg ritugarg.c...@gmail.comwrote:
@nphard
ideally,a flag is required in right threaded tree to distinguish whether
right child is a pointer to inorder successor or to right child.Even we can
do without flag assuming that there ll be no further insertions taking
place in tree and no other traversal is required.
here we suppose that right pointer always gives the successor..
The solution to get the linear inorder traversal is just tailored for a
situation where there is no extra space,not even for stack!!!
On Fri, Jan 28, 2011 at 5:42 AM, nphard nphard nphard.nph...@gmail.com
wrote:
@Ritu - Do you realize that you cannot just convert a given binary tree
into right-threaded binary tree? You need at least 1 bit information at
each
node to specify whether the right pointer of that node is a regular
pointer
or pointer to the inorder successor. This is because traversal is done
differently when you arrive at a node through its inorder predecessor.
On Thu, Jan 27, 2011 at 7:22 AM, Ritu Garg
ritugarg.c...@gmail.comwrote:
solution is not too hard to understand!!
1. [quote] For every none leaf node , go to the last node in it's left
subtree and mark the right child of that node as x [\quote]. How are
we going to refer to the right child now ??We have removed it's
reference now !!
last node in left sub tree of any node always have right pointer as
NULL because this is the last node
2. It is to be repeated for every node except the non leaf nodes .
This
will take O(n*n) time in worst case , say a leftist tree with only
left pointers . root makes n-1 traversals , root's left subtree's root
makes n-2 , and so on.
i said that it ll take O(n) time for well balanced tree.
for a node at height h ,it takes O(h) to fill this node as successor
of some other node.if combined for all sum(O(h)) h=1 to lg n ..total
time ll
come as O(n)
3. Take the case below .
1
2 3
1 1.5 2.5 4
for node 2 , you will go to 1 , which is the successor of 2 , you make
2-right=1 but what about node 1.5 ???
same is the case with node 3 ... 3-right=2.5 . How will we refer to 4
now ??
when you ll process node 1,it ll be filled in as right child of 1.5
there is no successor for 4.
In Brief
1. Convert the tree to right threaded binary tree.means all right
children point to their successors.
it ll take no additional space.ll take O(n) time if tree is well
balanced
2. Do inorder traversal to find ith element without using extra space
because succssor of each node is pointed by right child.
i hope you got it now!!
On Wed, Jan 26, 2011 at 5:31 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
I don't seem to understand ur solution .
[quote] For every none leaf node , go to the last node in it's left
subtree and mark the right child of that node as x [\quote]. How are
we going to refer to the right child now ??We have removed it's
reference now !!
It is to be repeated for every node except the non leaf nodes . This
will take O(n*n) time in worst case , say a leftist tree with only
left pointers . root makes n-1 traversals , root's left subtree's
root
makes n-2 , and so on.
Go to the largest node in the left subtree .This means go to the left
subtree and keep on going to the right until it becomes
Re: [algogeeks] Re: Amazon Question
@nphard,see the following approach carefully to know *if right pointer is
pointing to right child or in order successor*
*
*Q = node-right
IF (Q is not NULL)
{
/*Determine if Q is node's right child or successor*/
/*Q is inorder successor of node*/
IF (Q-left == node OR Q-left-val node-val)
{
}
/*Q is the right child of node*/
ELSE IF (Q-left == NULL or Q-left-val node-right)
{
}
}
1. Q-left is smaller than or equal to node if Q is Inorder Successor of
node
2. Q-left is either NULL or Q-left is greater than node if Q is right
child of node
*
*Hence* in order traversal of right threaded BST without flag* is possible
On Fri, Jan 28, 2011 at 9:40 AM, nphard nphard nphard.nph...@gmail.comwrote:
Not correct. You cannot assume that the right node always points to the
successor. If you do that, your traversal will be affected. Consider that
when you reach a node B from the right pointer of its parent A, you traverse
that subtree rooted at B in normal inorder. However, when you reach B from
its inorder predecessor C, you should have the knowledge that you have
visited that node's left subtree and should not visit again (which is only
known if you have the information that you are reaching that node through a
thread).
On Thu, Jan 27, 2011 at 10:57 PM, Ritu Garg ritugarg.c...@gmail.comwrote:
@nphard
ideally,a flag is required in right threaded tree to distinguish whether
right child is a pointer to inorder successor or to right child.Even we can
do without flag assuming that there ll be no further insertions taking
place in tree and no other traversal is required.
here we suppose that right pointer always gives the successor..
The solution to get the linear inorder traversal is just tailored for a
situation where there is no extra space,not even for stack!!!
On Fri, Jan 28, 2011 at 5:42 AM, nphard nphard
nphard.nph...@gmail.comwrote:
@Ritu - Do you realize that you cannot just convert a given binary tree
into right-threaded binary tree? You need at least 1 bit information at each
node to specify whether the right pointer of that node is a regular pointer
or pointer to the inorder successor. This is because traversal is done
differently when you arrive at a node through its inorder predecessor.
On Thu, Jan 27, 2011 at 7:22 AM, Ritu Garg ritugarg.c...@gmail.comwrote:
solution is not too hard to understand!!
1. [quote] For every none leaf node , go to the last node in it's left
subtree and mark the right child of that node as x [\quote]. How are
we going to refer to the right child now ??We have removed it's
reference now !!
last node in left sub tree of any node always have right pointer as NULL
because this is the last node
2. It is to be repeated for every node except the non leaf nodes . This
will take O(n*n) time in worst case , say a leftist tree with only
left pointers . root makes n-1 traversals , root's left subtree's root
makes n-2 , and so on.
i said that it ll take O(n) time for well balanced tree.
for a node at height h ,it takes O(h) to fill this node as successor of
some other node.if combined for all sum(O(h)) h=1 to lg n ..total time ll
come as O(n)
3. Take the case below .
1
2 3
1 1.5 2.5 4
for node 2 , you will go to 1 , which is the successor of 2 , you make
2-right=1 but what about node 1.5 ???
same is the case with node 3 ... 3-right=2.5 . How will we refer to 4
now ??
when you ll process node 1,it ll be filled in as right child of 1.5
there is no successor for 4.
In Brief
1. Convert the tree to right threaded binary tree.means all right
children point to their successors.
it ll take no additional space.ll take O(n) time if tree is well
balanced
2. Do inorder traversal to find ith element without using extra space
because succssor of each node is pointed by right child.
i hope you got it now!!
On Wed, Jan 26, 2011 at 5:31 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
I don't seem to understand ur solution .
[quote] For every none leaf node , go to the last node in it's left
subtree and mark the right child of that node as x [\quote]. How are
we going to refer to the right child now ??We have removed it's
reference now !!
It is to be repeated for every node except the non leaf nodes . This
will take O(n*n) time in worst case , say a leftist tree with only
left pointers . root makes n-1 traversals , root's left subtree's root
makes n-2 , and so on.
Go to the largest node in the left subtree .This means go to the left
subtree and keep on going to the right until it becomes null , in
which case , you make y-right as x . This means effectively , that y
is the predecessor of x , in the tree . Considering a very good code ,
it may take O(1) space , but you will still need additional pointers.
Take the case below .
1
2 3
1 1.5 2.5
Re: [algogeeks] Re: Amazon Question
solution is not too hard to understand!! 1. [quote] For every none leaf node , go to the last node in it's left subtree and mark the right child of that node as x [\quote]. How are we going to refer to the right child now ??We have removed it's reference now !! last node in left sub tree of any node always have right pointer as NULL because this is the last node 2. It is to be repeated for every node except the non leaf nodes . This will take O(n*n) time in worst case , say a leftist tree with only left pointers . root makes n-1 traversals , root's left subtree's root makes n-2 , and so on. i said that it ll take O(n) time for well balanced tree. for a node at height h ,it takes O(h) to fill this node as successor of some other node.if combined for all sum(O(h)) h=1 to lg n ..total time ll come as O(n) 3. Take the case below . 1 2 3 1 1.5 2.5 4 for node 2 , you will go to 1 , which is the successor of 2 , you make 2-right=1 but what about node 1.5 ??? same is the case with node 3 ... 3-right=2.5 . How will we refer to 4 now ?? when you ll process node 1,it ll be filled in as right child of 1.5 there is no successor for 4. In Brief 1. Convert the tree to right threaded binary tree.means all right children point to their successors. it ll take no additional space.ll take O(n) time if tree is well balanced 2. Do inorder traversal to find ith element without using extra space because succssor of each node is pointed by right child. i hope you got it now!! On Wed, Jan 26, 2011 at 5:31 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: I don't seem to understand ur solution . [quote] For every none leaf node , go to the last node in it's left subtree and mark the right child of that node as x [\quote]. How are we going to refer to the right child now ??We have removed it's reference now !! It is to be repeated for every node except the non leaf nodes . This will take O(n*n) time in worst case , say a leftist tree with only left pointers . root makes n-1 traversals , root's left subtree's root makes n-2 , and so on. Go to the largest node in the left subtree .This means go to the left subtree and keep on going to the right until it becomes null , in which case , you make y-right as x . This means effectively , that y is the predecessor of x , in the tree . Considering a very good code , it may take O(1) space , but you will still need additional pointers. Take the case below . 1 2 3 1 1.5 2.5 4 for node 2 , you will go to 1 , which is the successor of 2 , you make 2-right=1 but what about node 1.5 ??? same is the case with node 3 ... 3-right=2.5 . How will we refer to 4 now ?? Now using inorder traversal with a count , I will start at 1-left , 2- left = 1 , then 2 ... then 2-right = 1 again . then 1 , and then 1- right=3 ...clearly , this will not give us a solution . A reverse inorder looks just fine to me . On Jan 26, 3:14 pm, Ritu Garg ritugarg.c...@gmail.com wrote: @Algoose I said ..*.For every node x,go to the last node in its left subtree and mark the right child of that node as x.* it is to be repeated for all nodes except leaf nodes. to apply this approach ,you need to go down the tree.No parent pointers required. for every node say x whose left sub tree is not null ,go to the largest node in left sub-tree say y. Set y-right = x y is the last node to be processed in left sub-tree of x hence x is successor of y. On Wed, Jan 26, 2011 at 3:27 PM, Algoose chase harishp...@gmail.com wrote: @ritu how would you find a successor without extra space if you dont have a parent pointer ? for Instance from the right most node of left subtree to the parent of left subtree(root) ? @Juver++ Internal stack does count as extra space !! On Wed, Jan 26, 2011 at 3:02 PM, ritu ritugarg.c...@gmail.com wrote: No,no extra space is needed. Right children which are NULL pointers are replaced with pointer to successor. On Jan 26, 1:18 pm, nphard nphard nphard.nph...@gmail.com wrote: If you convert the given binary tree into right threaded binary tree, won't you be using extra space while doing so? Either the given tree should already be right-threaded (or with parent pointers at each node) or internal stack should be allowed for recursion but no extra space usage apart from that. On Wed, Jan 26, 2011 at 3:04 AM, ritu ritugarg.c...@gmail.com wrote: it can be done in O(n) time using right threaded binary tree. 1.Convert the tree to right threaded tree. right threaded tree means every node points to its successor in tree.if right child is not NULL,then it already contains a pointer to its successor Else it needs to filled up as following a. For every node x,go to the last node in its left subtree and mark the right child of that node as x.
Re: [algogeeks] Re: Amazon Question
@Ritu - Do you realize that you cannot just convert a given binary tree into right-threaded binary tree? You need at least 1 bit information at each node to specify whether the right pointer of that node is a regular pointer or pointer to the inorder successor. This is because traversal is done differently when you arrive at a node through its inorder predecessor. On Thu, Jan 27, 2011 at 7:22 AM, Ritu Garg ritugarg.c...@gmail.com wrote: solution is not too hard to understand!! 1. [quote] For every none leaf node , go to the last node in it's left subtree and mark the right child of that node as x [\quote]. How are we going to refer to the right child now ??We have removed it's reference now !! last node in left sub tree of any node always have right pointer as NULL because this is the last node 2. It is to be repeated for every node except the non leaf nodes . This will take O(n*n) time in worst case , say a leftist tree with only left pointers . root makes n-1 traversals , root's left subtree's root makes n-2 , and so on. i said that it ll take O(n) time for well balanced tree. for a node at height h ,it takes O(h) to fill this node as successor of some other node.if combined for all sum(O(h)) h=1 to lg n ..total time ll come as O(n) 3. Take the case below . 1 2 3 1 1.5 2.5 4 for node 2 , you will go to 1 , which is the successor of 2 , you make 2-right=1 but what about node 1.5 ??? same is the case with node 3 ... 3-right=2.5 . How will we refer to 4 now ?? when you ll process node 1,it ll be filled in as right child of 1.5 there is no successor for 4. In Brief 1. Convert the tree to right threaded binary tree.means all right children point to their successors. it ll take no additional space.ll take O(n) time if tree is well balanced 2. Do inorder traversal to find ith element without using extra space because succssor of each node is pointed by right child. i hope you got it now!! On Wed, Jan 26, 2011 at 5:31 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: I don't seem to understand ur solution . [quote] For every none leaf node , go to the last node in it's left subtree and mark the right child of that node as x [\quote]. How are we going to refer to the right child now ??We have removed it's reference now !! It is to be repeated for every node except the non leaf nodes . This will take O(n*n) time in worst case , say a leftist tree with only left pointers . root makes n-1 traversals , root's left subtree's root makes n-2 , and so on. Go to the largest node in the left subtree .This means go to the left subtree and keep on going to the right until it becomes null , in which case , you make y-right as x . This means effectively , that y is the predecessor of x , in the tree . Considering a very good code , it may take O(1) space , but you will still need additional pointers. Take the case below . 1 2 3 1 1.5 2.5 4 for node 2 , you will go to 1 , which is the successor of 2 , you make 2-right=1 but what about node 1.5 ??? same is the case with node 3 ... 3-right=2.5 . How will we refer to 4 now ?? Now using inorder traversal with a count , I will start at 1-left , 2- left = 1 , then 2 ... then 2-right = 1 again . then 1 , and then 1- right=3 ...clearly , this will not give us a solution . A reverse inorder looks just fine to me . On Jan 26, 3:14 pm, Ritu Garg ritugarg.c...@gmail.com wrote: @Algoose I said ..*.For every node x,go to the last node in its left subtree and mark the right child of that node as x.* it is to be repeated for all nodes except leaf nodes. to apply this approach ,you need to go down the tree.No parent pointers required. for every node say x whose left sub tree is not null ,go to the largest node in left sub-tree say y. Set y-right = x y is the last node to be processed in left sub-tree of x hence x is successor of y. On Wed, Jan 26, 2011 at 3:27 PM, Algoose chase harishp...@gmail.com wrote: @ritu how would you find a successor without extra space if you dont have a parent pointer ? for Instance from the right most node of left subtree to the parent of left subtree(root) ? @Juver++ Internal stack does count as extra space !! On Wed, Jan 26, 2011 at 3:02 PM, ritu ritugarg.c...@gmail.com wrote: No,no extra space is needed. Right children which are NULL pointers are replaced with pointer to successor. On Jan 26, 1:18 pm, nphard nphard nphard.nph...@gmail.com wrote: If you convert the given binary tree into right threaded binary tree, won't you be using extra space while doing so? Either the given tree should already be right-threaded (or with parent pointers at each node) or internal stack should be allowed for recursion but no extra space usage apart from that. On Wed, Jan 26, 2011 at 3:04 AM,
[algogeeks] Re: Amazon Question
this is a tree traversal(depth first) problem. as for the extra space, depends on how you see it. fifth can be the counter and when the counter reaches 0, you have your fifth largest element On Jan 21, 9:58 am, nagaraj N nagaraj1...@gmail.com wrote: How do you find out the fifth maximum element in an binary search tree in efficient manner without using any extra space? -- 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 Question
@nphard ideally,a flag is required in right threaded tree to distinguish whether right child is a pointer to inorder successor or to right child.Even we can do without flag assuming that there ll be no further insertions taking place in tree and no other traversal is required. here we suppose that right pointer always gives the successor.. The solution to get the linear inorder traversal is just tailored for a situation where there is no extra space,not even for stack!!! On Fri, Jan 28, 2011 at 5:42 AM, nphard nphard nphard.nph...@gmail.comwrote: @Ritu - Do you realize that you cannot just convert a given binary tree into right-threaded binary tree? You need at least 1 bit information at each node to specify whether the right pointer of that node is a regular pointer or pointer to the inorder successor. This is because traversal is done differently when you arrive at a node through its inorder predecessor. On Thu, Jan 27, 2011 at 7:22 AM, Ritu Garg ritugarg.c...@gmail.comwrote: solution is not too hard to understand!! 1. [quote] For every none leaf node , go to the last node in it's left subtree and mark the right child of that node as x [\quote]. How are we going to refer to the right child now ??We have removed it's reference now !! last node in left sub tree of any node always have right pointer as NULL because this is the last node 2. It is to be repeated for every node except the non leaf nodes . This will take O(n*n) time in worst case , say a leftist tree with only left pointers . root makes n-1 traversals , root's left subtree's root makes n-2 , and so on. i said that it ll take O(n) time for well balanced tree. for a node at height h ,it takes O(h) to fill this node as successor of some other node.if combined for all sum(O(h)) h=1 to lg n ..total time ll come as O(n) 3. Take the case below . 1 2 3 1 1.5 2.5 4 for node 2 , you will go to 1 , which is the successor of 2 , you make 2-right=1 but what about node 1.5 ??? same is the case with node 3 ... 3-right=2.5 . How will we refer to 4 now ?? when you ll process node 1,it ll be filled in as right child of 1.5 there is no successor for 4. In Brief 1. Convert the tree to right threaded binary tree.means all right children point to their successors. it ll take no additional space.ll take O(n) time if tree is well balanced 2. Do inorder traversal to find ith element without using extra space because succssor of each node is pointed by right child. i hope you got it now!! On Wed, Jan 26, 2011 at 5:31 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: I don't seem to understand ur solution . [quote] For every none leaf node , go to the last node in it's left subtree and mark the right child of that node as x [\quote]. How are we going to refer to the right child now ??We have removed it's reference now !! It is to be repeated for every node except the non leaf nodes . This will take O(n*n) time in worst case , say a leftist tree with only left pointers . root makes n-1 traversals , root's left subtree's root makes n-2 , and so on. Go to the largest node in the left subtree .This means go to the left subtree and keep on going to the right until it becomes null , in which case , you make y-right as x . This means effectively , that y is the predecessor of x , in the tree . Considering a very good code , it may take O(1) space , but you will still need additional pointers. Take the case below . 1 2 3 1 1.5 2.5 4 for node 2 , you will go to 1 , which is the successor of 2 , you make 2-right=1 but what about node 1.5 ??? same is the case with node 3 ... 3-right=2.5 . How will we refer to 4 now ?? Now using inorder traversal with a count , I will start at 1-left , 2- left = 1 , then 2 ... then 2-right = 1 again . then 1 , and then 1- right=3 ...clearly , this will not give us a solution . A reverse inorder looks just fine to me . On Jan 26, 3:14 pm, Ritu Garg ritugarg.c...@gmail.com wrote: @Algoose I said ..*.For every node x,go to the last node in its left subtree and mark the right child of that node as x.* it is to be repeated for all nodes except leaf nodes. to apply this approach ,you need to go down the tree.No parent pointers required. for every node say x whose left sub tree is not null ,go to the largest node in left sub-tree say y. Set y-right = x y is the last node to be processed in left sub-tree of x hence x is successor of y. On Wed, Jan 26, 2011 at 3:27 PM, Algoose chase harishp...@gmail.com wrote: @ritu how would you find a successor without extra space if you dont have a parent pointer ? for Instance from the right most node of left subtree to the parent of left subtree(root) ? @Juver++ Internal stack does count as extra space !! On Wed, Jan 26, 2011 at 3:02 PM, ritu ritugarg.c...@gmail.com
Re: [algogeeks] Re: Amazon Question
Not correct. You cannot assume that the right node always points to the successor. If you do that, your traversal will be affected. Consider that when you reach a node B from the right pointer of its parent A, you traverse that subtree rooted at B in normal inorder. However, when you reach B from its inorder predecessor C, you should have the knowledge that you have visited that node's left subtree and should not visit again (which is only known if you have the information that you are reaching that node through a thread). On Thu, Jan 27, 2011 at 10:57 PM, Ritu Garg ritugarg.c...@gmail.com wrote: @nphard ideally,a flag is required in right threaded tree to distinguish whether right child is a pointer to inorder successor or to right child.Even we can do without flag assuming that there ll be no further insertions taking place in tree and no other traversal is required. here we suppose that right pointer always gives the successor.. The solution to get the linear inorder traversal is just tailored for a situation where there is no extra space,not even for stack!!! On Fri, Jan 28, 2011 at 5:42 AM, nphard nphard nphard.nph...@gmail.comwrote: @Ritu - Do you realize that you cannot just convert a given binary tree into right-threaded binary tree? You need at least 1 bit information at each node to specify whether the right pointer of that node is a regular pointer or pointer to the inorder successor. This is because traversal is done differently when you arrive at a node through its inorder predecessor. On Thu, Jan 27, 2011 at 7:22 AM, Ritu Garg ritugarg.c...@gmail.comwrote: solution is not too hard to understand!! 1. [quote] For every none leaf node , go to the last node in it's left subtree and mark the right child of that node as x [\quote]. How are we going to refer to the right child now ??We have removed it's reference now !! last node in left sub tree of any node always have right pointer as NULL because this is the last node 2. It is to be repeated for every node except the non leaf nodes . This will take O(n*n) time in worst case , say a leftist tree with only left pointers . root makes n-1 traversals , root's left subtree's root makes n-2 , and so on. i said that it ll take O(n) time for well balanced tree. for a node at height h ,it takes O(h) to fill this node as successor of some other node.if combined for all sum(O(h)) h=1 to lg n ..total time ll come as O(n) 3. Take the case below . 1 2 3 1 1.5 2.5 4 for node 2 , you will go to 1 , which is the successor of 2 , you make 2-right=1 but what about node 1.5 ??? same is the case with node 3 ... 3-right=2.5 . How will we refer to 4 now ?? when you ll process node 1,it ll be filled in as right child of 1.5 there is no successor for 4. In Brief 1. Convert the tree to right threaded binary tree.means all right children point to their successors. it ll take no additional space.ll take O(n) time if tree is well balanced 2. Do inorder traversal to find ith element without using extra space because succssor of each node is pointed by right child. i hope you got it now!! On Wed, Jan 26, 2011 at 5:31 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: I don't seem to understand ur solution . [quote] For every none leaf node , go to the last node in it's left subtree and mark the right child of that node as x [\quote]. How are we going to refer to the right child now ??We have removed it's reference now !! It is to be repeated for every node except the non leaf nodes . This will take O(n*n) time in worst case , say a leftist tree with only left pointers . root makes n-1 traversals , root's left subtree's root makes n-2 , and so on. Go to the largest node in the left subtree .This means go to the left subtree and keep on going to the right until it becomes null , in which case , you make y-right as x . This means effectively , that y is the predecessor of x , in the tree . Considering a very good code , it may take O(1) space , but you will still need additional pointers. Take the case below . 1 2 3 1 1.5 2.5 4 for node 2 , you will go to 1 , which is the successor of 2 , you make 2-right=1 but what about node 1.5 ??? same is the case with node 3 ... 3-right=2.5 . How will we refer to 4 now ?? Now using inorder traversal with a count , I will start at 1-left , 2- left = 1 , then 2 ... then 2-right = 1 again . then 1 , and then 1- right=3 ...clearly , this will not give us a solution . A reverse inorder looks just fine to me . On Jan 26, 3:14 pm, Ritu Garg ritugarg.c...@gmail.com wrote: @Algoose I said ..*.For every node x,go to the last node in its left subtree and mark the right child of that node as x.* it is to be repeated for all nodes except leaf nodes. to apply this approach ,you need to go down the tree.No parent pointers required. for
[algogeeks] Re: Amazon Question
it can be done in O(n) time using right threaded binary tree. 1.Convert the tree to right threaded tree. right threaded tree means every node points to its successor in tree.if right child is not NULL,then it already contains a pointer to its successor Else it needs to filled up as following a. For every node x,go to the last node in its left subtree and mark the right child of that node as x. It Can be done in O(n) time if tree is a balanced tree. 2. Now,Traverse the tree with Inorder Traversal without using additional space(as successor of any node is available O(1) time) and keep track of 5th largest element. Regards, Ritu On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote: Theoretically, the internal stack used by recursive functions must be considered for space complexity. On Mon, Jan 24, 2011 at 5:40 AM, juver++ avpostni...@gmail.com wrote: internal stack != extra space -- 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.comalgogeeks%2bunsubscr...@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.
[algogeeks] Re: Amazon Question
it can be done in O(n) time using right threaded binary tree. 1.Convert the tree to right threaded tree. right threaded tree means every node points to its successor in tree.if right child is not NULL,then it already contains a pointer to its successor Else it needs to filled up as following a. For every node x,go to the last node in its left subtree and mark the right child of that node as x. It Can be done in O(n) time if tree is a balanced tree. 2. Now,Traverse the tree with Inorder Traversal without using additional space(as successor of any node is available O(1) time) and keep track of 5th largest element. Regards, Ritu On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote: Theoretically, the internal stack used by recursive functions must be considered for space complexity. On Mon, Jan 24, 2011 at 5:40 AM, juver++ avpostni...@gmail.com wrote: internal stack != extra space -- 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.comalgogeeks%2bunsubscr...@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 Question
If you convert the given binary tree into right threaded binary tree, won't you be using extra space while doing so? Either the given tree should already be right-threaded (or with parent pointers at each node) or internal stack should be allowed for recursion but no extra space usage apart from that. On Wed, Jan 26, 2011 at 3:04 AM, ritu ritugarg.c...@gmail.com wrote: it can be done in O(n) time using right threaded binary tree. 1.Convert the tree to right threaded tree. right threaded tree means every node points to its successor in tree.if right child is not NULL,then it already contains a pointer to its successor Else it needs to filled up as following a. For every node x,go to the last node in its left subtree and mark the right child of that node as x. It Can be done in O(n) time if tree is a balanced tree. 2. Now,Traverse the tree with Inorder Traversal without using additional space(as successor of any node is available O(1) time) and keep track of 5th largest element. Regards, Ritu On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote: Theoretically, the internal stack used by recursive functions must be considered for space complexity. On Mon, Jan 24, 2011 at 5:40 AM, juver++ avpostni...@gmail.com wrote: internal stack != extra space -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.comalgogeeks%2bunsubscr...@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.
[algogeeks] Re: Amazon Question
No,no extra space is needed. Right children which are NULL pointers are replaced with pointer to successor. On Jan 26, 1:18 pm, nphard nphard nphard.nph...@gmail.com wrote: If you convert the given binary tree into right threaded binary tree, won't you be using extra space while doing so? Either the given tree should already be right-threaded (or with parent pointers at each node) or internal stack should be allowed for recursion but no extra space usage apart from that. On Wed, Jan 26, 2011 at 3:04 AM, ritu ritugarg.c...@gmail.com wrote: it can be done in O(n) time using right threaded binary tree. 1.Convert the tree to right threaded tree. right threaded tree means every node points to its successor in tree.if right child is not NULL,then it already contains a pointer to its successor Else it needs to filled up as following a. For every node x,go to the last node in its left subtree and mark the right child of that node as x. It Can be done in O(n) time if tree is a balanced tree. 2. Now,Traverse the tree with Inorder Traversal without using additional space(as successor of any node is available O(1) time) and keep track of 5th largest element. Regards, Ritu On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote: Theoretically, the internal stack used by recursive functions must be considered for space complexity. On Mon, Jan 24, 2011 at 5:40 AM, juver++ avpostni...@gmail.com wrote: internal stack != extra space -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.comalgogeeks%2bunsubscr...@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.
