Re: [algogeeks] MS QUESTION_LINKED LIST

[Dheeraj Sharma]

Correct me if am wrong.. i think we can use Stack as follows
node * minFun(node *head)
{

stack st;
return fun(head,st);
}
node * fun(node *ptr,stack &st)
{
if(ptr)
{
node *x=fun(ptr->next,st);
while(!st.empty() && (ptr->data)>(st.top()->data))
  st.pop();

if(!st.empty())
ptr->high=st.top();
st.push(ptr);
return (x?((ptr->data)<(x->data)?ptr:x):ptr);
}
return NULL;
}
On Sun, Mar 25, 2012 at 12:20 AM, atul anand wrote:

> after push(&s,next) move head also
> head=head->next;
>
>
> On Sun, Mar 25, 2012 at 12:10 AM, atul anand wrote:
>
>> @all : i am getting this right , i guess given a linked list ...you need
>> to point to next larger element.
>> so if input linked list is 7 3 5 1 5 9
>> then nextLarger of each node will point as follows:-
>>
>> 3->5
>> 1->5
>> 5->9
>> 7->9
>> 9->NULL;
>>
>> i have no idea why the linked list is modified using merge sort...
>> anywayzz if the expected output is similar to one i have mentioned above
>> there this woud work using stack .. complexity O(n) n=number of nodes.
>>
>> findLarger(node *head)
>> {
>> s1 s;
>> node *ele,*next;
>>
>> s.top=NULL;
>> push(&s,head);
>> head=head->next;
>> while(head!=NULL)
>> {
>> next->data=head->data;
>> if(isEmpty(&s))
>> {
>>   ele=pop(&s);
>>   while(ele->data < next->data)
>>   {
>>  ele->nextLarger=next;
>> if(isEmpty(&s)==0)
>> {
>>  break;
>> }
>>   ele=pop(&s);
>>   }
>>   if(ele->data > next->data)
>>   {
>>  push(&s,ele);
>>   }
>>
>> }
>>
>> push(&s,next);
>> }
>>
>> On Sat, Mar 24, 2012 at 12:50 AM, Atul Singh wrote:
>>
>>> Given a linked list with each node having two pointers : one pointing to
>>> next node & other to null;
>>> how will u point the second pointer to next larger no. and return the
>>> pointer to smallest node
>>>
>>>
>>>
>>> --
>>> ATul Singh | Final Year  | Computer Science & Engineering | NIT
>>> Jalandhar  | 9530739855 |
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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.
>



-- 
*Dheeraj Sharma*

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

[atul anand]

i guess it can be done by modifying solution on
http://www.geeksforgeeks.org/archives/8405
my prev soln was based on the same..
instead of adding value to the stack...add index of that element.
in below code , line in bold are added

void nextSmaller(int arr[],int n)
{
s1 s;
int i,next,ele;

s.top=-1;
push(&s,0);

for(i=1;i arr[next])
  {*
swap(arr,idx,i);*   // swap value at index ele
end i
   * next=idx;  // *current value is at
index idx* , *this is to track the current element*
*
if(isEmpty(&s)==0)
{
break;
 }
  idx=pop(&s);
  }
  if(arr[idx] < arr[next])
  {
push(&s,idx);
  }

}

push(&s,i);
}

}





On Sun, Mar 25, 2012 at 10:39 PM, algo bard  wrote:

> http://www.geeksforgeeks.org/archives/8405
>
> ^ Similar question.
>
>
> On Sun, Mar 25, 2012 at 5:19 PM, atul anand wrote:
>
>> wont work for all cases...ignore
>> i will post the algoonce i fix it
>> On 25 Mar 2012 17:06, "Amol Sharma"  wrote:
>>
>>> @atul : it would be better for all to understand if you write the algo
>>> instead of writing the code..
>>> --
>>>
>>>
>>> Amol Sharma
>>> Third Year Student
>>> Computer Science and Engineering
>>> MNNIT Allahabad
>>>   
>>> 
>>>
>>>
>>>
>>>
>>>
>>>
>>> On Sun, Mar 25, 2012 at 4:51 PM, atul anand wrote:
>>>
 @shady : yes i guess this is what question says:-
 so acc to this below algo work , i didnt execute it but i guess it will
 work

 void nextSmaller(int arr[],int n)
 {
 s1 s;
 int i,next,ele;

 s.top=-1;
 push(&s,0);

 for(i=1;i>>> {
 next=arr[i];
  if(isEmpty(&s))
 {
   ele=pop(&s);
   while(arr[ele] > next)
   {
  swap(arr,ele,i);
   next=arr[ele];
 if(isEmpty(&s)==0)
 {
 break;
  }
   ele=pop(&s);
   }
   if(ele > next)
   {
 push(&s,ele);
   }

 }

 push(&s,i);
  }

 }


 On Sun, Mar 25, 2012 at 4:36 PM, shady  wrote:

> @gene
> i think for  3 4 2 you need to start from left most element, and then
> make substitutions one by one.
> so it will be
> 3 4 2
> 2 4 3
> 2 3 4
>
>
> @all i googled a bit, and found that O(n) solution is possible for it,
> any idea ?
>
> On Sun, Mar 25, 2012 at 1:59 PM, Kartik Sachan <
> kartik.sac...@gmail.com> wrote:
>
>> +1 @saurabh...:P
>>
>> --
>> You received this message because you are subscribed to the Google
>> Groups "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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.
>

-- 
You received this message because you are subscribed to the Go

[algogeeks] Re: Two most distant element in tree

[Lucifer]

@above:

Special Case : it need *not* be always leaves

On Mar 26, 2:42 am, Lucifer  wrote:
> I think we can tweak the standard "find the height of the tree"
> program to get the result..
>
> As we know that the 2 extremes of the longest path are nothing but
> leaves. Hence, all we need to do is figure out is for which set of
> leaves would the path be maximum..
> [ Special Case : it need to be always leaves. For ex- consider a
> binary tree having all right children set to NULL. Here, the 2 nodes
> comprising the longest path would be the ("only")leaf node and the
> root node. ]
>
> Pseudocode:
> -
> *mPathLeftNode= NULL;
> *mPathRightNode = NULL;
> *maxHeightLeafNode = NULL;
> *maxPathLength = 0;
>
> // returns the height of the tree..
>
> int findMPath(node * root, node **mPathLeftNode, node
> **mPathRightNode, int *maxPathLength, node **maxHeightLeafNode)
> {
>      int leftHeight =0, rightHeight=0;
>      node *maxHeightLTLeafNode = NULL;
>      node *maxHeightRTLeafNode = NULL;
>
>      if( !root ) return 0;
>
>      leftHeight = findMPath(root-> left, mPathLeftNode,
> mPathRightNode, maxPathLength, &maxHeightLTLeafNode);
>      rightHeight = findMPath(root-> right, mPathLeftNode,
> mPathRightNode, maxPathLength, &maxHeightRTLeafNode);
>
>      if( ! leftHeight)
>           maxHeightLTLeafNode = root;
>      if( ! rightHeight)
>           maxHeightRTLeafNode = root;
>
>      if( *maxPathLength < 1 + leftHeight + rightHeight)
>      {
>           *maxPathLength = 1 + leftHeight + rightHeight;
>           *mPathLeftNode = maxHeightLTLeafNode;
>           *mPathRightNode = maxHeightRTLeafNode;
>      }
>
>      *maxHeightLeafNode =  (leftHeight >= rightHeight ?
> maxHeightLTLeafNode : maxHeightRTLeafNode);
>
>      return 1 + (leftHeight >= rightHeight ? leftHeight :
> rightHeight);
>
> }
>
> On Mar 25, 10:45 pm, Amol Sharma  wrote:
>
>
>
>
>
>
>
> > @kartikeyan : +1
>
> > yes...bfs/dfs from the leave node will work.
> > --
>
> > Amol Sharma
> > Third Year Student
> > Computer Science and Engineering
> > MNNIT Allahabad
> >  
> > 
>
> > On Sun, Mar 25, 2012 at 11:07 PM, karthikeyan muthu <
>
> > keyankarthi1...@gmail.com> wrote:
> > > u can keep track of the last node u visit in two variables for every path
> > > and update new variables with the optimal path's last visited 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.

[algogeeks] Re: [Directi] Two most distant element in tree

[Lucifer]

I think we can tweak the standard "find the height of the tree"
program to get the result..

As we know that the 2 extremes of the longest path are nothing but
leaves. Hence, all we need to do is figure out is for which set of
leaves would the path be maximum..
[ Special Case : it need to be always leaves. For ex- consider a
binary tree having all right children set to NULL. Here, the 2 nodes
comprising the longest path would be the ("only")leaf node and the
root node. ]

Pseudocode:
-
*mPathLeftNode= NULL;
*mPathRightNode = NULL;
*maxHeightLeafNode = NULL;
*maxPathLength = 0;

// returns the height of the tree..

int findMPath(node * root, node **mPathLeftNode, node
**mPathRightNode, int *maxPathLength, node **maxHeightLeafNode)
{
 int leftHeight =0, rightHeight=0;
 node *maxHeightLTLeafNode = NULL;
 node *maxHeightRTLeafNode = NULL;

 if( !root ) return 0;

 leftHeight = findMPath(root-> left, mPathLeftNode,
mPathRightNode, maxPathLength, &maxHeightLTLeafNode);
 rightHeight = findMPath(root-> right, mPathLeftNode,
mPathRightNode, maxPathLength, &maxHeightRTLeafNode);

 if( ! leftHeight)
  maxHeightLTLeafNode = root;
 if( ! rightHeight)
  maxHeightRTLeafNode = root;

 if( *maxPathLength < 1 + leftHeight + rightHeight)
 {
  *maxPathLength = 1 + leftHeight + rightHeight;
  *mPathLeftNode = maxHeightLTLeafNode;
  *mPathRightNode = maxHeightRTLeafNode;
 }

 *maxHeightLeafNode =  (leftHeight >= rightHeight ?
maxHeightLTLeafNode : maxHeightRTLeafNode);

 return 1 + (leftHeight >= rightHeight ? leftHeight :
rightHeight);

}
On Mar 25, 10:45 pm, Amol Sharma  wrote:
> @kartikeyan : +1
>
> yes...bfs/dfs from the leave node will work.
> --
>
> Amol Sharma
> Third Year Student
> Computer Science and Engineering
> MNNIT Allahabad
>  
> 
>
> On Sun, Mar 25, 2012 at 11:07 PM, karthikeyan muthu <
>
>
>
>
>
>
>
> keyankarthi1...@gmail.com> wrote:
> > u can keep track of the last node u visit in two variables for every path
> > and update new variables with the optimal path's last visited 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: Interview question

[algo bard]

Urm. It's probably not the same. We could find the maximum element in the
array and use the trivial approach till we reach the max_element. After
that, all we need to do is to shift all the elements right of max_element
to the left by 1 and place max_element at the end. But again..this isn't
O(n). :-P Worst case: O(n^2).

On Sun, Mar 25, 2012 at 10:44 PM, algo bard  wrote:

> http://www.geeksforgeeks.org/archives/8405
>
> ^ Similar Question.
>
> On Mar 25, 4:49 pm, atul anand  wrote:
> > wont work for all cases...ignore
> > i will post the algoonce i fix it
> > On 25 Mar 2012 17:06, "Amol Sharma"  wrote:
> >
> >
> >
> >
> >
> >
> >
> > > @atul : it would be better for all to understand if you write the algo
> > > instead of writing the code..
> > > --
> >
> > > Amol Sharma
> > > Third Year Student
> > > Computer Science and Engineering
> > > MNNIT Allahabad
> > >   <
> http://in.linkedin.com/pub/amol-sharma/21/79b/507><
> http://www.simplyamol.blogspot.com/>
> >
> > > On Sun, Mar 25, 2012 at 4:51 PM, atul anand  >wrote:
> >
> > >> @shady : yes i guess this is what question says:-
> > >> so acc to this below algo work , i didnt execute it but i guess it
> will
> > >> work
> >
> > >> void nextSmaller(int arr[],int n)
> > >> {
> > >> s1 s;
> > >> int i,next,ele;
> >
> > >> s.top=-1;
> > >> push(&s,0);
> >
> > >> for(i=1;i > >> {
> > >> next=arr[i];
> > >>  if(isEmpty(&s))
> > >> {
> > >>   ele=pop(&s);
> > >>   while(arr[ele] > next)
> > >>   {
> > >>  swap(arr,ele,i);
> > >>   next=arr[ele];
> > >> if(isEmpty(&s)==0)
> > >> {
> > >> break;
> > >>  }
> > >>   ele=pop(&s);
> > >>   }
> > >>   if(ele > next)
> > >>   {
> > >> push(&s,ele);
> > >>   }
> >
> > >> }
> >
> > >> push(&s,i);
> > >>  }
> >
> > >> }
> >
> > >> On Sun, Mar 25, 2012 at 4:36 PM, shady  wrote:
> >
> > >>> @gene
> > >>> i think for  3 4 2 you need to start from left most element, and then
> > >>> make substitutions one by one.
> > >>> so it will be
> > >>> 3 4 2
> > >>> 2 4 3
> > >>> 2 3 4
> >
> > >>> @all i googled a bit, and found that O(n) solution is possible for
> it,
> > >>> any idea ?
> >
> > >>> On Sun, Mar 25, 2012 at 1:59 PM, Kartik Sachan <
> kartik.sac...@gmail.com>wrote:
> >
> >  +1 @saurabh...:P
> >
> >  --
> >  You received this message because you are subscribed to the Google
> >  Groups "Algorithm Geeks" group.
> >  To post to this group, send email to algogeeks@googlegroups.com.
> >  To unsubscribe from 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] Two most distant nodes

[Amol Sharma]

question already in discussioncheck thread started by navin [directi
question]


no more discussion here.
-Thread
Closed--
--


Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad








On Sun, Mar 25, 2012 at 4:23 PM, Algo-Geek  wrote:

> In the below example , two most distant nodes are  ( h,k) or  ( h,j )
>   - a-
>-b-  - c-
> d - e-j k
>- f - g
>  h
> So  we have to find two nodes between whom , the distance is maximised.
> This boils down to finding the two nodes in the diameter of the tree. as
> the diameter is the longest path between two nodes in tree.
> How to do this.This is not just finding the diameter length.but the two
> nodes in the diameter
>
> --
> 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/-/JVD4-Y1eZ14J.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] [Directi] Two most distant element in tree

