[algogeeks] Max to min heap
Convert a max heap to min heap -- 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: Max to min heap
You may use usual linear algorithm for constructing heap. Simply adjust the heap property for all internal nodes. On 20 окт, 11:47, MAC macatad...@gmail.com wrote: Convert a max heap to min heap -- 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: linked lists
Is there any additional condition saying if last 'n' characters of first list should match with first 'n' characters of 2nd list ? On Oct 7, 12:52 pm, snehal jain learner@gmail.com wrote: There are two linked list, both containing a character in each node. If one linked list contain characters o x e n c and second contain characters e n c a r t a then the final linked list should contain o x e n c a r t a i.e. if the end of one list is same as the start of second then those characters should come only once. can we do it in O(n+m) where n and m are the length of list. both are singly link list. -- 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] Yahoo coding round question
On Wed, Oct 20, 2010 at 5:11 AM, Kishen Das kishen@gmail.com wrote:
In the below code the jth and kth inner for loops can be run in parallel
making them O(1) and the entire thing O(n).
for ( i=0 to i=N-1 )
{
for ( j = i to j = 0 ) {
why till 0?
if S=107 , P= 210
and array is 10, -3 , 2 , 105, 13
code will fail
sum[j] += A[ i]
product[j] *= A [ i]
}
for( k=0 to k= i )
if ( sum[k] == S and product[k] == P ) {
Answer is the sub array A[k to i ]
break
}
}
Kishen
On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh
iiita2007...@gmail.comwrote:
@ Rahul patil ofcourse array may have negative or positive integers
@ Kishen both O(n) and O(n logn) solutions was asked in this yahoo
coding round question
On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh
iiita2007...@gmail.com wrote:
Given an array of length N. How will you find the minimum length
contiguous sub - array of whose sum is S and whose product is P . Here
S and P will be given to you.
--
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.
--
ABHISHEK KUMAR SINGH
BTECH (INFORMATION TECHNOLOGY)
IIIT ALLAHABAD
9956640538
--
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.
--
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.
[algogeeks] Re: Duplicate in an array
@juver++ - could u plz elaborate.. -- 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: Duplicate in an array
@Anirvana - In context to the XOR method u suggested, could u plz explain why does it so happen.. ?? -- 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: linked lists
@ligerdave - your algo will fail in the case the two arrays are: hellostl eeelexander ans : hellostlexander but according to ur method the answer would end up being hellostleeelexander -- 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: Duplicate in an array
Use C++ bitset class. It requires O(MaxValue / 8) bytes to represent set of integers with maximum number is MaxValue. To find repeated number: Iterate over the array. For each number check if it is already inserted into a bitset. If yes, then we find duplicated element. Otherwise, insert current number into a set (simply set up appropriate bit in the bitset). This approach is O(n). On 20 окт, 14:35, Asquare anshika.sp...@gmail.com wrote: @juver++ - could u plz elaborate.. -- 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: Duplicate in an array
Suggested approach by Anirvana doesn't work for this problem. It's ok if array contain numbers that are repeated twice except one element and we need to find it. For this version solution is simple - iterate over elements and find it's XOR value, so result = a[0] XOR a[1] ... XOR a[n - 1]. Resulted value is an element which presented only once in the array. It works because of a property of XOR operation - a XOR a = 0 (so repeated twice pairs disappeared). On 20 окт, 14:44, Asquare anshika.sp...@gmail.com wrote: @Anirvana - In context to the XOR method u suggested, could u plz explain why does it so happen.. ?? -- 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] How to associate a CRC code to an integer number
Hi to all, this is my first post here and i hope i can find an answer to my problem as well as to contribute, whenever possible, to this group! I have to solve the following problem: given an integer number of N bits (we can assume that N is = 32 bit), which we will call ID, i have to compute another integer number of M bits, with M = N. Call this last number CRC. The properties that CRC should have are: suppose to fix N and M = N and use a distance measure d which count the number of positions at which the corresponding bits are different (the Hamming distance) 1] if ID1 and ID2 are such that they are similar (for example, d(D1,D2) is a little fraction of N) then CRC1 (the CRC associated with ID1) and CRC2 (the CRC associated with ID2) are much more different 2] the computation of the CRC is deterministic 3] the computation of the CRC is fast 4] if the bit pattern of ID is uniform (number of times two adjacent bits are different) then CRC is much less uniform 5] since M = N, we have the collision problem (the same CRC associated to different ID's)...there should not be CRC that are associated to much more ID's than others CRC (NB 1. 4) is not so important). (NB 2. I know i should clarify things when i speak of similar, much more different, fast and so on, but to keep things simple, lets use the common sense...) I know of the exsistence of the CRC computation using polynomials (i admit i don't know much more about this topic), but my system should work with different values for M. The ideal solution would be the following: - suppose we are given M. We have two routine: - SetupCRCM(M) : pre-compute some data that will be used later (such like an array of integers..). Eventually, it does not do anything - ComputeCRC(ID, N): return an M-bit values wich is the CRC of the given ID and wich respects the above requirements. Is the CRC computation with polynomials the only way? Are there more simpler algorithms? Links, reference to books, papers or suggestions are really welcome! Thank you, Luca -- 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] SOMETHING SPECIAL FOR U
AISHWARIYA LATEST HOT PICS http://babes-devi.blogspot.com/2010/10/aish-latest-pics.html SOUTHACTRESS IN A SEXY TOWELS http://babes-devi.blogspot.com/2010/10/south-actress-in-sexy-towels.html UDAYATHRA IN A BATH ROOM http://babes-devi.blogspot.com/2010/10/udayatara-in-bath.html ACTRESS IN A HOT RED DRESS http://babes-devi.blogspot.com/2010/10/actress-in-sexy-red-dress.html ASIN CUTE HOT PHOTOS http://babes-devi.blogspot.com/2010/09/asin-cute-photos.html SEXY CHARMI IN A BATH http://babes-devi.blogspot.com/2010/06/charmi-in-bath.html FOR HOT PHOTOSVIDEOS http://babes-devi.blogspot.com/2010_06_01_archive.html HOT SEXY BOOBS SHOW http://babes-devi.blogspot.com/2010/09/sexy-boobs.html ASIN CUTE HOT PHOTOS http://babes-devi.blogspot.com/2010/09/asin-cute-photos.html MALLIKA SHARAWAT UNBELIVABLE PHOTOS http://babes-devi.blogspot.com/2010/08/sexy-mallika.html ANKHITA SPICY PHOTOS http://babes-devi.blogspot.com/2010/08/sexy-ankhitha.html -- 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] Yahoo coding round question
@rahul the code doesn't fail for the case you gave. Please check.
Also Kishen can you explain how is the complexity for two loops runninf in
parallel equal to O(1).
On Wed, Oct 20, 2010 at 3:06 PM, rahul patil
rahul.deshmukhpa...@gmail.comwrote:
On Wed, Oct 20, 2010 at 5:11 AM, Kishen Das kishen@gmail.com wrote:
In the below code the jth and kth inner for loops can be run in parallel
making them O(1) and the entire thing O(n).
for ( i=0 to i=N-1 )
{
for ( j = i to j = 0 ) {
why till 0?
if S=107 , P= 210
and array is 10, -3 , 2 , 105, 13
code will fail
sum[j] += A[ i]
product[j] *= A [ i]
}
for( k=0 to k= i )
if ( sum[k] == S and product[k] == P ) {
Answer is the sub array A[k to i ]
break
}
}
Kishen
On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh
iiita2007...@gmail.comwrote:
@ Rahul patil ofcourse array may have negative or positive integers
@ Kishen both O(n) and O(n logn) solutions was asked in this yahoo
coding round question
On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh
iiita2007...@gmail.com wrote:
Given an array of length N. How will you find the minimum length
contiguous sub - array of whose sum is S and whose product is P . Here
S and P will be given to you.
--
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.
--
ABHISHEK KUMAR SINGH
BTECH (INFORMATION TECHNOLOGY)
IIIT ALLAHABAD
9956640538
--
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.
--
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.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] Yahoo coding round question
@Kishen: Plz explain the complexity...
On 10/20/10, Lily Aldrin lily.hi...@gmail.com wrote:
@rahul the code doesn't fail for the case you gave. Please check.
Also Kishen can you explain how is the complexity for two loops runninf in
parallel equal to O(1).
On Wed, Oct 20, 2010 at 3:06 PM, rahul patil
rahul.deshmukhpa...@gmail.comwrote:
On Wed, Oct 20, 2010 at 5:11 AM, Kishen Das kishen@gmail.com wrote:
In the below code the jth and kth inner for loops can be run in parallel
making them O(1) and the entire thing O(n).
for ( i=0 to i=N-1 )
{
for ( j = i to j = 0 ) {
why till 0?
if S=107 , P= 210
and array is 10, -3 , 2 , 105, 13
code will fail
sum[j] += A[ i]
product[j] *= A [ i]
}
for( k=0 to k= i )
if ( sum[k] == S and product[k] == P ) {
Answer is the sub array A[k to i ]
break
}
}
Kishen
On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh
iiita2007...@gmail.comwrote:
@ Rahul patil ofcourse array may have negative or positive integers
@ Kishen both O(n) and O(n logn) solutions was asked in this yahoo
coding round question
On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh
iiita2007...@gmail.com wrote:
Given an array of length N. How will you find the minimum length
contiguous sub - array of whose sum is S and whose product is P . Here
S and P will be given to you.
--
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.
--
ABHISHEK KUMAR SINGH
BTECH (INFORMATION TECHNOLOGY)
IIIT ALLAHABAD
9956640538
--
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.
--
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.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.
--
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: Yahoo coding round question
i wanna get a clear picture of this before start. when you say min length of contiguous sub of an array let's say array A=[3,1,2,3,4,5], N=6 are below both good solutions? A[0] to A[m] where m=N A[i] to A[m] where i=m m=N On Oct 19, 3:58 am, Abhishek Kumar Singh iiita2007...@gmail.com wrote: Given an array of length N. How will you find the minimum length contiguous sub - array of whose sum is S and whose product is P . Here S and P will be given to you. -- 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: Yahoo coding round question
@Kishen
as long as you have one for loop in another, you wont have O(n). it
will most likely run O(n^2)
On Oct 19, 7:41 pm, Kishen Das kishen@gmail.com wrote:
In the below code the jth and kth inner for loops can be run in parallel
making them O(1) and the entire thing O(n).
for ( i=0 to i=N-1 )
{
for ( j = i to j = 0 ) {
sum[j] += A[ i]
product[j] *= A [ i]
}
for( k=0 to k= i )
if ( sum[k] == S and product[k] == P ) {
Answer is the sub array A[k to i ]
break
}
}
Kishen
On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh
iiita2007...@gmail.comwrote:
@ Rahul patil ofcourse array may have negative or positive integers
@ Kishen both O(n) and O(n logn) solutions was asked in this yahoo coding
round question
On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh
iiita2007...@gmail.com wrote:
Given an array of length N. How will you find the minimum length
contiguous sub - array of whose sum is S and whose product is P . Here
S and P will be given to you.
--
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.
--
ABHISHEK KUMAR SINGH
BTECH (INFORMATION TECHNOLOGY)
IIIT ALLAHABAD
9956640538
--
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: Duplicate in an array
what if two elements are not next to each other. would it work? On Oct 20, 8:19 am, juver++ avpostni...@gmail.com wrote: Suggested approach by Anirvana doesn't work for this problem. It's ok if array contain numbers that are repeated twice except one element and we need to find it. For this version solution is simple - iterate over elements and find it's XOR value, so result = a[0] XOR a[1] ... XOR a[n - 1]. Resulted value is an element which presented only once in the array. It works because of a property of XOR operation - a XOR a = 0 (so repeated twice pairs disappeared). On 20 окт, 14:44, Asquare anshika.sp...@gmail.com wrote: @Anirvana - In context to the XOR method u suggested, could u plz explain why does it so happen.. ?? -- 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] Frequent values spoj
i am getting wa for https://www.spoj.pl/problems/FREQUENT/
here is my code i have used segment trees it would be great if someone
could give me a test case for which my code gives wa.
Thanks in advance.
#includeiostream
#includevector
#includefstream
#includemath.h
#includestring.h
#includestdio.h
using namespace std;
int max(int a,int b)
{
if(ab)return a;
return b;
}
int min(int a,int b)
{
if(ab)return a;
return b;
}
templateclass T
class SegmentTree
{
int **A,size;
public:
SegmentTree(int N)
{
int x = (int)(ceil(log(N)/log(2)));
size = 2*(int)pow(2,x);
A = new int*[size];
for(int x=0;xsize;x++)
A[x]=new int[4];
for(int x=0;xsize;x++)
{
for(int y=0;y4;y++)
A[x][y]=-1;
}
}
void initialize(int node, int start,
int end, vectorintv1,vectorintv2,vectorintv3)
{
if (start==end)
{A[node][0] =
v1[start];A[node][2]=v2[start];A[node][3]=v3[start];A[node][1]=-1;}
else
{
int mid = (start+end)/2;
initialize(2*node,start,mid,v1,v2,v3);
initialize(2*node+1,mid+1,end,v1,v2,v3);
if (A[2*node][3]=
A[2*node+1][3])
{A[node][0] = A[2 * node][0];A[node][1] = A[2 *
node][2];A[node][2] = A[2 * node+1][2];A[node][3]=A[2*node][3];}
else
{A[node][0] = A[2 * node][0];A[node][1] = A[2 *
node][2];A[node][2] = A[2 * node+1][2];A[node][3]=A[2*node+1][3];}
}
}
// void pr()
// {
// for(int x=1;xsize;x++) coutx=x A[x][0]
A[x][1] A[x][2] A[x][3]\n;
// }
int query(int node,int i, int j)
{
// coutnode=node i=i j=j\n;
if (iA[node][2] || jA[node][0])
{return -1;}
else if (A[node][1]==-1j=A[node][2]i=A[node][0])
{int
ss=max(i,A[node][0])-A[node][0];ss=ss+A[node][2]-min(j,A[node][2]);return
(A[node][3]-ss);}
else
{ int id1=-1,id2=-1;
if(i=A[node][1])
id1 = query(2*node,i,min(j,A[node][1]));
if(A[node][1]j)
id2 = query(2*node+1,max(i,A[node][1]+1),j);
//coutnode=nodeid1=id1id2=id2\n;
if (id1==-1)
return id2;
if (id2==-1)
return id1;
if (id1=id2)
return id1;
else
return id2;
}
}
};
int main()
{
int i,j,N;
int A[16];
scanf(%d,N);
int M;
scanf(%d,M);
for (i=0;iN;i++)
scanf(%d,A[i]);
vectorintv1;
vectorintv2;
vectorintv3;
int ini=A[0],now,count=1,ip=0;
for(int x=1;xN;x++)
{
now=A[x];
if(now==ini)
count++;
else{ini=A[x];v1.push_back(ip);v2.push_back(x-1);v3.push_back(count);count=1;ip=x;}
}
v1.push_back(ip);v2.push_back(N-1);v3.push_back(count);
int sz=v1.size();
SegmentTreeint s(sz);
s.initialize(1,0,sz-1,v1,v2,v3);
for(int x=0;xM;x++)
{
(scanf(%d%d,i,j));
printf(%d\n,s.query(1,i-1,j-1));
}
int tmp;
cintmp;
return(0);
}
--
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: Duplicate in an array
Just add the number of the array and let the sum is S. Its complexity is O(n). Now XOR all elements of the array and say the result is X_SUM.Its complexity is O(n). Now the duplicate element is = (S - X_SUM)/2 On Wed, Oct 20, 2010 at 4:14 PM, Asquare anshika.sp...@gmail.com wrote: @Anirvana - In context to the XOR method u suggested, could u plz explain why does it so happen.. ?? -- 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. -- Mahesh Giri -- 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] Yahoo coding round question
for ( i=0 to i=N-1 )
{
// This inner for-loop can be run in parallel, as there is no dependency wrt
previously computed values or the values at other indices.
// you are just blindly adding the value at A[i] to all the elements of the
sub-array B[0 - j ] and hence can be run in parallel.
for ( j = i to j = 0 ) {
sum[j] = sum[j] + A[ i]
product[j]= product[j] * A [i]
if ( sum[j]==sum and product[j] ==product )
Answer is A [ j to i ]
}
}
Kishen
On Wed, Oct 20, 2010 at 12:34 PM, Lily Aldrin lily.hi...@gmail.com wrote:
@rahul the code doesn't fail for the case you gave. Please check.
Also Kishen can you explain how is the complexity for two loops runninf in
parallel equal to O(1).
On Wed, Oct 20, 2010 at 3:06 PM, rahul patil
rahul.deshmukhpa...@gmail.com wrote:
On Wed, Oct 20, 2010 at 5:11 AM, Kishen Das kishen@gmail.com wrote:
In the below code the jth and kth inner for loops can be run in parallel
making them O(1) and the entire thing O(n).
for ( i=0 to i=N-1 )
{
for ( j = i to j = 0 ) {
why till 0?
if S=107 , P= 210
and array is 10, -3 , 2 , 105, 13
code will fail
sum[j] += A[ i]
product[j] *= A [ i]
}
for( k=0 to k= i )
if ( sum[k] == S and product[k] == P ) {
Answer is the sub array A[k to i ]
break
}
}
Kishen
On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh iiita2007...@gmail.com
wrote:
@ Rahul patil ofcourse array may have negative or positive integers
@ Kishen both O(n) and O(n logn) solutions was asked in this yahoo
coding round question
On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh
iiita2007...@gmail.com wrote:
Given an array of length N. How will you find the minimum length
contiguous sub - array of whose sum is S and whose product is P . Here
S and P will be given to you.
--
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.
--
ABHISHEK KUMAR SINGH
BTECH (INFORMATION TECHNOLOGY)
IIIT ALLAHABAD
9956640538
--
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.
--
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.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.
--
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] 4th year project ideas
Hello Ayush, If you really want to work and learn something, I would suggest select an open source project according to interest and do something as your Btech Project. On Wed, Oct 20, 2010 at 4:20 AM, Ayush Mittal ayushmittal2...@gmail.comwrote: hello friends. plz suggest some new ideas for java projects for IT 4th year -- 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 Regards, Gaurav Gupta Associate Software Engineer IBM Software Lab |India Email: gauravgu...@in.ibm.com Ph No. : +91-7676-999-350 Quality is never an accident. It is always result of intelligent effort - John Ruskin -- 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: Yahoo coding round question
Well, looks like people are not understanding when I say run a loop in
parallel !!!
Please look at some of the examples on Nvidia website on how computations
can be parallelised in OpenCL or CUDA.
And also some of the high level programming languages like Scala which is
also providing these parallel constructs.
If you don't understand GPUs or not familiar with parallel constructs in
Java, then my algorithm will definitely look like O ( n ^ 2 ).
Kishen
On Wed, Oct 20, 2010 at 4:25 PM, ligerdave david.c...@gmail.com wrote:
@Kishen
as long as you have one for loop in another, you wont have O(n). it
will most likely run O(n^2)
On Oct 19, 7:41 pm, Kishen Das kishen@gmail.com wrote:
In the below code the jth and kth inner for loops can be run in parallel
making them O(1) and the entire thing O(n).
for ( i=0 to i=N-1 )
{
for ( j = i to j = 0 ) {
sum[j] += A[ i]
product[j] *= A [ i]
}
for( k=0 to k= i )
if ( sum[k] == S and product[k] == P ) {
Answer is the sub array A[k to i ]
break
}
}
Kishen
On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh iiita2007...@gmail.com
wrote:
@ Rahul patil ofcourse array may have negative or positive integers
@ Kishen both O(n) and O(n logn) solutions was asked in this yahoo
coding
round question
On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh
iiita2007...@gmail.com wrote:
Given an array of length N. How will you find the minimum length
contiguous sub - array of whose sum is S and whose product is P . Here
S and P will be given to you.
--
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
algogeeks%2bunsubscr...@googlegroups .com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
ABHISHEK KUMAR SINGH
BTECH (INFORMATION TECHNOLOGY)
IIIT ALLAHABAD
9956640538
--
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
algogeeks%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.
--
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] Yahoo coding round question
I am running my algorithm for your values -
I will just show it for sum.
Array B [ 0 0 0 0 0 ]
i = 0
Array B [ 10 0 0 0 0 ]
i = 1
Array B [7 -3 0 0 0 ]
i = 2
Array B [ 9 -1 2 0 0 ]
i=3
Array B [ 116 104 107 105 0 ]
You will stop here and the answer is the range [ k to i ] which is A [ 2 to
3 ]
I am attaching the modified algorithm.
-
for ( i=0 to i=N-1 )
{
for ( j = i to j = 0 ) {
sum[j] = sum[j] + A[ i]
product[j]= product[j] * A [i]
if ( sum[j]==sum and product[j] ==product )
Answer is A [ j to i ]
}
}
You can even flag the indexes whose sum or product exceeds the requirement,
so that you don't add or multiply at these indexes in the next set of
iterations, making it even more efficient algorithm.
Negative values do not affect this algorithm.
Kishen
On Wed, Oct 20, 2010 at 4:36 AM, rahul patil
rahul.deshmukhpa...@gmail.comwrote:
On Wed, Oct 20, 2010 at 5:11 AM, Kishen Das kishen@gmail.com wrote:
In the below code the jth and kth inner for loops can be run in parallel
making them O(1) and the entire thing O(n).
for ( i=0 to i=N-1 )
{
for ( j = i to j = 0 ) {
why till 0?
if S=107 , P= 210
and array is 10, -3 , 2 , 105, 13
code will fail
sum[j] += A[ i]
product[j] *= A [ i]
}
for( k=0 to k= i )
if ( sum[k] == S and product[k] == P ) {
Answer is the sub array A[k to i ]
break
}
}
Kishen
On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh
iiita2007...@gmail.comwrote:
@ Rahul patil ofcourse array may have negative or positive integers
@ Kishen both O(n) and O(n logn) solutions was asked in this yahoo
coding round question
On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh
iiita2007...@gmail.com wrote:
Given an array of length N. How will you find the minimum length
contiguous sub - array of whose sum is S and whose product is P . Here
S and P will be given to you.
--
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.
--
ABHISHEK KUMAR SINGH
BTECH (INFORMATION TECHNOLOGY)
IIIT ALLAHABAD
9956640538
--
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.
--
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.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: Duplicate in an array
@Mahesh: Let's try this on 1, 2, 3, 4, 4. Then S = 14 and X_SUM = 0. But the duplicate element is 4, not (14-0) / 2 = 7. Dave On Oct 20, 5:49 am, Mahesh_JNU mahesh.jnumc...@gmail.com wrote: Just add the number of the array and let the sum is S. Its complexity is O(n). Now XOR all elements of the array and say the result is X_SUM.Its complexity is O(n). Now the duplicate element is = (S - X_SUM)/2 On Wed, Oct 20, 2010 at 4:14 PM, Asquare anshika.sp...@gmail.com wrote: @Anirvana - In context to the XOR method u suggested, could u plz explain why does it so happen.. ?? -- 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. -- Mahesh Giri -- 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: Duplicate in an array
Considering sequence 1, 2, 3, 4, 4 and n = 5 lets have missing number as X and repeated number as Y. (1*2*3*4*4)/n! = 4/5=Y/X = 5Y = 4X = Y=4X/5 (sum of all numbers) + X - Y = n(n+1)/2. 14 + X - Y = 15 X-4X/5=1 X = 5 --- missing value is 5. Y = 4 -- repeated value. On Wed, Oct 20, 2010 at 7:26 PM, Dave dave_and_da...@juno.com wrote: @Mahesh: Let's try this on 1, 2, 3, 4, 4. Then S = 14 and X_SUM = 0. But the duplicate element is 4, not (14-0) / 2 = 7. Dave On Oct 20, 5:49 am, Mahesh_JNU mahesh.jnumc...@gmail.com wrote: Just add the number of the array and let the sum is S. Its complexity is O(n). Now XOR all elements of the array and say the result is X_SUM.Its complexity is O(n). Now the duplicate element is = (S - X_SUM)/2 On Wed, Oct 20, 2010 at 4:14 PM, Asquare anshika.sp...@gmail.com wrote: @Anirvana - In context to the XOR method u suggested, could u plz explain why does it so happen.. ?? -- 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 algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mahesh Giri -- 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 Regards, Karthik -- 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: Duplicate in an array
@Karthik: There was no requirement that the numbers be between 1 and n. Only positive and one number is repeated. So 1, 9, 11, 1 also is valid input, with expected output 1. Dave On Oct 20, 11:30 pm, karthik asok karthika...@gmail.com wrote: Considering sequence 1, 2, 3, 4, 4 and n = 5 lets have missing number as X and repeated number as Y. (1*2*3*4*4)/n! = 4/5=Y/X = 5Y = 4X = Y=4X/5 (sum of all numbers) + X - Y = n(n+1)/2. 14 + X - Y = 15 X-4X/5=1 X = 5 --- missing value is 5. Y = 4 -- repeated value. On Wed, Oct 20, 2010 at 7:26 PM, Dave dave_and_da...@juno.com wrote: @Mahesh: Let's try this on 1, 2, 3, 4, 4. Then S = 14 and X_SUM = 0. But the duplicate element is 4, not (14-0) / 2 = 7. Dave On Oct 20, 5:49 am, Mahesh_JNU mahesh.jnumc...@gmail.com wrote: Just add the number of the array and let the sum is S. Its complexity is O(n). Now XOR all elements of the array and say the result is X_SUM.Its complexity is O(n). Now the duplicate element is = (S - X_SUM)/2 On Wed, Oct 20, 2010 at 4:14 PM, Asquare anshika.sp...@gmail.com wrote: @Anirvana - In context to the XOR method u suggested, could u plz explain why does it so happen.. ?? -- 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 algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mahesh Giri -- 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 Regards, Karthik- 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 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.
