@above, "if initial position=final position or the final position was empty,then choose the next element(element next to the initial position) as current element"
How do you guarantee when you move to the next element, the next element is not already processed? Otherwise, you will double process on element. On Mon, Feb 7, 2011 at 9:36 AM, jalaj jaiswal <jalaj.jaiswa...@gmail.com>wrote: > algo in more detail :-o > > if the array is numbered from 0..(2n-1) > > i= initial position of int/char > f= final position of int/char > > if (i < (2n-1)/2) #for integer > f = i+i > else #for char > f = i - ((2n-1)-i) > > so iterate through the array in the following way > > choose first element > determine it final position > put the element in the final position > the next element to be processed is the original element in the final > position > if initial position=final position or the final position was empty,then > choose the next element(element next to the initial position) as current > element > > stop when last element has been processed. > > eg > 1234abcd > current = 1 > i = 0 > f = 0+0 = 0 > > i=f > so current= next element= 2 > i=1 > f=1+1=2 > put 2 in 2nd position > 1-24abcd > > current element = original element in 2nd position = 3 > for 3 > i = 2 > f=2+2=4 > > so put 3 in 4th position > 1-243bcd > current =a > i=4 > f=(i - ((2n-1)-i) = (4-(7-4)) = 1 > 1a243bcd > > now final position was empty > so next element = intital position +1 > = intitial position of a +1 = > 4 +1 = 5 > > current = b > processing in a similar way > > 1a2b3-cd > current = 4 > 1a2b3-4d > current = c > 1a2b3c4d > current = d > 1a2b3c4d > > processed last element so stop > > > > can't explain more better :-o > > > On Mon, Feb 7, 2011 at 10:59 PM, Manmeet Singh <mans.aus...@gmail.com>wrote: > >> thr is some error in algo >> >> >> On Mon, Feb 7, 2011 at 10:48 PM, abc abc <may.i.answ...@gmail.com> wrote: >> >>> I would like to have pseudo for this . >>> >>> On Mon, Feb 7, 2011 at 11:12 AM, jalaj jaiswal < >>> jalaj.jaiswa...@gmail.com> wrote: >>> >>>> A very common interview question >>>> >>>> let the array be from 0 to 2n-1 >>>> >>>> now, >>>> >>>> every element of array has its initial position and final position.. >>>> start from beginning >>>> if the elemnt you r processing is the first half of array then f=i+i; >>>> else f=2*i-(2n-1); >>>> replace the elemnt at final position with the initial element .. now >>>> next elemnt to process will be oroginal elemnt at final position >>>> if the final position is empty or the same position then process next >>>> element to the initial position. >>>> do until you process the last element. >>>> >>>> inplace with O(n). >>>> >>>> >>>> On Mon, Feb 7, 2011 at 8:32 AM, may.I.answer >>>> <may.i.answ...@gmail.com>wrote: >>>> >>>>> If [a1,a2,a3...,an,b1,b2...bn] is given input change this to >>>>> [a1,b1,a2,b2.....an,bn] >>>>> >>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "Algorithm Geeks" group. >>>>> To post to this group, send email to algogeeks@googlegroups.com. >>>>> To unsubscribe from 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. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from 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) > Software developer, Cisco Systems > > 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.