[Amol Sharma]

@kartikeyan : +1

yes...bfs/dfs from the leave node will work.
--


Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
 







On Sun, Mar 25, 2012 at 11:07 PM, karthikeyan muthu <
keyankarthi1...@gmail.com> wrote:

> u can keep track of the last node u visit in two variables for every path
> and update new variables with the optimal path's last visited 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] [Directi] Two most distant element in tree

[karthikeyan muthu]

the path we are looking for is surely between two leaf nodes.

start from the root and go to the deepest leaf node.. (dfs/bfs)

from that node traverse the entire tree to find the longest path that
exists (dfs/bfs)

u can keep track of the last node u visit in two variables for every path
and update new variables with the optimal path's last visited node ..

this way u get the two required nodes


On Sun, Mar 25, 2012 at 3:40 PM, Navin Kumar  wrote:

> How to find the two most distant nodes in a binary tree.
> Its not about calculating the diameter of  tree, but the two end nodes in
> the diameter of the tree.
> Optimal algorithm expected ..
>
> --
> 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/-/8pDy6hcBPOUJ.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Slang Decoder chatBot... give a try...

[Ravi Mohan]

Nice work yaari have added it .

Can you explain how do u make bolt.

On Sun, Mar 25, 2012 at 11:29 AM, amrit harry wrote:

> 'slangdeco...@gmail.com'
>



-- 
-
Thanks and Regards

Ravi Mohan



Technical Field Officer(Information Technology)
BAS- Advances Group,Dept of Information Technology,
Head Office,Canara Bank
14 M G Road ,Bangalore-561
Phone :-  +91 8553707621 ,
Email  :- ravimoha...@gmail.com | ravimo...@canarabank.com

*
'Human knowledge belongs to the World'*

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

[algo bard]

http://www.geeksforgeeks.org/archives/8405

^ Similar question.

On Sun, Mar 25, 2012 at 5:19 PM, atul anand  wrote:

> wont work for all cases...ignore
> i will post the algoonce i fix it
> On 25 Mar 2012 17:06, "Amol Sharma"  wrote:
>
>> @atul : it would be better for all to understand if you write the algo
>> instead of writing the code..
>> --
>>
>>
>> Amol Sharma
>> Third Year Student
>> Computer Science and Engineering
>> MNNIT Allahabad
>>   
>> 
>>
>>
>>
>>
>>
>>
>> On Sun, Mar 25, 2012 at 4:51 PM, atul anand wrote:
>>
>>> @shady : yes i guess this is what question says:-
>>> so acc to this below algo work , i didnt execute it but i guess it will
>>> work
>>>
>>> void nextSmaller(int arr[],int n)
>>> {
>>> s1 s;
>>> int i,next,ele;
>>>
>>> s.top=-1;
>>> push(&s,0);
>>>
>>> for(i=1;i>> {
>>> next=arr[i];
>>>  if(isEmpty(&s))
>>> {
>>>   ele=pop(&s);
>>>   while(arr[ele] > next)
>>>   {
>>>  swap(arr,ele,i);
>>>   next=arr[ele];
>>> if(isEmpty(&s)==0)
>>> {
>>> break;
>>>  }
>>>   ele=pop(&s);
>>>   }
>>>   if(ele > next)
>>>   {
>>> push(&s,ele);
>>>   }
>>>
>>> }
>>>
>>> push(&s,i);
>>>  }
>>>
>>> }
>>>
>>>
>>> On Sun, Mar 25, 2012 at 4:36 PM, shady  wrote:
>>>
 @gene
 i think for  3 4 2 you need to start from left most element, and then
 make substitutions one by one.
 so it will be
 3 4 2
 2 4 3
 2 3 4


 @all i googled a bit, and found that O(n) solution is possible for it,
 any idea ?

 On Sun, Mar 25, 2012 at 1:59 PM, Kartik Sachan >>> > wrote:

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

[algogeeks] Re: Interview question

[algo bard]

http://www.geeksforgeeks.org/archives/8405

^ Similar Question.

On Mar 25, 4:49 pm, atul anand  wrote:
> wont work for all cases...ignore
> i will post the algoonce i fix it
> On 25 Mar 2012 17:06, "Amol Sharma"  wrote:
>
>
>
>
>
>
>
> > @atul : it would be better for all to understand if you write the algo
> > instead of writing the code..
> > --
>
> > Amol Sharma
> > Third Year Student
> > Computer Science and Engineering
> > MNNIT Allahabad
> >   
> > 
>
> > On Sun, Mar 25, 2012 at 4:51 PM, atul anand wrote:
>
> >> @shady : yes i guess this is what question says:-
> >> so acc to this below algo work , i didnt execute it but i guess it will
> >> work
>
> >> void nextSmaller(int arr[],int n)
> >> {
> >> s1 s;
> >> int i,next,ele;
>
> >> s.top=-1;
> >> push(&s,0);
>
> >> for(i=1;i >> {
> >> next=arr[i];
> >>  if(isEmpty(&s))
> >> {
> >>       ele=pop(&s);
> >>       while(arr[ele] > next)
> >>       {
> >>  swap(arr,ele,i);
> >>                   next=arr[ele];
> >> if(isEmpty(&s)==0)
> >> {
> >> break;
> >>  }
> >>   ele=pop(&s);
> >>       }
> >>       if(ele > next)
> >>       {
> >> push(&s,ele);
> >>       }
>
> >> }
>
> >> push(&s,i);
> >>  }
>
> >> }
>
> >> On Sun, Mar 25, 2012 at 4:36 PM, shady  wrote:
>
> >>> @gene
> >>> i think for  3 4 2 you need to start from left most element, and then
> >>> make substitutions one by one.
> >>> so it will be
> >>> 3 4 2
> >>> 2 4 3
> >>> 2 3 4
>
> >>> @all i googled a bit, and found that O(n) solution is possible for it,
> >>> any idea ?
>
> >>> On Sun, Mar 25, 2012 at 1:59 PM, Kartik Sachan 
> >>> wrote:
>
>  +1 @saurabh...:P
>
>  --
>  You received this message because you are subscribed to the Google
>  Groups "Algorithm Geeks" group.
>  To post to this group, send email to algogeeks@googlegroups.com.
>  To unsubscribe from 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: Interview question

[atul anand]

wont work for all cases...ignore
i will post the algoonce i fix it
On 25 Mar 2012 17:06, "Amol Sharma"  wrote:

> @atul : it would be better for all to understand if you write the algo
> instead of writing the code..
> --
>
>
> Amol Sharma
> Third Year Student
> Computer Science and Engineering
> MNNIT Allahabad
>   
> 
>
>
>
>
>
>
> On Sun, Mar 25, 2012 at 4:51 PM, atul anand wrote:
>
>> @shady : yes i guess this is what question says:-
>> so acc to this below algo work , i didnt execute it but i guess it will
>> work
>>
>> void nextSmaller(int arr[],int n)
>> {
>> s1 s;
>> int i,next,ele;
>>
>> s.top=-1;
>> push(&s,0);
>>
>> for(i=1;i> {
>> next=arr[i];
>>  if(isEmpty(&s))
>> {
>>   ele=pop(&s);
>>   while(arr[ele] > next)
>>   {
>>  swap(arr,ele,i);
>>   next=arr[ele];
>> if(isEmpty(&s)==0)
>> {
>> break;
>>  }
>>   ele=pop(&s);
>>   }
>>   if(ele > next)
>>   {
>> push(&s,ele);
>>   }
>>
>> }
>>
>> push(&s,i);
>>  }
>>
>> }
>>
>>
>> On Sun, Mar 25, 2012 at 4:36 PM, shady  wrote:
>>
>>> @gene
>>> i think for  3 4 2 you need to start from left most element, and then
>>> make substitutions one by one.
>>> so it will be
>>> 3 4 2
>>> 2 4 3
>>> 2 3 4
>>>
>>>
>>> @all i googled a bit, and found that O(n) solution is possible for it,
>>> any idea ?
>>>
>>> On Sun, Mar 25, 2012 at 1:59 PM, Kartik Sachan 
>>> wrote:
>>>
 +1 @saurabh...:P

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

[atul anand]

@shady : yes i guess this is what question says:-
so acc to this below algo work , i didnt execute it but i guess it will work

void nextSmaller(int arr[],int n)
{
s1 s;
int i,next,ele;

s.top=-1;
push(&s,0);

for(i=1;i next)
  {
 swap(arr,ele,i);
  next=arr[ele];
if(isEmpty(&s)==0)
{
break;
}
  ele=pop(&s);
  }
  if(ele > next)
  {
push(&s,ele);
  }

}

push(&s,i);
}

}


On Sun, Mar 25, 2012 at 4:36 PM, shady  wrote:

> @gene
> i think for  3 4 2 you need to start from left most element, and then make
> substitutions one by one.
> so it will be
> 3 4 2
> 2 4 3
> 2 3 4
>
>
> @all i googled a bit, and found that O(n) solution is possible for it, any
> idea ?
>
> On Sun, Mar 25, 2012 at 1:59 PM, Kartik Sachan wrote:
>
>> +1 @saurabh...:P
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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: Run Length Decoding... inplace

[atul anand]

@ Kalyanasundaram : no need to check you algo , bcozz i can clearly see you
are not saving output to the bufffer , you are just printing it to stdout .
please read prev comment for better understanding the problem,

On Sun, Mar 25, 2012 at 11:54 AM, Kalyanasundaram wrote:

>scanf("%s",a);
>l=strlen(a);
>for(i=l-1;i>=0;i-=2)
> {
>  while((a[i]--)-'0')
> printf("%c",a[i-1]);
> }
>
> This works fine when the count of characters is a <10 .Also no extra space
> used.If you find any mistake, please do correct me!
>
>
> On Sun, Mar 25, 2012 at 10:18 AM, SAMM  wrote:
>
>> In this question is it mandatory to use array here .Because the output
>> and the space were the string is stored is required ..
>>
>> I was thinking of using LL approach ..
>>
>> Need four pointers to keep track of the positions .
>>
>> begin -> store the beginning of the LL initially containing the pointer
>> to he 1st node "a1b2c3d4".
>> end -> store the end node of the input string .
>> outputbegin -> store the position where the output index begin .. It will
>> be appended to the next node of the input string .
>> outputend  ->store the end node of the LL.
>>
>> begin --> a 1 b 2 c 3 d 4(<-end) (outputbegin->) NULL  <-(outputend)
>>
>> Delete d4 we hav now:-
>> begin --> a 1 b 2 c 3 (<-end) (outputbegin->) d d d d  <-(outputend)
>>
>> Take the character and corresponding value from the end index, change the
>> end pointer to '3' on the left of "d4" , delete both nodes of "d4" and
>> append it characters at the end .. All u have to do is remove and append ,
>> no extra memory greater than length(output) is used here ..
>>
>> As Nothing has been mentioned abt printing the output in the question ,
>> we will keep printing the character on the console while  appendiing the
>> character in the LL ).
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
>
>
> *Kalyan
>
> Dont take life seriously as it isnt Permanent!
>
> *
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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: Interview question

