Re: [algogeeks] Re: Amazon Question

[zoom]

//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  wrote:
>
>> bool firstCousins(struct node * pRoot, struct node *pThis, (struct 
>> node*)[] path, int pos, vector 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 (pos<2) 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  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 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!!
>>>
>>>
>>>  
>>  -- 
>> You received this message because you are subscribed to the Google Groups 
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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

[Mithun Kumar]

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  wrote:

> bool firstCousins(struct node * pRoot, struct node *pThis, (struct
> node*)[] path, int pos, vector 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 (pos<2) 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  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 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!!
>>
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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

[Ashish Goel]

bool firstCousins(struct node * pRoot, struct node *pThis, (struct node*)[]
path, int pos, vector 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 (pos<2) 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  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 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!!
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

[Ashish Goel]

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 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!!

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

[sivaviknesh]

 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  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  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.com>wrote:
>> >
>> >
>> >
>> > > 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  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  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.com>wrote:
>> >
>> >
>> >
>> > > 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  wrot

Re: [algogeeks] Re: Amazon question

[Amol Sharma]

+1 @ anurag's solution.agree with O(sqrt(n)) complexity.
--


Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
 







On Thu, Mar 22, 2012 at 11:42 AM, Anurag Gupta wrote:

> I think this works and the complexity is O(sqrt(n))
>
>
> #include
> #include
> #include
> #include
> #include
> 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 == 0  &&  minDis > (i/j - j) )
>   {
>  minDis = i/j - j;
>  minDiv = j;
>  val = i;
>   }
>}
>}
>cout<}
>//system("pause");
>return 0;
> }
>
> On Mar 22, 10:34 am, atul anand  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  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

[Ankur Garg]

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  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 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  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 
>> 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 
>> 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

[Ankur Garg]

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  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  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 
> 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 
> 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

[annarao kataru]

@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

[Jagannath Prasad Das]

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
wrote:

> 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 
> wrote:
>
>> :)
>>
>>
>> *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

[aditya kumar]

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 wrote:

> :)
>
>
> *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

[Sanjay Rajpal]

:)

*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

[priya ramesh]

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

[Sanjay Rajpal]

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

[priya ramesh]

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

[Sanjay Rajpal]

this is because I have XORed elements.

I assumed, in the array there are numbers from 1 to n and a number is
repeated once, all others occur once only. So when I XORed the result with
numbers from 1 to n(second loop), this will make the numbers XORed twice
except the number which was repeated( and now XORed thrice).

so repeated element is given by the result.
e.g.

say numbers are : 1,2,3,4,5,6,5
XOR them together, let result is Res.

Now XOR Res with Natural no.s 1-6.

The situation now is : 1 ^ 1, 2 ^ 2,3 ^ 3, 4 ^ 4, 5 ^ 5 ^ 5, 6 ^ 6.

So as is clear from above, the result will be 5 and thus algo will not work
if the numbers are not in the range 1-n.

But you can modify it for a given set of numbers, but the condition is all
the elements within that range have to be present in any order with a
duplicate one.

In this case, find the minimum and maximum, in O(n) time.
then follow the procedure mentioned in my earlier post.

*Regards

Sanju

Happy to Help :)*



On Fri, Aug 19, 2011 at 5:52 AM, priya ramesh <
love.for.programm...@gmail.com> wrote:

> @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.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

[priya ramesh]

@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

[rakesh kumar]

hi,

How about this solution
  if the elements are in the range and all the elements should present
then u can find sum of N numbers n(n+1)/2  by using range and factorial of n
numbers

then u will get 2 equations solve the equations u will get the actual
repeted no


 for 1,3,3,4
11-y+x=10
36x/y = 24

solve these equation to get the x value which is missing or y value
which is repeate...

Correct me if iam wrong




On Fri, Aug 19, 2011 at 5:01 PM, Sanjay Rajpal wrote:

> 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.

Re: [algogeeks] Re: Amazon question

[Sanjay Rajpal]

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 
> wrote:
>
>> 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

