Re: [algogeeks] Re: Interview Question

[Ila Jain]

No distinction has been amongst stduents. I think it is abt incraesing the
distance between any two students.


On Sun, Jul 28, 2013 at 10:45 AM, Dave  wrote:

> @Enchantress: I'm assuming that you are talking about cheating by copying
> from nearby students.
>
> If this is not the first exam, based on prior grades, put the A students
> in the back of the room, with the B students in front of the A students,
> the C students in front of the B students, the D students in front of the C
> students, and the F students in the front of the room.
>
> Put as many of the C students as you can in alternate seats, e.g., columns
> 1, 3, 5,  If you can alternate all of the C students, put as many of
> the B students as you can in alternate seats. If you can alternate all of
> the B students, put as many of the D students as you can in alternate
> seats. If you can alternate all of the D students, put as many F students
> as you can in alternate seats. Finally, if you can alternate all of the F
> students, put as many A students as you can in alternate seats.
>
> Rationale: An A or B student won't copy from anyone else, because he
> doesn't want someone else's mistake to mess up his grade. The C students
> have the most to gain by copying, but they will be spread out as much as
> possible. The D and F students will have only D and F students to copy
> from, so they won't gain much from copying.
>
> Probably not the solution you were looking for, but I think an effective
> one.
>
> Dave
>
> On Saturday, July 27, 2013 1:02:11 PM UTC-5, enchantress wrote:
>
>> Given m*n matrix and k students how can they be placed such that cheatig
>> is minimised.
>>
>>
>>  --
> You received this message because you are subscribed to a topic in the
> Google Groups "Algorithm Geeks" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/d/topic/algogeeks/l94hz2VTqWk/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to
> algogeeks+unsubscr...@googlegroups.com.
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

Re: [algogeeks] Re: Interview Question

[abhinav sikri]

Hope this helps :
space: o(n^2)
time: o(n^2)

#include
using namespace std;

inline int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}

int main()
{
char str[7]="hello";
int arr[3][3]={
{15,2,3},
{4,5,6},
{7,8,9},
};
int sum[3][3]={0};
int n=3,i,j;
sum[0][0]=arr[0][0];
for(i=1;ik)
min=k;
}
}
cout<<"ans : "
> @Hraday
> worst case complexity of your algorithm comes out to be O(n^4)..
> What I was thinking is precompute sums of all the rectangles in a sum
> matrix ..using dynamic programming because I read some where that sum of
> rectangles in a matrix has an optimal substructure property..
>
> So we can get sum of all the partitioned rectangles in O(1) reducing our
> complexity to O(n^2)..So, our job now is just to precompute the matrix..
>
>
> On Sunday, 12 August 2012 17:48:07 UTC+5:30, sahil taneja wrote:
>
>> Divide 2D array into 4 parts. Compute sum of each partition and get max
>> value from the four of them. For all possible partitions get min value of
>> such max values computed.
>>
>  --
> 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/-/dOI2SIuw-nMJ.
>
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Abhinav Sikri
B.E. (Computer Engineering)
Netaji Subhas Institute of Technology
Dwarka, New Delhi

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

Re: [algogeeks] Re: Interview Question

[Hraday Sharma]

# lengthy explanation give more attention
#here we are finding sums on all valid partition and storing all four 
possible sums in variable a,b,c,d and and for all possible a,b,c,d we will 
keep runninf  max and min/
 
lets take an example parttion is done at row=0, coloumn=1
 
00 01| 02 03
|-
10 11| 12 13
20 21| 21  22
 
a=arr[0][0]+arr[0][1]
b=arr[0][2]+arr[0][3]
c=arr[1][0]+arr[1][1]+arr[2][0][2][1]
d=arr[1][2]+arr[1][3]+arr[2][1]+arr[2][2];
 
this can be coded like this

int a,b,c,d,max,main;
a=b=c=d=max=min=0;
for(int row=0;row++;row
> @sahil Can you please explain your question with an example ? 

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

Re: [algogeeks] Re: Interview Question

[gaurav yadav]

@sahil Can you please explain your question with an example ?

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

Re: [algogeeks] Re: Interview Question based on histogram

[Nikhil Agarwal]

Navin , your reply is correct.

On Sat, May 19, 2012 at 10:36 PM, Gene  wrote:

> The problem is not so clear, so you must make some assumptions to gat
> an answer. Since we have water, we have to envision the histogram in
> 3d. Then assume that the distance between histogram bars is 1 and bar
> i has height H[i], 0<=i plane is at zero. Water is held in the "pockets" between bars.  Then
> the "pocket" between H[i] and H[i+1] holds min(H[i],H[i+1]).  To get
> the total, just sum these for 0 <= i < N-1 .
>
> On May 17, 1:57 am, Nikhil Agarwal  wrote:
> > Imagine that you have an histogram stored in an array. Now imagine that
> you
> > can pour water on top of your histogram. Describe an algorithm that
> > computes the amount of water that remains trapped among the columns of
> the
> > graph. Clearly on the edges the water would fall off. Use the language or
> > the pseudocode you prefer.
> >
> > --
> > Thanks & Regards
> > Nikhil Agarwal
> > B.Tech. in Computer Science & Engineering
> > National Institute Of Technology,
> Durgapur,Indiahttp://tech-nikk.blogspot.comhttp://
> beta.freshersworld.com/communities/nitd
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>


-- 
Thanks & Regards
Nikhil Agarwal
B.Tech. in Computer Science & Engineering
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd

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

Re: [algogeeks] Re: Interview question

[atul anand]

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

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

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

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

}

push(&s,i);
}

}





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

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

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

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

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

 }

 push(&s,i);
  }

 }


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

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

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

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

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

Re: [algogeeks] Re: Interview question

[algo bard]

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

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

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

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

Re: [algogeeks] Re: Interview question

[algo bard]

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

^ Similar question.

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

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


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

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

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

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

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

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

Re: [algogeeks] Re: Interview question

[atul anand]

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

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

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

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

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

Re: [algogeeks] Re: Interview question

[atul anand]

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

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

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

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

}

push(&s,i);
}

}


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

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

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

Re: [algogeeks] Re: Interview question

[shady]

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


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

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

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

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

Re: [algogeeks] Re: Interview question

[Kartik Sachan]

+1 @saurabh...:P

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

Re: [algogeeks] Re: Interview question

[saurabh singh]

@amol I was trying to put forward the point that the o/p need not be
sorted.If you check the difference between time of  my and payal's message
it was a case of race condition.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com



On Sun, Mar 25, 2012 at 6:54 AM, Gene  wrote:

> This problem isn't carefully defined.  If you have 3,4,2 then 2 is the
> first value smaller and of higher index than both 3 and 4.  So which
> to swap with?
>
> On Mar 24, 10:01 am, Navin Kumar  wrote:
> > Given an array of integers, for each index i, you have to swap the value
> at
> > i with the first value smaller than A[ i ] that comes after index i.
> > An efficient solution expected.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

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

Re: [algogeeks] Re: Interview question

[Algoose chase]

n = x%2 ?

x can be any integer.

On Fri, Dec 2, 2011 at 5:19 PM, Don  wrote:

> (!x || !(x^1))
> !(x>>1)
> !((x|1)-1)
> (x*x)==x
> (x==(x==x))||(x==(x!=x))
>
> etc.
>
> On Nov 29, 9:07 pm, Nitin Garg  wrote:
> > *What are the different ways to say, the value of x can be either a 0 or
> a
> > 1.*
> >
> > --
> > 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: Interview question

[sunny agrawal]

Reverse elements of set from start to end
Reverse elements of set from end+1 to destination
Reverse elements of set from start to destination

DONE
O(n)

On Sat, Jul 9, 2011 at 7:25 PM, Yogesh Yadav  wrote:

> @gopi: i didnt really understand what u want to say... what start,end and
> destination denotes here??
>
> u said it should start with 1 but in result it is starting with 9...plz
> explain ur question again
>
>
> On Sat, Jul 9, 2011 at 7:21 PM, Gopi  wrote:
>
>> Hi Geeks
>>
>> Can anyone please comment on this.
>> Let me know if the problem description is not clear enough.
>>
>> Thanks
>> Gopi
>>
>> On Jul 9, 5:36 pm, Gopi  wrote:
>> > Write code to move a set of elements (represented by start and end
>> > indexed) in an array to a given destination location (denoted by
>> > destination index).
>> >
>> > For example:
>> > Let say our array is {9, 7, 5, 8, 1, 5, 4, 8, 10, 1}
>> >
>> > move_set (array, start = 1, end = 3, destination = 8)
>> >
>> > should rearrage the array such that the new array looks like {9, 1, 5,
>> > 4, 8, 10, 7, 5, 8, 1}
>> >
>> > Try to come up with an algorithm that is faster than O(n^2)
>> >
>> > Thanks
>> > Gopi
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee

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

Re: [algogeeks] Re: Interview question

[Yogesh Yadav]

@gopi: i didnt really understand what u want to say... what start,end and
destination denotes here??

u said it should start with 1 but in result it is starting with 9...plz
explain ur question again

On Sat, Jul 9, 2011 at 7:21 PM, Gopi  wrote:

> Hi Geeks
>
> Can anyone please comment on this.
> Let me know if the problem description is not clear enough.
>
> Thanks
> Gopi
>
> On Jul 9, 5:36 pm, Gopi  wrote:
> > Write code to move a set of elements (represented by start and end
> > indexed) in an array to a given destination location (denoted by
> > destination index).
> >
> > For example:
> > Let say our array is {9, 7, 5, 8, 1, 5, 4, 8, 10, 1}
> >
> > move_set (array, start = 1, end = 3, destination = 8)
> >
> > should rearrage the array such that the new array looks like {9, 1, 5,
> > 4, 8, 10, 7, 5, 8, 1}
> >
> > Try to come up with an algorithm that is faster than O(n^2)
> >
> > Thanks
> > Gopi
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

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

Re: [algogeeks] Re: Interview Question

[sunny agrawal]

yes Heap Build is O(n)
but after build it will be nlgn for comparision. isn't it ?

On Tue, Jul 5, 2011 at 10:07 PM, vaibhav agarwal  wrote:

> @Dave bt  the heap build operation is O(n) there is a proof fr this
>
>
> On Tue, Jul 5, 2011 at 6:29 AM, saurabh singh  wrote:
>
>> Yes I know I said it with regard to the current problem
>>
>> On Tue, Jul 5, 2011 at 8:58 AM, Dave  wrote:
>>
>>> @Saurabh: Nope. You can construct a heap in-place. But it is not O(n).
>>>
>>> Dave
>>>
>>> On Jul 4, 10:02 pm, saurabh singh  wrote:
>>> > Again heap will require extra space.
>>> >
>>> > On Tue, Jul 5, 2011 at 8:25 AM, vaibhav agarwal
>>> > wrote:
>>> >
>>> >
>>> >
>>> >
>>> >
>>> > > what abt this...
>>> > > check length of the  array if same then we make a min heap of both
>>> the
>>> > > arrays which can be done in O(n) and call extraxtmin(). in this way
>>> we can
>>> > > find whether they r equal.
>>> > > othwersie nt equal.
>>> >
>>> > > correct me if i am wrong!!
>>> >
>>> > > On Mon, Jul 4, 2011 at 4:35 AM, saurabh singh 
>>> wrote:
>>> >
>>> > >> Lets conclude this post.Shall we?
>>> > >> .An o(n) seems infeasible without any significant extra memory
>>> > >> If extra memory is allowed,hash maps can be used to bring it down to
>>> > >> o(logn).But hash maps would eat up serious memory if numbers occupy
>>> a large
>>> > >> range.
>>> >
>>> > >> --
>>> > >> You received this message because you are subscribed to the Google
>>> Groups
>>> > >> "Algorithm Geeks" group.
>>> > >> To post to this group, send email to algogeeks@googlegroups.com.
>>> > >> To unsubscribe from this group, send email to
>>> > >> algogeeks+unsubscr...@googlegroups.com.
>>> > >> For more options, visit this group at
>>> > >>http://groups.google.com/group/algogeeks?hl=en.
>>> >
>>> > >  --
>>> > > You received this message because you are subscribed to the Google
>>> Groups
>>> > > "Algorithm Geeks" group.
>>> > > To post to this group, send email to algogeeks@googlegroups.com.
>>> > > To unsubscribe from this group, send email to
>>> > > algogeeks+unsubscr...@googlegroups.com.
>>> > > For more options, visit this group at
>>> > >http://groups.google.com/group/algogeeks?hl=en.
>>> >
>>> > --
>>> > Saurabh Singh
>>> > B.Tech (Computer Science)
>>> > MNNIT ALLAHABAD- 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.
>>>
>>>
>>
>>
>> --
>> Saurabh Singh
>> B.Tech (Computer Science)
>> MNNIT ALLAHABAD
>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee

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

