[algogeeks] Re: Interview Question
@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 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
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 dave_and_da...@juno.com 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.
[algogeeks] Re: Interview question
isnt the complexity should be o(m*n*n) instead of (n*n*n) as m can be greater than n..plz comment On Wed, Apr 10, 2013 at 10:11 PM, rahul sharma rahul23111...@gmail.comwrote: http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/ wat is complexity of thisn3 or mn2 -- 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. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: Interview question
M is a matrix, not a number. M is NxN, so the algorithm is O(N^3) as stated in the text. On Apr 10, 4:19 pm, rahul sharma rahul23111...@gmail.com wrote: isnt the complexity should be o(m*n*n) instead of (n*n*n) as m can be greater than n..plz comment On Wed, Apr 10, 2013 at 10:11 PM, rahul sharma rahul23111...@gmail.comwrote: http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-recta... wat is complexity of thisn3 or mn2 -- 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. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: Interview question
M is number of rows n n is col..outer 2 loops are running n times and inner is for kadane m tymes n for temp m times total 2m...so isnt it should be n*n*m? On Thursday, April 11, 2013, Don dondod...@gmail.com wrote: M is a matrix, not a number. M is NxN, so the algorithm is O(N^3) as stated in the text. On Apr 10, 4:19 pm, rahul sharma rahul23111...@gmail.com wrote: isnt the complexity should be o(m*n*n) instead of (n*n*n) as m can be greater than n..plz comment On Wed, Apr 10, 2013 at 10:11 PM, rahul sharma rahul23111...@gmail.com wrote: http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-recta... wat is complexity of thisn3 or mn2 -- 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. For more options, visit https://groups.google.com/groups/opt_out. -- 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. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Interview Question
Hope this helps :
space: o(n^2)
time: o(n^2)
#includeiostream
using namespace std;
inline int max(int a,int b)
{
if(ab)
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;in;i++)
{
sum[0][i]=sum[0][i-1]+arr[0][i];
sum[i][0]=sum[i-1][0]+arr[i][0];
}
for(i=1;in;i++)
{
for(j=1;jn;j++)
{
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j];
}
}
int min=INT_MAX;
for(i=0;in;i++)
{
for(j=0;jn;j++)
{
int
k=max(max(sum[i][j],sum[n-1][n-1]+sum[i][j]-sum[n-1][j]-sum[i][n-1]),max(sum[i][n-1]-sum[i][j],sum[n-1][j]-sum[i][j]));
if(mink)
min=k;
}
}
coutans : min;
}
On Fri, Aug 17, 2012 at 6:36 PM, sahil taneja sahiltanej...@gmail.comwrote:
@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
# 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++;rown-1)
for(int col=0;col++;coln-1)
{
for(int i=0;i=row;i++)
{
for(int j=0;j=col;j++)
a+=arr[i][j];
for(int j=col;j=n-1;j++)
b+=arr[i][j];
}
for(int i=row+1;i=n-1;i++)
{
for(int j=0;j=col;j++)
c+=arr[i][j];
for(int j=col;j=n-1;j++)
d+=arr[i][j];
}
max=maximum(max,maximum(maximum(a,b),maximum(c,d))); //maximum(a,b)
is predefined function to find maximum of two nos.
min=minimum(min,minimum(minimum(a,b),minimum(c,d)));
}
coutmax:max;
coutmin:min;
}
please check it and let me know if any m
On Thursday, August 16, 2012 2:09:20 PM UTC+5:30, g4ur4v wrote:
@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.
[algogeeks] Re: Interview Question
@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.
[algogeeks] Re: Interview Question
Can any one help me with this ...Any DP solution? 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/-/tNlJhsd8r-MJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
@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
Navin , your reply is correct. On Sat, May 19, 2012 at 10:36 PM, Gene gene.ress...@gmail.com 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=iN, zero width and unit depth, and the base 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 nikhil.bhoja...@gmail.com 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.
[algogeeks] Re: Interview Question based on histogram
we need to find the amount of water stored on every bar of the histogram. For this, we need to find two values :- v1 :- the highest bar to the left - O(n) v2:- the highest bar to the right - O(n) amount of the water stored on the current bar is Res= ( minimum of the two values(v1,v2) - height of the bar ) (assuming the length breadth of bar is unity) sum all the values of water store on individual bar Time complexity - O(n) Space Complexity - O(n) On Thursday, 17 May 2012 11:27:44 UTC+5:30, Nik_nitdgp 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,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd On Thursday, 17 May 2012 11:27:44 UTC+5:30, Nik_nitdgp 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,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd On Thursday, 17 May 2012 11:27:44 UTC+5:30, Nik_nitdgp 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,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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/SRp0wWOK_kUJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Interview Question based on histogram
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=iN, zero width and unit depth, and the base 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 nikhil.bhoja...@gmail.com 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.
Re: [algogeeks] Re: Interview question
+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
@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.comwrote: +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
@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;in;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 sinv...@gmail.com 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.comwrote:
+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
wont work for all cases...ignore
i will post the algoonce i fix it
On 25 Mar 2012 17:06, Amol Sharma amolsharm...@gmail.com 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://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Sun, Mar 25, 2012 at 4:51 PM, atul anand atul.87fri...@gmail.comwrote:
@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;in;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 sinv...@gmail.com 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.comwrote:
+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.
[algogeeks] Re: Interview question
http://www.geeksforgeeks.org/archives/8405
^ Similar Question.
On Mar 25, 4:49 pm, atul anand atul.87fri...@gmail.com wrote:
wont work for all cases...ignore
i will post the algoonce i fix it
On 25 Mar 2012 17:06, Amol Sharma amolsharm...@gmail.com 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://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Sun, Mar 25, 2012 at 4:51 PM, atul anand atul.87fri...@gmail.comwrote:
@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;in;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 sinv...@gmail.com 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.comwrote:
+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
http://www.geeksforgeeks.org/archives/8405
^ Similar question.
On Sun, Mar 25, 2012 at 5:19 PM, atul anand atul.87fri...@gmail.com wrote:
wont work for all cases...ignore
i will post the algoonce i fix it
On 25 Mar 2012 17:06, Amol Sharma amolsharm...@gmail.com 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://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Sun, Mar 25, 2012 at 4:51 PM, atul anand atul.87fri...@gmail.comwrote:
@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;in;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 sinv...@gmail.com 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
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 algo.b...@gmail.com wrote:
http://www.geeksforgeeks.org/archives/8405
^ Similar Question.
On Mar 25, 4:49 pm, atul anand atul.87fri...@gmail.com wrote:
wont work for all cases...ignore
i will post the algoonce i fix it
On 25 Mar 2012 17:06, Amol Sharma amolsharm...@gmail.com 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://gplus.to/amolsharma99 http://twitter.com/amolsharma99
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 atul.87fri...@gmail.com
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;in;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 sinv...@gmail.com 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.comwrote:
+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
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;in;i++)
{
next= i ;
if(isEmpty(s))
{
idx=pop(s);
while(arr[idx] 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 algo.b...@gmail.com wrote:
http://www.geeksforgeeks.org/archives/8405
^ Similar question.
On Sun, Mar 25, 2012 at 5:19 PM, atul anand atul.87fri...@gmail.comwrote:
wont work for all cases...ignore
i will post the algoonce i fix it
On 25 Mar 2012 17:06, Amol Sharma amolsharm...@gmail.com 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://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Sun, Mar 25, 2012 at 4:51 PM, atul anand atul.87fri...@gmail.comwrote:
@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;in;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 sinv...@gmail.com 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 Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Interview question
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 navin.nit...@gmail.com 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.
Re: [algogeeks] Re: Interview question
@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 gene.ress...@gmail.com 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 navin.nit...@gmail.com 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
n = x%2 ? x can be any integer. On Fri, Dec 2, 2011 at 5:19 PM, Don dondod...@gmail.com wrote: (!x || !(x^1)) !(x1) !((x|1)-1) (x*x)==x (x==(x==x))||(x==(x!=x)) etc. On Nov 29, 9:07 pm, Nitin Garg nitin.garg.i...@gmail.com 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.
[algogeeks] Re: Interview question
(!x || !(x^1)) !(x1) !((x|1)-1) (x*x)==x (x==(x==x))||(x==(x!=x)) etc. On Nov 29, 9:07 pm, Nitin Garg nitin.garg.i...@gmail.com 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.
[algogeeks] Re: Interview question
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 kodaligopi...@gmail.com 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.
Re: [algogeeks] Re: Interview question
@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 kodaligopi...@gmail.com 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 kodaligopi...@gmail.com 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
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 medu...@gmail.com 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 kodaligopi...@gmail.com 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 kodaligopi...@gmail.com 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.
[algogeeks] Re: Interview question
Hi Yogesh
start and end denote the indexes where the set that is to be moved
starts and ends in the given array.
Destination index denotes the index in the array where the given set
is to be moved. This needs some
rearrangement of the array elements as shown in the example before.
Hope that clarifies.
Thanks
Gopi
On Jul 9, 6:55 pm, Yogesh Yadav medu...@gmail.com 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 kodaligopi...@gmail.com 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 kodaligopi...@gmail.com 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.- 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.
[algogeeks] Re: Interview question
@sunny
That's excellent. Thanks Sunny.
On Jul 9, 7:04 pm, sunny agrawal sunny816.i...@gmail.com wrote:
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 medu...@gmail.com 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 kodaligopi...@gmail.com 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 kodaligopi...@gmail.com 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- 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.
[algogeeks] Re: Interview Question
If you allow for the following assumptions: 1. All numbers fit into a 32 bit or 64 bit integer. 2. The arrays are actually linked lists. Time complexity: O(N) Space complexity: O(1) Solution: 1. Apply radix sort. (binary radix sort would probably do fine) Note: You can make the sort stable only because of the linked lists (can't be done in a simple array). This is the reason for the 2 assumptions. Complexiy: O(N K). Space: 2 extra pointers = O(1). 2. Find mismatches between the 2 sorted sequences. O(N) The 2nd assumption sort-of cheats because it implicitly requires O(N) extra space in the pointers of the linked list. -- DK http://twitter.com/divyekapoor http://www.divye.in -- 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/-/vgEeAQHJN08J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
Yes I know I said it with regard to the current problem On Tue, Jul 5, 2011 at 8:58 AM, Dave dave_and_da...@juno.com 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 saurab...@gmail.com wrote: Again heap will require extra space. On Tue, Jul 5, 2011 at 8:25 AM, vaibhav agarwal vibhu.bitspil...@gmail.comwrote: 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 saurab...@gmail.com 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
@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 saurab...@gmail.com wrote: Yes I know I said it with regard to the current problem On Tue, Jul 5, 2011 at 8:58 AM, Dave dave_and_da...@juno.com 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 saurab...@gmail.com wrote: Again heap will require extra space. On Tue, Jul 5, 2011 at 8:25 AM, vaibhav agarwal vibhu.bitspil...@gmail.comwrote: 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 saurab...@gmail.com 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
http://www.cim.mcgill.ca/~langer/250/2010/lecture24.pdf On Tue, Jul 5, 2011 at 12:37 PM, vaibhav agarwal vibhu.bitspil...@gmail.com 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 saurab...@gmail.com wrote: Yes I know I said it with regard to the current problem On Tue, Jul 5, 2011 at 8:58 AM, Dave dave_and_da...@juno.com 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 saurab...@gmail.com wrote: Again heap will require extra space. On Tue, Jul 5, 2011 at 8:25 AM, vaibhav agarwal vibhu.bitspil...@gmail.comwrote: 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 saurab...@gmail.com 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
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 vibhu.bitspil...@gmail.com 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 saurab...@gmail.com wrote: Yes I know I said it with regard to the current problem On Tue, Jul 5, 2011 at 8:58 AM, Dave dave_and_da...@juno.com 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 saurab...@gmail.com wrote: Again heap will require extra space. On Tue, Jul 5, 2011 at 8:25 AM, vaibhav agarwal vibhu.bitspil...@gmail.comwrote: 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 saurab...@gmail.com 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
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
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 saurab...@gmail.com 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
Again heap will require extra space. On Tue, Jul 5, 2011 at 8:25 AM, vaibhav agarwal vibhu.bitspil...@gmail.comwrote: 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 saurab...@gmail.com 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
@saurabh bt we need only one extra array On Mon, Jul 4, 2011 at 11:02 PM, saurabh singh saurab...@gmail.com 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 saurab...@gmail.comwrote: 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.
[algogeeks] Re: Interview Question
@Vaibhav: Construction of a heap can be done in-place, but time complexity is O(n log n). Dave On Jul 4, 9:55 pm, 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 saurab...@gmail.com 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.- 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.
[algogeeks] Re: Interview Question
@Saurabh: Nope. You can construct a heap in-place. But it is not O(n). Dave On Jul 4, 10:02 pm, saurabh singh saurab...@gmail.com wrote: Again heap will require extra space. On Tue, Jul 5, 2011 at 8:25 AM, vaibhav agarwal vibhu.bitspil...@gmail.comwrote: 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 saurab...@gmail.com 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.
Re: [algogeeks] Re: Interview Question
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.comwrote:
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.comwrote:
@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.comwrote:
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 duman...@gmail.com 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 mohitm.1...@gmail.com 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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
Re: [algogeeks] Re: Interview Question
@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 sandeep6...@gmail.com 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.comwrote:
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.comwrote:
@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.comwrote:
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 duman...@gmail.com 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 mohitm.1...@gmail.com 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.
--
You received this message because you are
Re: [algogeeks] Re: Interview Question
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 sunny816.i...@gmail.comwrote:
@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 sandeep6...@gmail.comwrote:
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.comwrote:
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.comwrote:
@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.comwrote:
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 duman...@gmail.com 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 mohitm.1...@gmail.com 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
Re: [algogeeks] Re: Interview Question
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 sandeep6...@gmail.com 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 sunny816.i...@gmail.comwrote:
@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 sandeep6...@gmail.comwrote:
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.comwrote:
@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.comwrote:
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 duman...@gmail.comwrote:
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 mohitm.1...@gmail.com 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
Re: [algogeeks] Re: Interview Question
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 sandeep6...@gmail.com 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 sunny816.i...@gmail.comwrote:
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 sandeep6...@gmail.comwrote:
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
sunny816.i...@gmail.comwrote:
@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 sandeep6...@gmail.comwrote:
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 duman...@gmail.comwrote:
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 mohitm.1...@gmail.com 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
[algogeeks] Re: Interview Question
Either you will have to use hashmaps which means extra storage or compromise on time complexity as nlogn I dont think there is any other possible workaround! -- 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/-/21xV7cUULxcJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
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 deok...@gmail.com 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 sandeep6...@gmail.comwrote:
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 sunny816.i...@gmail.comwrote:
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 sandeep6...@gmail.comwrote:
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
sunny816.i...@gmail.comwrote:
@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
sandeep6...@gmail.comwrote:
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 duman...@gmail.comwrote:
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 mohitm.1...@gmail.com 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] Re: Interview Question
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 mohitm.1...@gmail.com 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
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 duman...@gmail.com 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 mohitm.1...@gmail.com 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
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.comwrote: 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 duman...@gmail.com 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 mohitm.1...@gmail.com 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
@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 duman...@gmail.com 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 mohitm.1...@gmail.com 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
@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.comwrote: @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.comwrote: 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 duman...@gmail.com 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 mohitm.1...@gmail.com 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
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.comwrote:
@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.comwrote:
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 duman...@gmail.com 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 mohitm.1...@gmail.com 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
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 anu.anurag@gmail.comwrote: 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 cegprak...@gmail.comwrote: 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.
[algogeeks] Re: Interview Question
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.
Re: [algogeeks] Re: Interview Question
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 cegprak...@gmail.com 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
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 cegprak...@gmail.com 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
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 cegprak...@gmail.com 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.
[algogeeks] Re: Interview Question
Anyone here who can answer this question? On Mon, Apr 4, 2011 at 9:18 PM, Umer Farooq the.um...@gmail.com wrote: Hello friends, The following question has appeared in two top companies of my city. I'd appreciate if anyone is able to answer it. Given a singly liked list comprising of three nodes Delete the middle node such that: 1- A temp pointer is pointing to the first node 2- A temp pointer is pointing to the second node. You can not use any other pointer and you can not move data. -- Umer -- Umer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Interview question amazon
@mac Path always should be go through the root of the tree? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Interview question amazon
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
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
On Mon, Jan 3, 2011 at 6:08 PM, juver++ avpostni...@gmail.com 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.comalgogeeks%2bunsubscr...@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
On Tue, Jan 4, 2011 at 8:13 AM, rahul patil rahul.deshmukhpa...@gmail.comwrote: On Mon, Jan 3, 2011 at 6:08 PM, juver++ avpostni...@gmail.com 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.comalgogeeks%2bunsubscr...@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
On Sun, Jan 2, 2011 at 8:30 PM, Akash Agrawal akash.agrawa...@gmail.comwrote: 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 macatad...@gmail.com 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 zhangyunq...@gmail.comwrote: 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 macatad...@gmail.com 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=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.comalgogeeks%2bunsubscr...@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
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 zhangyunq...@gmail.com 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.comwrote: 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 macatad...@gmail.com 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=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.comalgogeeks%2bunsubscr...@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.
[algogeeks] Re: Interview question amazon
There are 3 paths exist in bst, post, pre and inorder. store all these paths and find contiguous sum(and set of elements which leads to this sum) and check if it equals to given sum, then that is path. On Dec 27, 6:48 pm, mohit ranjan shoonya.mo...@gmail.com wrote: any hint for below question ? Mohit On Sun, Dec 26, 2010 at 10:38 PM, MAC macatad...@gmail.com 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.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=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.
[algogeeks] Re: Interview question amazon
Incorrect. Path can be combined from the several traversal algorithm's 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.
[algogeeks] Re: Interview question amazon
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 macatad...@gmail.com 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.
Re: [algogeeks] Re: Interview question amazon
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.comwrote: 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 macatad...@gmail.com 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=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.
[algogeeks] Re: Interview question amazon
And of course boundary cases(leaf nodes) are to be handled. For a leaf node 'i', ok[i][j]=1(if j==v[i]), 0 otherwise!!! On Dec 28, 11:04 pm, suhash suhash.venkat...@gmail.com wrote: I think this can be solved using dp. Consider the subtree rooted at node 'i'. Let ok[i][j] be a boolean (0 or 1) denoting whether you can achieve a sum of 'j', with the subtree rooted at node 'i', and node 'i' is chosen in the path. Hence, ok[i][j] = max((k=0 to (j-v[i])) ok[left(i)][k]ok[right(i)][j- v[i]-k]) This can be computed in a bottom up fashion for each node(each 'i') and for each possible sum(each 'j'). Hence, complexity is O(n*s*s). Now, if input is S (given sum value to find) Then, for each node 'i' if ok[i][S]=1, then a path exists with this node as root. After this, printing all paths can be done easily again similar to the first case. On Dec 26, 10:08 pm, MAC macatad...@gmail.com 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.
Re: [algogeeks] Re: Interview question
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
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++ avpostni...@gmail.com 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=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
@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 riteshkumar...@gmail.comwrote: 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 jalaj.jaiswa...@gmail.com 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.comalgogeeks%2bunsubscr...@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.
[algogeeks] Re: interview-question
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 jalaj.jaiswa...@gmail.com 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.
Re: [algogeeks] Re: interview-question
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 riteshkumar...@gmail.comwrote: 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 jalaj.jaiswa...@gmail.com 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=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
I hope the value of V is 0 or 1. Is this right? On Wed, Aug 4, 2010 at 12:48 AM, Manjunath Manohar manjunath.n...@gmail.com 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.comalgogeeks%2bunsubscr...@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.
[algogeeks] Re: Interview question: can this be done?
4), which will vary the value of k for many times. I think to cover up this problem.. 1. we can store the starting and ending numbers for every K in another file (with file name of every set) and then sort the file names according to the starting values for every K set, 2. hence creating an index based on the starting values of every set.. 3. so to check if a number is in a set or not we will simply have to perform a binary search on this index 4. and then for every matching set scan that particular set's file to see if the number is present or not. Thus the time for checking multiple instances will be reduced to some extent.. Regards, Prateek. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Interview question: can this be done?
I like Terry's idea.
Let's say the 5000 numbers are: {1,2,...,5000}
For every 200 numbers you choose, create a 5000 bit string .. which
corresponds to 625 bytes
which is infact less than the 800 bytes you would require to store the
200 numbers as ints.
You don't store the 200 numbers explicitly, only these 5000bit
bitstrings.
To analyze a particular subset, read in its bitstring. To check k,
calculate it's offset in the bitstring
and check if its 0 or 1. This is constant time operation.
I actually liked Kevin's original idea of using prime numbers and
coming up with a single hash value. But yeah, there are practical
limitations with that. You don't really need them all to be prime, u
just need them to be co-prime.
[algogeeks] Re: Interview question: can this be done?
I get what Terry means now. But it still uses 625/800 = 78% of the naive method in terms of diskspace (or memory, whatever), so I think the save is not big enough (the job interview is RD targeted, which I assume they want to hear one with large saving). Prateek's idea is to reduce the time of whole set read in (suppose they are saved to disk since there are many of them). It should work if the give k does not show up frequently. For each k, on average, I think we only need to read in 200/5000 = 4% percent of the whole sets, on 96% times we only need to check the begining and ending index. But I am kind of worry for the step 4), which will vary the value of k for many times. beelzebub mentioned co-prime, interesting. I will think a little bit more of it. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Interview question: can this be done?
I didn't fully get what you mean, but sounds not memory efficient: if we need to store the 200 integers per set, and don't forget they say it could be a lot of sets (even have to write to disk because memory does not fit).
[algogeeks] Re: Interview question: can this be done?
I think a better alternative could be to choose EVEN 5000 numbers (taking mod of 2 of any number out of these can help to check whether it can be in the set or not) and then make out set of 200 from these 5000 even numbers.. the set of 200 nos can be written on the disk in a sorted manner so that a binary search can be applied to them.. we can take out the first and the last number from the file and check whether its there or not.. and if its in range then apply binary search to find out the number.