[monty 1987]

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 wrote:

> 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 
>> 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.

Re: [algogeeks] Re: Amazon question

[Sanjay Rajpal]

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 
> 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.

Re: [algogeeks] Re: Amazon question

[monty 1987]

@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 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.

Re: [algogeeks] Re: Amazon question

[Sanjay Rajpal]

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

[Sanjay Rajpal]

I assume the no.s are in the range 1 to n.
Now XOR all the elements together.
Now XOR the result with all numbers from 1 to n in a loop.

The Repeated no. occurs thrice(the result is Repeated number) and all others
get XORed twice(give 0 result).

Thus the result will be the repeated number .

*Regards

Sanju

Happy to Help :)*



On Thu, Aug 18, 2011 at 8:42 PM, *$*  wrote:

> 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, *$*  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 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, *$*  wrote:

> only once
>
>
> On Fri, Aug 19, 2011 at 7:57 AM, saurabh singh wrote:
>
>> The element is repeated only once or can be repeated k number of
>> times??
>>
>> On Fri, Aug 19, 2011 at 7:50 AM, *$* 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`  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, "*$*"  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 

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  wrote:

> hash map is the solution provided the elements lie in a predefined range..
>
> On Fri, Aug 19, 2011 at 8:46 AM, *$*  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 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, *$*  wrote:
>>>
 only once


 On Fri, Aug 19, 2011 at 7:57 AM, saurabh singh wrote:

> The element is repeated only once or can be repeated k number of
> times??
>
> On Fri, Aug 19, 2011 at 7:50 AM, *$*  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`  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, "*$*"  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" g

Re: [algogeeks] Re: Amazon question

[Dheeraj Sharma]

hash map is the solution provided the elements lie in a predefined range..

On Fri, Aug 19, 2011 at 8:46 AM, *$*  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 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, *$*  wrote:
>>
>>> only once
>>>
>>>
>>> On Fri, Aug 19, 2011 at 7:57 AM, saurabh singh wrote:
>>>
 The element is repeated only once or can be repeated k number of times??

 On Fri, Aug 19, 2011 at 7:50 AM, *$*  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`  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, "*$*"  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 rece

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  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, *$*  wrote:
>
>> only once
>>
>>
>> On Fri, Aug 19, 2011 at 7:57 AM, saurabh singh wrote:
>>
>>> The element is repeated only once or can be repeated k number of times??
>>>
>>> On Fri, Aug 19, 2011 at 7:50 AM, *$*  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`  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, "*$*"  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

[Dipankar Patro]

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, *$*  wrote:

> only once
>
>
> On Fri, Aug 19, 2011 at 7:57 AM, saurabh singh wrote:
>
>> The element is repeated only once or can be repeated k number of times??
>>
>> On Fri, Aug 19, 2011 at 7:50 AM, *$*  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`  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, "*$*"  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

[*$*]

only once

On Fri, Aug 19, 2011 at 7:57 AM, saurabh singh  wrote:

> The element is repeated only once or can be repeated k number of times??
>
> On Fri, Aug 19, 2011 at 7:50 AM, *$*  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`  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, "*$*"  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

[saurabh singh]

The element is repeated only once or can be repeated k number of times??

On Fri, Aug 19, 2011 at 7:50 AM, *$*  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`  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, "*$*"  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

[*$*]

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`  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, "*$*"  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

[siddharam suresh]

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
wrote:

> bitset would work i guess
>
> On Aug 18, 7:10 pm, hary rathor  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.

[Ankur Garg]

@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 

> Can we find any alg. which runs faster than O(n^2) using these 2 axioms ?
>
>
> 2011/8/10 Amethy hobby 
>
>> it also like Pythagorean theorem;
>> so the a[k] also with the value where
>> a[j]-a[i]> and a[k]>a[j]>=a[i];
>>
>> On 8月9日, 下午10时43分, Samba Ganapavarapu  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.

[Samba Ganapavarapu]

Can we find any alg. which runs faster than O(n^2) using these 2 axioms ?

