Re: [algogeeks] MS Question -Reverse a Linked List in size of 2

[Ankur Garg]

Well for odd cases its lile this

1 ->2->3->4->5

4->5->2->3->1

Also u have to do this in single pass..U can use recursion though


On Tue, Jan 24, 2012 at 12:18 AM, Arun Vishwanathan
wrote:

> node *ptr =head;
>
> //function call is reverse(head,NULL)
>
> void reverse(node *ptr, node *follow)
> {
>if(ptr->next!=NULL && ptr->next->next!=NULL)
>reverse(ptr->next->next,ptr);
>   else
>   if(ptr->next!=NULL && ptr->next->next==NULL)
> {
>   ptr->next->next=follow;
>   head=ptr;
> }
>   ptr->next->next=follow;
>   if(follow!=NULL)
>   follow->next->next=NULL;
> }
>
> @ankur: if odd number of nodes then maybe just ask interviewer how he
> wants it to be and try including that case ;)
>
>
> }
>
> On Mon, Jan 23, 2012 at 10:32 AM, Ankur Garg  wrote:
>
>> wat if u have odd no of nodes
>>
>>
>>
>> On Tue, Jan 24, 2012 at 12:00 AM, atul anand wrote:
>>
>>> one simple way would be using stacks.
>>> push node,node->next;
>>> then pop() , and reversing the pointers.
>>>
>>> On Mon, Jan 23, 2012 at 11:46 PM, Ankur Garg wrote:
>>>
>>>> Say LL is
>>>>
>>>> 1->2->3->4->5->6->7->8
>>>>
>>>> Then u need to return
>>>>
>>>> 7->8->5->6->3->4->1->2
>>>>
>>>> U cant swap the values U have to rearrange the ptr...
>>>>
>>>>
>>>>  --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from 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.
>>
>
>
>
> --
>  "People often say that motivation doesn't last. Well, neither does
> bathing - that's why we recommend it daily."
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] MS Question -Reverse a Linked List in size of 2

[Ankur Garg]

wat if u have odd no of nodes



On Tue, Jan 24, 2012 at 12:00 AM, atul anand wrote:

> one simple way would be using stacks.
> push node,node->next;
> then pop() , and reversing the pointers.
>
> On Mon, Jan 23, 2012 at 11:46 PM, Ankur Garg  wrote:
>
>> Say LL is
>>
>> 1->2->3->4->5->6->7->8
>>
>> Then u need to return
>>
>> 7->8->5->6->3->4->1->2
>>
>> U cant swap the values U have to rearrange the ptr...
>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] MS Question -Reverse a Linked List in size of 2

[Ankur Garg]

Say LL is

1->2->3->4->5->6->7->8

Then u need to return

7->8->5->6->3->4->1->2

U cant swap the values U have to rearrange the ptr...

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

[Ankur Garg]

Hello

I was going through this link

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

Wonder what is the time complexity for this..?Can anyone explain >

Regards
Ankur

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

[Ankur Garg]

XOR Linked Lists

On Sat, Jan 14, 2012 at 7:06 PM, Ashish Goel  wrote:

> design a linked list that has only one pointer per node yet can be
> traversed in forward or reverse direction.
>
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] MS Question

[Ankur Garg]

@Himanshu

Nice idea..that shud do..but how do we code that ?

regards
Ankur

On Sat, Jan 14, 2012 at 2:23 PM, payal gupta  wrote:

> @himanshu thnx..:)
>
> Regards,
> PAYAL GUPTA,
> 3rd YR ,CSE,
> NIT-BHOPAL.
>
>
> On Fri, Jan 13, 2012 at 9:42 PM, Himanshu Neema <
> potential.himansh...@gmail.com> wrote:
>
>> Let a color below represent a single character in UTF-8 encoding ,
>> which means that each color can span multiple bytes , In example below I
>> denote one byte by one english character . i.e.
>> 'a' or 'b' or 'c'  ,etc.  below takes one byte :
>>
>> Let the string is :
>> x abc def gh ij klmn
>> now to reverse this UTF-8 encoded string in place in two steps :
>> 1) reverse bytes of a multibyte character in place ,
>> after this step the string will look like :
>> x cba fed hg ji nmlk
>> 2) Now apply a normal string reversal algo , i.e , to swap first byte
>> with last byte , swap second byte to second last byte .. and so on ...
>> after this step the string will look like :
>> klmn ij gh def abc x
>>
>> And look we have reversed an UTF-8 encoded string in place :)
>>
>>
>>
>>
>> On Fri, Jan 13, 2012 at 11:13 AM, Supraja Jayakumar <
>> suprajasank...@gmail.com> wrote:
>>
>>> Hi
>>>
>>> Normal string will not work I think. Because it is avriable length
>>> encoding scheme.
>>>
>>> On Fri, Jan 13, 2012 at 11:11 AM, b.kisha...@gmail.com <
>>> b.kisha...@gmail.com> wrote:
>>>
>>>> Is there anything called in-place reversal ??
>>>> UTF-8 is only encoding similar to ASCII but with a huge charecter set.
>>>> So normal string reversal would work fine..
>>>>
>>>>
>>>>
>>>> On Thu, Jan 12, 2012 at 2:02 AM, Ankur Garg wrote:
>>>>
>>>>> How to do this
>>>>>
>>>>> Write a function to reverse a UTF-8 encoded string in-place ??
>>>>>
>>>>>
>>>>>
>>>>>  --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>> To unsubscribe from 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.
>>>>
>>>
>>>
>>>
>>> --
>>> U
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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] MS Question

[Ankur Garg]

How to do this

Write a function to reverse a UTF-8 encoded string in-place ??

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

[Ankur Garg]

@Lucifer

I am not getting how u r working with heapifying each time ..

Initially the array is such that minimum value is ay (0,0) and and max at
index (m-1,n-1)

Now when u swap a value

Then u heapify i.e. make the prior arrangement again but that in turn will
lead to few swaps and so on...(Recursive)

Do you think it will be possible this way ?

Please correct me in case I got things wrong here

regards
Ankur




On Wed, Jan 11, 2012 at 5:07 PM, atul anand  wrote:

> i have little doubt in complexity of proposed algo..
> aren't we including complexity of heapifying each time. ??
>
>
>
> On Wed, Jan 11, 2012 at 2:57 PM, Lucifer  wrote:
>
>> @dipit ..
>>
>> Yup you are correct..
>>
>> Say, no of rows = M and no. of cols = N,
>> Time complexity = sum over all i (1 to M} { N*(M+N-i) }
>> =  M * N * (M + 2N - 1) /2
>>
>>
>>
>> On Jan 11, 2:19 pm, Dipit Grover  wrote:
>> > @Lucifer :  I came up with a similar algorithm as yours but I dont
>> > understand your complexity analysis : " sum over all i (1 to M} {
>> i*(M+N-i)} " .
>> >
>> > Shouldnt it be " M * sum over all i(1 to N) {(M+N-i)}  " ? M= no of
>> > columns, N= no of rows . Since we always have the min element at the 0th
>> > column of the next row for each element of the current row.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] sort 2D array

[Ankur Garg]

If we use K merge I think the time complexity would be nm lognm

I think we must try doing in O(m*n)

On Wed, Jan 11, 2012 at 1:54 PM, Ankur Garg  wrote:

> @Shady Rows are already sorted ...
>
>
> On Wed, Jan 11, 2012 at 1:53 PM, shady  wrote:
>
>> ^^ true, sort the rows and then a K-way merge.
>>
>>
>> On Wed, Jan 11, 2012 at 1:00 PM, Sanjay Rajpal wrote:
>>
>>> I guess sort the array such that elements are sorted finally in such a
>>> way that if we print them row by row, the result is a sorted array.
>>>
>>> K-way merge can be useful.
>>> *
>>> Sanjay Kumar
>>> B.Tech Final Year
>>> Department of Computer Engineering
>>> National Institute of Technology Kurukshetra
>>> Kurukshetra - 136119
>>> Haryana, India
>>> Contact: +91-8053566286
>>> *
>>>
>>>
>>>
>>> On Tue, Jan 10, 2012 at 11:28 PM, prakash y wrote:
>>>
>>>> "sort the whole matrix in ascending array" means?
>>>> can you please explain ?
>>>>
>>>>
>>>> On Wed, Jan 11, 2012 at 12:53 PM, atul anand 
>>>> wrote:
>>>>
>>>>> Given 2D array.
>>>>>
>>>>> The rows are sorted in ascending order and the colums are sorted in
>>>>> ascending order.
>>>>>
>>>>> We have to sort the whole matrix in ascending array.
>>>>>
>>>>> We cannot use 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] sort 2D array

[Ankur Garg]

@Shady Rows are already sorted ...

On Wed, Jan 11, 2012 at 1:53 PM, shady  wrote:

> ^^ true, sort the rows and then a K-way merge.
>
>
> On Wed, Jan 11, 2012 at 1:00 PM, Sanjay Rajpal wrote:
>
>> I guess sort the array such that elements are sorted finally in such a
>> way that if we print them row by row, the result is a sorted array.
>>
>> K-way merge can be useful.
>> *
>> Sanjay Kumar
>> B.Tech Final Year
>> Department of Computer Engineering
>> National Institute of Technology Kurukshetra
>> Kurukshetra - 136119
>> Haryana, India
>> Contact: +91-8053566286
>> *
>>
>>
>>
>> On Tue, Jan 10, 2012 at 11:28 PM, prakash y wrote:
>>
>>> "sort the whole matrix in ascending array" means?
>>> can you please explain ?
>>>
>>>
>>> On Wed, Jan 11, 2012 at 12:53 PM, atul anand wrote:
>>>
 Given 2D array.

 The rows are sorted in ascending order and the colums are sorted in
 ascending order.

 We have to sort the whole matrix in ascending array.

 We cannot use 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: finding subarray

[Ankur Garg]

I think this wont work for cases with negetive nos

Ex

-2,8,-6

On Tue, Jan 10, 2012 at 6:51 AM, sravanreddy001 wrote:

>
> solution at this link:
> http://ideone.com/ifVIv
>
> for every position, (iteration)
> maitain left, right for the sums,
> keep adding elements towards the begenning to left, and towards the end to
> right, (based on the conditions in the code)
>
> Complexity: outer forloop : O(n)
> inner while loop O(n)
> total O(n^2) and O(1) space.
>
> its currently printing all the position, & center is included to the left
> side,
>
> Left : 3, Right: 9, Center: 6
> this reads as.. sum(elements at 3,4,5,6) == sum(elements at 7,8,9)
>
> let me know if it needs more explanantion.
>
>
>
>
> for(int i=0;i int left=0,right=0;
> int p1 = i;
> int p2 = i+1;
> left = left + a[p1];
> right = right + a[p2];
> while(p1>=0 && p2< len){
> if( left == right){
> printf("Left : %d, Right: %d, Center: %d 
> \n",p1,p2,i);
> break;
> //return 0;
> }
> else if(left > right && p2 < len-1){
> p2++;
> right = right+ a[p2];
> }
> else if(left < right && p1 > 0){
> p1--;
> left = left + a[p1];
> }
> else{
> //printf("Left : %d, Right: %d, Center: %d 
> \n",p1,p2,i);
> //printf("Not Possible\n");
> break;
> //return 0;
> }
> }
>
> }
>
>
>  --
> 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/-/GoJEA73v8dcJ.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] MS Q

[Ankur Garg]

Can you give an example

Say  matrix is

1 1 0 0
1 1 0 0
0 0 1 1

Has it got 3 islands i.e 1-1 be in same row or they can be column wise also
i.e. 5



On Tue, Jan 10, 2012 at 7:09 AM, Ashish Goel  wrote:

> there is a matrix of 1 and 0
> 1 is a island and 0 is water
> 1-1 together makes one island
> calculate total no of islands
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] finding subarray

[Ankur Garg]

@Priyanka ...Do the elements of the subarray need to be continuous ..The
example considers it continuous but still just for clarity ?

On Tue, Jan 10, 2012 at 12:50 AM, surender sanke wrote:

> using extra space of O(n) we can do it in O(n^2)
> take an array for storing cumulative sums from index i till 0,
> then from i+1 till n-1 find summing each array value find whether it
> exists in array.
> if its so display indexes
> eg
> Array: 2,2,13,4,7,3,8,12,9,1,5
> i = 3   ^
> temp array:  4, 17, 19, 21
> finding for cumulative sums from i+1 till i<=(any of values in temp array)
> i = 6   ^
> temp array:  8, 11, 18, 22
> finding for cumulative sums from i+1 till i<=(any of values in temp array)
> found values from i+1 till i+3
> Repeating for every i,
>
> surender
>
>
> On Mon, Jan 9, 2012 at 11:22 PM, priyanka jaggi 
> wrote:
>
>> Given an array (length n), we need to find the subarray (length k) such
>> that the sum of the first j elements of the subarray equals the sum of the
>> remaining (k-j) elements of the subarray.
>> For e.g.
>> Array: 2,2,13,4,7,3,8,12,9,1,5
>> Output: 4,7,3,8,12,9,1 [4+7+3+8=12+9+1]
>> Could this be done with a complexity better than O(n^3)
>> k is not given .
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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: check Similar array

[Ankur Garg]

sorry it shud be
sum of squares and xor and sumof elements

I think this shud work

Regards
Ankur



On Wed, Jan 4, 2012 at 9:52 PM, atul anand  wrote:

> @ Karthikeyan :
>
> sum of cubes fails:-
>
> arr1={2,3,0,-3} =   4
> arr2={1,1,1,1}  = 4
>
> On Wed, Jan 4, 2012 at 6:53 PM, Karthikeyan V.B wrote:
>
>> Hi,
>>
>> Consider, arr1={1,2,3}  and arr2={-1,-2,-3}
>>
>> using sum of squares method sum(arr1) = 14 ans sum(arr2) = 14 (since
>> square of 1 and -1 is 1)
>>
>> so it won work with this case
>>
>> 1.better take the square and negate it before adding
>> or
>> 2.take sum of cubes
>>
>> pls correct me if i'm wrong
>>
>> Regards,
>> Karthikeyan
>> PSG TECH
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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: check Similar array

[Ankur Garg]

What if we check these 2 conditions

XOR and sum of elements  and sizeof array same

I cudnt find any counter example

Regards
Ankur

On Wed, Jan 4, 2012 at 6:53 PM, Karthikeyan V.B  wrote:

> Hi,
>
> Consider, arr1={1,2,3}  and arr2={-1,-2,-3}
>
> using sum of squares method sum(arr1) = 14 ans sum(arr2) = 14 (since
> square of 1 and -1 is 1)
>
> so it won work with this case
>
> 1.better take the square and negate it before adding
> or
> 2.take sum of cubes
>
> pls correct me if i'm wrong
>
> Regards,
> Karthikeyan
> PSG TECH
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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: Longest sequence of numbers with atmost diff K

[Ankur Garg]

@Lucifer

I checked again and saw a few flaws in my code . Please ignore my prev post
.. :P

1) I am always comparing with q.front()  and taking the diff but I should
also do the same with q.back() as it might contain values which have diff
>k . So yes , this is a bug

For this as you rightly pointed out we also need to compare with q.back()

So I modified my code accordingly

for(i=1;ik || abs(a[index.back()]-a[i])>k ){
   //binary_search(a,index,0,index.size()-1,i);
  s=index.size();
  cout<k))
  index.pop_front();
  while( (!index.empty()) && (abs(a[index.back()]-a[i])>k))
  index.pop_back();
   }

For the second part that you said , yes potentially if we use queue.size()
we can miss out on continuous part ..

Thanks for pointing these out


Regards
Ankur

On Tue, Jan 3, 2012 at 4:06 AM, Ankur Garg  wrote:

> @Lucifer
>
> I checked with my code
>
> The answer is coming out to be 4 ..So in this case its passing
>
> Also the queue is containing the indexes in order of increasing values
> ..so for curr min we need to only check the front of the queue.
>
> Also I remove the elements of the queue till all the diff of elements in
> the queue  with the current element is <=k
>
>
> If queue is containing elements
> say
>  i j k l m
>
> Then yesit is possible that i < j and i > k...  but a[i] is always
> less than a[j] and a[k]...
>
> So queue will always contain the correct elements I guess..
>
> Like I said I have not done its testing with many cases .. But for this
> case the answer is coming out correct
>
> One correction to the code though
> it should be
>  if(index.empty())
>index.push_back(i);
>   else
>   binary_search(a,index,0,index.size()-1,i);
>
> I missed the else part here..
>
> In case you find anyother case it would be great .. I am sharing the
> source codes .cpp file
>
> If u find any case thats missing ..please tell me and I will also update
> in case some case misses out
>
> Thanks very much for looking into it :)
>
> Thanks and Regards
> Ankur
> On Tue, Jan 3, 2012 at 3:26 AM, Lucifer  wrote:
>
>> @Ankur..
>>
>> A : 2 4 6 8 1, diff is 6.
>>
>> Looks like the answer acc. to ur code would be 5, but actually it
>> should  be 4..
>>
>> I m correct, then it can be fixed by looking at the front and back of
>> the queue and see whether the A[i] is actually the curr min or curr
>> max..
>> And then calculate the diff based on the above cond i.e either
>> abs(A[i] - Q.front()) or abs(A[i] - Q.back())
>>
>> Also,
>> Taking the size of queue for calculating the max is incorrect, as the
>> queue might contain elements with lower indices that actually
>> shouldn't be considered for subarray calculation...
>>
>> Say, Queue :  i j k l m
>>
>> Now, it is possible that i < j and i > k...
>> Hence, if u remove i and then calculate the next subarray it will also
>> take k into consideration which is incorrect..
>> The max length should be : Q.back - (i + 1) for the next iteration...
>> basically 'i+1' should be the start index...
>>
>> Also, say when the queue looks like: k l m , this state is incorrect..
>> While removing elements u should also look for indices, if the current
>> start index is grater than Q.front then u should remove Q.front...
>> i.t for k l m..
>> current start index would be 'j+1' and as k < j hence you should
>> remove it and loop over for further removals..
>>
>> I all my observations are correct, then a couple of modifications will
>> rectify the code..
>> In case i m wrong.. then cheers :)
>>
>> On Jan 3, 1:20 am, Lucifer  wrote:
>> > @ Optimization ... O(N).. single run O(n^2)
>> >
>> > Basically in a single run we can calculate the maximum value using
>> > praveen's logic..
>> >
>> > Say, A[N] is the array of integers..
>> >
>> > And X[N+1] stores the intermediate values for maximum size subarray...
>> >
>> > int max = 0;
>> > int strtind = -1;
>> > int endind = -1;
>> >
>> > for(int i =0; i<= N; ++i)
>> > X[i] = 0;
>> >
>> > for (int i = 0; i < N; ++i)
>> >for (j = N; j > 0; --j)
>> >{
>> > X[j] =  ( abs(A[i] - A[j]) > K ) ? 0 : 1+ min( X[j],
>> > X[j-1] ) ;
>> > if ( A[j] > max)
>> > {
>> >  max = A[j];
>> >  strtind = i - max + 1;
>> >  endind = j - 1;
>> > }
>> >}
>> >
>>

Re: [algogeeks] Re: Longest sequence of numbers with atmost diff K

[Ankur Garg]

@Lucifer

I checked with my code

The answer is coming out to be 4 ..So in this case its passing

Also the queue is containing the indexes in order of increasing values ..so
for curr min we need to only check the front of the queue.

Also I remove the elements of the queue till all the diff of elements in
the queue  with the current element is <=k


If queue is containing elements
say
 i j k l m

Then yesit is possible that i < j and i > k...  but a[i] is always less
than a[j] and a[k]...

So queue will always contain the correct elements I guess..

Like I said I have not done its testing with many cases .. But for this
case the answer is coming out correct

One correction to the code though
it should be
 if(index.empty())
   index.push_back(i);
  else
  binary_search(a,index,0,index.size()-1,i);

I missed the else part here..

In case you find anyother case it would be great .. I am sharing the source
codes .cpp file

If u find any case thats missing ..please tell me and I will also update in
case some case misses out

Thanks very much for looking into it :)

Thanks and Regards
Ankur
On Tue, Jan 3, 2012 at 3:26 AM, Lucifer  wrote:

> @Ankur..
>
> A : 2 4 6 8 1, diff is 6.
>
> Looks like the answer acc. to ur code would be 5, but actually it
> should  be 4..
>
> I m correct, then it can be fixed by looking at the front and back of
> the queue and see whether the A[i] is actually the curr min or curr
> max..
> And then calculate the diff based on the above cond i.e either
> abs(A[i] - Q.front()) or abs(A[i] - Q.back())
>
> Also,
> Taking the size of queue for calculating the max is incorrect, as the
> queue might contain elements with lower indices that actually
> shouldn't be considered for subarray calculation...
>
> Say, Queue :  i j k l m
>
> Now, it is possible that i < j and i > k...
> Hence, if u remove i and then calculate the next subarray it will also
> take k into consideration which is incorrect..
> The max length should be : Q.back - (i + 1) for the next iteration...
> basically 'i+1' should be the start index...
>
> Also, say when the queue looks like: k l m , this state is incorrect..
> While removing elements u should also look for indices, if the current
> start index is grater than Q.front then u should remove Q.front...
> i.t for k l m..
> current start index would be 'j+1' and as k < j hence you should
> remove it and loop over for further removals..
>
> I all my observations are correct, then a couple of modifications will
> rectify the code..
> In case i m wrong.. then cheers :)
>
> On Jan 3, 1:20 am, Lucifer  wrote:
> > @ Optimization ... O(N).. single run O(n^2)
> >
> > Basically in a single run we can calculate the maximum value using
> > praveen's logic..
> >
> > Say, A[N] is the array of integers..
> >
> > And X[N+1] stores the intermediate values for maximum size subarray...
> >
> > int max = 0;
> > int strtind = -1;
> > int endind = -1;
> >
> > for(int i =0; i<= N; ++i)
> > X[i] = 0;
> >
> > for (int i = 0; i < N; ++i)
> >for (j = N; j > 0; --j)
> >{
> > X[j] =  ( abs(A[i] - A[j]) > K ) ? 0 : 1+ min( X[j],
> > X[j-1] ) ;
> > if ( A[j] > max)
> > {
> >  max = A[j];
> >  strtind = i - max + 1;
> >  endind = j - 1;
> > }
> >}
> >
> > On Jan 3, 12:57 am, Lucifer  wrote:
> >
> >
> >
> >
> >
> >
> >
> > > @above..
> > > I m sorry,
> > > A would be 1 2 3 4 5 ..
> >
> > > On Jan 3, 12:03 am, atul anand  wrote:
> >
> > > > @praveen : i guess we can optimize the space to O(n);
> >
> > > > if diff b/w two number is <=K then A[i]=A[i-1]+1;
> >
> > > > if condition fails temp_maxLen=A[i-1];
> > > > if(temp_maxlen > maxLen)
> > > > {
> > > > maxLen=temp_maxlen;
> >
> > > > }
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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.

#include 
#include 
#include
#include
using namespace std;
void binary_search(int a[],deque&index,int low,int high,int i){
   int mid;
   deque::iterator it;
   it=index.begin();
   while(low<=high){
  mid=low+(high-low)/2;
	  if((mid==high || a[index[mid+1]]>=a[i]) && a[index[mid]]<= a[i]){
		   index.insert(it+mid+1,i);
		   return;
	  }	
  else if((mid==low || a[index[mid-1]]<=a[i]) && a[index[mid]]>= a[i] ){
	  if(mid==0){
			index.insert(it,i);
			return;
		  }else{
		 index.insert(it+mid-1,i);
			 return;

Re: [algogeeks] Re: Longest sequence of numbers with atmost diff K

[Ankur Garg]

I think this can be solved in NlogN using binary search

Here is the idea

We take a deque which stores the index of the array in increasing order
i.e. the index with minimum value is always on the front of the deque

Now when  a new element comes we check with the front of this deque .

If the diff of the front element of the deque and a[i] <=k that means it
can be part of the sequence . So we insert it into the correct position in
the deque using binary Search

If the diff is >k then we know that with this element the sequence cant be
formed .So we update the maxLength to max(maxLen,deque.size())

And then remove all the elements from front of the deque till which diff
between front and  a[i]<=k

and keep on repeating the same process

We traverse the array once only and perform binary seach every time so
complexity nlogn

Ex array
2,1,8,12,10,15,13,25

I took deque as data structure so that I can insert and remove elements
from both ends and also access any  in between element in O(1)

So Initially declare maxLen=INT_MIN

now 2 comes with index i=0

Since deque is empty we put its  index -> Deque -> 0

Now next element is 1
We compare front of deque with 1 -> 2-1 =1 .Its less than 7 so we insert it
into correct position in deque using Binary Search

 Deque ->1,0
Now 8 comes -Again 8-1 ==7 So we again put it in

Deque - > 1,0,2

Now comes 12
Now 12-1>7 So it cant be part of Sequence . So we need to remove the
elements . The deque will always contain elements which can be part of the
sequence

Before removing we update the maxLen= max(INT_MIN,deque.size()) so it
becomes 3 for Now

And now we remove elements from start of the deque until deque.front()-12
<=7
So deque becomes 2
Now insert 12 's index i.e 3 in correct position  Deque -> 2,3

Now comes 10 ..It will be part of the sequence So insert it in

Deque ->  2,4,3
Now comes 15 .. Insert it as well

Dequeu-> 2,4,3,5
13 comes

Dequeue-> 2,4,3,6,5
Now comes 25

Update Max len=5 and start removing
Deque will only have 1 now

Now we are done with array

So we return 5

I wrote the code for this and it worked on few cases .I am sharing it below
, but I guess the idea is cleared as I stated above.

I dont think we can do better than NlogN here

Code ->

void binary_search(int a[],deque&index,int low,int high,int i){
   int mid;
   deque::iterator it;
   it=index.begin();
   while(low<=high){
  mid=low+(high-low)/2;
  if((mid==high || a[index[mid+1]]>=a[i]) && a[index[mid]]<= a[i]){
   index.insert(it+mid+1,i);
   return;
  }
  else if((mid==low || a[index[mid-1]]<=a[i]) && a[index[mid]]>= a[i] ){
  if(mid==0){
index.insert(it,i);
return;
  }else{
 index.insert(it+mid-1,i);
 return;
  }
  }
  else if(a[index[mid]]<= a[i])
 low=mid+1;
  else if( a[index[mid]]>=a[i])
 high=mid-1;
   }
}
int FindMaxLength(int a[],int n,int k){
dequeindex;
int len=INT_MIN;
int i,s;
index.push_back(0);
//length.push_back(0);
for(i=1;ik){
   //binary_search(a,index,0,index.size()-1,i);
  s=index.size();
  len=max(len,s);
  while( (!index.empty()) && (abs(a[index.front()]-a[i])>k))
  index.pop_front();
   }
   if(index.empty())
   index.push_back(i);
   binary_search(a,index,0,index.size()-1,i);
}
s=index.size();
len=max(len,s);
return len;
}

On Tue, Jan 3, 2012 at 1:50 AM, Lucifer  wrote:

> @ Optimization ... O(N).. single run O(n^2)
>
> Basically in a single run we can calculate the maximum value using
> praveen's logic..
>
> Say, A[N] is the array of integers..
>
> And X[N+1] stores the intermediate values for maximum size subarray...
>
>
> int max = 0;
> int strtind = -1;
> int endind = -1;
>
> for(int i =0; i<= N; ++i)
>X[i] = 0;
>
> for (int i = 0; i < N; ++i)
>   for (j = N; j > 0; --j)
>   {
>X[j] =  ( abs(A[i] - A[j]) > K ) ? 0 : 1+ min( X[j],
> X[j-1] ) ;
>if ( A[j] > max)
>{
> max = A[j];
> strtind = i - max + 1;
> endind = j - 1;
> }
>   }
>
>
> On Jan 3, 12:57 am, Lucifer  wrote:
> > @above..
> > I m sorry,
> > A would be 1 2 3 4 5 ..
> >
> > On Jan 3, 12:03 am, atul anand  wrote:
> >
> >
> >
> >
> >
> >
> >
> > > @praveen : i guess we can optimize the space to O(n);
> >
> > > if diff b/w two number is <=K then A[i]=A[i-1]+1;
> >
> > > if condition fails temp_maxLen=A[i-1];
> > > if(temp_maxlen > maxLen)
> > > {
> > > maxLen=temp_maxlen;
> >
> > > }
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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...@g

Re: [algogeeks] [Off-topic] Amdocs Interview Questions

[Ankur Garg]

Dude please ask these question on Interviewstreet group..

Your queries will be answered there

Kindly adhere to the protocols of this group..

This may be one off thing but it can lead to start of interview queries.So
please understand :)


On Thu, Dec 29, 2011 at 12:35 AM, Jyoti Malik wrote:

> ooops sry i have no idea about that..
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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: Frequency Sort Algo

[Ankur Garg]

fpr the nos with same frequency , the one having lower value shud come first

For ex

3,1,1,3,1,3,2

Here 1 should come first
so
2,1,1,1,3,3,3



On Sun, Dec 25, 2011 at 11:18 AM, top coder  wrote:

> What about the case of the numbers having same frequency?
> Which one should come first?
>
> On Dec 24, 11:18 pm, atul anand  wrote:
> > first sort the given array , you will get
> >
> > 1,1,1,1,2,2,2,3,3,3,3,3,4,4,5
> >
> > now count frequency of each number and insert it into min heap.
> > each node contain 2 variable.
> > 1) frequency
> > 2) number
> >
> > now do extract min operation.
> >
> > and expand , for eg:-
> > for node 5
> > frequency = 0
> > number =5;
> > write 5 to the given array
> >
> > for node 4
> > frequency = 2
> > number =4
> > write 4,4 to array.
> >
> > for node 2
> > frequency = 3
> > number =2
> >
> > write 2,2,2 to the given array...
> >
> >
> >
> > On Sat, Dec 24, 2011 at 10:57 PM, Ankur Garg 
> wrote:
> > > how can one do frequency sort .
> >
> > > Suppose we have an integer array like
> >
> > > 1,2,3,1,2,3,1,1,2,3,4,4,3,5,3
> >
> > > Then 1 is appearing 4 times
> > >   2 - 3
> > >   3- 5
> > >   4-2
> > >   5-1
> >
> > > Then if we sort by frequency we shud have this as result
> >
> > > 5,4,4,2,2,2,1,1,1,1,3,3,3,3,3
> >
> > > How to do it
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.- 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: Frequency Sort Algo

[Ankur Garg]

@Atul..your solution is correct and would do the job but its complexity wud
be nlogn .

Any better way of solving it ?

Regards
Ankur

On Sun, Dec 25, 2011 at 2:10 AM, sravanreddy001 wrote:

> any better approach than O(N log N) time?
>
> maintain a heap of nodes 
> for each element, if already present increase the count. Else add the
> elements.
>
> Max-Heap --> fetch the node, print it count number of times, (time to
> search in heap -- log N)
> doing this for N elements.
>
>
>  --
> 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/-/rJMBHTFmv8IJ.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Frequency Sort Algo

[Ankur Garg]

how can one do frequency sort .

Suppose we have an integer array like

1,2,3,1,2,3,1,1,2,3,4,4,3,5,3

Then 1 is appearing 4 times
  2 - 3
  3- 5
  4-2
  5-1

Then if we sort by frequency we shud have this as result

5,4,4,2,2,2,1,1,1,1,3,3,3,3,3

How to do it

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

Re: [algogeeks] Re: How to solve this

[Ankur Garg]

The thing is ..will it ascertain that the probability is equal

I am not sure how ur method guarantees that...
May be if you and Dave can explain the algo a bit better that wud be great .

regards
Ankur

On Sat, Dec 24, 2011 at 5:48 AM, Piyush Kansal wrote:

> Hey Ankur,
>
> What is the order of time complexity we are looking for in this case. The
> option which Dave suggested can give us random node by traversing that many
> number of nodes from the head. That will be O(n).
>
> This can be further reduced to n/2 if we use two pointers, both of which
> will traverse two nodes at a time:
> 1. one pointing to first node (lets call it odd pointer)
> 2. other pointing to second node (lets call it even pointer)
>
> So, depending on the value returned by random number generator(even or
> odd), we can decide which pointer to pick.
>
>  --
> 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/-/N-5i9YH4AkYJ.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] How to solve this