[shady]

@gene
i think for  3 4 2 you need to start from left most element, and then make
substitutions one by one.
so it will be
3 4 2
2 4 3
2 3 4


@all i googled a bit, and found that O(n) solution is possible for it, any
idea ?

On Sun, Mar 25, 2012 at 1:59 PM, Kartik Sachan wrote:

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

[atul anand]

@raghavan : please read previous post...given m/m is fixed which
is sufficient enough to accommodate  input.
so if input string is a1b1c4 then max buffer available to us is 1+1+4=7 ,
7+1=8(+1 is for '\0' at the end) but 8 is also length of the input.

so to make your algo work first you need to further squeeze the input
before starting expanding.

On Sun, Mar 25, 2012 at 1:02 PM, raghavan M
wrote:

> Atul
> '1' is a special case for this RLE.Instead of copying back you have to
> copy front
>
> a1b2c1d4e5
> Step 1: expand e 5 times a1b2c1d4e
>  Step 2:  expand 'd' 4 times.before that shift 5e's by 4 right side.
>   a1b2c1ee
>  step 3: here since 1 is a special case shift 'ee' left side by 1
> 
>
>
>
>
>   --
> *From:* atul anand 
> *To:* algogeeks@googlegroups.com
> *Sent:* Saturday, 24 March 2012 4:32 PM
>
> *Subject:* Re: [algogeeks] Re: Run Length Decoding... inplace
>
> @raghavan: wont work...take input as a1b1c4...it willl fail.
> read prev comment ...
> On 24 Mar 2012 14:23, "raghavan M"  wrote:
>
> For sake of in-place
>
> Instead of doing it from the "Start" we can do it from the "end" in which
> case, the data precision wont be lost.
>
> Eg:
> a1b2c3d4
> start with d4
> a1b2c3
> now in next loop
> a1b2ccc- here we have to do a)reallocation and b)copy the last 3 
> from next  one it is more swaps :D  i hope it can be optimised by some
> way.
>
> not sure though.
>
>
>   --
> *From:* Ashish Goel 
> *To:* algogeeks@googlegroups.com
> *Sent:* Saturday, 24 March 2012 1:19 AM
> *Subject:* Re: [algogeeks] Re: Run Length Decoding... inplace
>
> Atul
>
>
>
> a10 looks good however, when there are multiple such cases within the same
> string, it is is a problem because i would not know if the char is the real
> character of the string or part ofthe length
>
> eg
>
> a10115
> is a valid string and can be interpreted as a01 or a 10115 times.
> RLE is the first case not the second case which is pretty easy to take
> care.
>
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
> On Fri, Mar 23, 2012 at 11:39 PM, atul anand wrote:
>
> @utkarsh: +1
> On 23 Mar 2012 18:38, "UTKARSH SRIVASTAV"  wrote:
>
> I am considering that I am having total size of buffer that is maximum of
> output or input buffer and input is given in the buffer.
>
> My first approach of the solution was that
> 1. first traverse whole array and then count total number of characters
> that will be present in whole array. O(n)
> 2. fill the output array from rightmost side and start filling it until
> you reach 0th index. O(n)
>
> But it failed on this test case a1b1c4 here I could lost data b1 once I
> start filling character from right side.It faile because of characters
> whose count is 1.
>
> So I think just a change in algo will give me correct answer.
> 1. first traverse whole array and then count total number of characters
> that will be present in whole array and in case if the character count is 1
> place '\0' in place of 1. O(n)
> 2. imagining \0 as space .convert this problem to removing white space
> from strings  and compress it . Again can be done in O(n).
> 3. fill the output array from rightmost side and start filling it until
> you reach 0th index. O(n)
>
> Please correct me if I am wrong.
>
>
>
> On Thu, Mar 22, 2012 at 9:13 AM, atul anand wrote:
>
> @Ashish : a10 will be represented as aa . Here '1' and '0' are
> character type in the given input , so you need to convert it into numeric
> 10.
>
>
> On Thu, Mar 22, 2012 at 1:09 AM, Ashish Goel  wrote:
>
> Gene, Atul
>
> How would a string of say 257 or say 10 times a would be represented, will
> it be a10 or a
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
> On Wed, Mar 21, 2012 at 2:04 PM, atul anand wrote:
>
> wasnt able to come up with an algo which would satisfy all the cases input
> like a1b1c4 here output length is equal to input length . till now i dont
> knw how to handle these type of input. :( :(
>
> On Wed, Mar 21, 2012 at 10:02 AM, atul anand wrote:
>
> @Gene : yes you are right , i misunderstood the problem . so m/m available
> is just enough to hold the output.
> thanks for correcting ... that would make this ques little interesting :)
> :)...i guess my first posted code can be modified to meet the requirement.
> i will post the updated code.
>
> On Tue, Mar 20, 2012 at 5:45 PM, Gene  wrote:
>
> I don't think you're seeing the requirement completely.  The problem
> promises only that the output buffer will be big enough to hold the
> output.  You have made it huge.  I tried your code on an input of
>
> a1b1c6
>
> with the required output space of 8 characters (plus 1 for the C null
> character), and it printed
>
> cc
>
> and stopped.
>
> Last night I realized there is another approach that will work in all
> cases, so I deleted my post.  