2011/8/10 Amethy hobby 

> it also like Pythagorean theorem;
> so the a[k] also with the value where
> a[j]-a[i] and a[k]>a[j]>=a[i];
>
> On 8月9日, 下午10时43分, Samba Ganapavarapu  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.

[Dinoja Padmanabhan]

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  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.

[Kunal Patil]

@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.

[ankit sambyal]

@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.

[Kunal Patil]

@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

[siddharam suresh]

@ankit:i feel  you are right!!!
Thank you,
Siddharam


On Mon, Aug 8, 2011 at 10:56 PM, ankit sambyal wrote:

> 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

[ankit sambyal]

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

[kumar raja]

@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  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 wrote:
>
>> @sagar thanx :)
>>
>>
>> On Mon, Aug 8, 2011 at 9:01 PM, sagar pareek wrote:
>>
>>> @aditi
>>> nope... it will run in parallel...so order is not fix
>>>
>>>
>>> On Mon, Aug 8, 2011 at 8:48 PM, Pradeep Mishra >> > 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 
 wrote:

> 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 wrote:
>
>>
>>
>>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 ret>0  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 > > 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 >>> > 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 

Re: [algogeeks] Re: amazon question

[Kamakshii Aggarwal]

@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 wrote:

> @sagar thanx :)
>
>
> On Mon, Aug 8, 2011 at 9:01 PM, sagar pareek wrote:
>
>> @aditi
>> nope... it will run in parallel...so order is not fix
>>
>>
>> On Mon, Aug 8, 2011 at 8:48 PM, Pradeep Mishra 
>> 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 wrote:
>>>
 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 wrote:

>
>
>  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 ret>0  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 
> 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 
>>> 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:
>
>>

Re: [algogeeks] Re: amazon question

[aditi garg]

@sagar thanx :)

On Mon, Aug 8, 2011 at 9:01 PM, sagar pareek  wrote:

> @aditi
> nope... it will run in parallel...so order is not fix
>
>
> On Mon, Aug 8, 2011 at 8:48 PM, Pradeep Mishra 
> 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 wrote:
>>
>>> 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 wrote:
>>>


  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 ret>0  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 
 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 
>> 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 
> wrote:
>
>> get it..!! :) :)
>>
>> On Aug 7, 10:49 pm, Shachindra A C  wrote:
>> > 8 one's and 8 two's. The order in which they get printed might
>> vary.
>> >
>

Re: [algogeeks] Re: amazon question

[sagar pareek]

@aditi
nope... it will run in parallel...so order is not fix

On Mon, Aug 8, 2011 at 8:48 PM, Pradeep Mishra 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 wrote:
>
>> 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 wrote:
>>
>>>
>>>
>>>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 ret>0  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 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 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 
 wrote:

> get it..!! :) :)
>
> On Aug 7, 10:49 pm, Shachindra A C  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
> > wrote:
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > > what will be the o/p of the following program:
> >
> > > main()
>

Re: [algogeeks] Re: amazon question

[Pradeep Mishra]

no it'll vary as the PID will vary from parent to child.


On Mon, Aug 8, 2011 at 8:05 AM, aditi garg wrote:

> 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 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 ret>0  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 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 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  > 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 wrote:
>>>
 get it..!! :) :)

 On Aug 7, 10:49 pm, Shachindra A C  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
 > wrote:
 >
 >
 >
 >
 >
 >
 >
 >
 >
 > > what will be the o/p of the following program:
 >
 > > main()
 > > {
 > > int ret;
 > > ret=fork();
 > > ret=fork();
 > > ret=fork();
 > > ret=fork();
 >
 > > if(!ret)
 > > printf("one");
 > > else
 > > printf("two");
 > > }
 >
 > > --
 > > Regards,
 > > Kamakshi
 > > kamak

Re: [algogeeks] Re: amazon question

[aditi garg]

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  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 ret>0  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 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 > > wrote:
>>
>>> ok ..thanks sagar..:)
>>>
>>>
>>> On Mon, Aug 8, 2011 at 6:42 PM, sagar pareek 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 
 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 wrote:
>>
>>> get it..!! :) :)
>>>
>>> On Aug 7, 10:49 pm, Shachindra A C  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
>>> > wrote:
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> > > what will be the o/p of the following program:
>>> >
>>> > > main()
>>> > > {
>>> > > int ret;
>>> > > ret=fork();
>>> > > ret=fork();
>>> > > ret=fork();
>>> > > ret=fork();
>>> >
>>> > > if(!ret)
>>> > > printf("one");
>>> > > else
>>> > > printf("two");
>>> > > }
>>> >
>>> > > --
>>> > > Regards,
>>> > > Kamakshi
>>> > > kamakshi...@gmail.com
>>> >
>>> > > --
>>> > > You received this message because you are subscribed to the
>>> Google Groups
>>> > > "Algorithm Geeks" group.
>>> > > To post to this group, send email to algogeeks@googlegroups.com.
>

Re: [algogeeks] Re: amazon question

[sagar pareek]

 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 ret>0  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 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 
> wrote:
>
>> ok ..thanks sagar..:)
>>
>>
>> On Mon, Aug 8, 2011 at 6:42 PM, sagar pareek 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 
>>> 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 wrote:
>
>> get it..!! :) :)
>>
>> On Aug 7, 10:49 pm, Shachindra A C  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
>> > wrote:
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > > what will be the o/p of the following program:
>> >
>> > > main()
>> > > {
>> > > int ret;
>> > > ret=fork();
>> > > ret=fork();
>> > > ret=fork();
>> > > ret=fork();
>> >
>> > > if(!ret)
>> > > printf("one");
>> > > else
>> > > printf("two");
>> > > }
>> >
>> > > --
>> > > Regards,
>> > > Kamakshi
>> > > kamakshi...@gmail.com
>> >
>> > > --
>> > > You received this message because you are subscribed to the Google
>> Groups
>> > > "Algorithm Geeks" group.
>> > > To post to this group, send email to algogeeks@googlegroups.com.
>> > > To unsubscribe from this group, send email to
>> > > algogeeks+unsubscr...@googlegroups.com.
>> > > For more options, visit this group at
>> > >http://groups.google.com/group/algogeeks?hl=en.
>> >
>> > --
>> > Regards,
>> > Shachindra A C
>>
>> --
>> You received this message because you are subscribed to the Google
>> Groups "Alg

Re: [algogeeks] Re: amazon question

[aditi garg]

@ 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 wrote:

> ok ..thanks sagar..:)
>
>
> On Mon, Aug 8, 2011 at 6:42 PM, sagar pareek 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 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 wrote:

> get it..!! :) :)
>
> On Aug 7, 10:49 pm, Shachindra A C  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
> > wrote:
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > > what will be the o/p of the following program:
> >
> > > main()
> > > {
> > > int ret;
> > > ret=fork();
> > > ret=fork();
> > > ret=fork();
> > > ret=fork();
> >
> > > if(!ret)
> > > printf("one");
> > > else
> > > printf("two");
> > > }
> >
> > > --
> > > Regards,
> > > Kamakshi
> > > kamakshi...@gmail.com
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > --
> > 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 gr

Re: [algogeeks] Re: amazon question

[Kamakshii Aggarwal]

ok ..thanks sagar..:)