[Ankur Garg]

Suggest an algo with which u can find a random node in an infinitely long
linked list

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Reverse n-Ary Tree and Return List of Leaf Nodes as Output - FYI Google MV

[Ankur Garg]

A better representation for a n-ary tree would be

struct node{
int data;
   node* left;
   node* sibling;
}

Like in a binary tree the second ptr points to its right child . Here it
points to its sibling.This one saves space and also We know in each level
we have how many nodes
@Shashank,
I think we can reverse the n-ary tree ,but again my doubt is what will be
leaf nodes then in that case , It seems it will be original root , so i was
confused . anyway , I will concentrate on reversing the tree only for now
based on ur definition.

Regards
Ankur

On Wed, Dec 21, 2011 at 1:08 PM, WgpShashank wrote:

> @atul,, yeah , but can you write some proper psuedo code/ Algorithm then
> we can discus more about test cases.
>
> Thanks
> Shashank
>
> --
> 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/-/VPZpHM8D_WcJ.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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: Reverse n-Ary Tree and Return List of Leaf Nodes as Output - FYI Google MV

[Ankur Garg]

@Atul

Even i thought so..but then the definition of leaf node is that its a node
which doesnt have any children...then the answer is root of the original
tree so I got confused here :(



On Wed, Dec 21, 2011 at 12:20 AM, atul anand wrote:

> @ankur : for the given tree above instead of parent pointing to its child
> , it would be child pointing to its parent after reversing
> i guess thats wat he is trying to say.
>
>
> On Tue, Dec 20, 2011 at 11:38 PM, Ankur Garg  wrote:
>
>> Hey Shashank
>>
>> Unfortunately I cudnt understand the problem
>>
>> What do u mean by reversing the tree here :(..
>>
>> On Tue, Dec 20, 2011 at 11:23 PM, WgpShashank > > wrote:
>>
>>> here is my code
>>>
>>>
>>> List list=new LinkeList();
>>>
>>> public List reverseTreeandReturnListContainingAllLeafNOdes(Node n)
>>> {
>>>int i=0;
>>>static int j=0;
>>>
>>>
>>>if(n==null)
>>>{
>>> n=n.children[++j];
>>> return null;
>>>}
>>>
>>>if(n.children[i]==null)
>>>{
>>> list.add(n);
>>>
>>> return list;
>>>}
>>>
>>>
>>> list=reverseTreeandReturnListContainingAllLeafNOdes(n.children[i]);
>>>n.children[i]=n;
>>>
>>>
>>>  return list;
>>> }
>>>
>>> may contains the bug ? any modification / suggestion will be appreciated
>>>
>>> Thanks
>>> Shashank
>>>
>>>  --
>>> 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/-/2puK42n-1yYJ.
>>>
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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: Reverse n-Ary Tree and Return List of Leaf Nodes as Output - FYI Google MV

[Ankur Garg]

Hey Shashank

Unfortunately I cudnt understand the problem

What do u mean by reversing the tree here :(..

On Tue, Dec 20, 2011 at 11:23 PM, WgpShashank wrote:

> here is my code
>
>
> List list=new LinkeList();
>
> public List reverseTreeandReturnListContainingAllLeafNOdes(Node n)
> {
>int i=0;
>static int j=0;
>
>
>if(n==null)
>{
> n=n.children[++j];
> return null;
>}
>
>if(n.children[i]==null)
>{
> list.add(n);
>
> return list;
>}
>
>list=reverseTreeandReturnListContainingAllLeafNOdes(n.children[i]);
>n.children[i]=n;
>
>
>  return list;
> }
>
> may contains the bug ? any modification / suggestion will be appreciated
>
> Thanks
> Shashank
>
>  --
> 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/-/2puK42n-1yYJ.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Can anyone help me with this problem

[Ankur Garg]

Hi

Can anyone help me with this question

Code for Serializing and Deserializing a binary Tree

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

[Ankur Garg]

@Atul ur solution is wrong
It seems u r comparing just the neighbouring elements .
The question is not to find the contiguous zig-zag sequence but longest
subsequence
Also even in case of contiguous sequence ur solution will not print the
correct length
like for 6 7 4 ur solution will print answer as 4 whereas in the answer
should be 3

Regards
Ankur

On Mon, Dec 19, 2011 at 1:16 AM, Ankur Garg  wrote:

> a linear solution for this problem . although its more than O(n) but will
> never be O(n*2)..used DP to solve it
>
> space used -O(2n)
>
> int ZigZagLength(vector a){
> int n=a.size();
> int DP[n][2];
> DP[0][0]=1;
> DP[0][1]=0;
> DP[1][0]=2;
> DP[1][1]=0;
> int j;
> for(int i=2;i if((a[i]-a[i-1])*(a[i-1]-a[DP[i-1][1]])==0){
> DP[i][0]=DP[i-1][0];
> DP[i][1]= i-1;
> }
> if((a[i]-a[i-1])*(a[i-1]-a[DP[i-1][1]])<0){
> DP[i][0]=DP[i-1][0]+1;
> DP[i][1]= i-1;
> }
> else{
> j = DP[i-1][1];
> while(j>0){
> if((a[i]-a[j])*(a[j]-a[DP[j][1]])<0){
> DP[i][0]=max(DP[j][0]+1,DP[i-1][0]);
> if(DP[i][0]==DP[j][0]+1)
> DP[i][1]=j ;
> else
> DP[i][1]= i-1;
> break;
> }else
> j= DP[j][1];
> }
> if(j==0){
> DP[i][0]=DP[i-1][0];
> DP[i][1]=DP[i-1][1];
> }
> }
> }
> return DP[n-1][0];
> }
>
> On Sun, Dec 18, 2011 at 11:04 AM, atul anand wrote:
>
>> complexity of this algo is O(n) ..I guess it is better than dynamic
>> programming approach which is O(n^2).
>>
>>
>> On Sat, Dec 17, 2011 at 6:28 PM, atul anand wrote:
>>
>>> please see the algo and let me know if i am doing it wrong:-
>>>
>>> toggle= arr[i+1] > arr[i];
>>> subseq=0;
>>>
>>> for( i=0 ; i>> {
>>>
>>>if ( toggle == 1)
>>>{
>>>if( arr[i+1] > arr[i])
>>>{
>>>   subseq=subseq+2;
>>>
>>>}
>>>
>>>toggle=0;
>>>}
>>>else
>>>{
>>>
>>>   if(arr[i] > arr[i+1])
>>>   {
>>>
>>>subseq=subseq+2;
>>>
>>>   }
>>>
>>>   toggle=1;
>>> }
>>>
>>>
>>> }
>>>
>>> print subseq;
>>>
>>>
>>> On Fri, Dec 16, 2011 at 10:33 AM, Sangeeta wrote:
>>>
>>>> Problem Statement
>>>> A sequence of numbers is called a zig-zag sequence if the differences
>>>> between successive numbers strictly alternate between positive and
>>>> negative. The first difference (if one exists) may be either positive
>>>> or negative. A sequence with fewer than two elements is trivially a
>>>> zig-zag sequence.
>>>>
>>>> For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences
>>>> (6,-3,5,-7,3) are alternately positive and negative. In contrast,
>>>> 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because
>>>> its first two differences are positive and the second because its last
>>>> difference is zero.
>>>>
>>>> Given a sequence of integers, sequence, return the length of the
>>>> longest subsequence of sequence that is a zig-zag sequence. A
>>>> subsequence is obtained by deleting some number of elements (possibly
>>>> zero) from the original sequence, leaving the remaining elements in
>>>> their original order
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from 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] zig zag problem

[Ankur Garg]

a linear solution for this problem . although its more than O(n) but will
never be O(n*2)..used DP to solve it

space used -O(2n)

int ZigZagLength(vector a){
int n=a.size();
int DP[n][2];
DP[0][0]=1;
DP[0][1]=0;
DP[1][0]=2;
DP[1][1]=0;
int j;
for(int i=2;i0){
if((a[i]-a[j])*(a[j]-a[DP[j][1]])<0){
DP[i][0]=max(DP[j][0]+1,DP[i-1][0]);
if(DP[i][0]==DP[j][0]+1)
DP[i][1]=j ;
else
DP[i][1]= i-1;
break;
}else
j= DP[j][1];
}
if(j==0){
DP[i][0]=DP[i-1][0];
DP[i][1]=DP[i-1][1];
}
}
}
return DP[n-1][0];
}

On Sun, Dec 18, 2011 at 11:04 AM, atul anand wrote:

> complexity of this algo is O(n) ..I guess it is better than dynamic
> programming approach which is O(n^2).
>
>
> On Sat, Dec 17, 2011 at 6:28 PM, atul anand wrote:
>
>> please see the algo and let me know if i am doing it wrong:-
>>
>> toggle= arr[i+1] > arr[i];
>> subseq=0;
>>
>> for( i=0 ; i> {
>>
>>if ( toggle == 1)
>>{
>>if( arr[i+1] > arr[i])
>>{
>>   subseq=subseq+2;
>>
>>}
>>
>>toggle=0;
>>}
>>else
>>{
>>
>>   if(arr[i] > arr[i+1])
>>   {
>>
>>subseq=subseq+2;
>>
>>   }
>>
>>   toggle=1;
>> }
>>
>>
>> }
>>
>> print subseq;
>>
>>
>> On Fri, Dec 16, 2011 at 10:33 AM, Sangeeta wrote:
>>
>>> Problem Statement
>>> A sequence of numbers is called a zig-zag sequence if the differences
>>> between successive numbers strictly alternate between positive and
>>> negative. The first difference (if one exists) may be either positive
>>> or negative. A sequence with fewer than two elements is trivially a
>>> zig-zag sequence.
>>>
>>> For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences
>>> (6,-3,5,-7,3) are alternately positive and negative. In contrast,
>>> 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because
>>> its first two differences are positive and the second because its last
>>> difference is zero.
>>>
>>> Given a sequence of integers, sequence, return the length of the
>>> longest subsequence of sequence that is a zig-zag sequence. A
>>> subsequence is obtained by deleting some number of elements (possibly
>>> zero) from the original sequence, leaving the remaining elements in
>>> their original order
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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] suggest algo

[Ankur Garg]

suggest algo to find k most frequently occuring numbers from a file of very
large size containing numbers.

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

[Ankur Garg]

I saw this term "non-decreasing order"
So we need to sort the numbers first..it will take nlogn .

On Fri, Dec 16, 2011 at 1:12 AM, Ankur Garg  wrote:

> on above algo , there is no need to calculate sum of array so we can do it
> in O(N) and not O(n).
>
>
> On Fri, Dec 16, 2011 at 12:59 AM, Ankur Garg  wrote:
>
>> Hi Topcoder.
>>
>> First of all you  posted  the wrong array .
>>
>> The array should be
>>
>> 4,  5,  10, 7,  12, 13
>> a+b  a+c   a+d   b+cb+d   c+d
>>
>> Now first calculate a+b+c+d which will be (sumofarray)/N-1
>>
>> So here a+b+c+d = 17
>>
>> Now take a[1] is a+c
>> and a[N-1] =  b+c
>> subtracting them gives b-a = 2
>>  a[0] is b+a=4
>> that gives  b=3,a=1
>> Now u have a and b calculate c as a[1]-a=4
>> and d as9 . For this we traverse from a[1] to a[N-2]
>> We calculate a and b because we know the order of sum of their
>> elements(a+bis given and b's  addition with rest elements are there in
>> array)
>>
>> This will work in Linear Time
>>
>> Now lets take an example with  8 elements to
>> let  a=1,b=2,c=3,d=4,e=5,f=6,g=7,h=8
>>
>> then N=8 and array is
>>  3  4  5  6 7 8 9 5 6 7 8 9 10 7 8 9 10 11 9 10 11 12 11 12 13 13 14 15
>> Now by above logic  first
>> a+b+c+d+e+f+g+h = (sum)/7 = 252/7 = 36
>> Now a[1]=a+c = 4 and a[N-1] =a[7]=b+c=5
>> a[8]-a[1]= b-a=1 and a+b=a[0]=3 gives b=2 and a =1
>> Now we have a=1,b=2
>> So we traverse from a[1] to a[N-2] to calculate values c to h
>> c= a[1]-a=4-1=3
>> d=a[2]-a=5-1=4
>> e=a[3]-a=6-1=5
>> similarly f=a[4]=6,g=a[5]=7 and h=a[6]=8
>>
>> This will work in O(n)
>>
>> Regards
>> Ankur
>>
>> On Thu, Dec 15, 2011 at 12:42 PM, WgpShashank > > wrote:
>>
>>> @all , a Naive Approach with Quadratic Time will be for each i=1 to n ,
>>> check if i and a[i]-i makes given sum , so for each each number we will do
>>> the thus can achieve the solution ...i am just thinking about if we can do
>>> it linear time ..will post if able to do it :)
>>>
>>>
>>> Thanks
>>> Shashank
>>> CSe BIT Mesra
>>>
>>>  --
>>> 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/-/lF0kSVRUp5cJ.
>>>
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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: find numbers if pair wise sums are given

[Ankur Garg]

on above algo , there is no need to calculate sum of array so we can do it
in O(N) and not O(n).

On Fri, Dec 16, 2011 at 12:59 AM, Ankur Garg  wrote:

> Hi Topcoder.
>
> First of all you  posted  the wrong array .
>
> The array should be
>
> 4,  5,  10, 7,  12, 13
> a+b  a+c   a+d   b+cb+d   c+d
>
> Now first calculate a+b+c+d which will be (sumofarray)/N-1
>
> So here a+b+c+d = 17
>
> Now take a[1] is a+c
> and a[N-1] =  b+c
> subtracting them gives b-a = 2
>  a[0] is b+a=4
> that gives  b=3,a=1
> Now u have a and b calculate c as a[1]-a=4
> and d as9 . For this we traverse from a[1] to a[N-2]
> We calculate a and b because we know the order of sum of their
> elements(a+bis given and b's  addition with rest elements are there in
> array)
>
> This will work in Linear Time
>
> Now lets take an example with  8 elements to
> let  a=1,b=2,c=3,d=4,e=5,f=6,g=7,h=8
>
> then N=8 and array is
>  3  4  5  6 7 8 9 5 6 7 8 9 10 7 8 9 10 11 9 10 11 12 11 12 13 13 14 15
> Now by above logic  first
> a+b+c+d+e+f+g+h = (sum)/7 = 252/7 = 36
> Now a[1]=a+c = 4 and a[N-1] =a[7]=b+c=5
> a[8]-a[1]= b-a=1 and a+b=a[0]=3 gives b=2 and a =1
> Now we have a=1,b=2
> So we traverse from a[1] to a[N-2] to calculate values c to h
> c= a[1]-a=4-1=3
> d=a[2]-a=5-1=4
> e=a[3]-a=6-1=5
> similarly f=a[4]=6,g=a[5]=7 and h=a[6]=8
>
> This will work in O(n)
>
> Regards
> Ankur
>
> On Thu, Dec 15, 2011 at 12:42 PM, WgpShashank 
> wrote:
>
>> @all , a Naive Approach with Quadratic Time will be for each i=1 to n ,
>> check if i and a[i]-i makes given sum , so for each each number we will do
>> the thus can achieve the solution ...i am just thinking about if we can do
>> it linear time ..will post if able to do it :)
>>
>>
>> Thanks
>> Shashank
>> CSe BIT Mesra
>>
>>  --
>> 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/-/lF0kSVRUp5cJ.
>>
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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: find numbers if pair wise sums are given

[Ankur Garg]

Hi Topcoder.

First of all you  posted  the wrong array .

The array should be

4,  5,  10, 7,  12, 13
a+b  a+c   a+d   b+cb+d   c+d

Now first calculate a+b+c+d which will be (sumofarray)/N-1

So here a+b+c+d = 17

Now take a[1] is a+c
and a[N-1] =  b+c
subtracting them gives b-a = 2
 a[0] is b+a=4
that gives  b=3,a=1
Now u have a and b calculate c as a[1]-a=4
and d as9 . For this we traverse from a[1] to a[N-2]
We calculate a and b because we know the order of sum of their
elements(a+bis given and b's  addition with rest elements are there in
array)