[algogeeks] Two most distant nodes

[Algo-Geek]

In the below example , two most distant nodes are  ( h,k) or  ( h,j )
  - a-
   -b-  - c-
d - e-j k
   - f - g
 h
So  we have to find two nodes between whom , the distance is maximised.
This boils down to finding the two nodes in the diameter of the tree. as 
the diameter is the longest path between two nodes in tree.
How to do this.This is not just finding the diameter length.but the two 
nodes in the diameter

-- 
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/-/JVD4-Y1eZ14J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] [Directi] Two most distant element in tree

[Navin Kumar]

How to find the two most distant nodes in a binary tree. 
Its not about calculating the diameter of  tree, but the two end nodes in 
the diameter of the tree.
Optimal algorithm expected ..

-- 
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/-/8pDy6hcBPOUJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Interview question

[Kartik Sachan]

+1 @saurabh...:P

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

[Kalyanasundaram]

   scanf("%s",a);
   l=strlen(a);
   for(i=l-1;i>=0;i-=2)
{
 while((a[i]--)-'0')
printf("%c",a[i-1]);
}

This works fine when the count of characters is a <10 .Also no extra space
used.If you find any mistake, please do correct me!


On Sun, Mar 25, 2012 at 10:18 AM, SAMM  wrote:

> In this question is it mandatory to use array here .Because the output and
> the space were the string is stored is required ..
>
> I was thinking of using LL approach ..
>
> Need four pointers to keep track of the positions .
>
> begin -> store the beginning of the LL initially containing the pointer to
> he 1st node "a1b2c3d4".
> end -> store the end node of the input string .
> outputbegin -> store the position where the output index begin .. It will
> be appended to the next node of the input string .
> outputend  ->store the end node of the LL.
>
> begin --> a 1 b 2 c 3 d 4(<-end) (outputbegin->) NULL  <-(outputend)
>
> Delete d4 we hav now:-
> begin --> a 1 b 2 c 3 (<-end) (outputbegin->) d d d d  <-(outputend)
>
> Take the character and corresponding value from the end index, change the
> end pointer to '3' on the left of "d4" , delete both nodes of "d4" and
> append it characters at the end .. All u have to do is remove and append ,
> no extra memory greater than length(output) is used here ..
>
> As Nothing has been mentioned abt printing the output in the question , we
> will keep printing the character on the console while  appendiing the
> character in the LL ).
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 