On Mon, Aug 8, 2011 at 6:42 PM, sagar pareek  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 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 wrote:
>>>
 get it..!! :) :)

 On Aug 7, 10:49 pm, Shachindra A C  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
 > wrote:
 >
 >
 >
 >
 >
 >
 >
 >
 >
 > > what will be the o/p of the following program:
 >
 > > main()
 > > {
 > > int ret;
 > > ret=fork();
 > > ret=fork();
 > > ret=fork();
 > > ret=fork();
 >
 > > if(!ret)
 > > printf("one");
 > > else
 > > printf("two");
 > > }
 >
 > > --
 > > Regards,
 > > Kamakshi
 > > kamakshi...@gmail.com
 >
 > > --
 > > You received this message because you are subscribed to the Google
 Groups
 > > "Algorithm Geeks" group.
 > > To post to this group, send email to algogeeks@googlegroups.com.
 > > To unsubscribe from this group, send email to
 > > algogeeks+unsubscr...@googlegroups.com.
 > > For more options, visit this group at
 > >http://groups.google.com/group/algogeeks?hl=en.
 >
 > --
 > 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 pareek]

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 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  > wrote:
>
>> then please elaborate?
>>
>>
>> On Mon, Aug 8, 2011 at 12:34 PM, Pradex  wrote:
>>
>>> get it..!! :) :)
>>>
>>> On Aug 7, 10:49 pm, Shachindra A C  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
>>> > wrote:
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> > > what will be the o/p of the following program:
>>> >
>>> > > main()
>>> > > {
>>> > > int ret;
>>> > > ret=fork();
>>> > > ret=fork();
>>> > > ret=fork();
>>> > > ret=fork();
>>> >
>>> > > if(!ret)
>>> > > printf("one");
>>> > > else
>>> > > printf("two");
>>> > > }
>>> >
>>> > > --
>>> > > Regards,
>>> > > Kamakshi
>>> > > kamakshi...@gmail.com
>>> >
>>> > > --
>>> > > You received this message because you are subscribed to the Google
>>> Groups
>>> > > "Algorithm Geeks" group.
>>> > > To post to this group, send email to algogeeks@googlegroups.com.
>>> > > To unsubscribe from this group, send email to
>>> > > algogeeks+unsubscr...@googlegroups.com.
>>> > > For more options, visit this group at
>>> > >http://groups.google.com/group/algogeeks?hl=en.
>>> >
>>> > --
>>> > 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

[Shachindra A C]

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
wrote:

> then please elaborate?
>
>
> On Mon, Aug 8, 2011 at 12:34 PM, Pradex  wrote:
>
>> get it..!! :) :)
>>
>> On Aug 7, 10:49 pm, Shachindra A C  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
>> > wrote:
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > > what will be the o/p of the following program:
>> >
>> > > main()
>> > > {
>> > > int ret;
>> > > ret=fork();
>> > > ret=fork();
>> > > ret=fork();
>> > > ret=fork();
>> >
>> > > if(!ret)
>> > > printf("one");
>> > > else
>> > > printf("two");
>> > > }
>> >
>> > > --
>> > > Regards,
>> > > Kamakshi
>> > > kamakshi...@gmail.com
>> >
>> > > --
>> > > You received this message because you are subscribed to the Google
>> Groups
>> > > "Algorithm Geeks" group.
>> > > To post to this group, send email to algogeeks@googlegroups.com.
>> > > To unsubscribe from this group, send email to
>> > > algogeeks+unsubscr...@googlegroups.com.
>> > > For more options, visit this group at
>> > >http://groups.google.com/group/algogeeks?hl=en.
>> >
>> > --
>> > 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

[Prem Krishna Chettri]

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
wrote:

> then please elaborate?
>
>
> On Mon, Aug 8, 2011 at 12:34 PM, Pradex  wrote:
>
>> get it..!! :) :)
>>
>> On Aug 7, 10:49 pm, Shachindra A C  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
>> > wrote:
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > > what will be the o/p of the following program:
>> >
>> > > main()
>> > > {
>> > > int ret;
>> > > ret=fork();
>> > > ret=fork();
>> > > ret=fork();
>> > > ret=fork();
>> >
>> > > if(!ret)
>> > > printf("one");
>> > > else
>> > > printf("two");
>> > > }
>> >
>> > > --
>> > > Regards,
>> > > Kamakshi
>> > > kamakshi...@gmail.com
>> >
>> > > --
>> > > You received this message because you are subscribed to the Google
>> Groups
>> > > "Algorithm Geeks" group.
>> > > To post to this group, send email to algogeeks@googlegroups.com.
>> > > To unsubscribe from this group, send email to
>> > > algogeeks+unsubscr...@googlegroups.com.
>> > > For more options, visit this group at
>> > >http://groups.google.com/group/algogeeks?hl=en.
>> >
>> > --
>> > 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