This will work in Linear Time

Now lets take an example with  8 elements to
let  a=1,b=2,c=3,d=4,e=5,f=6,g=7,h=8

then N=8 and array is
 3  4  5  6 7 8 9 5 6 7 8 9 10 7 8 9 10 11 9 10 11 12 11 12 13 13 14 15
Now by above logic  first
a+b+c+d+e+f+g+h = (sum)/7 = 252/7 = 36
Now a[1]=a+c = 4 and a[N-1] =a[7]=b+c=5
a[8]-a[1]= b-a=1 and a+b=a[0]=3 gives b=2 and a =1
Now we have a=1,b=2
So we traverse from a[1] to a[N-2] to calculate values c to h
c= a[1]-a=4-1=3
d=a[2]-a=5-1=4
e=a[3]-a=6-1=5
similarly f=a[4]=6,g=a[5]=7 and h=a[6]=8

This will work in O(n)

Regards
Ankur

On Thu, Dec 15, 2011 at 12:42 PM, WgpShashank wrote:

> @all , a Naive Approach with Quadratic Time will be for each i=1 to n ,
> check if i and a[i]-i makes given sum , so for each each number we will do
> the thus can achieve the solution ...i am just thinking about if we can do
> it linear time ..will post if able to do it :)
>
>
> Thanks
> Shashank
> CSe BIT Mesra
>
>  --
> 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/-/lF0kSVRUp5cJ.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Interesting Liked List problem..Suggest Algo

[Ankur Garg]

Twisted linked list problem: Two linked lists merge at some node p,both the
head pointers are given find the merging point under
the following restrictions.
1. You should not traverse to the end any of the linked list.
2. Merge node p should be detected by the time you reach at most most k
nodes from p.
3. Space should not exceed by k units.
4. No saving of nodes to hard discs.
5. No recursion.

Regards
Ankur

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

[Ankur Garg]

Given an array-based heap on n elements and a real number x, efficiently
determine whether the kth smallest element in the heap is greater than or
equal to x. Your algorithm should be O(k) in the worst-case, independent of
the size of the heap.


This question was also asked in Amazon

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

[Ankur Garg]

By Max Heapify I thought u meant to say u are making a Max Heap .. In case
you use Coreman Definition Of max Heapify it just heapifies assuming the
heap has been formed, But u need to make a max Heap first dude :)

P.S-> Clarify your concepts before posting the link :(

On Tue, Dec 13, 2011 at 12:11 AM, Dipit Grover wrote:

> ^it cant get better than O(n) apparently. Just applying max-heapify once
> would not yield the max element. You need to construct a heap for it, which
> is no less than O(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: Find Largest number in log(n)

[Ankur Garg]

Max Heapify is O(n).

On Mon, Dec 12, 2011 at 11:43 PM, ankit gupta wrote:

> apply MAXHEAPIFY on root ode and extract the root 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: Find Largest number in log(n)

[Ankur Garg]

Agree with dave..Its still O(n)

On Mon, Dec 12, 2011 at 10:57 PM, Dave  wrote:

> @Sagar: Don is correct. n/2+n/4+n/8+... ~= n. But even the first
> round, involving n/2 comparisons, is O(n).
>
> Dave
>
> On Dec 12, 11:23 am, sagar pareek  wrote:
> > Yes Mr. DoN
> >
> > First round of Tournament sort results in log(n) time for finding largest
> > no.
> >
> > n/2+n/4+n/8   results n/(2^i)   where ^ = power
> >
> >
> >
> >
> >
> > On Mon, Dec 12, 2011 at 8:16 AM, Don  wrote:
> > > No. To find the largest number in an unsorted array requires looking
> > > at each number, which is order n by definition.
> > > Don
> >
> > > On Dec 12, 10:02 am, sagar pareek  wrote:
> > > > Hi every one.
> >
> > > > Can we find largest number from an unsorted array in log(n) ?
> >
> > > > --
> > > > **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
> > 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.
>
>

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

[Ankur Garg]

U cant create any new ptrs .Just use this ptr :)

On Thu, Dec 8, 2011 at 6:30 PM, Prem Krishna Chettri wrote:

> Ofcourse we can..
>
>U knw the head address now U start visit the list what is the big
> deal?? Jst u gotto create two pointer say fast and slow with two diff speed
> of action..
>
> On Thu, Dec 8, 2011 at 6:27 PM, Ankur Garg  wrote:
>
>> Can we detect if a loop is present in Linked List if only head ptr is
>> given
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] Detect a loop with just head ptr given

[Ankur Garg]

Can we detect if a loop is present in Linked List if only head ptr is given

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

[Ankur Garg]

cWas it offcampus or on campus recruitment dude.

On Sat, Dec 3, 2011 at 12:5i7 PM, atul anand wrote:

> @payal : last problem is a dutch flag problem.
>
>
> On Sat, Dec 3, 2011 at 3:33 AM, payal gupta  wrote:
>
>> congrats..:):)
>> plzz...elaborate the last two problemsand it vud be very grateful
>> if u tell their solns tooo...
>>
>> Regards,
>> payal gupta,cse,3rd year,
>> nit-b.
>>
>>
>> On 12/2/11, rahul sharma  wrote:
>> > plz post how you prepared for MS..like the books or websites you
>> > followedwould b of gr8 help.
>> >
>> > On Fri, Dec 2, 2011 at 9:42 PM, rahul sharma > >wrote:
>> >
>> >> gr8...congrats dude
>> >>
>> >>
>> >> On Fri, Dec 2, 2011 at 9:05 PM, Karthikeyan V.B
>> >> wrote:
>> >>
>> >>> Congratulations:)
>> >>>
>> >>> --
>> >>> You received this message because you are subscribed to the Google
>> Groups
>> >>> "Algorithm Geeks" group.
>> >>> To post to this group, send email to algogeeks@googlegroups.com.
>> >>> To unsubscribe from 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: Google Question--Suggest Algo

[Ankur Garg]

Cool Solution...I was thinking of DP but wasnt clear on the recurrence...

Nice thinking man and thanks :)



On Mon, Nov 28, 2011 at 2:47 AM, sourabh  wrote:

> Consider the example that you have given:
> [0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
>
> Now we need to partition the array into 3 contiguous sub arrays such
> that :
> a) The expected sum value is maximum
> b) and the size of each sub array should be between 2 and 6, both
> inclusive. In case, this constraint is not satisfied then its not a
> valid candidate for the solution even if the partition produces the
> max value.
>
>  2 = ceil (n / 2k) = ceil (12/6)
>  6 = floor (3n / 2k) = floor (36/6)
> -
>  As mentioned above the following equation :
> F(n,k) = MAX for all r such that ceil(n/2k) <= r <=  floor(3n/2k)
> { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
> k-1) }
>
> /**
> For understanding how partitioning of the array is represented by the
> above equation:
>
> Say there is an array denoted by A[i] and it needs to be divided into
> 3 contiguous parts, one of the ways to do so would be to take the
> following steps :
>
> Let K(partition no.) be initialized to 3.
> Let array size N be 12.
>
> a) If N is 0, the goto step 'f'
> b) If K == 1 then call it as partition K and goto step 'e'.
> c) Lets take X no. of elements from the end of array A of size N and
> call it partition K.
> d) Decrement K by 1 and N by X { --K; and N-=X;}
> d) Goto step 'a'
> e) Valid partition and End.
> f) Not a valid partition and End.
>
> Now if the above set of steps is run for all values of X such that
> 2<=X<=6 , then it will generate all possible candidates (partitions)
> as per the given problem statement. And for all the valid
> partitions(the ones that will hit step 'e') we need to calculate the
> expected sum value.
> **/
>
> can be translated into,
> // I am using 1-based array indexing for better clarity
> // A[x .. y] means all elements from A[y] to A[x]..
>
> F(12, 3) = MAX
>   {
>  ExpVal (A[12 .. 11])  +  F(10, 2) ,
>  ExpVal (A[12 .. 10])  +  F(9, 2) ,
>  ExpVal (A[12 .. 9])+  F(8, 2) ,   //
> this will yield the maximum sum..
>  ExpVal (A[12 .. 8])+  F(7, 2) ,
>  ExpVal (A[12 .. 7])+  F(6, 2)
>   }
>
> which is nothing but,
> F(12, 3) = MAX
>   {
>  1/2  +  F(10, 2) ,
>  2/3  +  F(9, 2) ,
>  2/4  +  F(8, 2) , // this will yield the
> maximum sum..
>  3/5  +  F(7, 2) ,
>  4/6  +  F(6, 2)
>   }
>
> Trace the above equation and you should get it..
>
> On Nov 28, 12:57 am, Ankur Garg  wrote:
> > Hey Sourabh
> >
> > Could you please explain the solution in a bit detail perhaps using an
> > example or so..It wud be really helpful ..Just logic not code
> >
> >
> >
> >
> >
> >
> >
> > On Mon, Nov 28, 2011 at 1:03 AM, sourabh  wrote:
> > > Looks like a dynamic programming problem
> >
> > > Say F(n,k) denotes the maximum expected sum value for an array of n
> > > elements and partition k , then
> >
> > > F(n,k) = MAX for all r such that ceil(n/2k) <= r <=  floor(3n/2k)
> > > { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
> > > k-1) }
> >
> > > Base condition:
> > > 1) F(N, 1) = expected value for array A[n] such that  ceil(n/2k) <= N
> > > <=  floor(3n/2k)
> > > 2) If any of the sub problems where the array size is not between
> > > ceil(n/2k) and  floor(3n/2k) , both inclusive, then its not a valid
> > > candidate for the final solution. This is can be handled by giving
> > > initial value to all such combination a value of -1.
> >
> > > To store that the intermediate computations take an array Max[N][K],
> > > F(N,K) = Max[N][K]
> >
> > > On Nov 28, 12:17 am, sourabh  wrote:
> > > > Because in the previous example k = 3.
> >
> > > > On Nov 27, 10:46 pm, Piyush Grover 
> wrote:
> >
> > > > > Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
> > > > > Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
> > > > > why this is not the optimal split???
> >
> > > > > On Sun, Nov 27, 2011 at 6:58 PM, Ankur G

Re: [algogeeks] Re: Google Question--Suggest Algo

[Ankur Garg]

Hey Sourabh

Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code

On Mon, Nov 28, 2011 at 1:03 AM, sourabh  wrote:

> Looks like a dynamic programming problem
>
> Say F(n,k) denotes the maximum expected sum value for an array of n
> elements and partition k , then
>
> F(n,k) = MAX for all r such that ceil(n/2k) <= r <=  floor(3n/2k)
> { (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
> k-1) }
>
> Base condition:
> 1) F(N, 1) = expected value for array A[n] such that  ceil(n/2k) <= N
> <=  floor(3n/2k)
> 2) If any of the sub problems where the array size is not between
> ceil(n/2k) and  floor(3n/2k) , both inclusive, then its not a valid
> candidate for the final solution. This is can be handled by giving
> initial value to all such combination a value of -1.
>
> To store that the intermediate computations take an array Max[N][K],
> F(N,K) = Max[N][K]
>
>
> On Nov 28, 12:17 am, sourabh  wrote:
> > Because in the previous example k = 3.
> >
> > On Nov 27, 10:46 pm, Piyush Grover  wrote:
> >
> >
> >
> >
> >
> >
> >
> > > Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
> > > Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
> > > why this is not the optimal split???
> >
> > > On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg 
> wrote:
> > > > You have an array with *n* elements. The elements are either 0 or 1.
> You
> > > > want to *split the array into kcontiguous subarrays*. The size of
> each
> > > > subarray can vary between ceil(n/2k) and floor(3n/2k). You can
> assume that
> > > > k << n. After you split the array into k subarrays. One element of
> each
> > > > subarray will be randomly selected.
> >
> > > > Devise an algorithm for maximizing the sum of the randomly selected
> > > > elements from the k subarrays. Basically means that we will want to
> split
> > > > the array in such way such that the sum of all the expected values
> for the
> > > > elements selected from each subarray is maximum.
> >
> > > > You can assume that n is a power of 2.
> >
> > > > Example:
> >
> > > > Array: [0,0,1,1,0,0,1,1,0,1,1,0]
> > > > n = 12
> > > > k = 3
> > > > Size of subarrays can be: 2,3,4,5,6
> >
> > > > Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
> > > > Expected Value of the sum of the elements randomly selected from the
> subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433
> >
> > > > Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
> > > > Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333
> >
> > > > Source ->
> http://stackoverflow.com/questions/8189334/google-combinatorial-optim...
> >
> > > >  --
> > > > You received this message because you are subscribed to the Google
> Groups
> > > > "Algorithm Geeks" group.
> > > > To post to this group, send email to algogeeks@googlegroups.com.
> > > > To unsubscribe from 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: Finding the repeated element

[Ankur Garg]