*Kalyan

Dont take life seriously as it isnt Permanent!

*

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

[raghavan M]

Atul
'1' is a special case for this RLE.Instead of copying back you have to copy 
front

a1b2c1d4e5
Step 1: expand e 5 times a1b2c1d4e
 Step 2:  expand 'd' 4 times.before that shift 5e's by 4 right side.
 a1b2c1ee
 step 3: here since 1 is a special case shift 'ee' left side by 1 







 From: atul anand 
To: algogeeks@googlegroups.com 
Sent: Saturday, 24 March 2012 4:32 PM
Subject: Re: [algogeeks] Re: Run Length Decoding... inplace
 

@raghavan: wont work...take input as a1b1c4...it willl fail.
read prev comment ...
On 24 Mar 2012 14:23, "raghavan M"  wrote:

For sake of in-place
>
>
>Instead of doing it from the "Start" we can do it from the "end" in which 
>case, the data precision wont be lost.
>
>
>Eg:
>a1b2c3d4
>start with d4
>a1b2c3
>now in next loop
>a1b2ccc- here we have to do a)reallocation and b)copy the last 3  
>
>from next  one it is more swaps :D  i hope it can be optimised by some way. 
>
>
>
>not sure though.
>
>
>
>
>
>
>
> From: Ashish Goel 
>To: algogeeks@googlegroups.com 
>Sent: Saturday, 24 March 2012 1:19 AM
>Subject: Re: [algogeeks] Re: Run Length Decoding... inplace
> 
>
>Atul
>
>
>
>
>
>
>a10 looks good however, when there are multiple such cases within the same 
>string, it is is a problem because i would not know if the char is the real 
>character of the string or part ofthe length
>
>
>eg
>
>
>a10115
>is a valid string and can be interpreted as a01 or a 10115 times.
>RLE is the first case not the second case which is pretty easy to take care.
>
>
>
>
>Best Regards
>Ashish Goel
>"Think positive and find fuel in failure"
>+919985813081
>+919966006652
>
>
>
>On Fri, Mar 23, 2012 at 11:39 PM, atul anand  wrote:
>
>@utkarsh: +1
>>On 23 Mar 2012 18:38, "UTKARSH SRIVASTAV"  wrote:
>>
>>I am considering that I am having total size of buffer that is maximum of 
>>output or input buffer and input is given in the buffer.
>>>
>>>My first approach of the solution was that 
>>>1. first traverse whole array and then count total number of characters that 
>>>will be present in whole array. O(n)
>>>2. fill the output array from rightmost side and start filling it until you 
>>>reach 0th index. O(n)
>>>
>>>But it failed on this test case a1b1c4 here I could lost data b1 once I 
>>>start filling character from right side.It faile because of characters whose 
>>>count is 1.
>>>
>>>So I think just a change in algo will give me correct answer. 
>>>1. first traverse whole array and then count total number of characters that 
>>>will be present in whole array and in case if the character count is 1 place 
>>>'\0' in place of 1. O(n)
>>>2. imagining \0 as space .convert this problem to removing white space from 
>>>strings  and compress it . Again can be done in O(n).
>>>3. fill the output array from rightmost side and start filling it until you 
>>>reach 0th index. O(n)
>>>
>>>Please correct me if I am wrong.
>>>
>>>
>>>
>>>
>>>On Thu, Mar 22, 2012 at 9:13 AM, atul anand  wrote:
>>>
>>>@Ashish : a10 will be represented as aa . Here '1' and '0' are 
>>>character type in the given input , so you need to convert it into numeric 
>>>10.