[Kamakshii Aggarwal]

then please elaborate?

On Mon, Aug 8, 2011 at 12:34 PM, Pradex  wrote:

> get it..!! :) :)
>
> On Aug 7, 10:49 pm, Shachindra A C  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
> > wrote:
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > > what will be the o/p of the following program:
> >
> > > main()
> > > {
> > > int ret;
> > > ret=fork();
> > > ret=fork();
> > > ret=fork();
> > > ret=fork();
> >
> > > if(!ret)
> > > printf("one");
> > > else
> > > printf("two");
> > > }
> >
> > > --
> > > Regards,
> > > Kamakshi
> > > kamakshi...@gmail.com
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > --
> > 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

[*$*]

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"
#include
#include
#include
#include

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;iwrote:

> in the above example y ac is not included in the substring?
>
>
> On Wed, Jul 27, 2011 at 3:45 PM, saurabh singh 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 wrote:
>>
>>> @ sunny , ur right!!
>>>
>>> surender
>>>
>>> On Wed, Jul 27, 2011 at 1:58 PM, sunny agrawal 
>>> wrote:
>>>
 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 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.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 > > 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;
 }
 }

  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  wrote:
 >> > how?
 >> >
 >> > On 26 July 2011 23:18, ankit sambyal 
 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 

Re: [algogeeks] Re: Amazon Question

[Kamakshii Aggarwal]

in the above example y ac is not included in the substring?

On Wed, Jul 27, 2011 at 3:45 PM, saurabh singh  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 wrote:
>
>> @ sunny , ur right!!
>>
>> surender
>>
>> On Wed, Jul 27, 2011 at 1:58 PM, sunny agrawal 
>> wrote:
>>
>>> 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 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.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 
> 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;
>>> }
>>> }
>>>
>>>  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  wrote:
>>> >> > how?
>>> >> >
>>> >> > On 26 July 2011 23:18, ankit sambyal 
>>> 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 

Re: [algogeeks] Re: Amazon Question

[saurabh singh]

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  wrote:

> @ sunny , ur right!!
>
> surender
>
> On Wed, Jul 27, 2011 at 1:58 PM, sunny agrawal wrote:
>
>> 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 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 >> > 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 
 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;
>> }
>> }
>>
>>  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  wrote:
>> >> > how?
>> >> >
>> >> > On 26 July 2011 23:18, ankit sambyal 
>> 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 th

Re: [algogeeks] Re: Amazon Question

[surender sanke]

@ sunny , ur right!!

surender

On Wed, Jul 27, 2011 at 1:58 PM, sunny agrawal wrote:

> 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 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 
>> 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 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;
> }
> }
>
>  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  wrote:
> >> > how?
> >> >
> >> > On 26 July 2011 23:18, ankit sambyal 
> 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=

Re: [algogeeks] Re: Amazon Question

[sunny agrawal]

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  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 
> 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 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 >> > 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;
 }
 }

  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  wrote:
 >> > how?
 >> >
 >> > On 26 July 2011 23:18, ankit sambyal 
 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.

Re: [algogeeks] Re: Amazon Question

[surender sanke]

*
 /  \\
   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 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 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 
>> 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;
>>> }
>>> }
>>>
>>>  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 
>>> wrote:
>>> >>
>>> >> http://geeksforgeeks.org/?p=767
>>> >>
>>> >> On Jul 26, 11:49 pm, Pratz mary  wrote:
>>> >> > how?
>>> >> >
>>> >> > On 26 July 2011 23:18, ankit sambyal 
>>> 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/algogee

Re: [algogeeks] Re: Amazon Question