Yup Gene ..rightly said and very well pointed out  :) ..My Mistake :(

On Sun, Nov 27, 2011 at 12:49 AM, Gene  wrote:

> Isn't this overkill? If you're already using a set, just check the set
> before you insert each new element, and you'll discover the
> duplicates:
>
> S = empty
> while i = input item existss
>  if i in S output "i has a duplicate";
>  insert i in S
> end
>
> XOR is generally useful only for detecting a single item that's
> included in a list an odd number of times rather than an even number
> of times.
>
> On Nov 24, 3:56 pm, Ankur Garg  wrote:
> > ^^+1..how matrix formed ??
> > But as Gene said we can use a set to store all the unique elements
> >
> > Now we xor all the set elements and then xor them with the elements of
> the
> > array . This wud give us the repeating element as all the elements coming
> > once will be 0(xored twice) and repeating element wud be xored twice .
> >
> > To code it as follows
> >
> > int FindSingle(int a[],int n){
> >sets;
> >s.insert(a,a+n);
> >   set::iterator it;
> >   it = s.begin();
> >   int XOR= *it;
> >   it++;
> >  while(it!=s.end()){
> >XOR =XOR^*it;
> >it++;}
> >
> >  for(int i=0;i >XOR=XOR^a[i];
> > return XOR;
> >
> > }
> >
> > On Fri, Nov 25, 2011 at 1:03 AM, kumar raja  >wrote:
> >
> >
> >
> > > @Anup:
> > > Atleast u tell me how the M has formed???
> >
> > > On 24 November 2011 11:21, Anup Ghatage  wrote:
> >
> > >> @kunzmilan
> > >> Nice idea, how do you decide the row-size or column-size of the
> matrix?
> >
> > >> On Thu, Nov 24, 2011 at 8:00 PM, kumar raja  >wrote:
> >
> > >>> @kunzmilan :
> > >>> Can u please maintain the clarity ??
> > >>> How did u find the M
> >
> > >>> if the list is 4 2 8 9  5 1 9 how M looks like ?? please elaborate
> it...
> >
> > >>> On 24 November 2011 06:15, kunzmize an  wrote:
> >
> > >>>> On 24 lis, 09:09, kumar raja  wrote:
> > >>>> > @kunzmilan : i did not get  u, once explain with example...
> >
> > >>>> > On 23 November 2011 23:47, kunzmilan  wrote:
> > >>>> Matrix M
> > >>>> 0 1 0
> > >>>> 0 1 0
> > >>>> 1 0 0
> > >>>> multiplied with M(T)
> > >>>> 0 0 1
> > >>>> 1 1 0
> > >>>> 0 0 0
> > >>>> gives
> > >>>> 1 0 0
> > >>>> 0 2 0
> > >>>> 0 0 0.
> > >>>> On its diagonal are numbers of repeated elements.
> > >>>> kunzmilan
> >
> > >>>> > > On 24 lis, 07:02, kumar raja  wrote:
> > >>>> > > > In the given array all the elements occur single time except
>  one
> > >>>> element
> > >>>> > > > which occurs  2 times find it in O(n) time and O(1) space.
> >
> > >>>> > > > e.g.  2 3 4 9 3 7
> >
> > >>>> > > > output :3
> >
> > >>>> > > > If such a solution exist can we extend the logic to find "All
> the
> > >>>> > > repeated
> > >>>> > > > elements in an array in O(n) time and O(1) space"
> >
> > >>>> > > > --
> > >>>> > > > Regards
> > >>>> > > > Kumar Raja
> > >>>> > > > M.Tech(SIT)
> > >>>> > > > IIT Kharagpur,
> > >>>> > > > 10it60...@iitkgp.ac.in
> > >>>> > > > Write the list in the form of a matrix M, e.g.
> > >>>> > > > 0 1 0 0...
> > >>>> > > > 0 0 1 0...
> > >>>> > > > 0 0 0 1...
> > >>>> > > > ..etc.,
> > >>>> > > > and its quadratic form M(T)M shows, how many times each
> element
> > >>>> repeats.
> > >>>> > > kunzmilan
> >
> > >>>> > > --
> > >>>> > > You received this message because you are subscribed to the
> Google
> > >>>> Groups
> > >>>> > > "Algorithm Geeks" group.
> > >>>> > > To post to this group, send email to algogeeks@googlegroups.com
> .

[algogeeks] Google Question--Suggest Algo

[Ankur Garg]

You have an array with *n* elements. The elements are either 0 or 1. You
want to *split the array into kcontiguous subarrays*. The size of each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that
k << n. After you split the array into k subarrays. One element of each
subarray will be randomly selected.

Devise an algorithm for maximizing the sum of the randomly selected
elements from the k subarrays. Basically means that we will want to split
the array in such way such that the sum of all the expected values for the
elements selected from each subarray is maximum.

You can assume that n is a power of 2.

Example:

Array: [0,0,1,1,0,0,1,1,0,1,1,0]
n = 12
k = 3
Size of subarrays can be: 2,3,4,5,6

Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
Expected Value of the sum of the elements randomly selected from the
subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433

Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333


Source ->  
http://stackoverflow.com/questions/8189334/google-combinatorial-optimization-interview-problm

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

[Ankur Garg]

^^+1..how matrix formed ??
But as Gene said we can use a set to store all the unique elements

Now we xor all the set elements and then xor them with the elements of the
array . This wud give us the repeating element as all the elements coming
once will be 0(xored twice) and repeating element wud be xored twice .

To code it as follows

int FindSingle(int a[],int n){
   sets;
   s.insert(a,a+n);
  set::iterator it;
  it = s.begin();
  int XOR= *it;
  it++;
 while(it!=s.end()){
   XOR =XOR^*it;
   it++;
}
 for(int i=0;iwrote:

> @Anup:
> Atleast u tell me how the M has formed???
>
>
> On 24 November 2011 11:21, Anup Ghatage  wrote:
>
>> @kunzmilan
>> Nice idea, how do you decide the row-size or column-size of the matrix?
>>
>>
>> On Thu, Nov 24, 2011 at 8:00 PM, kumar raja wrote:
>>
>>> @kunzmilan :
>>> Can u please maintain the clarity ??
>>> How did u find the M
>>>
>>> if the list is 4 2 8 9  5 1 9 how M looks like ?? please elaborate it...
>>>
>>>
>>> On 24 November 2011 06:15, kunzmize an  wrote:
>>>


 On 24 lis, 09:09, kumar raja  wrote:
 > @kunzmilan : i did not get  u, once explain with example...
 >
 > On 23 November 2011 23:47, kunzmilan  wrote:
 Matrix M
 0 1 0
 0 1 0
 1 0 0
 multiplied with M(T)
 0 0 1
 1 1 0
 0 0 0
 gives
 1 0 0
 0 2 0
 0 0 0.
 On its diagonal are numbers of repeated elements.
 kunzmilan

 >
 >
 >
 >
 >
 >
 >
 >
 >
 >
 >
 > > On 24 lis, 07:02, kumar raja  wrote:
 > > > In the given array all the elements occur single time except  one
 element
 > > > which occurs  2 times find it in O(n) time and O(1) space.
 >
 > > > e.g.  2 3 4 9 3 7
 >
 > > > output :3
 >
 > > > If such a solution exist can we extend the logic to find "All the
 > > repeated
 > > > elements in an array in O(n) time and O(1) space"
 >
 > > > --
 > > > Regards
 > > > Kumar Raja
 > > > M.Tech(SIT)
 > > > IIT Kharagpur,
 > > > 10it60...@iitkgp.ac.in
 > > > Write the list in the form of a matrix M, e.g.
 > > > 0 1 0 0...
 > > > 0 0 1 0...
 > > > 0 0 0 1...
 > > > ..etc.,
 > > > and its quadratic form M(T)M shows, how many times each element
 repeats.
 > > kunzmilan
 >
 > > --
 > > You received this message because you are subscribed to the Google
 Groups
 > > "Algorithm Geeks" group.
 > > To post to this group, send email to algogeeks@googlegroups.com.
 > > To unsubscribe from 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
 > Kumar Raja
 > M.Tech(SIT)
 > IIT Kharagpur,
 > 10it60...@iitkgp.ac.in

 --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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
>>> Kumar Raja
>>> M.Tech(SIT)
>>> IIT Kharagpur,
>>> 10it60...@iitkgp.ac.in
>>>
>>>
>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> Anup Ghatage
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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
> Kumar Raja
> M.Tech(SIT)
> IIT Kharagpur,
> 10it60...@iitkgp.ac.in
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Does Y lies between x and z

[Ankur Garg]

This approach would fail in certain cases :P..in fact lot many cases :D..It
needs to be modified using space


The thing is while calculating LCA we must also store the path in an Array
or vector and then Iterate over its elements to check if match occurs.

Cant think of O(1) solution though :(









On Fri, Nov 25, 2011 at 12:57 AM, Ankur Garg  wrote:

> As it seems to me this can be solved like this
>
> Find LCA(Least common ancestor) of node x and z .. See if it equals y or
> not . If not recursively search for y in left and right subtree of LCA ..If
> you find y in the descendents of LCA answer is true else its false .
>
> This method will give perfect answer just that complexity would be a bit
> large (greater than n)  but space wll be O(1) neglecting stack space during
> recursive calls
>
> I coded the same and it works to me ..
>
> If anyone can suggest a finer approach  that wud be great :)
>
> Regards
> Ankur
>
>
> On Thu, Nov 24, 2011 at 11:28 PM, Nitin Garg wrote:
>
>> Please explain what do you mean by 'path between x and z'.
>>
>>
>> On Wed, Nov 23, 2011 at 11:46 PM, Ankuj Gupta wrote:
>>
>>> There is a binary tree (Not a BST) in which you are given three nodes
>>> X,Y, and Z .Write a function which finds whether y lies in the path b/
>>> w x and z.
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>
>>
>> --
>> Nitin Garg
>>
>> "Personality can open doors, but only Character can keep them open"
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] Does Y lies between x and z

[Ankur Garg]

As it seems to me this can be solved like this

Find LCA(Least common ancestor) of node x and z .. See if it equals y or
not . If not recursively search for y in left and right subtree of LCA ..If
you find y in the descendents of LCA answer is true else its false .

This method will give perfect answer just that complexity would be a bit
large (greater than n)  but space wll be O(1) neglecting stack space during
recursive calls

I coded the same and it works to me ..

If anyone can suggest a finer approach  that wud be great :)

Regards
Ankur

On Thu, Nov 24, 2011 at 11:28 PM, Nitin Garg wrote:

> Please explain what do you mean by 'path between x and z'.
>
>
> On Wed, Nov 23, 2011 at 11:46 PM, Ankuj Gupta  wrote:
>
>> There is a binary tree (Not a BST) in which you are given three nodes
>> X,Y, and Z .Write a function which finds whether y lies in the path b/
>> w x and z.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
> Nitin Garg
>
> "Personality can open doors, but only Character can keep them open"
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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: An Array Problem

[Ankur Garg]

@Gene

Your algo is also right...Just that I followed techcoders logic and coded
the same...pair I used to map the index of the element ..But urs working
fine too :)

On Wed, Nov 23, 2011 at 7:04 PM, Gene  wrote:

> Sorry I forgot to initialize p. It's fixed below.
>
> On Nov 23, 6:59 am, Gene  wrote:
> > Thanks. Maybe I'm not reading correctly, but tech coder's algorithm
> > doesn't mention anything about pairs, which are necessary to obtain
> > O(n).  This is what I meant by "almost."
> >
> > In reverse order, you don't need the pairs. Its simpler.
> >
> > In a subroutine like yours,
> >
> > void find_smaller_to_right(int *a, int n)
> > {
> >   int i, in, p=0, stk[n]; // C99 var length array
> >   for (i = n - 1; i >= 0; i--) {
> > in = a[i];
> > while (p > 0 && stk[p - 1] >= in) p--;  // pop
> > a[i] = (p > 0) ? stk[p - 1] : 0;
> > stk[p++] = in;  // push
> >   }
> >
> > }
> >
> > On Nov 23, 5:13 am, Ankur Garg  wrote:
> >
> >
> >
> > > Solution given by tech coder is fine and is working .. I coded it and
> its
> > > working perfectly using stack
> >
> > > On Wed, Nov 23, 2011 at 2:50 PM, Gene  wrote:
> > > > It's a nice problem, and this solution is almost right.
> >
> > > > Process the input in _reverse_ order, which means we'll also generate
> > > > output in reverse order.
> >
> > > > The invariant is that the stack is a sorted list - highest value on
> > > > top - of the strictly descending subsequence of elements seen so far
> > > > in reverse.
> >
> > > > So when we get a new input, we want to search backward through the
> > > > stack to find the first smaller element. This is handy however,
> > > > because the new input also means that when we search past an element,
> > > > it's too big to maintain the invariant, so it must be popped!  We can
> > > > both find the output value and update the stack at the same time:
> >
> > > > stack = empty
> > > > for next input I in _reverse order_
> > > >  while stack not empty and top of stack is >= I
> > > >pop and throw away top of stack
> > > >  if stack is empty, output is zero
> > > >  else output top of stack
> > > >  push I
> > > > end
> >
> > > > Since each item is pushed and popped no more than once, this is O(n).
> >
> > > > Here's your example:
> >
> > > > #include 
> >
> > > > int main(void)
> > > > {
> > > >  int in[] = { 1, 5, 7, 6, 3, 16, 29, 2, 7 };
> > > >  int n = sizeof in / sizeof *in - 1;
> > > >  int out[100], stk[100], p = 0, i;
> >
> > > >  for (i = n - 1; i >= 0; i--) {
> > > >while (p && stk[p - 1] >= in[i]) p--;
> > > >out[i] = (p > 0) ? stk[p - 1] : 0;
> > > >stk[p++] = in[i];
> > > >  }
> > > >  for (i = 0; i < n; i++) printf(" %d", out[i]);
> > > >  printf("\n");
> > > >  return 0;
> > > > }
> >
> > > > On Nov 22, 2:20 pm, Aamir Khan  wrote:
> > > > > On Tue, Nov 22, 2011 at 11:50 PM, tech coder <
> techcoderonw...@gmail.com
> > > > >wrote:
> >
> > > > > > here is an O(n) approach  using  a stack.
> >
> > > > > > problem can be stated as " find the 1st smaller element on the
> right.
> >
> > > > > > put the first element in stack.
> > > > > > take next element suppose "num"  if this number is less than
> elements
> > > > > >  stored in stack, pop those elements , for these pooped elements
>  num
> > > > will
> > > > > > be the required number.
> > > > > > put the the element (num)   in stack.
> >
> > > > > > repeat this.
> >
> > > > > > at last the elements which are in next , they will have 0
> (valaue)
> >
> > > > > > @techcoder : If the numbers are not in sorted order, What
> benefit the
> >
> > > > > stack would provide ? So, are you storing the numbers in sorted
> order
> > > > > inside the stack ?
> >
> > > > > I can think of this solution :
> >
> > > > > Maintain a stack in which the elements will be stored in sorted
> or

Re: [algogeeks] Re: An Array Problem

[Ankur Garg]

Here is my code with logic techcoder described ...

void PushSmallerElement(int a[],int n){
   stack >s;
   pairp;
   int top;
   for(int i=0;i(a[i],i));
   else{
  p=s.top();
  while( !s.empty() && a[i](a[i],i));
   }
   while(!s.empty()){
  p=s.top();
  s.pop();
  a[p.second]=0;
   }
}

On Wed, Nov 23, 2011 at 3:43 PM, Ankur Garg  wrote:

> Solution given by tech coder is fine and is working .. I coded it and its
> working perfectly using stack
>
>
>
> On Wed, Nov 23, 2011 at 2:50 PM, Gene  wrote:
>
>> It's a nice problem, and this solution is almost right.
>>
>> Process the input in _reverse_ order, which means we'll also generate
>> output in reverse order.
>>
>> The invariant is that the stack is a sorted list - highest value on
>> top - of the strictly descending subsequence of elements seen so far
>> in reverse.
>>
>> So when we get a new input, we want to search backward through the
>> stack to find the first smaller element. This is handy however,
>> because the new input also means that when we search past an element,
>> it's too big to maintain the invariant, so it must be popped!  We can
>> both find the output value and update the stack at the same time:
>>
>> stack = empty
>> for next input I in _reverse order_
>>  while stack not empty and top of stack is >= I
>>pop and throw away top of stack
>>  if stack is empty, output is zero
>>  else output top of stack
>>  push I
>> end
>>
>> Since each item is pushed and popped no more than once, this is O(n).
>>
>> Here's your example:
>>
>> #include 
>>
>> int main(void)
>> {
>>  int in[] = { 1, 5, 7, 6, 3, 16, 29, 2, 7 };
>>  int n = sizeof in / sizeof *in - 1;
>>  int out[100], stk[100], p = 0, i;
>>
>>  for (i = n - 1; i >= 0; i--) {
>>while (p && stk[p - 1] >= in[i]) p--;
>>out[i] = (p > 0) ? stk[p - 1] : 0;
>>stk[p++] = in[i];
>>  }
>>  for (i = 0; i < n; i++) printf(" %d", out[i]);
>>  printf("\n");
>>  return 0;
>> }
>>
>> On Nov 22, 2:20 pm, Aamir Khan  wrote:
>> > On Tue, Nov 22, 2011 at 11:50 PM, tech coder > >wrote:
>> >
>> > > here is an O(n) approach  using  a stack.
>> >
>> > > problem can be stated as " find the 1st smaller element on the right.
>> >
>> > > put the first element in stack.
>> > > take next element suppose "num"  if this number is less than elements
>> > >  stored in stack, pop those elements , for these pooped elements  num
>> will
>> > > be the required number.
>> > > put the the element (num)   in stack.
>> >
>> > > repeat this.
>> >
>> > > at last the elements which are in next , they will have 0 (valaue)
>> >
>> > > @techcoder : If the numbers are not in sorted order, What benefit the
>> >
>> > stack would provide ? So, are you storing the numbers in sorted order
>> > inside the stack ?
>> >
>> > I can think of this solution :
>> >
>> > Maintain a stack in which the elements will be stored in sorted order.
>> Get
>> > a new element from array and lets call this number as m. Push m into the
>> > stack. Now, find all elements which are <= (m-1) using binary search.
>> Pop
>> > out all these elements and assign the value m in the output array.
>> Elements
>> > remaining at the end will have the value 0.
>> >
>> > I am not sure about the complexity of this algorithm...
>> >
>> >
>> >
>> >
>> >
>> > > On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage 
>> wrote:
>> >
>> > >> I can't think of a better than O(n^2) solution for this..
>> > >> Any one got anything better?
>> >
>> > >> On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta 
>> wrote:
>> >
>> > >>> Input: A unsorted array of size n.
>> > >>> Output: An array of size n.
>> >
>> > >>> Relationship:
>> >
>> > >>> > elements of input array and output array have 1:1 correspondence.
>> > >>> > output[i] is equal to the input[j] (j>i) which is smaller than
>> > >>> input[i] and jth is nearest to ith ( i.e. first element which is
>> smaller).
>> > >>> > If no such element exists for Input[i] then output[i]=0.
>> >
>> >

Re: [algogeeks] Re: An Array Problem

[Ankur Garg]

Solution given by tech coder is fine and is working .. I coded it and its
working perfectly using stack



On Wed, Nov 23, 2011 at 2:50 PM, Gene  wrote:

> It's a nice problem, and this solution is almost right.
>
> Process the input in _reverse_ order, which means we'll also generate
> output in reverse order.
>
> The invariant is that the stack is a sorted list - highest value on
> top - of the strictly descending subsequence of elements seen so far
> in reverse.
>
> So when we get a new input, we want to search backward through the
> stack to find the first smaller element. This is handy however,
> because the new input also means that when we search past an element,
> it's too big to maintain the invariant, so it must be popped!  We can
> both find the output value and update the stack at the same time:
>
> stack = empty
> for next input I in _reverse order_
>  while stack not empty and top of stack is >= I
>pop and throw away top of stack
>  if stack is empty, output is zero
>  else output top of stack
>  push I
> end
>
> Since each item is pushed and popped no more than once, this is O(n).
>
> Here's your example:
>
> #include 
>
> int main(void)
> {
>  int in[] = { 1, 5, 7, 6, 3, 16, 29, 2, 7 };
>  int n = sizeof in / sizeof *in - 1;
>  int out[100], stk[100], p = 0, i;
>
>  for (i = n - 1; i >= 0; i--) {
>while (p && stk[p - 1] >= in[i]) p--;
>out[i] = (p > 0) ? stk[p - 1] : 0;
>stk[p++] = in[i];
>  }
>  for (i = 0; i < n; i++) printf(" %d", out[i]);
>  printf("\n");
>  return 0;
> }
>
> On Nov 22, 2:20 pm, Aamir Khan  wrote:
> > On Tue, Nov 22, 2011 at 11:50 PM, tech coder  >wrote:
> >
> > > here is an O(n) approach  using  a stack.
> >
> > > problem can be stated as " find the 1st smaller element on the right.
> >
> > > put the first element in stack.
> > > take next element suppose "num"  if this number is less than elements
> > >  stored in stack, pop those elements , for these pooped elements  num
> will
> > > be the required number.
> > > put the the element (num)   in stack.
> >
> > > repeat this.
> >
> > > at last the elements which are in next , they will have 0 (valaue)
> >
> > > @techcoder : If the numbers are not in sorted order, What benefit the
> >
> > stack would provide ? So, are you storing the numbers in sorted order
> > inside the stack ?
> >
> > I can think of this solution :
> >
> > Maintain a stack in which the elements will be stored in sorted order.
> Get
> > a new element from array and lets call this number as m. Push m into the
> > stack. Now, find all elements which are <= (m-1) using binary search. Pop
> > out all these elements and assign the value m in the output array.
> Elements
> > remaining at the end will have the value 0.
> >
> > I am not sure about the complexity of this algorithm...
> >
> >
> >
> >
> >
> > > On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage 
> wrote:
> >
> > >> I can't think of a better than O(n^2) solution for this..
> > >> Any one got anything better?
> >
> > >> On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta 
> wrote:
> >
> > >>> Input: A unsorted array of size n.
> > >>> Output: An array of size n.
> >
> > >>> Relationship:
> >
> > >>> > elements of input array and output array have 1:1 correspondence.
> > >>> > output[i] is equal to the input[j] (j>i) which is smaller than
> > >>> input[i] and jth is nearest to ith ( i.e. first element which is
> smaller).
> > >>> > If no such element exists for Input[i] then output[i]=0.
> >
> > >>> Eg.
> > >>> Input: 1 5 7 6 3 16 29 2 7
> > >>> Output: 0 3 6 3 2 2 2 0 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.
> >
> > >> --
> > >> Anup Ghatage
> >
> > >>  --
> > >> You received this message because you are subscribed to the Google
> Groups
> > >> "Algorithm Geeks" group.
> > >> To post to this group, send email to algogeeks@googlegroups.com.
> > >> To unsubscribe from 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*
> > > *"The Coder"*
> >
> > > *"Life is a Game. The more u play, the more u win, the more u win , the
> > > more successfully u play"*
> >
> > >  --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > --
> > Aamir Khan | 3rd Year  | C

Re: [algogeeks] Re: Soritng

[Ankur Garg]

I think Merge Sort doesnt require any swapping . So , for 3 my answer wud
be Merge Sort

On Mon, Nov 21, 2011 at 11:55 AM, Dave  wrote:

> @Kumar: For question 1, the answer is radix sort. It doesn't use data
> comparisons at all.
>
> Dave
>
> On Nov 21, 12:04 am, kumar raja  wrote:
> > if we have set of n elements then
> >
> > 1) which sorting method uses least number of comparisons??
> >
> > 2) which sorting method uses least number of swaps??
> >
> > 3) suppose the array is 2 8 4 6 5 9
> > if we want to swap 8  and 5 the cost is 2(5-2)=6   .here 5 and 2 are
> > indices of 5 and 8.
> > so what sorting method minimizes the cost, i want the answer in general
> > case ,not for this particular array. it is also called least distance
> > sorting
> >
> > --
> > Regards
> > Kumar Raja
> > M.Tech(SIT)
> > IIT Kharagpur,
> > 10it60...@iitkgp.ac.in
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Linked List Problem-Suggest Algo