On Thu, Mar 22, 2012 at 1:09 AM, Ashish Goel  wrote:

Gene, Atul
>
>How would a string of say 257 or say 10 times a would be represented, will 
>it be a10 or a
>
>Best Regards
>Ashish Goel
>"Think positive and find fuel in failure"
>+919985813081
>+919966006652
>
>
>
>On Wed, Mar 21, 2012 at 2:04 PM, atul anand  
>wrote:
>
>wasnt able to come up with an algo which would satisfy all the cases input 
>like a1b1c4 here output length is equal to input length . till now i dont 
>knw how to handle these type of input. :( :( 
>>
>>
>>
>>On Wed, Mar 21, 2012 at 10:02 AM, atul anand  
>>wrote:
>>
>>@Gene : yes you are right , i misunderstood the problem . so m/m 
>>available is just enough to hold the output.
>>>thanks for correcting ... that would make this ques little interesting 
>>>:) :)...i guess my first posted code can be modified to meet the 
>>>requirement.
>>>i will post the updated code.   
>>>
>>>
>>>
>>>On Tue, Mar 20, 2012 at 5:45 PM, Gene  wrote:
>>>
>>>I don't think you're seeing the requirement completely.  The problem
promises only that the output buffer will be big enough to hold the
output.  You have made it huge.  I tried your code on an input of

a1b1c6

with the required output space of 8 characters (plus 1 for the C null
character), and it printed

cc

and stopped.

Last night I realized there is another approach that will work in all
cases, so I deleted my post.  I guess it wasn't deleted on the server
in your part of the world.

You all can