[sunny agrawal]

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 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 
> 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;
>> }
>> }
>>
>>  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 
>> wrote:
>> >>
>> >> http://geeksforgeeks.org/?p=767
>> >>
>> >> On Jul 26, 11:49 pm, Pratz mary  wrote:
>> >> > how?
>> >> >
>> >> > On 26 July 2011 23:18, ankit sambyal  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

[surender sanke]

@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 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;
> }
> }
>
>  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 
> wrote:
> >>
> >> http://geeksforgeeks.org/?p=767
> >>
> >> On Jul 26, 11:49 pm, Pratz mary  wrote:
> >> > how?
> >> >
> >> > On 26 July 2011 23:18, ankit sambyal  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

[sunny agrawal]

@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;
                }
        }

 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  wrote:
>>
>> http://geeksforgeeks.org/?p=767
>>
>> On Jul 26, 11:49 pm, Pratz mary  wrote:
>> > how?
>> >
>> > On 26 July 2011 23:18, ankit sambyal  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

[saurabh singh]

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 wrote:

> http://geeksforgeeks.org/?p=767
>
> On Jul 26, 11:49 pm, Pratz mary  wrote:
> > how?
> >
> > On 26 July 2011 23:18, ankit sambyal  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

[Pratz mary]

how?


On 26 July 2011 23:18, ankit sambyal  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

[ankit sambyal]

@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

[Ashish Goel]

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  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  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.com>wrote:
> >
> >
> >
> > > 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

[priya mehta]

@Dave i understood it thanks :)

On Thu, Apr 14, 2011 at 9:53 AM, Dave  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  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.com>wrote:
> >
> >
> >
> > > 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

[Gunjan Sharma]

And Integers too :P

On Fri, Mar 4, 2011 at 12:03 AM, nishaanth  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 wrote:
>
>> he already  pointed out that  there are no repetations..!!
>>
>>
>> On Thu, Mar 3, 2011 at 9:40 PM, Vipin Agrawal 
>> wrote:
>>
>>> take an example
>>>
>>> 3 3 3 5 5 5 7 8
>>>
>>> I think this would fail
>>>
>>> On Mar 3, 8:22 pm, Ankit Sinha  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 
>>> 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 
>>> 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

[nishaanth]

@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 wrote:

> he already  pointed out that  there are no repetations..!!
>
>
> On Thu, Mar 3, 2011 at 9:40 PM, Vipin Agrawal wrote:
>
>> take an example
>>
>> 3 3 3 5 5 5 7 8
>>
>> I think this would fail
>>
>> On Mar 3, 8:22 pm, Ankit Sinha  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 
>> 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 
>> 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

[sukhmeet singh]

he already  pointed out that  there are no repetations..!!

On Thu, Mar 3, 2011 at 9:40 PM, Vipin Agrawal wrote:

> take an example
>
> 3 3 3 5 5 5 7 8
>
> I think this would fail
>
> On Mar 3, 8:22 pm, Ankit Sinha  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 
> 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 
> 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

[Gajendra Dadheech]

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 (R&D)

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 wrote:

> @ bittu and bharath
>
> the tree is given in form of string
>
>
>
>
>
> On Sun, Feb 6, 2011 at 6:55 PM, Bharath M R wrote:
>
>> 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

[jalaj jaiswal]

@ bittu and bharath

the tree is given in form of string




On Sun, Feb 6, 2011 at 6:55 PM, Bharath M R wrote:

> 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.

Re: [algogeeks] Re: Amazon Question

[Ritu Garg]

Yes,it works for binary search tree only

On Sat, Jan 29, 2011 at 2:22 PM, nphard nphard wrote:

> Looks good. I concede that it works for a Binary "Search" Tree.
>
> On Sat, Jan 29, 2011 at 1:35 AM, Ritu Garg 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 
>> wrote:
>>
>>> 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 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 >>> > 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 
> 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 

Re: [algogeeks] Re: Amazon Question

[nphard nphard]

Looks good. I concede that it works for a Binary "Search" Tree.

On Sat, Jan 29, 2011 at 1:35 AM, Ritu Garg  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 wrote:
>
>> 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 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 
>>> 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 
 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 lefti