[Ankur Garg]

a linked list contains
2 19 _ _ 3 47 _ _ _ 2 20 _ _ ..and so on
I have to fill those empty nodes with numbers whose sum is equal to the
numbers
occurring just before the gaps and the number of gaps is determined by the
node
which is at 2 distance before the gaps with the limitation that their would
be no
repetition in list only the nodes designating the number of gaps can be
repeated
for example 2 20 should be broken in two parts like 19 1
3 47 should be broken in three parts like 42 2 3
and not in 44 1 2 because 1 already occurred in the list due previous
partition

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

[Ankur Garg]

Can u provide a pseudo code for the same and c if it works


On Thu, Nov 17, 2011 at 2:37 AM, sravanreddy001 wrote:

> Start with counting sort of the input.
> Use shuffling algorithm on it.
>
> Store index as cumulative sums of counts.
>
> --
> 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/-/0Uoq_OqBLn8J.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Google Question--Suggest Algo

[Ankur Garg]

Given a string of lowercase characters, reorder them such that the same
characters are at least distance d from each other.

Input: { a, b, b }, distance = 2
Output: { b, a, b }

How to approach this question ?

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

[Ankur Garg]

Radix Sort

On Mon, Nov 14, 2011 at 1:57 PM, Vijay Khandar wrote:

> Which is the sorting algm sorts the integers  [1...n^3]  in
> O(n).
> a)Heapsort
> b)Quicksort
> c)Mergesort
> d)Radix sort
>
> please tell anyone.
> Vijay.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Amazon Onsite Chennai SDE

[Ankur Garg]

We can use a trie here .. Create a trie with all words of dictionary .

Now delete the last character of the word and check if such a word is a
valid word . If not see if adding a new character can make it a valid word
. If not delete the next character and repeat the process again .

This is what I can think of here. Any other solutions/guesses ?



On Mon, Nov 14, 2011 at 12:43 PM, Aniket  wrote:

> You are given a word and a dictionary. Now propose an algorithm edit
> the word (insert / delete characters) minimally to get a word that
> also exists in the dictionary. Cost of insertion and deletion is same.
> Write pseudocode for it.
>
> Seems like minimum edit distance problem but some modification is
> needed.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Amazon Question

[Ankur Garg]

@Srinivas

Wat if the string is abc
then it reduces to cc :) ...So  size 2 can also be there.so u cant say it
will be 1 "always"

On Sun, Nov 13, 2011 at 12:01 AM, Srinivasa Chaitanya T <
tschaitanya@gmail.com> wrote:

>
>
> 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?
>>
>> 1) if the string a..aaa, or bb..bb, etc... string cannot be
> modified
> 2) if string starts with ac => this can be reduced to b -> aaac ->
> aab -> ac -> b
> 3) So if string not of type (1), then it can be reduced to single
> character "always" using  method 2
>e.g:
>   *aab*cacaab // first reduce aab to b
>   *bbc*acaab  // reduce bbc to c
>   *ca*caab
>   *bc*aab
>   *aaab*
>   c
> .. i guess u got the idea
>
>
>
>
>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
> T Srinivasa Chaitanya
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Amazon Question

[Ankur Garg]

Hey I coded it . The answer is either 2 or 1 ..So I guess you guys are rite
:)

Here is the code
void smallestString(string &str){
if(str.empty()) return;
int j=0,i,k=0;
for(i=1;i0)j--;
i=j;
  }
}
}

On Sat, Nov 12, 2011 at 8:19 PM, Nitin Garg wrote:

> If yes, how do you prove it?
>
>
> On Sat, Nov 12, 2011 at 8:18 PM, Nitin Garg wrote:
>
>> I can prove that the size of resulting string will be 1 or 2.
>>
>> @surender -
>> what do you mean by no of distinct characters? they are 3 in this case -
>> a,b and c.
>> Do you mean to say that the no. of times each character appears are equal
>> then the final string is of size 2. and 1 otherwise?
>>
>>
>> On Sat, Nov 12, 2011 at 4:57 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.
>>>
>>
>>
>>
>> --
>> Nitin Garg
>>
>> "Personality can open doors, but only Character can keep them open"
>>
>
>
>
> --
> Nitin Garg
>
> "Personality can open doors, but only Character can keep them open"
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Amazon Question

[Ankur Garg]

Did they ask you to code this or just asked logic



On Sat, Nov 12, 2011 at 4:57 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] Amazon Onsite

[Ankur Garg]

I think this can be solved like this .
Start from the first petrol pump i.e first point in the circle . Now if the
petrol finishes befor reaching the second petrol pump that means we chose
the incorrect point . So , choose second petrol pump now. If u reach third,
fill ur tanker and move to 4th . Now if before 4th we again run out of
petrol that means our choice was incorrect . Start from 4th and so on .. If
u reach the starting point again this is the choice we need to make ..and
thats the answer . Programatically , it can be thought of Kadane Algo
..(seems to me ..not sure of algo) but I think this way we just make at most
2 pass (in case the petrol pump of choice is just before the first point )
.

Please comment in case you think its  right/wrong

Regards
Ankur

On Mon, Oct 24, 2011 at 10:15 PM, ravindra patel
wrote:

> @Nitin, excellent algo.
>
> >> if S < 0 && j = i-1 return 0  // I believe this mean there is no
> solution, you might want to return -1.
>
>
> Thanks,
> - Ravindra
>
>
>
> On Mon, Oct 24, 2011 at 8:39 PM, Nitin Garg wrote:
>
>> Lets say the Amount of petrol is Pi and distance to next petrol pump is Di
>> for ith petrol pump.
>>
>> start from i=1, j=1 S =0
>> while (i<=n)
>>   S += Pj - Dj;
>>   if S >= 0 && j = i-1 return i
>>   if S < 0 && j = i-1 return 0
>>   else if S >= 0 j++ mod n;
>>   else  if S < 0  j ++ mod n, i = j , S = 0;
>>
>> return 0
>>
>>
>>
>> it will traverse atmost twice, and hence O(n). no extra space required.
>>
>>
>> On Mon, Oct 24, 2011 at 4:06 AM, Aniket  wrote:
>>
>>> Suppose there is a circle. You have five points on that circle. Each
>>> point corresponds to a petrol pump. You are given two sets of data.
>>>
>>> 1. The amount of petrol that petrol pump will give.
>>> 2. Distance from that petrol pump to the next petrol pump.
>>>
>>>
>>> (Assume for 1 lit Petrol the truck will go 1 km)
>>>
>>> Now calculate the first point from where a truck will be able to
>>> complete the circle.
>>> (The truck will stop at each petrol pump and it has infinite
>>> capacity).
>>> Give o(n) solution. You may use 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 algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>
>>
>> --
>> Nitin Garg
>>
>> "Personality can open doors, but only Character can keep them open"
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] Search an element in an Infinite array

[Ankur Garg]

@Bittu...When we choose low as 2^(n-1) and high as 2^n we are reducing the
complexity from O(n) (Linear Search ) to logn (base2) . Here the thing is to
apply normal binary search between low and high  and thats where we decrease
the complexity . If the required element is not in this range we change
low=high and high =  2*high and again apply Binary Search. In the code
before applying binary search u each time check whether k  wrote:

> @Ankur Don't think there's any major reason for using powers of 2 except
> the fact that computing the powers of 2 can be done very efficiently than
> computing the powers of any other number. Complexity in any case remains the
> same.
>
>
> On 24 October 2011 10:29, rahul sharma  wrote:
>
>> +1 ankur
>>
>>
>> On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg  wrote:
>>
>>> Use Binary Search
>>>
>>> start = 2^n-1 high =2^n where n=0,1
>>>
>>> On Mon, Oct 24, 2011 at 12:28 AM, sunny agrawal >> > wrote:
>>>
>>>> hint 1: try to find 2 indexes i, j such that a[i] <= K <= a[j]
>>>>
>>>>
>>>> On Sun, Oct 23, 2011 at 11:23 PM, Ankuj Gupta wrote:
>>>>
>>>>> Given a sorted array of Infinite size, find an element ‘K’ in the
>>>>> array without using extra memory in O (lgn) 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.
>>>>>
>>>>>
>>>>
>>>>
>>>> --
>>>> Sunny Aggrawal
>>>> B.Tech. V 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.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Bittu Sarkar
> 5th Year Dual Degree Student
> Department of Computer Science & Engineering
> Indian Institute of Technology Kharagpur
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Search an element in an Infinite array

[Ankur Garg]

Use Binary Search

start = 2^n-1 high =2^n where n=0,1

On Mon, Oct 24, 2011 at 12:28 AM, sunny agrawal wrote:

> hint 1: try to find 2 indexes i, j such that a[i] <= K <= a[j]
>
>
> On Sun, Oct 23, 2011 at 11:23 PM, Ankuj Gupta  wrote:
>
>> Given a sorted array of Infinite size, find an element ‘K’ in the
>> array without using extra memory in O (lgn) 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.
>>
>>
>
>
> --
> Sunny Aggrawal
> B.Tech. V 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: Inplace Array Convertion

[Ankur Garg]

@Sunny

Your technique of Inshuffle and Outshuffle are perfect. But how to translate
into the code without using extra space or say even constant space


On Tue, Oct 18, 2011 at 12:43 AM, Dan  wrote:

> I have a hard copy of the book (years back,  I implemented a fortran
> version of the algorithm described in the book).  I don't know if you
> can find an online version or not.  I'm sure there is stuff there.
> Have you done a simple Google search for "in place reorder
> array"  ??   It's not a difficult algorithm.  And Sedgewicks's books
> are well known.  Searches for his name may also yield results.
>
> Just FYI:  If your rearrangement doesn't have to be in-place...  you
> will achieve more speed by other methods.  I did testing with
> rearrangement of some very large data sets.  The in-place method was
> noticeably slower.  It also required you to write your own routine to
> do the reordering.  Using basic fortran, I could do the same thing in
> just one or two lines of very simple code.  The only advantage to the
> in-place algorithm is that it uses less memory.   This should only be
> important if you are dealing with some very large arrays.
>
> Dan   :-)
>
>
> On Oct 14, 9:44 pm, Ankur Garg  wrote:
> > @Dan ..can you post the algo here or link to the book??
> > @Anika ...yes please post the code here..but please explain a bit about
> > underlying algo ...(algo is more important than actual code )
> >
> >
> >
> >
> >
> >
> >
> > On Sat, Oct 15, 2011 at 1:54 AM, Dan  wrote:
> > > On Oct 13, 7:52 pm, "shiva@Algo"  wrote:
> > > > Convert an array "a1 a2 a3...an b1 b2 b3...bn c1 c2 c3...cn" to
> "a1b1c1
> > > > a2b2c2...anbncn", inplace
> >
> > > See the algorithm for memory efficient rearrangement of array elements
> > > in one of the books by Robert Sedgewick such as Algorithms in C++ or
> > > Algorithms in Pascal, etc.
> >
> > > Dan
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from 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] Amazon Ques Suggest Algo

[Ankur Garg]