Re: [algogeeks] Re: Interview Question

[vaibhav agarwal]

http://www.cim.mcgill.ca/~langer/250/2010/lecture24.pdf


On Tue, Jul 5, 2011 at 12:37 PM, vaibhav agarwal  wrote:

> @Dave bt  the heap build operation is O(n) there is a proof fr this
>
>
> On Tue, Jul 5, 2011 at 6:29 AM, saurabh singh  wrote:
>
>> Yes I know I said it with regard to the current problem
>>
>> On Tue, Jul 5, 2011 at 8:58 AM, Dave  wrote:
>>
>>> @Saurabh: Nope. You can construct a heap in-place. But it is not O(n).
>>>
>>> Dave
>>>
>>> On Jul 4, 10:02 pm, saurabh singh  wrote:
>>> > Again heap will require extra space.
>>> >
>>> > On Tue, Jul 5, 2011 at 8:25 AM, vaibhav agarwal
>>> > wrote:
>>> >
>>> >
>>> >
>>> >
>>> >
>>> > > what abt this...
>>> > > check length of the  array if same then we make a min heap of both
>>> the
>>> > > arrays which can be done in O(n) and call extraxtmin(). in this way
>>> we can
>>> > > find whether they r equal.
>>> > > othwersie nt equal.
>>> >
>>> > > correct me if i am wrong!!
>>> >
>>> > > On Mon, Jul 4, 2011 at 4:35 AM, saurabh singh 
>>> wrote:
>>> >
>>> > >> Lets conclude this post.Shall we?
>>> > >> .An o(n) seems infeasible without any significant extra memory
>>> > >> If extra memory is allowed,hash maps can be used to bring it down to
>>> > >> o(logn).But hash maps would eat up serious memory if numbers occupy
>>> a large
>>> > >> range.
>>> >
>>> > >> --
>>> > >> You received this message because you are subscribed to the Google
>>> Groups
>>> > >> "Algorithm Geeks" group.
>>> > >> To post to this group, send email to algogeeks@googlegroups.com.
>>> > >> To unsubscribe from this group, send email to
>>> > >> algogeeks+unsubscr...@googlegroups.com.
>>> > >> For more options, visit this group at
>>> > >>http://groups.google.com/group/algogeeks?hl=en.
>>> >
>>> > >  --
>>> > > You received this message because you are subscribed to the Google
>>> Groups
>>> > > "Algorithm Geeks" group.
>>> > > To post to this group, send email to algogeeks@googlegroups.com.
>>> > > To unsubscribe from this group, send email to
>>> > > algogeeks+unsubscr...@googlegroups.com.
>>> > > For more options, visit this group at
>>> > >http://groups.google.com/group/algogeeks?hl=en.
>>> >
>>> > --
>>> > Saurabh Singh
>>> > B.Tech (Computer Science)
>>> > MNNIT ALLAHABAD- 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.
>>>
>>>
>>
>>
>> --
>> Saurabh Singh
>> B.Tech (Computer Science)
>> MNNIT ALLAHABAD
>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>

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

Re: [algogeeks] Re: Interview Question

[vaibhav agarwal]

@Dave bt  the heap build operation is O(n) there is a proof fr this

On Tue, Jul 5, 2011 at 6:29 AM, saurabh singh  wrote:

> Yes I know I said it with regard to the current problem
>
> On Tue, Jul 5, 2011 at 8:58 AM, Dave  wrote:
>
>> @Saurabh: Nope. You can construct a heap in-place. But it is not O(n).
>>
>> Dave
>>
>> On Jul 4, 10:02 pm, saurabh singh  wrote:
>> > Again heap will require extra space.
>> >
>> > On Tue, Jul 5, 2011 at 8:25 AM, vaibhav agarwal
>> > wrote:
>> >
>> >
>> >
>> >
>> >
>> > > what abt this...
>> > > check length of the  array if same then we make a min heap of both the
>> > > arrays which can be done in O(n) and call extraxtmin(). in this way we
>> can
>> > > find whether they r equal.
>> > > othwersie nt equal.
>> >
>> > > correct me if i am wrong!!
>> >
>> > > On Mon, Jul 4, 2011 at 4:35 AM, saurabh singh 
>> wrote:
>> >
>> > >> Lets conclude this post.Shall we?
>> > >> .An o(n) seems infeasible without any significant extra memory
>> > >> If extra memory is allowed,hash maps can be used to bring it down to
>> > >> o(logn).But hash maps would eat up serious memory if numbers occupy a
>> large
>> > >> range.
>> >
>> > >> --
>> > >> You received this message because you are subscribed to the Google
>> Groups
>> > >> "Algorithm Geeks" group.
>> > >> To post to this group, send email to algogeeks@googlegroups.com.
>> > >> To unsubscribe from this group, send email to
>> > >> algogeeks+unsubscr...@googlegroups.com.
>> > >> For more options, visit this group at
>> > >>http://groups.google.com/group/algogeeks?hl=en.
>> >
>> > >  --
>> > > You received this message because you are subscribed to the Google
>> Groups
>> > > "Algorithm Geeks" group.
>> > > To post to this group, send email to algogeeks@googlegroups.com.
>> > > To unsubscribe from this group, send email to
>> > > algogeeks+unsubscr...@googlegroups.com.
>> > > For more options, visit this group at
>> > >http://groups.google.com/group/algogeeks?hl=en.
>> >
>> > --
>> > Saurabh Singh
>> > B.Tech (Computer Science)
>> > MNNIT ALLAHABAD- 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.
>>
>>
>
>
> --
> Saurabh Singh
> B.Tech (Computer Science)
> MNNIT ALLAHABAD
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] Re: Interview Question

[saurabh singh]

Yes I know I said it with regard to the current problem

On Tue, Jul 5, 2011 at 8:58 AM, Dave  wrote:

> @Saurabh: Nope. You can construct a heap in-place. But it is not O(n).
>
> Dave
>
> On Jul 4, 10:02 pm, saurabh singh  wrote:
> > Again heap will require extra space.
> >
> > On Tue, Jul 5, 2011 at 8:25 AM, vaibhav agarwal
> > wrote:
> >
> >
> >
> >
> >
> > > what abt this...
> > > check length of the  array if same then we make a min heap of both the
> > > arrays which can be done in O(n) and call extraxtmin(). in this way we
> can
> > > find whether they r equal.
> > > othwersie nt equal.
> >
> > > correct me if i am wrong!!
> >
> > > On Mon, Jul 4, 2011 at 4:35 AM, saurabh singh 
> wrote:
> >
> > >> Lets conclude this post.Shall we?
> > >> .An o(n) seems infeasible without any significant extra memory
> > >> If extra memory is allowed,hash maps can be used to bring it down to
> > >> o(logn).But hash maps would eat up serious memory if numbers occupy a
> large
> > >> range.
> >
> > >> --
> > >> You received this message because you are subscribed to the Google
> Groups
> > >> "Algorithm Geeks" group.
> > >> To post to this group, send email to algogeeks@googlegroups.com.
> > >> To unsubscribe from this group, send email to
> > >> algogeeks+unsubscr...@googlegroups.com.
> > >> For more options, visit this group at
> > >>http://groups.google.com/group/algogeeks?hl=en.
> >
> > >  --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > --
> > Saurabh Singh
> > B.Tech (Computer Science)
> > MNNIT ALLAHABAD- 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.
>
>


-- 
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD

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

Re: [algogeeks] Re: Interview Question

[vaibhav agarwal]

@saurabh bt we need only one extra array

On Mon, Jul 4, 2011 at 11:02 PM, saurabh singh  wrote:

> Again heap will require extra space.
>
>
> On Tue, Jul 5, 2011 at 8:25 AM, vaibhav agarwal <
> vibhu.bitspil...@gmail.com> wrote:
>
>> what abt this...
>> check length of the  array if same then we make a min heap of both the
>> arrays which can be done in O(n) and call extraxtmin(). in this way we can
>> find whether they r equal.
>> othwersie nt equal.
>>
>> correct me if i am wrong!!
>>
>> On Mon, Jul 4, 2011 at 4:35 AM, saurabh singh wrote:
>>
>>> Lets conclude this post.Shall we?
>>> .An o(n) seems infeasible without any significant extra memory
>>> If extra memory is allowed,hash maps can be used to bring it down to
>>> o(logn).But hash maps would eat up serious memory if numbers occupy a large
>>> range.
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Saurabh Singh
> B.Tech (Computer Science)
> MNNIT ALLAHABAD
>
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] Re: Interview Question

[saurabh singh]

Again heap will require extra space.

On Tue, Jul 5, 2011 at 8:25 AM, vaibhav agarwal
wrote:

> what abt this...
> check length of the  array if same then we make a min heap of both the
> arrays which can be done in O(n) and call extraxtmin(). in this way we can
> find whether they r equal.
> othwersie nt equal.
>
> correct me if i am wrong!!
>
> On Mon, Jul 4, 2011 at 4:35 AM, saurabh singh  wrote:
>
>> Lets conclude this post.Shall we?
>> .An o(n) seems infeasible without any significant extra memory
>> If extra memory is allowed,hash maps can be used to bring it down to
>> o(logn).But hash maps would eat up serious memory if numbers occupy a large
>> range.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD

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

Re: [algogeeks] Re: Interview Question

[vaibhav agarwal]

what abt this...
check length of the  array if same then we make a min heap of both the
arrays which can be done in O(n) and call extraxtmin(). in this way we can
find whether they r equal.
othwersie nt equal.

correct me if i am wrong!!

On Mon, Jul 4, 2011 at 4:35 AM, saurabh singh  wrote:

> Lets conclude this post.Shall we?
> .An o(n) seems infeasible without any significant extra memory
> If extra memory is allowed,hash maps can be used to bring it down to
> o(logn).But hash maps would eat up serious memory if numbers occupy a large
> range.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] Re: Interview Question

[saurabh singh]

Lets conclude this post.Shall we?
.An o(n) seems infeasible without any significant extra memory
If extra memory is allowed,hash maps can be used to bring it down to
o(logn).But hash maps would eat up serious memory if numbers occupy a large
range.

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

Re: [algogeeks] Re: Interview Question

[Anantha Krishnan]

I guess this question is similar to anagram.

On Mon, Jul 4, 2011 at 1:07 AM, Arpit Sood  wrote:

> Hey,
> what is the solution with XOR, methods mentioned above seem to
> fail there any reference ?
>
>
> On Sun, Jul 3, 2011 at 10:39 PM, Deoki Nandan  wrote:
>
>> there is no possible solution for this question in less than O(nlgn) time.
>> As  by theorem given in cormen and solution is possible using xor
>>
>>
>> On Sun, Jul 3, 2011 at 2:27 PM, Sandeep Jain wrote:
>>
>>> For case1) yes XOR works,
>>> for Well, for the other two cases hash-maps may come in handy. :)
>>>
>>>
>>> Regards,
>>> Sandeep Jain
>>>
>>>
>>>
>>>
>>>
>>> On Sun, Jul 3, 2011 at 1:48 PM, sunny agrawal 
>>> wrote:
>>>
 But i don't think xor method will work at all for all of the cases above
 you mentioned.
 setA = {4,7}
 setB = {5,6}

 -> all numbers in both set are nonzero and distinct
 -> all numbers are in some range :D
 and for character parts it will similarly failby taking character
 set of ascii values 4,5,6,7

 and about general solution i dont know how to do it in O(n)
 one thing i was thinking of goes this way, taking arrays A and B instead
 of sets.
 if we can prove these polynomial to be same in O(n) time.
 (x-a[0])*(x-a[1])*.*(x-a[n-1]) ==
 (x-b[0])*(x-b[1])*.(x-b[n-1])
 dont know if it can be done efficienty


 On Sun, Jul 3, 2011 at 1:25 PM, Sandeep Jain wrote:

> Agreed, BUT if you don't add a stipulation. You won't be able to reduce
> the complexity.
> For a 100% general solution, I don't think you can reduce the
> complexity more than O(nLgn.)
> There are variations of this question:
> --> All numbers are non-zero and distinct.
> --> All numbers belong to given range
> --> You can also have character's in place of numbers
> In all the above cases, you will have time complexity O(n)
>
> PS: I'm definitely looking forward to learn a solution, better than
> O(nLgn)
>
>
>
> Regards,
> Sandeep Jain
>
>
>
>
> On Sun, Jul 3, 2011 at 1:09 PM, sunny agrawal  > wrote:
>
>> @sandeep
>> SET A -> {0,3,4,7}
>> SET B -> {1,2,5,6}
>>
>> xor of all elements is zero
>> sum of both the sets is same
>> no of elements in both are same
>>
>> overall result : all Algorithm posted above Fails
>>
>> On Sun, Jul 3, 2011 at 12:59 PM, Sandeep Jain 
>> wrote:
>>
>>> I was thinking the same, BUT here the question is that we have two
>>> *SETS* and that's the catch.
>>> So, XORing all elements of SET A with SET B should result in ZERO
>>> only when both the set have same elements.
>>>
>>>
>>> Regards,
>>> Sandeep Jain
>>>
>>>
>>>
>>>
>>>
>>> On Sun, Jul 3, 2011 at 11:25 AM, Pranav Agarwal <
>>> meetpranav...@gmail.com> wrote:
>>>
 I think that the above algo will fail for the following two arrays:
 a={2,2,3,3}
 b={4,4,1,1}

 sum(a)=sum(b);
 a^b=0;
 len(a)=len(b);

 Correct me if i am wrong!

 Pranav


 On Sun, Jul 3, 2011 at 7:43 AM, varun pahwa <
 varunpahwa2...@gmail.com> wrote:

> @aditya. xor all elements mean that. take xor of each element of
> 1st array store in a variable that take xor of variable and each 
> element of
> the second array if all elements are common then the variable will be 
> 0 some
> where.
> var = a[0];
> for(i = 1; i < sizeof(a)/sizeof(a[0]); i++)
> var = var ^ a[i];
> for(i = 0; i < sizeof(b)/sizeof(b[0]); i++)
> var = var ^ b[i];
>
>
>
> On Sat, Jul 2, 2011 at 2:19 PM, aditya kumar <
> aditya.kumar130...@gmail.com> wrote:
>
>> @mohit..:i dint get the logic behind XOR plz explain ..nd ya i
>> dont think dat you can find second largest in less than O(n).
>>
>>
>> On Sun, Jul 3, 2011 at 2:43 AM, mohit mittal <
>> mohitm.1...@gmail.com> wrote:
>>
>>> Dont think that the corresponding elements should be same.
>>> XOR Should do it anyway.
>>>
>>> Btw other question "How would you find the second largest
>>> element in an array using minimum no of comparisons?Any thing 
>>> better than
>>> O(n)."?
>>>
>>>
>>> On Sun, Jul 3, 2011 at 2:41 AM, aditya kumar <
>>> aditya.kumar130...@gmail.com> wrote:
>>>
 xor will only result if corresponding elements are same . what
 if in both the array set of integers are same but they arnt 
 corresponding to
 each other ??


 On Sun, Jul 3, 2011 at 2:37 AM, Dumanshu wrote

Re: [algogeeks] Re: Interview Question

[Arpit Sood]

Hey,
what is the solution with XOR, methods mentioned above seem to
fail there any reference ?

On Sun, Jul 3, 2011 at 10:39 PM, Deoki Nandan  wrote:

> there is no possible solution for this question in less than O(nlgn) time.
> As  by theorem given in cormen and solution is possible using xor
>
>
> On Sun, Jul 3, 2011 at 2:27 PM, Sandeep Jain wrote:
>
>> For case1) yes XOR works,
>> for Well, for the other two cases hash-maps may come in handy. :)
>>
>>
>> Regards,
>> Sandeep Jain
>>
>>
>>
>>
>>
>> On Sun, Jul 3, 2011 at 1:48 PM, sunny agrawal wrote:
>>
>>> But i don't think xor method will work at all for all of the cases above
>>> you mentioned.
>>> setA = {4,7}
>>> setB = {5,6}
>>>
>>> -> all numbers in both set are nonzero and distinct
>>> -> all numbers are in some range :D
>>> and for character parts it will similarly failby taking character set
>>> of ascii values 4,5,6,7
>>>
>>> and about general solution i dont know how to do it in O(n)
>>> one thing i was thinking of goes this way, taking arrays A and B instead
>>> of sets.
>>> if we can prove these polynomial to be same in O(n) time.
>>> (x-a[0])*(x-a[1])*.*(x-a[n-1]) ==
>>> (x-b[0])*(x-b[1])*.(x-b[n-1])
>>> dont know if it can be done efficienty
>>>
>>>
>>> On Sun, Jul 3, 2011 at 1:25 PM, Sandeep Jain wrote:
>>>
 Agreed, BUT if you don't add a stipulation. You won't be able to reduce
 the complexity.
 For a 100% general solution, I don't think you can reduce the complexity
 more than O(nLgn.)
 There are variations of this question:
 --> All numbers are non-zero and distinct.
 --> All numbers belong to given range
 --> You can also have character's in place of numbers
 In all the above cases, you will have time complexity O(n)

 PS: I'm definitely looking forward to learn a solution, better than
 O(nLgn)



 Regards,
 Sandeep Jain




 On Sun, Jul 3, 2011 at 1:09 PM, sunny agrawal 
 wrote:

> @sandeep
> SET A -> {0,3,4,7}
> SET B -> {1,2,5,6}
>
> xor of all elements is zero
> sum of both the sets is same
> no of elements in both are same
>
> overall result : all Algorithm posted above Fails
>
> On Sun, Jul 3, 2011 at 12:59 PM, Sandeep Jain 
> wrote:
>
>> I was thinking the same, BUT here the question is that we have two
>> *SETS* and that's the catch.
>> So, XORing all elements of SET A with SET B should result in ZERO only
>> when both the set have same elements.
>>
>>
>> Regards,
>> Sandeep Jain
>>
>>
>>
>>
>>
>> On Sun, Jul 3, 2011 at 11:25 AM, Pranav Agarwal <
>> meetpranav...@gmail.com> wrote:
>>
>>> I think that the above algo will fail for the following two arrays:
>>> a={2,2,3,3}
>>> b={4,4,1,1}
>>>
>>> sum(a)=sum(b);
>>> a^b=0;
>>> len(a)=len(b);
>>>
>>> Correct me if i am wrong!
>>>
>>> Pranav
>>>
>>>
>>> On Sun, Jul 3, 2011 at 7:43 AM, varun pahwa <
>>> varunpahwa2...@gmail.com> wrote:
>>>
 @aditya. xor all elements mean that. take xor of each element of 1st
 array store in a variable that take xor of variable and each element 
 of the
 second array if all elements are common then the variable will be 0 
 some
 where.
 var = a[0];
 for(i = 1; i < sizeof(a)/sizeof(a[0]); i++)
 var = var ^ a[i];
 for(i = 0; i < sizeof(b)/sizeof(b[0]); i++)
 var = var ^ b[i];



 On Sat, Jul 2, 2011 at 2:19 PM, aditya kumar <
 aditya.kumar130...@gmail.com> wrote:

> @mohit..:i dint get the logic behind XOR plz explain ..nd ya i dont
> think dat you can find second largest in less than O(n).
>
>
> On Sun, Jul 3, 2011 at 2:43 AM, mohit mittal <
> mohitm.1...@gmail.com> wrote:
>
>> Dont think that the corresponding elements should be same.
>> XOR Should do it anyway.
>>
>> Btw other question "How would you find the second largest element
>> in an array using minimum no of comparisons?Any thing better than 
>> O(n)."?
>>
>>
>> On Sun, Jul 3, 2011 at 2:41 AM, aditya kumar <
>> aditya.kumar130...@gmail.com> wrote:
>>
>>> xor will only result if corresponding elements are same . what if
>>> in both the array set of integers are same but they arnt 
>>> corresponding to
>>> each other ??
>>>
>>>
>>> On Sun, Jul 3, 2011 at 2:37 AM, Dumanshu wrote:
>>>
 xor all the elements of both arrays ==0
 sum of 1st array == sum of 2nd array
 no. of elements in 1st == no. of elements in 2nd
 if the above conditions are met, they have the same set.
 m i missin sth?

Re: [algogeeks] Re: Interview Question

[vaibhav agarwal]

may be we can add condition that sum of squares and cubes be same.


On Sun, Jul 3, 2011 at 1:09 PM, Deoki Nandan  wrote:

> there is no possible solution for this question in less than O(nlgn) time.
> As  by theorem given in cormen and solution is possible using xor
>
>
> On Sun, Jul 3, 2011 at 2:27 PM, Sandeep Jain wrote:
>
>> For case1) yes XOR works,
>> for Well, for the other two cases hash-maps may come in handy. :)
>>
>>
>> Regards,
>> Sandeep Jain
>>
>>
>>
>>
>>
>> On Sun, Jul 3, 2011 at 1:48 PM, sunny agrawal wrote:
>>
>>> But i don't think xor method will work at all for all of the cases above
>>> you mentioned.
>>> setA = {4,7}
>>> setB = {5,6}
>>>
>>> -> all numbers in both set are nonzero and distinct
>>> -> all numbers are in some range :D
>>> and for character parts it will similarly failby taking character set
>>> of ascii values 4,5,6,7
>>>
>>> and about general solution i dont know how to do it in O(n)
>>> one thing i was thinking of goes this way, taking arrays A and B instead
>>> of sets.
>>> if we can prove these polynomial to be same in O(n) time.
>>> (x-a[0])*(x-a[1])*.*(x-a[n-1]) ==
>>> (x-b[0])*(x-b[1])*.(x-b[n-1])
>>> dont know if it can be done efficienty
>>>
>>>
>>> On Sun, Jul 3, 2011 at 1:25 PM, Sandeep Jain wrote:
>>>
 Agreed, BUT if you don't add a stipulation. You won't be able to reduce
 the complexity.
 For a 100% general solution, I don't think you can reduce the complexity
 more than O(nLgn.)
 There are variations of this question:
 --> All numbers are non-zero and distinct.
 --> All numbers belong to given range
 --> You can also have character's in place of numbers
 In all the above cases, you will have time complexity O(n)

 PS: I'm definitely looking forward to learn a solution, better than
 O(nLgn)



 Regards,
 Sandeep Jain




 On Sun, Jul 3, 2011 at 1:09 PM, sunny agrawal 
 wrote:

> @sandeep
> SET A -> {0,3,4,7}
> SET B -> {1,2,5,6}
>
> xor of all elements is zero
> sum of both the sets is same
> no of elements in both are same
>
> overall result : all Algorithm posted above Fails
>
> On Sun, Jul 3, 2011 at 12:59 PM, Sandeep Jain 
> wrote:
>
>> I was thinking the same, BUT here the question is that we have two
>> *SETS* and that's the catch.
>> So, XORing all elements of SET A with SET B should result in ZERO only
>> when both the set have same elements.
>>
>>
>> Regards,
>> Sandeep Jain
>>
>>
>>
>>
>>
>> On Sun, Jul 3, 2011 at 11:25 AM, Pranav Agarwal <
>> meetpranav...@gmail.com> wrote:
>>
>>> I think that the above algo will fail for the following two arrays:
>>> a={2,2,3,3}
>>> b={4,4,1,1}
>>>
>>> sum(a)=sum(b);
>>> a^b=0;
>>> len(a)=len(b);
>>>
>>> Correct me if i am wrong!
>>>
>>> Pranav
>>>
>>>
>>> On Sun, Jul 3, 2011 at 7:43 AM, varun pahwa <
>>> varunpahwa2...@gmail.com> wrote:
>>>
 @aditya. xor all elements mean that. take xor of each element of 1st
 array store in a variable that take xor of variable and each element 
 of the
 second array if all elements are common then the variable will be 0 
 some
 where.
 var = a[0];
 for(i = 1; i < sizeof(a)/sizeof(a[0]); i++)
 var = var ^ a[i];
 for(i = 0; i < sizeof(b)/sizeof(b[0]); i++)
 var = var ^ b[i];



 On Sat, Jul 2, 2011 at 2:19 PM, aditya kumar <
 aditya.kumar130...@gmail.com> wrote:

> @mohit..:i dint get the logic behind XOR plz explain ..nd ya i dont
> think dat you can find second largest in less than O(n).
>
>
> On Sun, Jul 3, 2011 at 2:43 AM, mohit mittal <
> mohitm.1...@gmail.com> wrote:
>
>> Dont think that the corresponding elements should be same.
>> XOR Should do it anyway.
>>
>> Btw other question "How would you find the second largest element
>> in an array using minimum no of comparisons?Any thing better than 
>> O(n)."?
>>
>>
>> On Sun, Jul 3, 2011 at 2:41 AM, aditya kumar <
>> aditya.kumar130...@gmail.com> wrote:
>>
>>> xor will only result if corresponding elements are same . what if
>>> in both the array set of integers are same but they arnt 
>>> corresponding to
>>> each other ??
>>>
>>>
>>> On Sun, Jul 3, 2011 at 2:37 AM, Dumanshu wrote:
>>>
 xor all the elements of both arrays ==0
 sum of 1st array == sum of 2nd array
 no. of elements in 1st == no. of elements in 2nd
 if the above conditions are met, they have the same set.
 m i missin sth?
 On Jul 3, 1:23 am, mittal  wrot

Re: [algogeeks] Re: Interview Question

[Deoki Nandan]

there is no possible solution for this question in less than O(nlgn) time.
As  by theorem given in cormen and solution is possible using xor

On Sun, Jul 3, 2011 at 2:27 PM, Sandeep Jain  wrote:

> For case1) yes XOR works,
> for Well, for the other two cases hash-maps may come in handy. :)
>
>
> Regards,
> Sandeep Jain
>
>
>
>
>
> On Sun, Jul 3, 2011 at 1:48 PM, sunny agrawal wrote:
>
>> But i don't think xor method will work at all for all of the cases above
>> you mentioned.
>> setA = {4,7}
>> setB = {5,6}
>>
>> -> all numbers in both set are nonzero and distinct
>> -> all numbers are in some range :D
>> and for character parts it will similarly failby taking character set
>> of ascii values 4,5,6,7
>>
>> and about general solution i dont know how to do it in O(n)
>> one thing i was thinking of goes this way, taking arrays A and B instead
>> of sets.
>> if we can prove these polynomial to be same in O(n) time.
>> (x-a[0])*(x-a[1])*.*(x-a[n-1]) ==
>> (x-b[0])*(x-b[1])*.(x-b[n-1])
>> dont know if it can be done efficienty
>>
>>
>> On Sun, Jul 3, 2011 at 1:25 PM, Sandeep Jain wrote:
>>
>>> Agreed, BUT if you don't add a stipulation. You won't be able to reduce
>>> the complexity.
>>> For a 100% general solution, I don't think you can reduce the complexity
>>> more than O(nLgn.)
>>> There are variations of this question:
>>> --> All numbers are non-zero and distinct.
>>> --> All numbers belong to given range
>>> --> You can also have character's in place of numbers
>>> In all the above cases, you will have time complexity O(n)
>>>
>>> PS: I'm definitely looking forward to learn a solution, better than
>>> O(nLgn)
>>>
>>>
>>>
>>> Regards,
>>> Sandeep Jain
>>>
>>>
>>>
>>>
>>> On Sun, Jul 3, 2011 at 1:09 PM, sunny agrawal 
>>> wrote:
>>>
 @sandeep
 SET A -> {0,3,4,7}
 SET B -> {1,2,5,6}

 xor of all elements is zero
 sum of both the sets is same
 no of elements in both are same

 overall result : all Algorithm posted above Fails

 On Sun, Jul 3, 2011 at 12:59 PM, Sandeep Jain wrote:

> I was thinking the same, BUT here the question is that we have two
> *SETS* and that's the catch.
> So, XORing all elements of SET A with SET B should result in ZERO only
> when both the set have same elements.
>
>
> Regards,
> Sandeep Jain
>
>
>
>
>
> On Sun, Jul 3, 2011 at 11:25 AM, Pranav Agarwal <
> meetpranav...@gmail.com> wrote:
>
>> I think that the above algo will fail for the following two arrays:
>> a={2,2,3,3}
>> b={4,4,1,1}
>>
>> sum(a)=sum(b);
>> a^b=0;
>> len(a)=len(b);
>>
>> Correct me if i am wrong!
>>
>> Pranav
>>
>>
>> On Sun, Jul 3, 2011 at 7:43 AM, varun pahwa > > wrote:
>>
>>> @aditya. xor all elements mean that. take xor of each element of 1st
>>> array store in a variable that take xor of variable and each element of 
>>> the
>>> second array if all elements are common then the variable will be 0 some
>>> where.
>>> var = a[0];
>>> for(i = 1; i < sizeof(a)/sizeof(a[0]); i++)
>>> var = var ^ a[i];
>>> for(i = 0; i < sizeof(b)/sizeof(b[0]); i++)
>>> var = var ^ b[i];
>>>
>>>
>>>
>>> On Sat, Jul 2, 2011 at 2:19 PM, aditya kumar <
>>> aditya.kumar130...@gmail.com> wrote:
>>>
 @mohit..:i dint get the logic behind XOR plz explain ..nd ya i dont
 think dat you can find second largest in less than O(n).


 On Sun, Jul 3, 2011 at 2:43 AM, mohit mittal >>> > wrote:

> Dont think that the corresponding elements should be same.
> XOR Should do it anyway.
>
> Btw other question "How would you find the second largest element
> in an array using minimum no of comparisons?Any thing better than 
> O(n)."?
>
>
> On Sun, Jul 3, 2011 at 2:41 AM, aditya kumar <
> aditya.kumar130...@gmail.com> wrote:
>
>> xor will only result if corresponding elements are same . what if
>> in both the array set of integers are same but they arnt 
>> corresponding to
>> each other ??
>>
>>
>> On Sun, Jul 3, 2011 at 2:37 AM, Dumanshu wrote:
>>
>>> xor all the elements of both arrays ==0
>>> sum of 1st array == sum of 2nd array
>>> no. of elements in 1st == no. of elements in 2nd
>>> if the above conditions are met, they have the same set.
>>> m i missin sth?
>>> On Jul 3, 1:23 am, mittal  wrote:
>>> > Given two arrays of numbers, find if each of the two arrays
>>> have the same
>>> > set of ntegers ? Suggest an algo which can run faster than
>>> NlogN without
>>> > extra space?
>>>
>>> --
>>> You received this message because you are subscribed to the
>>> Google Gro

Re: [algogeeks] Re: Interview Question

[Sandeep Jain]

For case1) yes XOR works,
for Well, for the other two cases hash-maps may come in handy. :)


Regards,
Sandeep Jain




On Sun, Jul 3, 2011 at 1:48 PM, sunny agrawal wrote:

> But i don't think xor method will work at all for all of the cases above
> you mentioned.
> setA = {4,7}
> setB = {5,6}
>
> -> all numbers in both set are nonzero and distinct
> -> all numbers are in some range :D
> and for character parts it will similarly failby taking character set
> of ascii values 4,5,6,7
>
> and about general solution i dont know how to do it in O(n)
> one thing i was thinking of goes this way, taking arrays A and B instead of
> sets.
> if we can prove these polynomial to be same in O(n) time.
> (x-a[0])*(x-a[1])*.*(x-a[n-1]) ==
> (x-b[0])*(x-b[1])*.(x-b[n-1])
> dont know if it can be done efficienty
>
>
> On Sun, Jul 3, 2011 at 1:25 PM, Sandeep Jain wrote:
>
>> Agreed, BUT if you don't add a stipulation. You won't be able to reduce
>> the complexity.
>> For a 100% general solution, I don't think you can reduce the complexity
>> more than O(nLgn.)
>> There are variations of this question:
>> --> All numbers are non-zero and distinct.
>> --> All numbers belong to given range
>> --> You can also have character's in place of numbers
>> In all the above cases, you will have time complexity O(n)
>>
>> PS: I'm definitely looking forward to learn a solution, better than
>> O(nLgn)
>>
>>
>>
>> Regards,
>> Sandeep Jain
>>
>>
>>
>>
>> On Sun, Jul 3, 2011 at 1:09 PM, sunny agrawal wrote:
>>
>>> @sandeep
>>> SET A -> {0,3,4,7}
>>> SET B -> {1,2,5,6}
>>>
>>> xor of all elements is zero
>>> sum of both the sets is same
>>> no of elements in both are same
>>>
>>> overall result : all Algorithm posted above Fails
>>>
>>> On Sun, Jul 3, 2011 at 12:59 PM, Sandeep Jain wrote:
>>>
 I was thinking the same, BUT here the question is that we have two
 *SETS* and that's the catch.
 So, XORing all elements of SET A with SET B should result in ZERO only
 when both the set have same elements.


 Regards,
 Sandeep Jain





 On Sun, Jul 3, 2011 at 11:25 AM, Pranav Agarwal <
 meetpranav...@gmail.com> wrote:

> I think that the above algo will fail for the following two arrays:
> a={2,2,3,3}
> b={4,4,1,1}
>
> sum(a)=sum(b);
> a^b=0;
> len(a)=len(b);
>
> Correct me if i am wrong!
>
> Pranav
>
>
> On Sun, Jul 3, 2011 at 7:43 AM, varun pahwa 
> wrote:
>
>> @aditya. xor all elements mean that. take xor of each element of 1st
>> array store in a variable that take xor of variable and each element of 
>> the
>> second array if all elements are common then the variable will be 0 some
>> where.
>> var = a[0];
>> for(i = 1; i < sizeof(a)/sizeof(a[0]); i++)
>> var = var ^ a[i];
>> for(i = 0; i < sizeof(b)/sizeof(b[0]); i++)
>> var = var ^ b[i];
>>
>>
>>
>> On Sat, Jul 2, 2011 at 2:19 PM, aditya kumar <
>> aditya.kumar130...@gmail.com> wrote:
>>
>>> @mohit..:i dint get the logic behind XOR plz explain ..nd ya i dont
>>> think dat you can find second largest in less than O(n).
>>>
>>>
>>> On Sun, Jul 3, 2011 at 2:43 AM, mohit mittal 
>>> wrote:
>>>
 Dont think that the corresponding elements should be same.
 XOR Should do it anyway.

 Btw other question "How would you find the second largest element
 in an array using minimum no of comparisons?Any thing better than 
 O(n)."?


 On Sun, Jul 3, 2011 at 2:41 AM, aditya kumar <
 aditya.kumar130...@gmail.com> wrote:

> xor will only result if corresponding elements are same . what if
> in both the array set of integers are same but they arnt 
> corresponding to
> each other ??
>
>
> On Sun, Jul 3, 2011 at 2:37 AM, Dumanshu wrote:
>
>> xor all the elements of both arrays ==0
>> sum of 1st array == sum of 2nd array
>> no. of elements in 1st == no. of elements in 2nd
>> if the above conditions are met, they have the same set.
>> m i missin sth?
>> On Jul 3, 1:23 am, mittal  wrote:
>> > Given two arrays of numbers, find if each of the two arrays have
>> the same
>> > set of ntegers ? Suggest an algo which can run faster than NlogN
>> without
>> > extra space?
>>
>> --
>> You received this message because you are subscribed to the Google
>> Groups "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>  --

Re: [algogeeks] Re: Interview Question

[sunny agrawal]

But i don't think xor method will work at all for all of the cases above you
mentioned.
setA = {4,7}
setB = {5,6}

-> all numbers in both set are nonzero and distinct
-> all numbers are in some range :D
and for character parts it will similarly failby taking character set of
ascii values 4,5,6,7

and about general solution i dont know how to do it in O(n)
one thing i was thinking of goes this way, taking arrays A and B instead of
sets.
if we can prove these polynomial to be same in O(n) time.
(x-a[0])*(x-a[1])*.*(x-a[n-1]) ==
(x-b[0])*(x-b[1])*.(x-b[n-1])
dont know if it can be done efficienty

On Sun, Jul 3, 2011 at 1:25 PM, Sandeep Jain  wrote:

> Agreed, BUT if you don't add a stipulation. You won't be able to reduce the
> complexity.
> For a 100% general solution, I don't think you can reduce the complexity
> more than O(nLgn.)
> There are variations of this question:
> --> All numbers are non-zero and distinct.
> --> All numbers belong to given range
> --> You can also have character's in place of numbers
> In all the above cases, you will have time complexity O(n)
>
> PS: I'm definitely looking forward to learn a solution, better than O(nLgn)
>
>
>
> Regards,
> Sandeep Jain
>
>
>
>
> On Sun, Jul 3, 2011 at 1:09 PM, sunny agrawal wrote:
>
>> @sandeep
>> SET A -> {0,3,4,7}
>> SET B -> {1,2,5,6}
>>
>> xor of all elements is zero
>> sum of both the sets is same
>> no of elements in both are same
>>
>> overall result : all Algorithm posted above Fails
>>
>> On Sun, Jul 3, 2011 at 12:59 PM, Sandeep Jain wrote:
>>
>>> I was thinking the same, BUT here the question is that we have two *SETS*
>>> and that's the catch.
>>> So, XORing all elements of SET A with SET B should result in ZERO only
>>> when both the set have same elements.
>>>
>>>
>>> Regards,
>>> Sandeep Jain
>>>
>>>
>>>
>>>
>>>
>>> On Sun, Jul 3, 2011 at 11:25 AM, Pranav Agarwal >> > wrote:
>>>
 I think that the above algo will fail for the following two arrays:
 a={2,2,3,3}
 b={4,4,1,1}

 sum(a)=sum(b);
 a^b=0;
 len(a)=len(b);

 Correct me if i am wrong!

 Pranav


 On Sun, Jul 3, 2011 at 7:43 AM, varun pahwa 
 wrote:

> @aditya. xor all elements mean that. take xor of each element of 1st
> array store in a variable that take xor of variable and each element of 
> the
> second array if all elements are common then the variable will be 0 some
> where.
> var = a[0];
> for(i = 1; i < sizeof(a)/sizeof(a[0]); i++)
> var = var ^ a[i];
> for(i = 0; i < sizeof(b)/sizeof(b[0]); i++)
> var = var ^ b[i];
>
>
>
> On Sat, Jul 2, 2011 at 2:19 PM, aditya kumar <
> aditya.kumar130...@gmail.com> wrote:
>
>> @mohit..:i dint get the logic behind XOR plz explain ..nd ya i dont
>> think dat you can find second largest in less than O(n).
>>
>>
>> On Sun, Jul 3, 2011 at 2:43 AM, mohit mittal 
>> wrote:
>>
>>> Dont think that the corresponding elements should be same.
>>> XOR Should do it anyway.
>>>
>>> Btw other question "How would you find the second largest element in
>>> an array using minimum no of comparisons?Any thing better than O(n)."?
>>>
>>>
>>> On Sun, Jul 3, 2011 at 2:41 AM, aditya kumar <
>>> aditya.kumar130...@gmail.com> wrote:
>>>
 xor will only result if corresponding elements are same . what if in
 both the array set of integers are same but they arnt corresponding to 
 each
 other ??


 On Sun, Jul 3, 2011 at 2:37 AM, Dumanshu wrote:

> xor all the elements of both arrays ==0
> sum of 1st array == sum of 2nd array
> no. of elements in 1st == no. of elements in 2nd
> if the above conditions are met, they have the same set.
> m i missin sth?
> On Jul 3, 1:23 am, mittal  wrote:
> > Given two arrays of numbers, find if each of the two arrays have
> the same
> > set of ntegers ? Suggest an algo which can run faster than NlogN
> without
> > 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/algoge

Re: [algogeeks] Re: Interview Question

[Sandeep Jain]

Agreed, BUT if you don't add a stipulation. You won't be able to reduce the
complexity.
For a 100% general solution, I don't think you can reduce the complexity
more than O(nLgn.)
There are variations of this question:
--> All numbers are non-zero and distinct.
--> All numbers belong to given range
--> You can also have character's in place of numbers
In all the above cases, you will have time complexity O(n)

PS: I'm definitely looking forward to learn a solution, better than O(nLgn)



Regards,
Sandeep Jain




On Sun, Jul 3, 2011 at 1:09 PM, sunny agrawal wrote:

> @sandeep
> SET A -> {0,3,4,7}
> SET B -> {1,2,5,6}
>
> xor of all elements is zero
> sum of both the sets is same
> no of elements in both are same
>
> overall result : all Algorithm posted above Fails
>
> On Sun, Jul 3, 2011 at 12:59 PM, Sandeep Jain wrote:
>
>> I was thinking the same, BUT here the question is that we have two *SETS*
>> and that's the catch.
>> So, XORing all elements of SET A with SET B should result in ZERO only
>> when both the set have same elements.
>>
>>
>> Regards,
>> Sandeep Jain
>>
>>
>>
>>
>>
>> On Sun, Jul 3, 2011 at 11:25 AM, Pranav Agarwal 
>> wrote:
>>
>>> I think that the above algo will fail for the following two arrays:
>>> a={2,2,3,3}
>>> b={4,4,1,1}
>>>
>>> sum(a)=sum(b);
>>> a^b=0;
>>> len(a)=len(b);
>>>
>>> Correct me if i am wrong!
>>>
>>> Pranav
>>>
>>>
>>> On Sun, Jul 3, 2011 at 7:43 AM, varun pahwa wrote:
>>>
 @aditya. xor all elements mean that. take xor of each element of 1st
 array store in a variable that take xor of variable and each element of the
 second array if all elements are common then the variable will be 0 some
 where.
 var = a[0];
 for(i = 1; i < sizeof(a)/sizeof(a[0]); i++)
 var = var ^ a[i];
 for(i = 0; i < sizeof(b)/sizeof(b[0]); i++)
 var = var ^ b[i];



 On Sat, Jul 2, 2011 at 2:19 PM, aditya kumar <
 aditya.kumar130...@gmail.com> wrote:

> @mohit..:i dint get the logic behind XOR plz explain ..nd ya i dont
> think dat you can find second largest in less than O(n).
>
>
> On Sun, Jul 3, 2011 at 2:43 AM, mohit mittal wrote:
>
>> Dont think that the corresponding elements should be same.
>> XOR Should do it anyway.
>>
>> Btw other question "How would you find the second largest element in
>> an array using minimum no of comparisons?Any thing better than O(n)."?
>>
>>
>> On Sun, Jul 3, 2011 at 2:41 AM, aditya kumar <
>> aditya.kumar130...@gmail.com> wrote:
>>
>>> xor will only result if corresponding elements are same . what if in
>>> both the array set of integers are same but they arnt corresponding to 
>>> each
>>> other ??
>>>
>>>
>>> On Sun, Jul 3, 2011 at 2:37 AM, Dumanshu  wrote:
>>>
 xor all the elements of both arrays ==0
 sum of 1st array == sum of 2nd array
 no. of elements in 1st == no. of elements in 2nd
 if the above conditions are met, they have the same set.
 m i missin sth?
 On Jul 3, 1:23 am, mittal  wrote:
 > Given two arrays of numbers, find if each of the two arrays have
 the same
 > set of ntegers ? Suggest an algo which can run faster than NlogN
 without
 > 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.
>>>
>>
>>
>>
>> --
>> Mohit Mittal
>> 4th year , Computer Engineering
>> Student-Coordinator , DTU WebTeam
>> Delhi Technological University
>>
>>  --
>> You received this message because you are subscribed to the Google
>> Groups "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
>>>

Re: [algogeeks] Re: Interview Question

[sunny agrawal]

@sandeep
SET A -> {0,3,4,7}
SET B -> {1,2,5,6}

xor of all elements is zero
sum of both the sets is same
no of elements in both are same

overall result : all Algorithm posted above Fails

On Sun, Jul 3, 2011 at 12:59 PM, Sandeep Jain  wrote:

> I was thinking the same, BUT here the question is that we have two *SETS*
> and that's the catch.
> So, XORing all elements of SET A with SET B should result in ZERO only when
> both the set have same elements.
>
>
> Regards,
> Sandeep Jain
>
>
>
>
>
> On Sun, Jul 3, 2011 at 11:25 AM, Pranav Agarwal 
> wrote:
>
>> I think that the above algo will fail for the following two arrays:
>> a={2,2,3,3}
>> b={4,4,1,1}
>>
>> sum(a)=sum(b);
>> a^b=0;
>> len(a)=len(b);
>>
>> Correct me if i am wrong!
>>
>> Pranav
>>
>>
>> On Sun, Jul 3, 2011 at 7:43 AM, varun pahwa wrote:
>>
>>> @aditya. xor all elements mean that. take xor of each element of 1st
>>> array store in a variable that take xor of variable and each element of the
>>> second array if all elements are common then the variable will be 0 some
>>> where.
>>> var = a[0];
>>> for(i = 1; i < sizeof(a)/sizeof(a[0]); i++)
>>> var = var ^ a[i];
>>> for(i = 0; i < sizeof(b)/sizeof(b[0]); i++)
>>> var = var ^ b[i];
>>>
>>>
>>>
>>> On Sat, Jul 2, 2011 at 2:19 PM, aditya kumar <
>>> aditya.kumar130...@gmail.com> wrote:
>>>
 @mohit..:i dint get the logic behind XOR plz explain ..nd ya i dont
 think dat you can find second largest in less than O(n).


 On Sun, Jul 3, 2011 at 2:43 AM, mohit mittal wrote:

> Dont think that the corresponding elements should be same.
> XOR Should do it anyway.
>
> Btw other question "How would you find the second largest element in
> an array using minimum no of comparisons?Any thing better than O(n)."?
>
>
> On Sun, Jul 3, 2011 at 2:41 AM, aditya kumar <
> aditya.kumar130...@gmail.com> wrote:
>
>> xor will only result if corresponding elements are same . what if in
>> both the array set of integers are same but they arnt corresponding to 
>> each
>> other ??
>>
>>
>> On Sun, Jul 3, 2011 at 2:37 AM, Dumanshu  wrote:
>>
>>> xor all the elements of both arrays ==0
>>> sum of 1st array == sum of 2nd array
>>> no. of elements in 1st == no. of elements in 2nd
>>> if the above conditions are met, they have the same set.
>>> m i missin sth?
>>> On Jul 3, 1:23 am, mittal  wrote:
>>> > Given two arrays of numbers, find if each of the two arrays have
>>> the same
>>> > set of ntegers ? Suggest an algo which can run faster than NlogN
>>> without
>>> > 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.
>>
>
>
>
> --
> Mohit Mittal
> 4th year , Computer Engineering
> Student-Coordinator , DTU WebTeam
> Delhi Technological University
>
>  --
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

>>>
>>>
>>>
>>> --
>>> Varun Pahwa
>>> B.Tech (IT)
>>> 7th Sem.
>>> Indian Institute of Information Technology Allahabad.
>>> Ph : 09793899112 ,08011820777
>>> Official Email :: rit2008...@iiita.ac.in
>>> Another Email :: varunpahwa.ii...@gmail.com
>>>
>>> People who fail to plan are those who plan to fail.
>>>
>>>  --
>>> You received this message because you are subscribed to the Google Groups
>>> "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] Re: Interview Question

[Sandeep Jain]

I was thinking the same, BUT here the question is that we have two *SETS*
and that's the catch.
So, XORing all elements of SET A with SET B should result in ZERO only when
both the set have same elements.


Regards,
Sandeep Jain




On Sun, Jul 3, 2011 at 11:25 AM, Pranav Agarwal wrote:

> I think that the above algo will fail for the following two arrays:
> a={2,2,3,3}
> b={4,4,1,1}
>
> sum(a)=sum(b);
> a^b=0;
> len(a)=len(b);
>
> Correct me if i am wrong!
>
> Pranav
>
>
> On Sun, Jul 3, 2011 at 7:43 AM, varun pahwa wrote:
>
>> @aditya. xor all elements mean that. take xor of each element of 1st array
>> store in a variable that take xor of variable and each element of the second
>> array if all elements are common then the variable will be 0 some where.
>> var = a[0];
>> for(i = 1; i < sizeof(a)/sizeof(a[0]); i++)
>> var = var ^ a[i];
>> for(i = 0; i < sizeof(b)/sizeof(b[0]); i++)
>> var = var ^ b[i];
>>
>>
>>
>> On Sat, Jul 2, 2011 at 2:19 PM, aditya kumar <
>> aditya.kumar130...@gmail.com> wrote:
>>
>>> @mohit..:i dint get the logic behind XOR plz explain ..nd ya i dont think
>>> dat you can find second largest in less than O(n).
>>>
>>>
>>> On Sun, Jul 3, 2011 at 2:43 AM, mohit mittal wrote:
>>>
 Dont think that the corresponding elements should be same.
 XOR Should do it anyway.

 Btw other question "How would you find the second largest element in an
 array using minimum no of comparisons?Any thing better than O(n)."?


 On Sun, Jul 3, 2011 at 2:41 AM, aditya kumar <
 aditya.kumar130...@gmail.com> wrote:

> xor will only result if corresponding elements are same . what if in
> both the array set of integers are same but they arnt corresponding to 
> each
> other ??
>
>
> On Sun, Jul 3, 2011 at 2:37 AM, Dumanshu  wrote:
>
>> xor all the elements of both arrays ==0
>> sum of 1st array == sum of 2nd array
>> no. of elements in 1st == no. of elements in 2nd
>> if the above conditions are met, they have the same set.
>> m i missin sth?
>> On Jul 3, 1:23 am, mittal  wrote:
>> > Given two arrays of numbers, find if each of the two arrays have the
>> same
>> > set of ntegers ? Suggest an algo which can run faster than NlogN
>> without
>> > 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.
>



 --
 Mohit Mittal
 4th year , Computer Engineering
 Student-Coordinator , DTU WebTeam
 Delhi Technological University

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

>>>
>>>  --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> Varun Pahwa
>> B.Tech (IT)
>> 7th Sem.
>> Indian Institute of Information Technology Allahabad.
>> Ph : 09793899112 ,08011820777
>> Official Email :: rit2008...@iiita.ac.in
>> Another Email :: varunpahwa.ii...@gmail.com
>>
>> People who fail to plan are those who plan to fail.
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit 

Re: [algogeeks] Re: Interview Question

[Pranav Agarwal]

I think that the above algo will fail for the following two arrays:
a={2,2,3,3}
b={4,4,1,1}

sum(a)=sum(b);
a^b=0;
len(a)=len(b);

Correct me if i am wrong!

Pranav

On Sun, Jul 3, 2011 at 7:43 AM, varun pahwa wrote:

> @aditya. xor all elements mean that. take xor of each element of 1st array
> store in a variable that take xor of variable and each element of the second
> array if all elements are common then the variable will be 0 some where.
> var = a[0];
> for(i = 1; i < sizeof(a)/sizeof(a[0]); i++)
> var = var ^ a[i];
> for(i = 0; i < sizeof(b)/sizeof(b[0]); i++)
> var = var ^ b[i];
>
>
>
> On Sat, Jul 2, 2011 at 2:19 PM, aditya kumar  > wrote:
>
>> @mohit..:i dint get the logic behind XOR plz explain ..nd ya i dont think
>> dat you can find second largest in less than O(n).
>>
>>
>> On Sun, Jul 3, 2011 at 2:43 AM, mohit mittal wrote:
>>
>>> Dont think that the corresponding elements should be same.
>>> XOR Should do it anyway.
>>>
>>> Btw other question "How would you find the second largest element in an
>>> array using minimum no of comparisons?Any thing better than O(n)."?
>>>
>>>
>>> On Sun, Jul 3, 2011 at 2:41 AM, aditya kumar <
>>> aditya.kumar130...@gmail.com> wrote:
>>>
 xor will only result if corresponding elements are same . what if in
 both the array set of integers are same but they arnt corresponding to each
 other ??


 On Sun, Jul 3, 2011 at 2:37 AM, Dumanshu  wrote:

> xor all the elements of both arrays ==0
> sum of 1st array == sum of 2nd array
> no. of elements in 1st == no. of elements in 2nd
> if the above conditions are met, they have the same set.
> m i missin sth?
> On Jul 3, 1:23 am, mittal  wrote:
> > Given two arrays of numbers, find if each of the two arrays have the
> same
> > set of ntegers ? Suggest an algo which can run faster than NlogN
> without
> > 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.

>>>
>>>
>>>
>>> --
>>> Mohit Mittal
>>> 4th year , Computer Engineering
>>> Student-Coordinator , DTU WebTeam
>>> Delhi Technological University
>>>
>>>  --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Varun Pahwa
> B.Tech (IT)
> 7th Sem.
> Indian Institute of Information Technology Allahabad.
> Ph : 09793899112 ,08011820777
> Official Email :: rit2008...@iiita.ac.in
> Another Email :: varunpahwa.ii...@gmail.com
>
> People who fail to plan are those who plan to fail.
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] Re: Interview Question

[varun pahwa]

@aditya. xor all elements mean that. take xor of each element of 1st array
store in a variable that take xor of variable and each element of the second
array if all elements are common then the variable will be 0 some where.
var = a[0];
for(i = 1; i < sizeof(a)/sizeof(a[0]); i++)
var = var ^ a[i];
for(i = 0; i < sizeof(b)/sizeof(b[0]); i++)
var = var ^ b[i];


On Sat, Jul 2, 2011 at 2:19 PM, aditya kumar
wrote:

> @mohit..:i dint get the logic behind XOR plz explain ..nd ya i dont think
> dat you can find second largest in less than O(n).
>
>
> On Sun, Jul 3, 2011 at 2:43 AM, mohit mittal wrote:
>
>> Dont think that the corresponding elements should be same.
>> XOR Should do it anyway.
>>
>> Btw other question "How would you find the second largest element in an
>> array using minimum no of comparisons?Any thing better than O(n)."?
>>
>>
>> On Sun, Jul 3, 2011 at 2:41 AM, aditya kumar <
>> aditya.kumar130...@gmail.com> wrote:
>>
>>> xor will only result if corresponding elements are same . what if in both
>>> the array set of integers are same but they arnt corresponding to each other
>>> ??
>>>
>>>
>>> On Sun, Jul 3, 2011 at 2:37 AM, Dumanshu  wrote:
>>>
 xor all the elements of both arrays ==0
 sum of 1st array == sum of 2nd array
 no. of elements in 1st == no. of elements in 2nd
 if the above conditions are met, they have the same set.
 m i missin sth?
 On Jul 3, 1:23 am, mittal  wrote:
 > Given two arrays of numbers, find if each of the two arrays have the
 same
 > set of ntegers ? Suggest an algo which can run faster than NlogN
 without
 > 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.
>>>
>>
>>
>>
>> --
>> Mohit Mittal
>> 4th year , Computer Engineering
>> Student-Coordinator , DTU WebTeam
>> Delhi Technological University
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Varun Pahwa
B.Tech (IT)
7th Sem.
Indian Institute of Information Technology Allahabad.
Ph : 09793899112 ,08011820777
Official Email :: rit2008...@iiita.ac.in
Another Email :: varunpahwa.ii...@gmail.com

People who fail to plan are those who plan to fail.

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

Re: [algogeeks] Re: Interview Question

[aditya kumar]

@mohit..:i dint get the logic behind XOR plz explain ..nd ya i dont think
dat you can find second largest in less than O(n).

On Sun, Jul 3, 2011 at 2:43 AM, mohit mittal  wrote:

> Dont think that the corresponding elements should be same.
> XOR Should do it anyway.
>
> Btw other question "How would you find the second largest element in an
> array using minimum no of comparisons?Any thing better than O(n)."?
>
>
> On Sun, Jul 3, 2011 at 2:41 AM, aditya kumar  > wrote:
>
>> xor will only result if corresponding elements are same . what if in both
>> the array set of integers are same but they arnt corresponding to each other
>> ??
>>
>>
>> On Sun, Jul 3, 2011 at 2:37 AM, Dumanshu  wrote:
>>
>>> xor all the elements of both arrays ==0
>>> sum of 1st array == sum of 2nd array
>>> no. of elements in 1st == no. of elements in 2nd
>>> if the above conditions are met, they have the same set.
>>> m i missin sth?
>>> On Jul 3, 1:23 am, mittal  wrote:
>>> > Given two arrays of numbers, find if each of the two arrays have the
>>> same
>>> > set of ntegers ? Suggest an algo which can run faster than NlogN
>>> without
>>> > 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.
>>
>
>
>
> --
> Mohit Mittal
> 4th year , Computer Engineering
> Student-Coordinator , DTU WebTeam
> Delhi Technological University
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] Re: Interview Question

[mohit mittal]

Dont think that the corresponding elements should be same.
XOR Should do it anyway.

Btw other question "How would you find the second largest element in an
array using minimum no of comparisons?Any thing better than O(n)."?


On Sun, Jul 3, 2011 at 2:41 AM, aditya kumar
wrote:

> xor will only result if corresponding elements are same . what if in both
> the array set of integers are same but they arnt corresponding to each other
> ??
>
>
> On Sun, Jul 3, 2011 at 2:37 AM, Dumanshu  wrote:
>
>> xor all the elements of both arrays ==0
>> sum of 1st array == sum of 2nd array
>> no. of elements in 1st == no. of elements in 2nd
>> if the above conditions are met, they have the same set.
>> m i missin sth?
>> On Jul 3, 1:23 am, mittal  wrote:
>> > Given two arrays of numbers, find if each of the two arrays have the
>> same
>> > set of ntegers ? Suggest an algo which can run faster than NlogN without
>> > 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.
>



-- 
Mohit Mittal
4th year , Computer Engineering
Student-Coordinator , DTU WebTeam
Delhi Technological University

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

Re: [algogeeks] Re: Interview Question

[aditya kumar]

xor will only result if corresponding elements are same . what if in both
the array set of integers are same but they arnt corresponding to each other
??

On Sun, Jul 3, 2011 at 2:37 AM, Dumanshu  wrote:

> xor all the elements of both arrays ==0
> sum of 1st array == sum of 2nd array
> no. of elements in 1st == no. of elements in 2nd
> if the above conditions are met, they have the same set.
> m i missin sth?
> On Jul 3, 1:23 am, mittal  wrote:
> > Given two arrays of numbers, find if each of the two arrays have the same
> > set of ntegers ? Suggest an algo which can run faster than NlogN without
> > extra space?
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

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

Re: [algogeeks] Re: Interview Question

[Kamakshii Aggarwal]

but according to the question,ptr is pointing to the second node in this
case

On Fri, Apr 8, 2011 at 8:55 PM, Anurag atri wrote:

> if innitially temp is pointing to A then there is no problem in deleting
> the middle node ..
>
>
> On Fri, Apr 8, 2011 at 4:49 PM, murthy.krishn...@gmail.com <
> murthy.krishn...@gmail.com> wrote:
>
>> hii,
>>
>> Small correction
>>
>>
>> For the second case,
>>
>> Consider,
>>
>> A -> B -> C -> NULL
>>
>> Initially temp is pointing to A.
>>
>>
>> Accor 2 me he has asked to reverse d list to make it as C -> A by deleting
>> B, which can be done like this,
>>
>> temp->next = temp->next->next; // A->C->NULL
>> temp->next->next = temp; //A->C->A
>> temp = temp->next; //C->A->C
>> temp->next->next = NULL; //C->A->NULL
>>
>> Correct me, If am wrong
>>
>> Thanks,
>>
>> On Fri, Apr 8, 2011 at 4:47 PM, murthy.krishn...@gmail.com <
>> murthy.krishn...@gmail.com> wrote:
>>
>>> For the second case,
>>>
>>> Consider,
>>>
>>> A -> B -> C -> NULL
>>>
>>> Accor 2 me he has asked to reverse d list to make it as C -> A by
>>> deleting B, which can be done like this,
>>>
>>> temp->next = temp->next->next; // A->C->NULL
>>> temp->next->next = temp; //A->C->A
>>> temp = temp->next; //C->A->C
>>> temp->next->next = NULL; //C->A->NULL
>>>
>>> Correct me, If am wrong
>>>
>>> Thanks,
>>>
>>>
>>>
>>> now temp is poiting to
>>>  On Fri, Apr 8, 2011 at 2:13 PM, cegprakash wrote:
>>>
 for the second case it is possible only if the node contains the
 previous node's address. Else there should be data movement

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


>>>
>>>
>>> --
>>> P.V.N.S.S. Krishna Murthy,
>>> Intern at Broadcom Private Limited,
>>> Bangalore,
>>> Contact no:- +919845812996.
>>>
>>>
>>
>>
>> --
>> P.V.N.S.S. Krishna Murthy,
>> Intern at Broadcom Private Limited,
>> Bangalore,
>> Contact no:- +919845812996.
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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
> Anurag Atri
> II year
> Computer Engineering
> Delhi College Of Engineering
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Regards,
Kamakshi
kamakshi...@gmail.com

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

Re: [algogeeks] Re: Interview Question

[Anurag atri]

if innitially temp is pointing to A then there is no problem in deleting the
middle node ..

On Fri, Apr 8, 2011 at 4:49 PM, murthy.krishn...@gmail.com <
murthy.krishn...@gmail.com> wrote:

> hii,
>
> Small correction
>
>
> For the second case,
>
> Consider,
>
> A -> B -> C -> NULL
>
> Initially temp is pointing to A.
>
>
> Accor 2 me he has asked to reverse d list to make it as C -> A by deleting
> B, which can be done like this,
>
> temp->next = temp->next->next; // A->C->NULL
> temp->next->next = temp; //A->C->A
> temp = temp->next; //C->A->C
> temp->next->next = NULL; //C->A->NULL
>
> Correct me, If am wrong
>
> Thanks,
>
> On Fri, Apr 8, 2011 at 4:47 PM, murthy.krishn...@gmail.com <
> murthy.krishn...@gmail.com> wrote:
>
>> For the second case,
>>
>> Consider,
>>
>> A -> B -> C -> NULL
>>
>> Accor 2 me he has asked to reverse d list to make it as C -> A by deleting
>> B, which can be done like this,
>>
>> temp->next = temp->next->next; // A->C->NULL
>> temp->next->next = temp; //A->C->A
>> temp = temp->next; //C->A->C
>> temp->next->next = NULL; //C->A->NULL
>>
>> Correct me, If am wrong
>>
>> Thanks,
>>
>>
>>
>> now temp is poiting to
>>  On Fri, Apr 8, 2011 at 2:13 PM, cegprakash  wrote:
>>
>>> for the second case it is possible only if the node contains the
>>> previous node's address. Else there should be data movement
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>
>>
>> --
>> P.V.N.S.S. Krishna Murthy,
>> Intern at Broadcom Private Limited,
>> Bangalore,
>> Contact no:- +919845812996.
>>
>>
>
>
> --
> P.V.N.S.S. Krishna Murthy,
> Intern at Broadcom Private Limited,
> Bangalore,
> Contact no:- +919845812996.
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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
Anurag Atri
II year
Computer Engineering
Delhi College Of Engineering

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

Re: [algogeeks] Re: Interview Question

[murthy.krishn...@gmail.com]

hii,

Small correction

For the second case,

Consider,

A -> B -> C -> NULL

Initially temp is pointing to A.

Accor 2 me he has asked to reverse d list to make it as C -> A by deleting
B, which can be done like this,

temp->next = temp->next->next; // A->C->NULL
temp->next->next = temp; //A->C->A
temp = temp->next; //C->A->C
temp->next->next = NULL; //C->A->NULL

Correct me, If am wrong

Thanks,

On Fri, Apr 8, 2011 at 4:47 PM, murthy.krishn...@gmail.com <
murthy.krishn...@gmail.com> wrote:

> For the second case,
>
> Consider,
>
> A -> B -> C -> NULL
>
> Accor 2 me he has asked to reverse d list to make it as C -> A by deleting
> B, which can be done like this,
>
> temp->next = temp->next->next; // A->C->NULL
> temp->next->next = temp; //A->C->A
> temp = temp->next; //C->A->C
> temp->next->next = NULL; //C->A->NULL
>
> Correct me, If am wrong
>
> Thanks,
>
>
>
> now temp is poiting to
> On Fri, Apr 8, 2011 at 2:13 PM, cegprakash  wrote:
>
>> for the second case it is possible only if the node contains the
>> previous node's address. Else there should be data movement
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
> P.V.N.S.S. Krishna Murthy,
> Intern at Broadcom Private Limited,
> Bangalore,
> Contact no:- +919845812996.
>
>


-- 
P.V.N.S.S. Krishna Murthy,
Intern at Broadcom Private Limited,
Bangalore,
Contact no:- +919845812996.

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

Re: [algogeeks] Re: Interview Question

[murthy.krishn...@gmail.com]

For the second case,

Consider,

A -> B -> C -> NULL

Accor 2 me he has asked to reverse d list to make it as C -> A by deleting
B, which can be done like this,

temp->next = temp->next->next; // A->C->NULL
temp->next->next = temp; //A->C->A
temp = temp->next; //C->A->C
temp->next->next = NULL; //C->A->NULL

Correct me, If am wrong

Thanks,



now temp is poiting to
On Fri, Apr 8, 2011 at 2:13 PM, cegprakash  wrote:

> for the second case it is possible only if the node contains the
> previous node's address. Else there should be data movement
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>


-- 
P.V.N.S.S. Krishna Murthy,
Intern at Broadcom Private Limited,
Bangalore,
Contact no:- +919845812996.

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

Re: [algogeeks] Re: Interview question amazon

[juver++]

Why??? It doesn't help to solve problem. You are already have tree structure 
with parent links. Taunt.

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

Re: [algogeeks] Re: Interview question amazon

[rahul patil]

On Tue, Jan 4, 2011 at 8:13 AM, rahul patil
wrote:

>
>
> On Mon, Jan 3, 2011 at 6:08 PM, juver++  wrote:
>
>> Tree structure already have parent node link. Even we reconstruct the tree
>> as linked list we are not allowed to achieve
>
>
> Normal tree node does not contain link to its parent. I am not saying
> convert tree into linklist directly. I want to say that convert tree into a
> branched list(not linear) in which each node can have (at max) 2 nodes as
> its next.
>
> Further u can add some extra fields into ur node struct for optimal
> solution.
>

Just add and set a link to parent of node in node struct it will be a
branched list.



>
>
>> the goal. Path can be combined using non-contigious (created from inorder
>> traversal) elements. The only solution is using DP with O(MAX_SUM_VALUE)
>> extra space for each node.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
>
> --
> Regards,
> Rahul Patil
>



-- 
Regards,
Rahul Patil

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

Re: [algogeeks] Re: Interview question amazon

[rahul patil]

On Mon, Jan 3, 2011 at 6:08 PM, juver++  wrote:

> Tree structure already have parent node link. Even we reconstruct the tree
> as linked list we are not allowed to achieve


Normal tree node does not contain link to its parent. I am not saying
convert tree into linklist directly. I want to say that convert tree into a
branched list(not linear) in which each node can have (at max) 2 nodes as
its next.

Further u can add some extra fields into ur node struct for optimal
solution.


> the goal. Path can be combined using non-contigious (created from inorder
> traversal) elements. The only solution is using DP with O(MAX_SUM_VALUE)
> extra space for each node.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>




-- 
Regards,
Rahul Patil

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

Re: [algogeeks] Re: Interview question amazon

[juver++]

Tree structure already have parent node link. Even we reconstruct the tree 
as linked list we are not allowed to achieve the goal. Path can be combined 
using non-contigious (created from inorder traversal) elements. The only 
solution is using DP with O(MAX_SUM_VALUE) extra space for each node.

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

Re: [algogeeks] Re: Interview question amazon

[rahul patil]

On Sun, Jan 2, 2011 at 8:30 PM, Akash Agrawal wrote:

> I have written a kinda messed-up code for the same. Which is basically a
> bottom-up approach.
>
> Please find the same as attached. Some boundary conditions might be missed
> and code can be written in a more decorated, beautiful fashion.
>
> Logic:
>
>- start from the root,
>- keep the nodes value in an array.
>- Move up until current node is right child of its parent.
>- then search for value in right sub-tree.(LFS)
>
>
> Regards,
> Akash Agrawal
> http://tech-queries.blogspot.com/
>
>
>
> On Fri, Dec 31, 2010 at 7:59 PM, MAC  wrote:
>
>> No , we had to find all the paths . Some paths could include the root .
>>
>>
>> On Tue, Dec 28, 2010 at 11:12 PM, yq Zhang wrote:
>>
>>> I think the original question says "Path can go from left subtree tree ,
>>> include root and go to right tree as well". This should mean the path must
>>> include the root.
>>>
>>>
>>> On Tue, Dec 28, 2010 at 4:52 AM, shanushaan <
>>> er.srivastavaro...@gmail.com> wrote:
>>>
 Not clear what path you are referring to.

 Question. Should the path include root value always? (What is problem
 with only left or only right path (not containing root))
   In your example for 16 one more path can be 0 1 5 10 as
 well. Should algo return all the paths or just first one.

 On Dec 26, 10:08 pm, MAC  wrote:
 > you are given a bst where each node has a int value , parent pointer ,
 and
 > left and right pointers , write a function to find a path with a given
 sum
 > value. Path can go from left subtree tree , include root and go to
 right
 > tree as well . we need to find these paths also .
 >
 > 5
 >1 10
 > 0 2  6 11
 >
 > so to find 16 we say it is 1 to 5 to 10
 >
 > --
 > thanks
 > --mac

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


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


If we rebuild a tree in which a node can point its parent too(adding extra
field parent in tree node)
then whole tree structure  will look like branched linked list.

Then, it will be easy to find out the best complexity solution with the help
of dynamic programming approach and introducing boundaries.

though it will take extra O(n) space and at max  O(n^2) time complexity.

-- 
Regards,
Rahul Patil

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

Re: [algogeeks] Re: Interview question amazon

[Akash Agrawal]

I have written a kinda messed-up code for the same. Which is basically a
bottom-up approach.

Please find the same as attached. Some boundary conditions might be missed
and code can be written in a more decorated, beautiful fashion.

Logic:

   - start from the root,
   - keep the nodes value in an array.
   - Move up until current node is right child of its parent.
   - then search for value in right sub-tree.(LFS)


Regards,
Akash Agrawal
http://tech-queries.blogspot.com/


On Fri, Dec 31, 2010 at 7:59 PM, MAC  wrote:

> No , we had to find all the paths . Some paths could include the root .
>
>
> On Tue, Dec 28, 2010 at 11:12 PM, yq Zhang  wrote:
>
>> I think the original question says "Path can go from left subtree tree ,
>> include root and go to right tree as well". This should mean the path must
>> include the root.
>>
>>
>> On Tue, Dec 28, 2010 at 4:52 AM, shanushaan > > wrote:
>>
>>> Not clear what path you are referring to.
>>>
>>> Question. Should the path include root value always? (What is problem
>>> with only left or only right path (not containing root))
>>>   In your example for 16 one more path can be 0 1 5 10 as
>>> well. Should algo return all the paths or just first one.
>>>
>>> On Dec 26, 10:08 pm, MAC  wrote:
>>> > you are given a bst where each node has a int value , parent pointer ,
>>> and
>>> > left and right pointers , write a function to find a path with a given
>>> sum
>>> > value. Path can go from left subtree tree , include root and go to
>>> right
>>> > tree as well . we need to find these paths also .
>>> >
>>> > 5
>>> >1 10
>>> > 0 2  6 11
>>> >
>>> > so to find 16 we say it is 1 to 5 to 10
>>> >
>>> > --
>>> > thanks
>>> > --mac
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> thanks
> --mac
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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



treesum.cc
Description: Binary data

Re: [algogeeks] Re: Interview question amazon

[MAC]

No , we had to find all the paths . Some paths could include the root .

On Tue, Dec 28, 2010 at 11:12 PM, yq Zhang  wrote:

> I think the original question says "Path can go from left subtree tree ,
> include root and go to right tree as well". This should mean the path must
> include the root.
>
>
> On Tue, Dec 28, 2010 at 4:52 AM, shanushaan 
> wrote:
>
>> Not clear what path you are referring to.
>>
>> Question. Should the path include root value always? (What is problem
>> with only left or only right path (not containing root))
>>   In your example for 16 one more path can be 0 1 5 10 as
>> well. Should algo return all the paths or just first one.
>>
>> On Dec 26, 10:08 pm, MAC  wrote:
>> > you are given a bst where each node has a int value , parent pointer ,
>> and
>> > left and right pointers , write a function to find a path with a given
>> sum
>> > value. Path can go from left subtree tree , include root and go to right
>> > tree as well . we need to find these paths also .
>> >
>> > 5
>> >1 10
>> > 0 2  6 11
>> >
>> > so to find 16 we say it is 1 to 5 to 10
>> >
>> > --
>> > thanks
>> > --mac
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
thanks
--mac

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

Re: [algogeeks] Re: Interview question amazon

[yq Zhang]

I think the original question says "Path can go from left subtree tree ,
include root and go to right tree as well". This should mean the path must
include the root.

On Tue, Dec 28, 2010 at 4:52 AM, shanushaan wrote:

> Not clear what path you are referring to.
>
> Question. Should the path include root value always? (What is problem
> with only left or only right path (not containing root))
>   In your example for 16 one more path can be 0 1 5 10 as
> well. Should algo return all the paths or just first one.
>
> On Dec 26, 10:08 pm, MAC  wrote:
> > you are given a bst where each node has a int value , parent pointer ,
> and
> > left and right pointers , write a function to find a path with a given
> sum
> > value. Path can go from left subtree tree , include root and go to right
> > tree as well . we need to find these paths also .
> >
> > 5
> >1 10
> > 0 2  6 11
> >
> > so to find 16 we say it is 1 to 5 to 10
> >
> > --
> > thanks
> > --mac
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

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

Re: [algogeeks] Re: Interview question

[juver++]

Check it once again. There is no submatrix with 8 1's in it.

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

Re: [algogeeks] Re: Interview question

[monty 1987]

Hi ,
  the program outputs the co-ordinate of bottom-right of the largest
1*1 rectangular submatrix and the size is total number of elements in that
matrix.

On Mon, Dec 27, 2010 at 7:31 PM, juver++  wrote:

> Program is incorrect. Why does it output the following answer: point at
> (3,5 )size is 8???
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] Re: Interview question

[juver++]

Program is incorrect. Why does it output the following answer: point at (3,5 
)size is 8???

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

Re: [algogeeks] Re: Interview question

[monty 1987]

Hi Guys ,
 I have coded the first part soon i will come with the
solution of part 2 :---
Let me know if u find any error case (hope u will find none)

public class Largestsubmatrix {
 public point [][] a;
int [][] binmatrix;
public point loc;
 public Largestsubmatrix(int [][] a) {
this.binmatrix =a;
}
 public void preProcess(){
a = new point[binmatrix.length][binmatrix[0].length];
if(binmatrix[0][0] ==1){
a[0][0]=new point(1,1);
}
else {
a[0][0]=new point(0,0);
}
 for(int i=1;i a[i][j-1].y ){
a[i][j] =  new point(a[i-1][j].x +1 ,1);
 }
else{
a[i][j] = new point(1,a[i][j-1].y + 1);
}
}
else{
if(a[i-1][j].x > a[i][j-1].x)
tempx = a[i][j-1].x+1;
else
tempx = a[i-1][j].x+1;
if(a[i-1][j].y > a[i][j-1].y)
tempy = a[i][j-1].y+1;
else
tempy = a[i-1][j].y+1;
a[i][j] = new point(tempx,tempy);
}
}
else{
a[i][j] =new point(0, 0);
 }
}
int val =-5;
loc = new point(0,0);
for(int i =0; i temp ? val : (temp)) ;
if(temp == val){
loc.x=i;loc.y=j;
}
}
}
public class point{
public int x;
public int y;
public point(int x, int y){
this.x=x;
this.y=y;
}
}
public static void main(String args[]){
 int[][] a  =
{{0,0,0,1,0,0,0},{0,1,1,0,0,0,0},{0,0,0,1,1,1,0},{0,0,1,1,1,1,1},{1,1,0,1,0,0,0},{1,1,1,1,0,0,0}};
 Largestsubmatrix ls = new Largestsubmatrix(a);
 ls.preProcess();
 int size = ls.a[ls.loc.x][ls.loc.y].x * ls.a[ls.loc.x][ls.loc.y].y ;
 System.out.print("point at (" + ls.loc.x + "," + ls.loc.y + " )" +
"size is " + size );

}
}





On Sun, Dec 26, 2010 at 3:31 AM, yq Zhang  wrote:

> How to solve the second question? it is different from the other question
> posted where it requres only SQUARE sub matrix.
>
> Sent from Nexus one
> On Dec 25, 2010 11:00 AM, "juver++"  wrote:
> > Try to search the answer before sumbitting the question here.
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> > For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
> >
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] Re: Interview question

[yq Zhang]

How to solve the second question? it is different from the other question
posted where it requres only SQUARE sub matrix.

Sent from Nexus one
On Dec 25, 2010 11:00 AM, "juver++"  wrote:
> Try to search the answer before sumbitting the question here.
>
> --
> You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
.
> For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] Re: interview-question

[jalaj jaiswal]

@ritesh..you dnt have to output v.. you have to output the minimum number of
flips so that your tree evaluates to v(v is either 0 or 1)
and if it alreday evaluates to v then return 0(no flips required)
if not possible return -1


On Wed, Aug 4, 2010 at 12:11 AM, RITESH SRIVASTAV
wrote:

> level of the tree is given or not ?
> and where do we have to output V , just at the node we get it or at
> the  root ?
>
> On Aug 3, 1:56 pm, jalaj jaiswal  wrote:
> > given a complete binary tree (either a node is a leaf node or has two
> > children)
> > every leaf node has value 0 or 1.
> > every internal node has value as the AND gate or OR gate.
> > you are given with the tree and a value V.
> > you have to output the minimum number of flips (AND to OR or OR to AND)
> if
> > the evaluated value is not equal to V, if it is equal return 0, if not
> > possible return -1.
> > you can just change the value of internal nodes i.e can make and to or ,
> or
> > to and to get the desired output
> > give the minimum number of flips required to get the desired output.
> >
> > --
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>


-- 
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD

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

Re: [algogeeks] Re: interview-question

[Abhishek Shrivastav]

I hope the value of V is 0 or 1. Is this right?

On Wed, Aug 4, 2010 at 12:48 AM, Manjunath Manohar  wrote:

> @above: i have little difficulty in perceiving the question... can u give
> certain test cases..sample input/output ..
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Regards,
Abhishek Shrivastav

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

Re: [algogeeks] Re: interview-question

[Manjunath Manohar]

@above: i have little difficulty in perceiving the question... can u give
certain test cases..sample input/output ..

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

Re: [algogeeks] Re: interview-question

[Seçkin Can Şahin]

write a recursive function getmin(node, value) that returns the least number
of flips necessary for the subtree rooted at "node" to give the result
"value". recursive relations are easy to come up with, so I leave it as an
exercise :)

memorize the values calculated, so, never calculate a result more than once.

Since "value" is either 0 or 1, this algorithm works in O(n) time and space
complexity where n is the number of nodes.


On Tue, Aug 3, 2010 at 11:41 AM, RITESH SRIVASTAV
wrote:

> level of the tree is given or not ?
> and where do we have to output V , just at the node we get it or at
> the  root ?
>
> On Aug 3, 1:56 pm, jalaj jaiswal  wrote:
> > given a complete binary tree (either a node is a leaf node or has two
> > children)
> > every leaf node has value 0 or 1.
> > every internal node has value as the AND gate or OR gate.
> > you are given with the tree and a value V.
> > you have to output the minimum number of flips (AND to OR or OR to AND)
> if
> > the evaluated value is not equal to V, if it is equal return 0, if not
> > possible return -1.
> > you can just change the value of internal nodes i.e can make and to or ,
> or
> > to and to get the desired output
> > give the minimum number of flips required to get the desired output.
> >
> > --
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

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