Re: [algogeeks] Re: Amazon Question

[Ritu Garg]

@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 wrote:

> 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 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 
>> 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 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
> w

Re: [algogeeks] Re: Amazon Question

[nphard nphard]

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  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 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 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  wrote:
 > @Algoose
 >
 > I said ..*

Re: [algogeeks] Re: Amazon Question

[Ritu Garg]

@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 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 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  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 
>>> wrote:
>>> > > @ritu
>>> > > how would you find a successor without extra space if you dont have a
>>> > > parent point

Re: [algogeeks] Re: Amazon Question

[nphard nphard]

@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  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  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 
>> 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 
>> 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  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 p

Re: [algogeeks] Re: Amazon Question

[Ritu Garg]

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  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 
> 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 
> 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  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 
> 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 no

Re: [algogeeks] Re: Amazon Question

[nphard nphard]

@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 wrote:

> 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 
> 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  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 
> 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 
> 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  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 
> 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 
> wrote:
> > > >> > > > Theoretically, the internal stack used by recursive functions
> must
> > > >> be
> >

Re: [algogeeks] Re: Amazon Question

[Algoose chase]

@Ritu,
Right ! I misread you post

On Wed, Jan 26, 2011 at 3:44 PM, Ritu Garg  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 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  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  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  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  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++ 
>>> 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.com
>>> 
>>> >
>>> > > 
>>> 
>>> >
>>> >
>>> > > > > .
>>> > > > > For more options, visit this group at
>>> > > > >http://groups.google.com/group/algogeeks?hl=en.
>>> >
>>> > > --
>>> > > You received this message because you are subscribed to the Google
>>> Groups
>>> > > "Algorithm Geeks" group.
>>> > > To post to this group, send email to algogeeks@googlegroups.com.
>>> > > To unsubscribe from this group, send email to
>>> > > algogeeks+unsubscr...@googlegroups.com
>>> 
>>> >
>>> > > .
>>> > > For more options, visit this group at
>>> > >http://groups.google.com/group/algogeeks?hl=en.
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Amazon Question

[Ritu Garg]

@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  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  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  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  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  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++ 
>> 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.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

[Priyanka Chatterjee]

1>do 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++  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.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 chase]

@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  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  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  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  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++ 
> 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.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

[nphard nphard]

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  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  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++  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.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

[nphard nphard]

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++  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.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

[juver++]

@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

[nphard nphard]

Theoretically, the internal stack used by recursive functions must be
considered for space complexity.

On Mon, Jan 24, 2011 at 5:40 AM, juver++  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.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

[juver++]

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

[Algoose chase]

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++  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.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

[juver++]

@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

[nishaanth]

@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++  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.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

[sunny agrawal]

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  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.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

[juver++]

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

[Akash Agrawal]

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++  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.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-Linux Shell

[Neeraj]

*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  wrote:

> With perl installed:
>
>  find directory | xargs perl -pi -e 's/needle/replace/g'
>
> With sed installed:
>
>  #!/bin/bash
>
>  find directory > mirror
>  exec 3
>  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  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.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

[Nikhil Jindal]

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 wrote:

> 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  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|<
> --
> 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.
>
>

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 !!!!!!!

[Terence]

 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, Terence  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, Minotaurauswrote:

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 Wangwrote:

actually, there are many solutions, just pick up one from them...
On Tue, Sep 14, 2010 at 3:23 AM, Abhilasha jain
wrote:

how can u solve 3 variables using 2 equations?
On Tue, Sep 14, 2010 at 3:44 PM, Yan Wangwrote:

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, bittuwrote:

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

[Terence]

 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 > 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
.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@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 make confused !!!!!!!

[Terence]

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 > 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, Minotaurausmailto: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 Wangmailto: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
mailto:mail2abhila...@gmail.com>>  wrote:

how can u solve 3 variables using 2 equations?
On Tue, Sep 14, 2010 at 3:44 PM, Yan
Wangmailto: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,
bittumailto: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
.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.g