{You are given an unsorted array of integers. You have to find out the first
sub array whose elements when added sum up to zero.
eg:- int Array[] = {1,2,-4,-3, 6 ,-3.}Here sub array is -3,6,-3 bcos
adding all these sum to zero. A sub array can be of size 2 to whole length
of the array. You can use extra space also for the same


Brute Force will do it in O(n^2). Any better way

I was thinking DP but couldnt find proper sub-problems and even if we do
cudnt figure out lesser than O(n^2) :(

Any suggestions?

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Amazon Question - Find Pythagorean triplet in an unsorted array

[Ankur Garg]

@Shashank ..+1 ..I wud say he must be given a tuning award :D :D  for
solving such eternal conundrum ;)



On Mon, Oct 17, 2011 at 2:37 PM, WgpShashank wrote:

> @wladimir , its PPT (Pythagoras triplets ) but its number theory based
> approach  http://en.wikipedia.org/wiki/Pythagorean_triple might not be
> good idea
>
> Here is approach :
> *
> *
> *Euclid's 
> formula*[1] is
> a fundamental formula for generating Pythagorean triples given an arbitrary
> pair of positive integers *m* and *n* with *m* > *n*. The formula states
> that the integers p=m^2-n^2 , q=2mn r=m^2+n^2  , we have to sort the array
> in non-increasing order  , then for each m>n we have to generate the  all
> such p,q,r in worst case it will also requires O(N^2) such p,q,r for each
> M>N isn't it ? then its not less then O(n^2) ??
> Even with this approach,The triple generated by Euclid's formula is
> primitive if and only if *m* and *n* are coprime and *m*-*n* is odd. If
> both *m* and *n* are odd, then *a*, *b*, and *c* will be even, and so the
> triple will not be primitive; however, dividing *a*, *b*, and *c* by 2
> will yield a primitive triple if *m* and *n* are coprime.
>
> @all other , its similar to 3 sun , can't be done in less then O(N^2) if
> number are not in range , When the integers are in the range [-*u* ... *u*],
> 3SUM can be solved in time O(n + *u* lg *u*) by representing *S* as a bit
> vector and performing a discrete convolution using FFT.
>
> i wondered if any other  algo/code/link you have which works in less then
> O(N^2) , Better if One Explain The Approach or Algorithm , You Might able to
> fill Patent :D
>
> Thanks
> Shashank
> CSE, BIT Mesra
>
> --
> 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/-/JQWWHDKMCiAJ.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Amazon Question - Find Pythagorean triplet in an unsorted array

[Ankur Garg]

*Turing :P

On Mon, Oct 17, 2011 at 3:51 PM, Ankur Garg  wrote:

> @Shashank ..+1 ..I wud say he must be given a tuning award :D :D  for
> solving such eternal conundrum ;)
>
>
>
> On Mon, Oct 17, 2011 at 2:37 PM, WgpShashank 
> wrote:
>
>> @wladimir , its PPT (Pythagoras triplets ) but its number theory based
>> approach  http://en.wikipedia.org/wiki/Pythagorean_triple might not be
>> good idea
>>
>> Here is approach :
>> *
>> *
>> *Euclid's 
>> formula*[1]<http://en.wikipedia.org/wiki/Pythagorean_triple#cite_note-0> is
>> a fundamental formula for generating Pythagorean triples given an arbitrary
>> pair of positive integers *m* and *n* with *m* > *n*. The formula states
>> that the integers p=m^2-n^2 , q=2mn r=m^2+n^2  , we have to sort the array
>> in non-increasing order  , then for each m>n we have to generate the  all
>> such p,q,r in worst case it will also requires O(N^2) such p,q,r for each
>> M>N isn't it ? then its not less then O(n^2) ??
>> Even with this approach,The triple generated by Euclid's formula is
>> primitive if and only if *m* and *n* are coprime and *m*-*n* is odd. If
>> both *m* and *n* are odd, then *a*, *b*, and *c* will be even, and so the
>> triple will not be primitive; however, dividing *a*, *b*, and *c* by 2
>> will yield a primitive triple if *m* and *n* are coprime.
>>
>> @all other , its similar to 3 sun , can't be done in less then O(N^2) if
>> number are not in range , When the integers are in the range [-*u* ... *u
>> *], 3SUM can be solved in time O(n + *u* lg *u*) by representing *S* as a
>> bit vector and performing a discrete convolution using FFT.
>>
>> i wondered if any other  algo/code/link you have which works in less then
>> O(N^2) , Better if One Explain The Approach or Algorithm , You Might able to
>> fill Patent :D
>>
>> Thanks
>> Shashank
>> CSE, BIT Mesra
>>
>> --
>> 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/-/JQWWHDKMCiAJ.
>>
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] print vertical sums of a binary tree

[Ankur Garg]

Sorry code got reposted twice here is the correct one
void getLevelSum(node* root,int level,int &minL,int &maxR,int left[],int
right[]){
if(!root) return ;
minL = min(minL,level);
maxR = max(maxR,level);
getLevelSum(root->left,level-1,minL,maxR,left,right);
getLevelSum(root->right,level+1,minL,maxR,left,right);
if(level<0)
  left[abs(level)] +=root->data;
else
  right[level] +=root->data;
}
On Sun, Oct 16, 2011 at 4:23 PM, Ankur Garg  wrote:

> I am assuming we are allowed to use space ..With that i make 2 arrays 1 to
> store values from left side and other from right side .
>
> Here is the func
>
>
> void getLevelSum(node* root,int level,int &minL,int &maxR,int left[],int
> right[]){
> if(!root) return ;
> minL = min(minL,level);
> maxR = max(maxR,level);
> getLevelSum(root->left,level-1,minL,maxR,left,right);
> getLevelSum(root->right,level+1,minL,maxR,left,right);
> if(level<0)
>   left[abs(level)] +=root->data;
> else
>   right[level] +=root->data;
> }
>
> I am traversing whole tree nodes only once but storing them in an array so
> Space complexity is also O(n) for me
>
> Anyone having a better solution or approach ?
>
>
> On Sun, Oct 16, 2011 at 9:27 AM, SUMANTH M  wrote:
>
>> Hi,
>>
>>A binary tree is given we need to print vertical sums of nodes. for
>> example
>>
>>   12  34 5
>>
>>   |  |   5| |
>>   |  | / |   \ | |
>>   |  |   /   |8 |
>>   |  | / |   / |\|
>>   |  4  |/|   10
>>   |/ |  \9| |
>>   |  /   |  \  | |
>>   7 |  6   |
>>   |  |  |  | |
>>   |  |  |  | |
>>   ---
>>   7 4 20   8   10
>>
>>  Here we need to print sum 7,4,20,8,10.
>>
>> -Thanks
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] print vertical sums of a binary tree

[Ankur Garg]

I am assuming we are allowed to use space ..With that i make 2 arrays 1 to
store values from left side and other from right side .

Here is the func


void getLevelSum(node* root,int &minL,int &maxR,int level){
if(!root) return ;
minL = min(minL,level);
maxR = max(maxR,level);
getLevelSum(root->left,minL,maxR,level-1);
getLevelSum(root->right,minL,maxR,level+1);
}
void getLevelSum(node* root,int level,int &minL,int &maxR,int left[],int
right[]){
if(!root) return ;
minL = min(minL,level);
maxR = max(maxR,level);
getLevelSum(root->left,level-1,minL,maxR,left,right);
getLevelSum(root->right,level+1,minL,maxR,left,right);
if(level<0)
  left[abs(level)] +=root->data;
else
  right[level] +=root->data;
}
I am traversing whole tree nodes only once but storing them in an array so
Space complexity is also O(n) for me

Anyone having a better solution or approach ?


On Sun, Oct 16, 2011 at 9:27 AM, SUMANTH M  wrote:

> Hi,
>
>A binary tree is given we need to print vertical sums of nodes. for
> example
>
>   12  34 5
>
>   |  |   5| |
>   |  | / |   \ | |
>   |  |   /   |8 |
>   |  | / |   / |\|
>   |  4  |/|   10
>   |/ |  \9| |
>   |  /   |  \  | |
>   7 |  6   |
>   |  |  |  | |
>   |  |  |  | |
>   ---
>   7 4 20   8   10
>
>  Here we need to print sum 7,4,20,8,10.
>
> -Thanks
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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: Inplace Array Convertion

[Ankur Garg]

@Sunny ..Superb Algo ..but can you share some link where we can read abt it
 :)..especially where the info abt the equation u used is given


Thanks in Advance

On Sat, Oct 15, 2011 at 12:37 PM, Kunal Patil  wrote:

> @Sunny: Thanks for the info !! That's gr8..& your logic also seems to be
> working perfectly fine..
>
>
> On Sat, Oct 15, 2011 at 12:16 PM, shady  wrote:
>
>> u can always post the code.,... but before posting code, you must state
>> your algorithm
>>   else code becomes useless for other users
>>
>> On Sat, Oct 15, 2011 at 1:10 AM, Anika Jain wrote:
>>
>>> i have the code solution to this.. if m allowed to post it here then i
>>> can i post it. m i allowed to post code here?
>>>
>>>
>>> On Fri, Oct 14, 2011 at 9:40 PM, gaurav yadav >> > wrote:
>>>
 @shiva...keep swapping the underline elements

 a1*a2*a3a4a5*b1*b2b3b4b5c1c2c3c4c5
 a1b1*a3*a4a5a2b2b3b4b5*c1*c2c3c4c5
 a1b1c1*a4*a5*a2*b2b3b4b5a3c2c3c4c5
 a1b1c1a2*a5*a4*b2*b3b4b5a3c2c3c4c5
 a1b1c1a2b2*a4*a5b3b4b5a3*c2*c3c4c5
 a1b1c1a2b2c2*a5*b3b4b5*a3*a4c3c4c5
 a1b1c1a2b2c2a3b3*b4*b5a5a4*c3*c4c5
 a1b1c1a2b2c2a3b3c3*b5*a5*a4*b4c4c5
 a1b1c1a2b2c2a3b3c3a4*a5*b5*b4*c4c5
 a1b1c1a2b2c2a3b3c3a4b4*b5*a5*c4*c5
 a1b1c1a2b2c2a3b3c3a4b4*c4*a5*b5*c5
 a1b1c1a2b2c2a3b3c3a4b4c4a5b5c5



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

[Ankur Garg]

@Dan ..can you post the algo here or link to the book??
@Anika ...yes please post the code here..but please explain a bit about
underlying algo ...(algo is more important than actual code )



On Sat, Oct 15, 2011 at 1:54 AM, Dan  wrote:

> On Oct 13, 7:52 pm, "shiva@Algo"  wrote:
> > Convert an array "a1 a2 a3...an b1 b2 b3...bn c1 c2 c3...cn" to "a1b1c1
> > a2b2c2...anbncn", inplace
>
>
> See the algorithm for memory efficient rearrangement of array elements
> in one of the books by Robert Sedgewick such as Algorithms in C++ or
> Algorithms in Pascal, etc.
>
> Dan
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Amazon Question - Find Pythagorean triplet in an unsorted array

[Ankur Garg]

@Rahul

Pls elaborate with an example ...

On Fri, Oct 14, 2011 at 2:35 PM, rahul patil
wrote:

> You can take advantage of a basic property of triagle that
>
> sum of largest side of triangle < sum of other two sides,
>
> After sorting you could easily deside the range in which possible solution
> could be found for a chosen hypotenuse
>
> On Fri, Oct 14, 2011 at 11:10 AM, ravindra patel  > wrote:
>
>> @Wladimir, yeah I have heard about that. Another way of populating
>> primitive pythagoreans is, for any natural number m > 1  (m^2 - 1, 2m, m^2 +
>> 1) forms a pythagorean triplet. This is useful in populating pythagorean
>> tiplets but here the problem is to search such triplets from a given int
>> array.
>>
>> @ rahul, Hash of z^2 - x^2 for each pair of z,x itself will of the size
>> n*(n-1). I am not sure how it will work in O(n) time then.
>>
>> Thanks,
>> - Ravindra
>>
>>
>> On Fri, Oct 14, 2011 at 12:25 AM, Ankur Garg wrote:
>>
>>> @rahul...How do u choose z and x for computing z^2 -x^2 ?
>>>
>>> On Thu, Oct 13, 2011 at 11:34 PM, rahul  wrote:
>>>
>>>> You can create a hash with sqrt(z2-x2). This will make it o(n). The
>>>> interviewer just made it lil tricky. That's all
>>>>
>>>> --
>>>> 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/-/2Ge2pjt4N-4J.
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from 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.
>>
>
>
>
> --
> Regards,
> Rahul Patil
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Amazon Question - Find Pythagorean triplet in an unsorted array

[Ankur Garg]

@rahul...How do u choose z and x for computing z^2 -x^2 ?

On Thu, Oct 13, 2011 at 11:34 PM, rahul  wrote:

> You can create a hash with sqrt(z2-x2). This will make it o(n). The
> interviewer just made it lil tricky. That's all
>
> --
> 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/-/2Ge2pjt4N-4J.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Amazon Question - Find Pythagorean triplet in an unsorted array

[Ankur Garg]

BTW can we solve this by hashing..That is the only feasible solution which
comes to my mind to reduce the time complexity ?

On Thu, Oct 13, 2011 at 11:20 PM, Ankur Garg  wrote:

> Dude this is nothing but 3 sum problem
>
> http://en.wikipedia.org/wiki/3SUM
>
> Ask interviewer to check this link and say he has gone mad!! :P
>
> Regards
> Ankur
>
> On Thu, Oct 13, 2011 at 10:29 PM, ravindra patel  > wrote:
>
>> Hi,
>> Another question I faced in Amazon F2F.
>>
>> Given an unsorted array of integers, find all triplets that satisfy x^2 +
>> y^2 = z^2.
>>
>> For example if given array is -  1, 3, 7, 5, 4, 12, 13
>> The answer should be -
>> 5, 12, 13 and
>> 3, 4, 5
>>
>> I suggested below algo with complexity O(n^2) -
>>
>> - Sort the array in descending order. - O(nlogn)
>> - square each element. - O(n)
>>
>> Now it reduces to the problem of  finding all triplets(a,b,c) in a
>> sorted array such that a = b+c.
>>
>> The interviewer was insisting on a solution better than O(n^2) which I
>> dont think is feasible, but I couldn't prove that. Anyone has any idea.
>>
>>
>>
>> Thanks,
>> - Ravindra
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] Amazon Question - Find Pythagorean triplet in an unsorted array

[Ankur Garg]

Dude this is nothing but 3 sum problem

http://en.wikipedia.org/wiki/3SUM

Ask interviewer to check this link and say he has gone mad!! :P

Regards
Ankur

On Thu, Oct 13, 2011 at 10:29 PM, ravindra patel
wrote:

> Hi,
> Another question I faced in Amazon F2F.
>
> Given an unsorted array of integers, find all triplets that satisfy x^2 +
> y^2 = z^2.
>
> For example if given array is -  1, 3, 7, 5, 4, 12, 13
> The answer should be -
> 5, 12, 13 and
> 3, 4, 5
>
> I suggested below algo with complexity O(n^2) -
>
> - Sort the array in descending order. - O(nlogn)
> - square each element. - O(n)
>
> Now it reduces to the problem of  finding all triplets(a,b,c) in a
> sorted array such that a = b+c.
>
> The interviewer was insisting on a solution better than O(n^2) which I dont
> think is feasible, but I couldn't prove that. Anyone has any idea.
>
>
>
> Thanks,
> - Ravindra
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] remove duplicate words from a string

[Ankur Garg]

@Sunny..How do u intend to store them in a Tree ? Can you explain ?

In a trie u first insert the first word ..take the second word..If its not
present in the trie u insert it else remove it from original string
.Alternatively u store the elements in a trie in the initial string and
terminate it with '\0' and return it . In the worst case trie will take O(n)
space where n is the no of letters in the string . and Traversal  and
creation and search too will take O(n).

How abt Balanced Binary Tree ?

On Tue, Oct 11, 2011 at 12:38 AM, sunny agrawal wrote:

> Trie will take too much space..
> Balanced Binary tree can be Better ...??
>
>
> On Tue, Oct 11, 2011 at 12:16 AM, Ankur Garg  wrote:
>
>> I think this can be done through tries
>>
>> Any better solution ?
>>
>> On Mon, Oct 10, 2011 at 10:59 PM, sachin goyal wrote:
>>
>>> remove duplicate words from a string with min. complexityy.
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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. V 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] remove duplicate words from a string

[Ankur Garg]

I think this can be done through tries

Any better solution ?

