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.
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.
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.
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.
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.
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.
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 :)
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.
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.
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.
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.
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.
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,
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
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.
Re: [algogeeks] Re: Amazon Question
@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. 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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252bunsubscr...@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 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.
Re: [algogeeks] Re: Amazon Question
1do reverse inorder and increment count variable it uses internal stack... 2 otherwise modify morris traversal I agree with* juver++*...internal stack!=extra space.internal stack=auxillary space On 26 January 2011 12:53, juver++ avpostni...@gmail.com wrote: @abovew NO! -- You received this message because you are subscribed to the Google Groups Algorithm 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. -- Thanks Regards, Priyanka Chatterjee Final Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.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
@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. 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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252bunsubscr...@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 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.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
@Ritu, Right ! I misread you post On Wed, Jan 26, 2011 at 3:44 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.comwrote: @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. 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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252bunsubscr...@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 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.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.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
Re: [algogeeks] Re: Amazon Question
@Priyanka - what exactly is the difference between extra space and auxiliary
space? As far as the algorithm is concerned, it does use space whose order
of growth is a function of the input size and that is all that matters here.
On Wed, Jan 26, 2011 at 7:55 AM, may.I.answer may.i.answ...@gmail.comwrote:
Well the solution is pretty simple.
What you have to do is just do inoder traversal of tree in reverse
order.
Here goes my C++ code for that
int ith_order(Tree *root,int i)
{
static int c;
static int ans;
if(root)
{
ith_order(root-right,i);
++c;
if(c==i)
return ans=root-data;
ith_order(root-left,i);
}
return ans;
}
please correct me if i am wrong :)
On Jan 26, 5:01 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.
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
Re: [algogeeks] Re: Amazon Question
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
@abovew NO! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 understand what you mean.
Consider a simple inorder traversal of a balanced binary tree. Using
recursion, the code is simply:
void inorder(Node *node) {
if (node == NULL)
return;
inorder(node-left);
print(node-val);
inorder(node-right);
}
What do you consider to be the above code's space complexity? It is O(log n)
but what you are saying is that it is O(1)!!
On Wed, Jan 26, 2011 at 2:23 AM, juver++ avpostni...@gmail.com wrote:
@abovew NO!
--
You received this message because you are subscribed to the Google Groups
Algorithm 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 we shouldn't use recursion at it uses internal stack, then I hope we can use Morris tree traversal and use a counter to find the 5th max. On Fri, Jan 21, 2011 at 11:19 PM, juver++ avpostni...@gmail.com wrote: @above yes, posted solution needs parent links. Another solution is to process tree in reverse inorder: right subtree, root, left subtree and keeping counter k, when k is zero return current node -- You received this message because you are subscribed to the Google Groups Algorithm 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
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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Question
@Juver..doesnt it require the parent information ? What if the data structure has only left and right pointers. On Fri, Jan 21, 2011 at 8:41 PM, juver++ avpostni...@gmail.com wrote: This question was posted some time ago. One solution is - start from the largest element (which is the righmost one in the tree). Then apply algorithm of searchin node's predecessor. It takes O(k) time to find k-th largest/smallest number. -- You received this message because you are subscribed to the Google Groups Algorithm 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. -- 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
@above yes, posted solution needs parent links. Another solution is to process tree in reverse inorder: right subtree, root, left subtree and keeping counter k, when k is zero return current node -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
best method i know is. start comparing elements from ends and put the larger at end and so on TC: O(X+Y) SC: O(1) On Tue, Jan 11, 2011 at 8:11 PM, bittu shashank7andr...@gmail.com wrote: @juver++ so post your approach...i will also do the same..i posted the question here so that we can learn new way to solve or you can say best way to solve problem... One Problem Can be Solved My Many Ways But There is Only One Best Way to Solve It Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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. -- 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 algoge...@googlegroups.com. To unsubscribe from 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
2D matrix sum is a simple DP problem, but U need n*n extra space as well or have to change the i/p. (u can get the i/p back once if required) If this is acceptable, let me explain. Regards, Akash Agrawal http://tech-queries.blogspot.com/ On Sun, Dec 19, 2010 at 7:01 PM, juver++ avpostni...@gmail.com wrote: There is a linear solution in terms of the matrix's size. So in a whole it has O(n^2) time complexity. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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 algoge...@googlegroups.com. To unsubscribe from 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
There is O(n^2) solution with O(n) 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 algoge...@googlegroups.com. To unsubscribe from 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-Linux Shell
*grep -R \[0-9]\+.[0-9]\+.[0-9]\+.[0-9]\+\ * | awk -F':' '{print $1}' |
uniq
*
works on my system :P
On Tue, Sep 21, 2010 at 2:07 PM, Chi c...@linuxdna.com wrote:
With perl installed:
find directory | xargs perl -pi -e 's/needle/replace/g'
With sed installed:
#!/bin/bash
find directory mirror
exec 3mirror
while read file 3
do
replace=`more $file | sed -r -e 's/needle/replace/g'`
cat $replace $file
done
On Sep 19, 11:30 pm, bittu shashank7andr...@gmail.com wrote:
Linux shell command to find all files in a directory which contain ip
addresses
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
--
Neeraj
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from 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
Keep an augmented balanced BST. Augmented data: number of elements in the
right and left subtrees .
Insertion: logn
Find Median: logn
Cheers
Nikhil Jindal
Delhi College of Engineering
On Fri, Sep 17, 2010 at 12:09 PM, vikas kumar vikas.kumar...@gmail.comwrote:
struct list
{
median -- median from the start to num
number ---number
list *next
};
during insertion : insert in sorted LL
after that all subseq node's median has to be modified
O(n)
during median_retriev
check the median value and return that
O(1)
I assumed deletion is not happening. if supported , can be done in
O(n)
On Sep 15, 8:24 pm, bittu shashank7andr...@gmail.com wrote:
Propose a data structure that would store numbers, without any
knowledge about them, and allow to perform the operations: insert, get
median, as efficiently as possible same as before, only this time the
numbers are from a group V, which is |V|n
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from 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 make confused !!!!!!!
It is true that there are infinitely many solutions (or zero solutions) (x, y, z) in any case. But what we are interested here is S=x+y+z. Apply y = S-x-z, you get: S/Vp+x(1/Vd-1/Vp)+z/(1/Vu-1/Vp) = T1 S/Vp+x(1/Vu-1/Vp)+z/(1/Vd-1/Vp) = T2 Adding the two, you get 2S/Vp + (x+z)(1/Vd+1/Vu-2/Vp) = T1+T2 When 1/Vd+1/Vu-2/Vp = 0, S = Vp(T1+T2)/2, no matter what x and z are. In this condition, All the solution (S,x,z) forms a line: (the intersection line of above 2 planes) x-z = (T2-T1) / (2(1/Vu-1/Vp)) S = Vp(T1+T2)/2. which is parallel to x-z plane. On 2010-9-16 6:32, Gene wrote: No. Two linear equations in three unknowns will always yield many solutions (or zero solutions). These are essentially plane equations. Two planes intersect in a line (unless they are parallel). You might get a de facto unique solution for some values of Vu, Vd, Vu, T1, T2 from the constraints x,y,z= 0. It would have to lie on an axis. For example, you can aways pick z and find x and y. Using your notation, x/Vd + y/Vp + z/Vu = T1 x/Vu + y/Vp + z/Vd = T2 Subtract to get: x(1/Vd - 1/Vu) + z(1/Vu - 1/Vd) = T1 - T2 then x = [ (T1 - T2) - z(1/Vu - 1/Vd) ] / (1/Vd - 1/Vu) So now you can pick any z and get x. Once you have both of these, plug them in here: y = Vp (T1 - x/Vd - z/Vu) As long as x,y,z= 0, you are in business. On Sep 14, 10:51 pm, Terencetechnic@gmail.com wrote: You could also get a unique solution if the car has speed of 72 63 56 in downhill, plain and uphill respectively. I think the speed Vd, Vp, Vu was chosen so that 2Vp = Vd + Vu. But for unique solution, it ought to be 2/Vp = 1/Vd + 1/Vu. Under this condition, we can get the unique S=x+y+z: From x/Vd + y/Vp + z/Vu = T1 x/Vu + y/Vp + z/Vd = T2 We get (1/Vu+1/Vd)(x+z)+2/Vp*y = T1+T2 Apply 2/Vp = 1/Vd + 1/Vu, then 2/Vp(x+y+z)=T1+T2 S=x+y+z = Vp(T1+T2)/2 On 2010-9-15 9:31, Gene wrote: This isn't right. Dropping both y terms is the same as setting y to zero. The answer you get is correct, but there are many others as has been said. You could get a unique solution if the route were constrained to be monotonic (level and up or else level and down). On Sep 14, 4:28 pm, Minotaurausanike...@gmail.comwrote: Actually the solution is unique. The middle part with the Ys is the same and therefore can be omitted out. Now you are left with 2 equations and 2 unknowns. I used time in minutes and I have x = 1.28, z = 0.30476 units (y can be found out). I guess the trick was 1. to write the equations that Yan did and 2. to recognize that the plain part is the same and hence can be cancelled. On Sep 14, 3:31 am, Yan Wangwangyanadam1...@gmail.comwrote: actually, there are many solutions, just pick up one from them... On Tue, Sep 14, 2010 at 3:23 AM, Abhilasha jain mail2abhila...@gmail.comwrote: how can u solve 3 variables using 2 equations? On Tue, Sep 14, 2010 at 3:44 PM, Yan Wangwangyanadam1...@gmail.comwrote: x/72 + y/64 + z/56 = 4 x/56 + y/64 + z/72 = 4+2/3 find a solution to this ... On Tue, Sep 14, 2010 at 2:31 AM, bittushashank7andr...@gmail.comwrote: Amazon Interview Question for Software Engineer / Developers A car has speed of 72 64 56 in downhill, plain and uphill respectively . A guy travels in the car from Pt. A to pt. B in 4 Hrs and pt. B to pt. A in 4 Hrs and 40 min. what is the distance between A and B? Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from 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 algoge...@googlegroups.com. To unsubscribe from 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 algoge...@googlegroups.com. To unsubscribe from 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 -- 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 algoge...@googlegroups.com. To unsubscribe from 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 make confused !!!!!!!
You could also get a unique solution if the car has speed of 72 63 56 in downhill, plain and uphill respectively. I think the speed Vd, Vp, Vu was chosen so that 2Vp = Vd + Vu. But for unique solution, it ought to be 2/Vp = 1/Vd + 1/Vu. Under this condition, we can get the unique S=x+y+z: From x/Vd + y/Vp + z/Vu = T1 x/Vu + y/Vp + z/Vd = T2 We get (1/Vu+1/Vd)(x+z)+2/Vp*y = T1+T2 Apply 2/Vp = 1/Vd + 1/Vu, then 2/Vp(x+y+z)=T1+T2 S=x+y+z = Vp(T1+T2)/2 On 2010-9-15 9:31, Gene wrote: This isn't right. Dropping both y terms is the same as setting y to zero. The answer you get is correct, but there are many others as has been said. You could get a unique solution if the route were constrained to be monotonic (level and up or else level and down). On Sep 14, 4:28 pm, Minotaurausanike...@gmail.com wrote: Actually the solution is unique. The middle part with the Ys is the same and therefore can be omitted out. Now you are left with 2 equations and 2 unknowns. I used time in minutes and I have x = 1.28, z = 0.30476 units (y can be found out). I guess the trick was 1. to write the equations that Yan did and 2. to recognize that the plain part is the same and hence can be cancelled. On Sep 14, 3:31 am, Yan Wangwangyanadam1...@gmail.com wrote: actually, there are many solutions, just pick up one from them... On Tue, Sep 14, 2010 at 3:23 AM, Abhilasha jain mail2abhila...@gmail.com wrote: how can u solve 3 variables using 2 equations? On Tue, Sep 14, 2010 at 3:44 PM, Yan Wangwangyanadam1...@gmail.com wrote: x/72 + y/64 + z/56 = 4 x/56 + y/64 + z/72 = 4+2/3 find a solution to this ... On Tue, Sep 14, 2010 at 2:31 AM, bittushashank7andr...@gmail.com wrote: Amazon Interview Question for Software Engineer / Developers A car has speed of 72 64 56 in downhill, plain and uphill respectively . A guy travels in the car from Pt. A to pt. B in 4 Hrs and pt. B to pt. A in 4 Hrs and 40 min. what is the distance between A and B? Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from 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 algoge...@googlegroups.com. To unsubscribe from 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 algoge...@googlegroups.com. To unsubscribe from 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 algoge...@googlegroups.com. To unsubscribe from 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 make confused !!!!!!!
the solution seems to be simple. Just try to imagine what is happening You have a road with downhill and uphill. So if u travel 5 km uphill and then 5 km on plain and then 5 km on downhill then time taken by you will be equal to 15 km on the plain road(that is solely due avg of speed of downhill and uphill is = speed on plain road) so the from A to B we reach 40 min earlier due to there more downhill road. while from A to B it is uphill. So let us take x km as the road distance which is not plain. t1 = time to travel x on downhill = x/72 t2 = time to travel x on uphill = x/56 but as given 40min = 2/3 hr = x/56 - x/72 so, x= 168. so it will take 3 hrs to climb while travelling from B to A and plain road distance = 5/3 * 64 = 106.67 km dist = 168 + 106.67 On Wed, Sep 15, 2010 at 8:21 AM, Terence technic@gmail.com wrote: You could also get a unique solution if the car has speed of 72 63 56 in downhill, plain and uphill respectively. I think the speed Vd, Vp, Vu was chosen so that 2Vp = Vd + Vu. But for unique solution, it ought to be 2/Vp = 1/Vd + 1/Vu. Under this condition, we can get the unique S=x+y+z: From x/Vd + y/Vp + z/Vu = T1 x/Vu + y/Vp + z/Vd = T2 We get (1/Vu+1/Vd)(x+z)+2/Vp*y = T1+T2 Apply 2/Vp = 1/Vd + 1/Vu, then 2/Vp(x+y+z)=T1+T2 S=x+y+z = Vp(T1+T2)/2 On 2010-9-15 9:31, Gene wrote: This isn't right. Dropping both y terms is the same as setting y to zero. The answer you get is correct, but there are many others as has been said. You could get a unique solution if the route were constrained to be monotonic (level and up or else level and down). On Sep 14, 4:28 pm, Minotaurausanike...@gmail.com wrote: Actually the solution is unique. The middle part with the Ys is the same and therefore can be omitted out. Now you are left with 2 equations and 2 unknowns. I used time in minutes and I have x = 1.28, z = 0.30476 units (y can be found out). I guess the trick was 1. to write the equations that Yan did and 2. to recognize that the plain part is the same and hence can be cancelled. On Sep 14, 3:31 am, Yan Wangwangyanadam1...@gmail.com wrote: actually, there are many solutions, just pick up one from them... On Tue, Sep 14, 2010 at 3:23 AM, Abhilasha jain mail2abhila...@gmail.com wrote: how can u solve 3 variables using 2 equations? On Tue, Sep 14, 2010 at 3:44 PM, Yan Wangwangyanadam1...@gmail.com wrote: x/72 + y/64 + z/56 = 4 x/56 + y/64 + z/72 = 4+2/3 find a solution to this ... On Tue, Sep 14, 2010 at 2:31 AM, bittushashank7andr...@gmail.com wrote: Amazon Interview Question for Software Engineer / Developers A car has speed of 72 64 56 in downhill, plain and uphill respectively . A guy travels in the car from Pt. A to pt. B in 4 Hrs and pt. B to pt. A in 4 Hrs and 40 min. what is the distance between A and B? Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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 algoge...@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 algoge...@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.- 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 algoge...@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. -- Regards, Rahul Patil -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from 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 dont have the structure of the node
typedef struct member node
{
int data;
struct member * next;
}ll;
On Tue, Sep 14, 2010 at 5:57 PM, soundar soundha...@gmail.com wrote:
From first linked list set flag value in each traversal of
node..then start from second linked list suppose if flag value is
already set that is the intersection point
correct me if i am wrong
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from 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 make confused !!!!!!!
So if u travel 5 km uphill and then 5 km on plain and then 5 km on downhill then time taken by you will be equal to 15 km on the plain road This is not the truth. 5/72 + 5/64 + 5/56 - 15/64 = 5/72+5/56-10/64 = 10/63-10/64 0 (that is solely due avg of speed of downhill and uphill is = speed on plain road) This only leads to: if u travel 5 hrs uphill and then 5 hrs on plain and then 5 hrs on downhill then distance traveled by you will be equal to travel 15 hrs on the plain road. On 2010-9-15 15:07, rahul patil wrote: the solution seems to be simple. Just try to imagine what is happening You have a road with downhill and uphill. So if u travel 5 km uphill and then 5 km on plain and then 5 km on downhill then time taken by you will be equal to 15 km on the plain road(that is solely due avg of speed of downhill and uphill is = speed on plain road) so the from A to B we reach 40 min earlier due to there more downhill road. while from A to B it is uphill. So let us take x km as the road distance which is not plain. t1 = time to travel x on downhill = x/72 t2 = time to travel x on uphill = x/56 but as given 40min = 2/3 hr = x/56 - x/72 so, x= 168. so it will take 3 hrs to climb while travelling from B to A and plain road distance = 5/3 * 64 = 106.67 km dist = 168 + 106.67 On Wed, Sep 15, 2010 at 8:21 AM, Terence technic@gmail.com mailto:technic@gmail.com wrote: You could also get a unique solution if the car has speed of 72 63 56 in downhill, plain and uphill respectively. I think the speed Vd, Vp, Vu was chosen so that 2Vp = Vd + Vu. But for unique solution, it ought to be 2/Vp = 1/Vd + 1/Vu. Under this condition, we can get the unique S=x+y+z: From x/Vd + y/Vp + z/Vu = T1 x/Vu + y/Vp + z/Vd = T2 We get (1/Vu+1/Vd)(x+z)+2/Vp*y = T1+T2 Apply 2/Vp = 1/Vd + 1/Vu, then 2/Vp(x+y+z)=T1+T2 S=x+y+z = Vp(T1+T2)/2 On 2010-9-15 9:31, Gene wrote: This isn't right. Dropping both y terms is the same as setting y to zero. The answer you get is correct, but there are many others as has been said. You could get a unique solution if the route were constrained to be monotonic (level and up or else level and down). On Sep 14, 4:28 pm, Minotaurausanike...@gmail.com mailto:anike...@gmail.com wrote: Actually the solution is unique. The middle part with the Ys is the same and therefore can be omitted out. Now you are left with 2 equations and 2 unknowns. I used time in minutes and I have x = 1.28, z = 0.30476 units (y can be found out). I guess the trick was 1. to write the equations that Yan did and 2. to recognize that the plain part is the same and hence can be cancelled. On Sep 14, 3:31 am, Yan Wangwangyanadam1...@gmail.com mailto:wangyanadam1...@gmail.com wrote: actually, there are many solutions, just pick up one from them... On Tue, Sep 14, 2010 at 3:23 AM, Abhilasha jain mail2abhila...@gmail.com mailto:mail2abhila...@gmail.com wrote: how can u solve 3 variables using 2 equations? On Tue, Sep 14, 2010 at 3:44 PM, Yan Wangwangyanadam1...@gmail.com mailto:wangyanadam1...@gmail.com wrote: x/72 + y/64 + z/56 = 4 x/56 + y/64 + z/72 = 4+2/3 find a solution to this ... On Tue, Sep 14, 2010 at 2:31 AM, bittushashank7andr...@gmail.com mailto:shashank7andr...@gmail.com wrote: Amazon Interview Question for Software Engineer / Developers A car has speed of 72 64 56 in downhill, plain and uphill respectively . A guy travels in the car from Pt. A to pt. B in 4 Hrs and pt. B to pt. A in 4 Hrs and 40 min. what is the distance between A and B? Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to
Re: [algogeeks] Re: Amazon Question
The following algorithm traversals both lists twice to find the
intersection point, without modification to the original nodes.
The only assumptions:
1) Head pointer of two list: La, Lb
2) .next point to the next node.
3) .next of the tail node is NULL
intersect(La,Lb)
{
// Find the length difference of two lists
for (pA = La, pB = Lb; pA != NULL pB != NULL; pA = pA-next, pB =
pB-next);
// Discard the beginning of the longer list, to get equal length as
the shorter one.
if(pA != NULL) {
for(pC = pA, pA = La; pC != NULL; pA = pA-next, pC = pC-next);
pB = Lb;
} else if(pB != NULL) {
for(pC = pB, pB = Lb; pC != NULL; pB = pB-next, pC = pC-next);
pA = La;
}
// Traversal both list, until we get a common node, return this node.
// If no such intersection, NULL is returned. (pA,pB will get NULL at
the same time)
for( ; pA != pB; pA = pA-next, pB = pB-next);
return pA;
}
On 2010-9-15 15:50, sharad kumar wrote:
you dont have the structure of the node
typedef struct member node
{
int data;
struct member * next;
}ll;
On Tue, Sep 14, 2010 at 5:57 PM, soundar soundha...@gmail.com
mailto:soundha...@gmail.com wrote:
From first linked list set flag value in each traversal of
node..then start from second linked list suppose if flag value is
already set that is the intersection point
correct me if i am 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
mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from 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 algoge...@googlegroups.com.
To unsubscribe from 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 that we have to generate substrings from the given string such that
the similarity is above 50%
for eg.
word =foo
we have to generate the strings which must be greater than half of the given
string length
{fo,oo} (in this case)
after this operation we have the following string set {foo,fo,oo}
then we can doselect* from product where name like '%foo%'select*
from product where name like '%fo%'. select* from product where name
like '%oo%'
please do correct me if i am wrong
On Mon, Sep 13, 2010 at 1:01 PM, SVIX saivivekh.swaminat...@gmail.comwrote:
select * from product
where
name like '%foo%'
and len(name) =6;
btw, how do u define similarity? i'm guessing it wouldn't be this
simple...
On Sep 12, 5:12 am, Snoopy Me thesnoop...@gmail.com wrote:
You are given the amazon.com database which consists of names of
millions of products. When a user enters a search query for particular
object with the keyword say foo , output all the products which have
names having 50% or more similarity with the given keyword ie foo
Write the most efficient algorithm for the same.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
--
By B. Praveen
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from 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 will have to use the concept of edit distance ..
google for edit distance and you may find too many good articles on it.
Levenshtein distance is one such algorithm for measuring the amount of
difference between two sequences [edit distance]
On Mon, Sep 13, 2010 at 2:55 PM, Praveen Baskar praveen200...@gmail.comwrote:
i think that we have to generate substrings from the given string such that
the similarity is above 50%
for eg.
word =foo
we have to generate the strings which must be greater than half of the
given string length
{fo,oo} (in this case)
after this operation we have the following string set {foo,fo,oo}
then we can doselect* from product where name like '%foo%'select*
from product where name like '%fo%'. select* from product where name
like '%oo%'
please do correct me if i am wrong
On Mon, Sep 13, 2010 at 1:01 PM, SVIX saivivekh.swaminat...@gmail.comwrote:
select * from product
where
name like '%foo%'
and len(name) =6;
btw, how do u define similarity? i'm guessing it wouldn't be this
simple...
On Sep 12, 5:12 am, Snoopy Me thesnoop...@gmail.com wrote:
You are given the amazon.com database which consists of names of
millions of products. When a user enters a search query for particular
object with the keyword say foo , output all the products which have
names having 50% or more similarity with the given keyword ie foo
Write the most efficient algorithm for the same.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
--
By B. Praveen
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
--
regards ,
Anuj Maurice
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from 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
cant it be like '%f%'
On Mon, Sep 13, 2010 at 2:55 PM, Praveen Baskar praveen200...@gmail.comwrote:
i think that we have to generate substrings from the given string such that
the similarity is above 50%
for eg.
word =foo
we have to generate the strings which must be greater than half of the
given string length
{fo,oo} (in this case)
after this operation we have the following string set {foo,fo,oo}
then we can doselect* from product where name like '%foo%'select*
from product where name like '%fo%'. select* from product where name
like '%oo%'
please do correct me if i am wrong
On Mon, Sep 13, 2010 at 1:01 PM, SVIX
saivivekh.swaminat...@gmail.comwrote:
select * from product
where
name like '%foo%'
and len(name) =6;
btw, how do u define similarity? i'm guessing it wouldn't be this
simple...
On Sep 12, 5:12 am, Snoopy Me thesnoop...@gmail.com wrote:
You are given the amazon.com database which consists of names of
millions of products. When a user enters a search query for particular
object with the keyword say foo , output all the products which have
names having 50% or more similarity with the given keyword ie foo
Write the most efficient algorithm for the same.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
--
By B. Praveen
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