On Mon, Oct 10, 2011 at 10:59 PM, sachin goyal wrote:

> remove duplicate words from a string with min. complexityy.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Memorization

[Ankur Garg]

Memoization ?

On Mon, Oct 10, 2011 at 6:34 PM, arvind kumar  wrote:

> Can anyone tell me how to go about with the memorization technique to
> retrieve values from already stored values,in case of eveluating
> sequences(fibonacci series,etc).?
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Give Algo to do this in O(n)

[Ankur Garg]

@Sravan ..Counting Sort takes O(n) time but it needs range of nos to be
known
@Snehi jain..there is no range given so am not sure if count sort will work
,Can you please elaborate a bit on ur method

Ankur

On Mon, Oct 10, 2011 at 10:09 PM, sravanreddy001
wrote:

> Just went throught what a count sort is at
> http://en.wikipedia.org/wiki/Counting_sort
>
> If all the elements are distinct which is possible, will this count sort
> have any use?
>
> Also, the sorting takes O(nlogn) time right?
>
> Did I miss anything?
>
>  --
> 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/-/08bcRsmFYJgJ.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Algo for Search in a 2D Matrix

[Ankur Garg]

Given a 2D matrix which is both row wise and column wise sorted. Propose an
algorithm for finding the kth smallest element in it in least time
complexity

A General Max Heap can be used with k space and n+klogk complexity

Any other solution  or even a way by which we dont scan the whole matrix to
find the solution ?

I

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

[Ankur Garg]

Given an unsorted array of Integers

Find 2 nos whose diff is minimum

Say Array is  4 2 18 19 11 8 5

Nos are 18 and 19

Algo shud be of O(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] i cannot solve this written test question

[Ankur Garg]

Is it sum of bits or sum of digits ?

On Sun, Oct 9, 2011 at 1:39 PM, wujin chen  wrote:

> Given a positive number N, find a minimum number M greater than N, M  has
> the same length with N and the sum of the bits are equal.
>
> example:
> N=134 , M=143,  // 1+3+4=1+4+3
> N=020, M = 101, //2=1+1
>
> the length of N is less than 1000.
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Deletion in AVL tree

[Ankur Garg]

Can anyone suggest a pseudocode handling rotations in an AVL tree for
deleting a node

I couldnt find one in the internet and was unable to derive a proper logic
which cud be transformed into code :(

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

[Ankur Garg]

+1

On Sun, Oct 9, 2011 at 2:07 AM, Sunny  wrote:

> Now All of the messages are being Moderated and will be posted on the
> group only if they are found relevant, any irrelevant post be simply
> discarded without any notification till percentage of irrelevant posts
> reduces by a significant amount.
> if someone is found posting too many irrelevant post, he/she will be
> banned.
>
> Irrelevant Posts
> 1. Any Company Interview Question (Except Google, Facebook only)
> 2. Any Code Debugging Post (of type Plz Debug my code "You should be
> able to do it yourself")
> 3. any kind of C/C++ output question.
> 4. Any Company related Queries
> 5. Any Book Requests
> 6. Any Post having No subjects. (if Subject are there they must be
> related and Give idea about the post. and again Don't post the
> complete Question in the subject. it should be posted in the body of
> the message)
>
> + Any OS compiler or other topics unless it requires some good Quality
> discussion.
>
> All the above types of post (Except 6) are now part of new group
> Interview Street (search Archives for the link).
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Efficient Algo for Merging 2 Binary Search Trees

[Ankur Garg]

Hi ,

Can anyone think of any better for doing this other than converting into
List and then converting back again to BST ..

Regards

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

[Ankur Garg]

To do inplace stack reversal u need a mechanism by which u can transfer the
first node to last of the stack  making sure u have count of other nodes
here

Say u have stack

5<- top
4
3
2
1

The answer should generate the stack as
1-&s){
   if(s.empty()) return;
   temp=s.top();
   s.pop();
   InplaceReverse(s);
}

Now if one had to  print the stack nodes from bottom to top this would have
helped as we get to bottom of stack.But we need a storing mechanism so may
be one more recursive function can help so that we can pop the nodes first
and then insert the top node

Say the stack at a pt of time is
1<-top
2

Then to insert 3 at bottom we shud have some mechanism which can store
values 1 and 2

So u pop 1 and pop 2  ..Insert 2 and then Insert 1
1<- top
2
3

Only way to achieve this without using extra space is another recursion .So
 I write a helper func which can help me here to achieve this. I call this
helper Func as something like ReverseHelper and push the temp variable to it
.

So

InplaceReverse(stack&s){
   if(s.empty()) return;
   temp=s.top();
   s.pop();
   InplaceReverse(s);
   ReverseHelper(s,temp);
}
ReverseHelper(stack&s,int val){
 if(s.empty()) {
  s. push(val);
 return;
 }
temp = s.pop();
   ReverseHelper(s,val);
  s.push(temp);
}

Remember to pass stack as reference

Regards
Ankur

}




On Fri, Oct 7, 2011 at 7:54 PM, sravanreddy001 wrote:

> in place means:
>
> use constant extra space
>
> in simple terms O(1) space
>
>  --
> 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/-/nDVS4k7fF34J.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] amazon,microsoft link list probs

[Ankur Garg]

Implement recursive merge sort for first question

For second just swap the values of node and node b



On Wed, Oct 5, 2011 at 9:18 PM, 9ight coder <9ightco...@gmail.com> wrote:

> 1.perform inplace(we cant create new node)merge sort of two sorted
> linked list.(asked in amazon 1 mon before)
> 2.a->b->c->d->e  convert to b->a->d->c->e  without creating new node.
> (asked in microsoft on 4rth oct at thapar).
>
> sugeest solutions.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Amazon Ques

[Ankur Garg]

Find out the smallest segment in a document containing all the given words.
Desired Complexity is O nlogK  ..n is the total no of words in the document
and k is the number of input words

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

[Ankur Garg]

Code for Compression

I am doing it inplace

void convert(char* s,int len){
int i=0;
int count=1;
int index=1; //*maintain the index where number is to be added*
for(i=1;i<=len;i++){
   if(s[i]==s[i-1])
   count++;
   else{
   s[index-1]=s[i-1];*//put the char first like a3abbb . then this
step converts it into a3*
   s[index]= (count+'0');/*/convert the count integer into char  so
it becomes a3b4bb*
   count=1;
   index = index+2;
   }
}
s[index-1]='\0'*;//terminate the string* *(a3b4bb will become a3b4)*
}

On Mon, Oct 3, 2011 at 12:12 PM, rahul sharma wrote:

> check my code for compression..
>
> check if it is ok
> abc i/p
> o/p abc
>
> means if character has no count.but still present in string it is its only
> occurance.plz check that code...
>
> #include
> #include
> int main()
> {
> cout<<"\nenter the string";
> char str[30];
> cin>>str;
> int c=1;
> for(int i=0;str[i];i++)
> {
> if(str[i+1]>='0' && str[i+1]<='9')
> {
> c=c+(str[i+1]-'0');
> for(int j=1;j cout<   i++;
>
> }
>
>else
>cout
>
> }
>
> getch();
>
>}
>
>
>
> On Mon, Oct 3, 2011 at 12:08 PM, Rahul Verma wrote:
>
>> @rahul sharma
>>
>> for that you have to check that string is alphanumeric or not. if it is
>> alphanumeric then you have to call the function exapansion else you have to
>> call the compression function.
>>
>> and
>>
>> if the desired output for *abc *is *a1b1c1* then you have to call the 
>> *exapnsion
>> function* or if the desired output is *abc* then you have to add a
>> feature in the *compression function* i.e. in output the string have to
>> omit the 1's
>>
>> --
>> 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/-/8olzJ_YJVWMJ.
>>
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] rise and fall of power

[Ankur Garg]

Keep an array to store multiplication of numbers like for input

9 3
U have to compute 9^9

So an array to store the digits and do simple multiplication like 9*9  will
give 81 so Array will have 81

then 81*9  729  ..so on

Then output the first k digits and last k digits of the array

Any1 having a better solution ?

On Mon, Oct 3, 2011 at 11:48 PM, g4ur4v  wrote:

> can anyone please help me on how to approach this problem=>
> http://www.codechef.com/problems/MARCHA4
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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: Urgent sol needed

[Ankur Garg]

Many times this problem has been discussed ..Please check the archives yaar
:(


On Mon, Oct 3, 2011 at 11:39 PM, Shruti Gupta wrote:

> I had inserted 0 instead of 1 The corrected code will be:
>  public static void setZeros(int[][] matrix) {
>int[] row = new int[matrix.length];
>int[] column = new int[matrix[0].length];
>// Store the row and column index with value 0
>  for (int i = 0; i < matrix.length; i++) {
> for (int j = 0; j < matrix[0].length;j++) {
> if (matrix[i][j] == 1) {
>   row[i] = 1;
>   column[j] = 1;
>   }
>   }
>
>  }
>
>   // Set arr[i][j] to 0 if either row i or column j has a 0
>for (int i = 0; i < matrix.length; i++) {
> for (int j = 0; j < matrix[0].length; j++) {
> if ((row[i] == 1 || column[j] == 1)) {
>matrix[i][j] = 1;
> }
>   }
>   }
>
> On Oct 3, 11:06 pm, Shruti Gupta  wrote:
> > Hi!
> > A effecient way to solve the problem in O(1) space is by making use of
> > the fact that instead of keeping track of which cell has a 0, we can
> > just know which row or column has zero, as eventually that row/col
> > will become 0. The code looks like this:
> >
> > public static void setZeros(int[][] matrix) {
> >   int[] row = new int[matrix.length];
> >   int[] column = new int[matrix[0].length];
> >   // Store the row and column index with value 0
> > for (int i = 0; i < matrix.length; i++) {
> >for (int j = 0; j < matrix[0].length;j++) {
> >if (matrix[i][j] == 0) {
> >  row[i] = 1;
> >  column[j] = 1;
> >  }
> >  }
> >
> > }
> >
> >  // Set arr[i][j] to 0 if either row i or column j has a 0
> >   for (int i = 0; i < matrix.length; i++) {
> >for (int j = 0; j < matrix[0].length; j++) {
> >if ((row[i] == 1 || column[j] == 1)) {
> >   matrix[i][j] = 0;
> >}
> >  }
> >  }
> >
> > Thus there is no extra space taken.
> >
> > Shruti
> >
> > On Oct 3, 12:27 am, rahul sharma  wrote:
> >
> >
> >
> >
> >
> >
> >
> > > nput is a matrix of size n x m of 0s and 1s.
> >
> > > eg:
> > > 1 0 0 1
> > > 0 0 1 0
> > > 0 0 0 0
> >
> > > If a location has 1; make all the elements of that row and column = 1.
> eg
> >
> > > 1 1 1 1
> > > 1 1 1 1
> > > 1 0 1 1
> >
> > > Solution should be with Time complexity = O(n*m) and O(1) 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.

[algogeeks] Can Any1 provide a proper implementation of a Hashtable(Seperation Chaining) in C,C++

[Ankur Garg]

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

[Ankur Garg]

Committed to launch a website,formatting ..clarifying in case you mistook it
for somethin else :D

On Mon, Oct 3, 2011 at 7:50 PM, Ankur Garg  wrote:

> Nice Idea but for pulling this you need committed people :)
>
> On Mon, Oct 3, 2011 at 7:36 PM, sukran dhawan wrote:
>
>> Hello guys,
>> Here is a suggestion.With so much talented people in this group,why cant
>> we a website that is similar to geeksforgeeks.
>> It will be really helpful to others if all the topics are well organised
>> in the form of website
>> This is just a suggestion.just ignore the message if im wrong or u guys
>> don like the idea
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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] suggestion

[Ankur Garg]

Nice Idea but for pulling this you need committed people :)

On Mon, Oct 3, 2011 at 7:36 PM, sukran dhawan wrote:

> Hello guys,
> Here is a suggestion.With so much talented people in this group,why cant we
> a website that is similar to geeksforgeeks.
> It will be really helpful to others if all the topics are well organised in
> the form of website
> This is just a suggestion.just ignore the message if im wrong or u guys don
> like the idea
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Imp->Amazon Question

[Ankur Garg]

Can u provide a proper HashMap

Not Implementation..A proper Idea wud do :)

On Mon, Oct 3, 2011 at 1:03 AM, Preetam Purbia wrote:

> you can implement using hashmap..
>
> On Mon, Oct 3, 2011 at 12:51 AM, Ankur Garg  wrote:
>
>> Define a data structure , using extra memory/space , such that :
>>
>>
>>
>> Insert(int a)
>>
>> Delete(int a)
>>
>> isPresent(int a)
>>
>> get(int a)
>>
>>
>>
>> All above operations on the defined data structure take O(1) , i.e.
>> constant 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.
>>
>
>
>
> --
> Preetam Purbia
> http://twitter.com/preetam_purbia
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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] Imp->Amazon Question

[Ankur Garg]

Define a data structure , using extra memory/space , such that :



Insert(int a)

Delete(int a)

isPresent(int a)

get(int a)



All above operations on the defined data structure take O(1) , i.e. constant
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] urgent soln needed

[Ankur Garg]

@Rahul
Scan the matrix and whenver u see  a[i][j]=0 put a[i]]0]=0 and a[0][j]=0

Meaning to say that put that row or column as 0

Now,
Scan the first row and first column and whereever u see a 0 make that column
and row 0 respectively

Eg

1 1 1 1
0 1 0 1
1 1 1 0

Answer shud be

0  1 0 0
0 0 0 0
0 0 0 0

Scan Array First After Scanning it become

0 1 0 0
0 1 0 1
0 1 1 1
Now Scan first row and for a[0][j]  make a[i][j] 0
so

0 1 0 0
0 1 0 0
0  1 0 0
Now scan column ..Remember to start from a[1][0] and a[0][1]

0 1 0 0
0  0 0 0
0 0 0 0

Hope it helps

Ankur

On Fri, Sep 30, 2011 at 3:47 PM, rahul sharma wrote:

> provide me with o(1) space ...i need it vey urgent.can it be
> done...thnx in advance.
>
>
> On Fri, Sep 30, 2011 at 3:44 PM, rahul sharma wrote:
>
>> sorry n*m complex where n rows and m col
>> but correct for space pzl and it uses two xtras array row and col
>>
>>
>> On Fri, Sep 30, 2011 at 3:42 PM, rahul sharma wrote:
>>
>>> i cant find xact soln on previous threadi have sol with n*n
>>> complexity  but used space,, i.e
>>>
>>> scan whole matrix
>>> if( matrix([i][j]==1)
>>> {
>>> row[i]=1;
>>> col[j]=1;
>>> }
>>>
>>> scan agin
>>> if(row[i]==1 ||| col[j]==1)
>>> matrix[i][j]=0;
>>>
>>>
>>> two n*n loops so takes n*n and uses space too plz give me opt. soln
>>>
>>> On Fri, Sep 30, 2011 at 3:08 PM, Yogesh Yadav  wrote:
>>>
 Already discussed


 https://groups.google.com/group/algogeeks/browse_thread/thread/8a3e1a6665702f54/66bb2e804b43ae1d?hl=en&lnk=gst&q=MS+question+ankur#66bb2e804b43ae1d

 .


 On Fri, Sep 30, 2011 at 2:59 PM, sumit kumar pathak <
 sumitkp1...@gmail.com> wrote:

> *find all the zeros in first iteration and store (size = array bool
> [2n])*
> *and then make zero. *
> *time = O(n^2)*
> *space = O(n)*
> *
> *
> *case 2:*
> * if any zero whole matrix zero, (once we get a zero its row and
> column will become zero which in turn lead to whole matrix being zero).
> *
> *
> *regards
> - Sumit Kumar Pathak
> (Sumit/ Pathak/ SKP ...)
> *Smile is only good contagious thing.*
> *Spread it*!
>
>
>
>
> On Fri, Sep 30, 2011 at 2:38 PM, rahul sharma  > wrote:
>
>> it will zero only row not column
>>
>> On Fri, Sep 30, 2011 at 12:25 PM, Tamanna Afroze > > wrote:
>>
>>>
>>> if(matrix[i][j]==0){
>>>   for(int j=0;j>>matrix[i][j]=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.
>>
>
>  --
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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.