Re: [algogeeks] Programming Question
u can use strtok to tokenise the string on the parameter of comma. now maintain an array of linked lists or hashtable in which the key will be a starting character. On Fri, Jun 22, 2012 at 8:41 PM, Abhishek Sharma abhi120...@gmail.comwrote: make a hashtable where, key is the first character of each word and, value is a list which contains index of each word starting with that character. Now, sort that hash table wrt keys. Now print u can use each each key and words corresponding to that key ( given by arr[index1], arr[index2] ) On Fri, Jun 22, 2012 at 5:55 PM, Ashot Madatyan ashot...@gmail.comwrote: 1. read the file one char at a time, and tokenize the standalone words (stop char is either space or comma or eol) 2. put each parsed word in a structure mapchar, vectorstring , where the char is the key (the first letter of each scanned word). You are basically creating a hash table here. 3. now print the hash table content using the formatting of your choice. Rgds, Ashot -Original Message- From: algogeeks@googlegroups.com [mailto:algogeeks@googlegroups.com] On Behalf Of Gobind Kumar Hembram Sent: Friday, June 22, 2012 2:01 PM To: algogeeks@googlegroups.com Subject: [algogeeks] Programming Question I was asked this question in one company Programming Round.Please help me in solving this,I tried with array of pointers ,2-D array and by buffering. You have a file with names of brands separated by comma. Write a program (in language of your choice) to group them by their starting letter. For example, if the input file is this: Reebok, Puma, Adidas, Clarks, Catwalk, Converse, FILA, Lotto, Newfeel, Nike, Numero Uno, New Balance, ASICS, Carlton London, Crocs The program should print the following: A ASICS, Adidas C Carlton London, Catwalk, Clarks, Converse, Crocs F FILA L Lotto N New Balance, Newfeel, Nike, Numero Uno P Puma R Reebok -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Abhishek Sharma Under-Graduate Student, PEC University of Technology -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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 Lomash Goyal * * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Question asked in Amazon online test
Given an array containing sequence of bits (0 or 1), you have to sort this array in the ascending order i.e. all 0' in first part of array followed by all 1's. The constraints is that you can swap only the adjacent elements in the array. Find the minimum number of swaps required to sort the given input array. Example: Given the array (0,0,1,0,1,0,1,1) the minimum number of swaps is 3. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Question asked in Amazon Online test
Let u and r be the distance to move in the up and right directions. u=y2-y1 and r=x2-x1. We have to move a total of u+r units. So the answer would be (u+r)!/u!r! since we are counting only the distinct paths. Each path from (x1,y1) to (x2,y2) may be expressed as a sequence of u+r steps consisting of U or R. If seq[i] has U then it means we moved up at the i th step. Similarly R is for right. The number of distinct paths would be the number of distinct arrangements of the sequence. On Sat, Jun 23, 2012 at 11:05 AM, Gobind Kumar Hembram gobind@gmail.com wrote: Given two positions in a 2-D matrix, say (x1, y1) and (x2, y2) where x2=x1 and y2=y1. Find the total number of distinct paths between (x1, y1) and (x2, y2). You can only move in right direction i.e. positive x direction (+1, 0) or in up direction i.e. positive y direction (0, +1) from any given position. Example: If the given coordinates are (3,3) and (5,5), the number of distinct paths are 6 : one going through 3,5 ; one going through 5,3 and four going through 4,4. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Question asked in Amazon online test
Use a merge sort like procedure to count the number of inversions such that 0 appears after 1. On Sat, Jun 23, 2012 at 11:34 AM, Gobind Kumar Hembram gobind@gmail.com wrote: Given an array containing sequence of bits (0 or 1), you have to sort this array in the ascending order i.e. all 0' in first part of array followed by all 1's. The constraints is that you can swap only the adjacent elements in the array. Find the minimum number of swaps required to sort the given input array. Example: Given the array (0,0,1,0,1,0,1,1) the minimum number of swaps is 3. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Question asked in Amazon online test
If we use merge sort like procedure,ans will be 1 here it should be 3.we have to swap 0s and 1s linearly. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Question asked in Amazon online test
We need to sort as we count the inversions. On Sat, Jun 23, 2012 at 11:56 AM, Gobind Kumar Hembram gobind@gmail.com wrote: If we use merge sort like procedure,ans will be 1 here it should be 3.we have to swap 0s and 1s linearly. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Question asked in Amazon online test
will bubble sort give number of swaps?? I tried the (bubble sort) code of 1,0,0,1,1,0,1 swapcount = 5 and for the array (0,0,1,0,1,0,1,1)swapcount = 3 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Question asked in Amazon online test
@deepika yes, it's giving number of swaps. still Linear time solution would be better :-) On Fri, Jun 22, 2012 at 11:38 PM, deepikaanand swinyanand...@gmail.com wrote: will bubble sort give number of swaps?? I tried the (bubble sort) code of 1,0,0,1,1,0,1 swapcount = 5 and for the array (0,0,1,0,1,0,1,1)swapcount = 3 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Question asked in Amazon online test
i think it can be done in O(n) for each 1, calculate no. of zeros in right and adding all no. of zeros in right of all 1's will give no. of swaps. correct me if i am wrong On Sat, Jun 23, 2012 at 12:19 PM, Sourabh Singh singhsourab...@gmail.comwrote: @deepika yes, it's giving number of swaps. still Linear time solution would be better :-) On Fri, Jun 22, 2012 at 11:38 PM, deepikaanand swinyanand...@gmail.com wrote: will bubble sort give number of swaps?? I tried the (bubble sort) code of 1,0,0,1,1,0,1 swapcount = 5 and for the array (0,0,1,0,1,0,1,1)swapcount = 3 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- *DARPAN BAWEJA* *3rd year, I.T* *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: Question asked in Amazon online test
@ALL
see if this work's :
#includeiostream
using namespace std;
int a[8]={0,0,1,0,1,0,1,1};
int count_zero(int size)
{ int i,count =0;
for(i=0;isize;i++) if(!a[i]) count++;
return count;
}
int solve(int size)
{ int num_zero=count_zero(size);
int p_zero,p_one,i;
int count=0;
p_zero=0;
for(p_one=0;p_onesize p_zeronum_zero;p_one++)
{
if(!a[p_one])
{ count+=(p_one-p_zero);
p_zero++;
a[p_one]=1;
}
}
return count;
}
main()
{ printf(%d\n,solve(8));
system(pause);
return 0;
}
On Sat, Jun 23, 2012 at 12:09 AM, Darpan Baweja darpan.bav...@gmail.com wrote:
i think it can be done in O(n)
for each 1, calculate no. of zeros in right
and adding all no. of zeros in right of all 1's will give no. of swaps.
correct me if i am wrong
On Sat, Jun 23, 2012 at 12:19 PM, Sourabh Singh singhsourab...@gmail.com
wrote:
@deepika
yes, it's giving number of swaps.
still Linear time solution would be better :-)
On Fri, Jun 22, 2012 at 11:38 PM, deepikaanand swinyanand...@gmail.com
wrote:
will bubble sort give number of swaps??
I tried the (bubble sort) code of 1,0,0,1,1,0,1 swapcount = 5
and for the array (0,0,1,0,1,0,1,1)swapcount = 3
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.
--
DARPAN BAWEJA
3rd year, I.T
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: Question asked in Amazon online test
@saurabh..wat array r u getting finallyis it all 1's or in sorted
order for the input
int a[8]={1,1,1,0,1,0,1,1};
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Question asked in Amazon online test
if we just need to determine number of swaps, it can be Done in O(n) Ex : 11100010 start counting number of zeros from the end so we have zeroCount = 1 whenever we encounter a 1 we add current zeroCount to numberOfSwaps so numberOfSwaps = 1 and so on the final value of numberOsSwaps is the answer correct me if i am wrong -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Reverse Queue
recursion internally uses one stack for maintaining the return
addresses.which all we need... :-)
On Friday, June 22, 2012 11:38:39 AM UTC+5:30, joker wrote:
@ALL this shud work :-)
#includeiostream
#includequeue
using namespace std;
queueint Q;
void rev()
{ if(!Q.empty())
{ int x=Q.front(); Q.pop();
rev();
Q.push(x);
}
}
main()
{ for(int i=1;i12;i++) Q.push(i);
rev();
while(!Q.empty())
{ int x=Q.front(); Q.pop();
printf(%d ,x);
}
system(pause);
}
On Thu, Jun 21, 2012 at 12:14 PM, sanjay pandey
sanjaypandey...@gmail.com wrote:
it seems @hassan sol is correctcan nybody knw d flaw in it???
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
On Friday, June 22, 2012 11:38:39 AM UTC+5:30, joker wrote:
@ALL this shud work :-)
#includeiostream
#includequeue
using namespace std;
queueint Q;
void rev()
{ if(!Q.empty())
{ int x=Q.front(); Q.pop();
rev();
Q.push(x);
}
}
main()
{ for(int i=1;i12;i++) Q.push(i);
rev();
while(!Q.empty())
{ int x=Q.front(); Q.pop();
printf(%d ,x);
}
system(pause);
}
On Thu, Jun 21, 2012 at 12:14 PM, sanjay pandey
sanjaypandey...@gmail.com wrote:
it seems @hassan sol is correctcan nybody knw d flaw in it???
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
On Friday, June 22, 2012 11:38:39 AM UTC+5:30, joker wrote:
@ALL this shud work :-)
#includeiostream
#includequeue
using namespace std;
queueint Q;
void rev()
{ if(!Q.empty())
{ int x=Q.front(); Q.pop();
rev();
Q.push(x);
}
}
main()
{ for(int i=1;i12;i++) Q.push(i);
rev();
while(!Q.empty())
{ int x=Q.front(); Q.pop();
printf(%d ,x);
}
system(pause);
}
On Thu, Jun 21, 2012 at 12:14 PM, sanjay pandey
sanjaypandey...@gmail.com wrote:
it seems @hassan sol is correctcan nybody knw d flaw in it???
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
On Friday, June 22, 2012 11:38:39 AM UTC+5:30, joker wrote:
@ALL this shud work :-)
#includeiostream
#includequeue
using namespace std;
queueint Q;
void rev()
{ if(!Q.empty())
{ int x=Q.front(); Q.pop();
rev();
Q.push(x);
}
}
main()
{ for(int i=1;i12;i++) Q.push(i);
rev();
while(!Q.empty())
{ int x=Q.front(); Q.pop();
printf(%d ,x);
}
system(pause);
}
On Thu, Jun 21, 2012 at 12:14 PM, sanjay pandey
sanjaypandey...@gmail.com wrote:
it seems @hassan sol is correctcan nybody knw d flaw in it???
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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 view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/rKd4pNXXxLoJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Question asked in Amazon online test
start scanning the array from last .. maintain two pointers. one for last
encountered zero. second for moving backward. whenever you encounter the
one just swap it with the last zero. enhance the pointer till next zero
encounters. at last you will have the number of swaps.
I think my solution works if i hv not misunderstood the problem..
Correct me if I am wrong.
Regards
Rajesh Pandey
On Sat, Jun 23, 2012 at 12:51 PM, Sourabh Singh singhsourab...@gmail.comwrote:
@ALL
see if this work's :
#includeiostream
using namespace std;
int a[8]={0,0,1,0,1,0,1,1};
int count_zero(int size)
{ int i,count =0;
for(i=0;isize;i++) if(!a[i]) count++;
return count;
}
int solve(int size)
{ int num_zero=count_zero(size);
int p_zero,p_one,i;
int count=0;
p_zero=0;
for(p_one=0;p_onesize p_zeronum_zero;p_one++)
{
if(!a[p_one])
{ count+=(p_one-p_zero);
p_zero++;
a[p_one]=1;
}
}
return count;
}
main()
{ printf(%d\n,solve(8));
system(pause);
return 0;
}
On Sat, Jun 23, 2012 at 12:09 AM, Darpan Baweja darpan.bav...@gmail.com
wrote:
i think it can be done in O(n)
for each 1, calculate no. of zeros in right
and adding all no. of zeros in right of all 1's will give no. of swaps.
correct me if i am wrong
On Sat, Jun 23, 2012 at 12:19 PM, Sourabh Singh
singhsourab...@gmail.com
wrote:
@deepika
yes, it's giving number of swaps.
still Linear time solution would be better :-)
On Fri, Jun 22, 2012 at 11:38 PM, deepikaanand swinyanand...@gmail.com
wrote:
will bubble sort give number of swaps??
I tried the (bubble sort) code of 1,0,0,1,1,0,1 swapcount = 5
and for the array (0,0,1,0,1,0,1,1)swapcount = 3
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.
--
DARPAN BAWEJA
3rd year, I.T
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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Question asked in Amazon Online test
bcaz choosing any vertical will automatically fix the horizontals and vice verse (u+r) C r= (u+r) C u On Sat, Jun 23, 2012 at 1:08 PM, Kumar Vishal kumar...@gmail.com wrote: Let u and r be the distance to move in the up and right directions. u=y2-y1 and r=x2-x1. (u+r) C r On Sat, Jun 23, 2012 at 11:40 AM, Guruprasad Sridharan sridharan.mi...@gmail.com wrote: Let u and r be the distance to move in the up and right directions. u=y2-y1 and r=x2-x1. We have to move a total of u+r units. So the answer would be (u+r)!/u!r! since we are counting only the distinct paths. Each path from (x1,y1) to (x2,y2) may be expressed as a sequence of u+r steps consisting of U or R. If seq[i] has U then it means we moved up at the i th step. Similarly R is for right. The number of distinct paths would be the number of distinct arrangements of the sequence. On Sat, Jun 23, 2012 at 11:05 AM, Gobind Kumar Hembram gobind@gmail.com wrote: Given two positions in a 2-D matrix, say (x1, y1) and (x2, y2) where x2=x1 and y2=y1. Find the total number of distinct paths between (x1, y1) and (x2, y2). You can only move in right direction i.e. positive x direction (+1, 0) or in up direction i.e. positive y direction (0, +1) from any given position. Example: If the given coordinates are (3,3) and (5,5), the number of distinct paths are 6 : one going through 3,5 ; one going through 5,3 and four going through 4,4. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Vishal _ *http://wethecommonpeople.wordpress.com/ * *h**ttp://kumartechnicalarticles.wordpress.com/http://kumartechnicalarticles.wordpress.com/ * _ -- Regards Kumar Vishal _ *http://wethecommonpeople.wordpress.com/ * *h**ttp://kumartechnicalarticles.wordpress.com/http://kumartechnicalarticles.wordpress.com/ * _ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Question asked in Amazon Online test
Let u and r be the distance to move in the up and right directions. u=y2-y1 and r=x2-x1. (u+r)Cr On Sat, Jun 23, 2012 at 11:40 AM, Guruprasad Sridharan sridharan.mi...@gmail.com wrote: Let u and r be the distance to move in the up and right directions. u=y2-y1 and r=x2-x1. We have to move a total of u+r units. So the answer would be (u+r)!/u!r! since we are counting only the distinct paths. Each path from (x1,y1) to (x2,y2) may be expressed as a sequence of u+r steps consisting of U or R. If seq[i] has U then it means we moved up at the i th step. Similarly R is for right. The number of distinct paths would be the number of distinct arrangements of the sequence. On Sat, Jun 23, 2012 at 11:05 AM, Gobind Kumar Hembram gobind@gmail.com wrote: Given two positions in a 2-D matrix, say (x1, y1) and (x2, y2) where x2=x1 and y2=y1. Find the total number of distinct paths between (x1, y1) and (x2, y2). You can only move in right direction i.e. positive x direction (+1, 0) or in up direction i.e. positive y direction (0, +1) from any given position. Example: If the given coordinates are (3,3) and (5,5), the number of distinct paths are 6 : one going through 3,5 ; one going through 5,3 and four going through 4,4. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Vishal _ *http://wethecommonpeople.wordpress.com/ * *h**ttp://kumartechnicalarticles.wordpress.com/http://kumartechnicalarticles.wordpress.com/ * _ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Question asked in Amazon online test
It will work because we need to swap only adjacent elements. So we do a
sweep from left to right finding the number of ones encountered to the left
of a zero when we find a zero. We keep adding the number as we sweep the
entire length.
On Sat, Jun 23, 2012 at 1:14 PM, deepikaanand swinyanand...@gmail.comwrote:
@saurabh..wat array r u getting finallyis it all 1's or in sorted
order for the input
int a[8]={1,1,1,0,1,0,1,1};
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Question asked in Amazon online test
@all
yaa.. For getting number of swaps.. we have to calculate total number of
zeroes on the right for each '1' and on adding them
we will get the number of swaps. and in O(n) time.
On Sat, Jun 23, 2012 at 1:16 PM, Guruprasad Sridharan
sridharan.mi...@gmail.com wrote:
It will work because we need to swap only adjacent elements. So we do a
sweep from left to right finding the number of ones encountered to the left
of a zero when we find a zero. We keep adding the number as we sweep the
entire length.
On Sat, Jun 23, 2012 at 1:14 PM, deepikaanand swinyanand...@gmail.comwrote:
@saurabh..wat array r u getting finallyis it all 1's or in sorted
order for the input
int a[8]={1,1,1,0,1,0,1,1};
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Largest Path in Tree [SPOJ BENFECT]
Some how I found that we need to run bfs twice to get the largest distance between any two nodes of a tree. Please explain me how it works. regards, avinash -- 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/-/jodahB_dChYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Question asked in Amazon online test
@deepika anand
solution given by me is for getting number of swap's in O(n)
as far as sorting goes any O(n lgn) algo can be used .
if count sort is allowed then O(n) for sorting also.[constant extra space.. ]
On Sat, Jun 23, 2012 at 12:49 AM, ashish jain ashishjainco...@gmail.com wrote:
@all
yaa.. For getting number of swaps.. we have to calculate total number of
zeroes on the right for each '1' and on adding them
we will get the number of swaps. and in O(n) time.
On Sat, Jun 23, 2012 at 1:16 PM, Guruprasad Sridharan
sridharan.mi...@gmail.com wrote:
It will work because we need to swap only adjacent elements. So we do a
sweep from left to right finding the number of ones encountered to the left
of a zero when we find a zero. We keep adding the number as we sweep the
entire length.
On Sat, Jun 23, 2012 at 1:14 PM, deepikaanand swinyanand...@gmail.com
wrote:
@saurabh..wat array r u getting finallyis it all 1's or in sorted
order for the input
int a[8]={1,1,1,0,1,0,1,1};
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Largest Path in Tree [SPOJ BENFECT]
Is this similar to finding the diameter of a tree(longest disteance between two leaves) ?? If yes than visit this link http://www.cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.html On Sat, Jun 23, 2012 at 2:44 PM, Avinash jain.av...@gmail.com wrote: Some how I found that we need to run bfs twice to get the largest distance between any two nodes of a tree. Please explain me how it works. regards, avinash -- 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/-/jodahB_dChYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Largest Path in Tree [SPOJ BENFECT]
Is longest path between two node in a tree is equal two logest path between two leaves?? On Sat, Jun 23, 2012 at 5:35 PM, Navin Kumar algorithm.i...@gmail.comwrote: Is this similar to finding the diameter of a tree(longest disteance between two leaves) ?? If yes than visit this link http://www.cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.html On Sat, Jun 23, 2012 at 2:44 PM, Avinash jain.av...@gmail.com wrote: Some how I found that we need to run bfs twice to get the largest distance between any two nodes of a tree. Please explain me how it works. regards, avinash -- 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/-/jodahB_dChYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Question
Write a function longest_palindrome, which takes an array of strings as argument and returns the longest palindrome in that array if any.Please give ideas how to implement this function. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] 4Sum
@bhaskar,rammar: I don't think your algo willn not work for the following test case -- test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array -- Amol Sharma Final 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/http://facebook.com/amolsharma99 On Fri, Jun 22, 2012 at 11:45 PM, Bhaskar Kushwaha bhaskar.kushwaha2...@gmail.com wrote: We first compute the N^2 two sums, and sort the two sums. The for each TwoSum t, we check whether there is another two sum t' such that t.value + t'.value = target. The time complexity of this approach is O(N^2 logN) On Wed, Jun 20, 2012 at 1:36 AM, rammar getam...@gmail.com wrote: Lets see ur example... We can have two other arrays corresponding to our n^2 array. For every (target-arr[i]) which we search in our look up array, we can also search the components which were used to get that sum. This can be done in addition constant amount search. I hope we can still go with Hemesh's algo. Please let me know if it breaks somewhere... let's take a test case : arr: 2 4 68 arr[0]: 6 8 10 10 12 14 arr[1]: 2 22 4 46 arr[2]: 4 68 6 88 P.S. Can we do better? On Wednesday, June 20, 2012 12:22:52 AM UTC+5:30, Amol Sharma wrote: @rammar: can you please explain the case...which i took in the earlier post..with this method. -- Amol Sharma Final 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/http://facebook.com/amolsharma99 On Tue, Jun 19, 2012 at 11:27 PM, rammar getam...@gmail.com wrote: @Hemesh +1 Please correct me if i am wrong. Creation of our look up array a[n*n] - sum of all the pairs will take O(n^2). Search using binary sort or quick sort in O(n^2 log (n^2) ) == O(n^2 log n) We will traverse this array, and for every element we will find (target - a[i]) - This traversal will again take O(n^2). For every (target -a[i]) we will search it in our lookup array using binary search - This will take O(log n^2) = O(2log n) = O(log n) We will store all the matched for the target. Final complexity = O(n^2) + O(n^2 log n) + O(n^2)*O(log n) == O (n^2 log n) If the values of max of a[n] is not very high, we can go with a hash map. This will result in a quick look up. And we can get the answer in O(n^2). P.S. Can we do better? On Monday, June 18, 2012 6:10:33 PM UTC+5:30, Jalaj wrote: @KK and hemesh target is not a constant value , it can be any element in array , so you need to do binary search for all (array[i] - (a+b)) to find which increases the complexity to n^3logn. So, i think the n^3 approach which i gave before do it ?? -- Correct me if m wrong On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma amolsharm...@gmail.comwrote: @hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final 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/http://facebook.com/amolsharma99 On Mon, Jun 18, 2012 at 12:29 AM, KK kunalkapadi...@gmail.comwrote: @Hemesh : +1 @Jalaj : read Hemesh's solution again it is for 4sum. In short, make a new array having sum of each unique pair of given array. - O(n^2) sort it - O(n^2) for each number bi in new array, binary search (target - bi) in the same array - O(n^2) On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and doing a binary search again that sums upto n^3*logn. @shashank it is not a variation of 3SUM problem as in 3SUM problem a+b+c = some constant , but in your case it is b+c+d = s-a, where a can change again and again so
Re: [algogeeks] Re: Largest Path in Tree [SPOJ BENFECT]
no this problem is different from finding the longest path which is actually maximum number of nodes covered in the longest path On Sat, Jun 23, 2012 at 5:45 PM, Navin Kumar algorithm.i...@gmail.comwrote: Is longest path between two node in a tree is equal two logest path between two leaves?? On Sat, Jun 23, 2012 at 5:35 PM, Navin Kumar algorithm.i...@gmail.comwrote: Is this similar to finding the diameter of a tree(longest disteance between two leaves) ?? If yes than visit this link http://www.cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.html On Sat, Jun 23, 2012 at 2:44 PM, Avinash jain.av...@gmail.com wrote: Some how I found that we need to run bfs twice to get the largest distance between any two nodes of a tree. Please explain me how it works. regards, avinash -- 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/-/jodahB_dChYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, avinash (+91) 9502681447 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Largest Path in Tree [SPOJ BENFECT]
What I can think is case is : 10 / \ 6 13 / \ 4 5 / \ \ 6 7 8 / \ \ 9 a b so from a-b is a-7-4-2-5-8-b 1- Left Tree then 2- Right Tree add them On Sat, Jun 23, 2012 at 3:49 PM, Kumar Vishal kumar...@gmail.com wrote: What I can think is case is : 1 / \ 2 3 / \ 4 5 / \ \ 6 7 8 / \ \ 9 a b so from a-b is a-7-4-2-5-8-b On Sat, Jun 23, 2012 at 2:44 PM, Avinash jain.av...@gmail.com wrote: Some how I found that we need to run bfs twice to get the largest distance between any two nodes of a tree. Please explain me how it works. regards, avinash -- 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/-/jodahB_dChYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Vishal _ *http://wethecommonpeople.wordpress.com/ * *h**ttp://kumartechnicalarticles.wordpress.com/http://kumartechnicalarticles.wordpress.com/ * _ -- Regards Kumar Vishal _ *http://wethecommonpeople.wordpress.com/ * *h**ttp://kumartechnicalarticles.wordpress.com/http://kumartechnicalarticles.wordpress.com/ * _ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Largest Path in Tree [SPOJ BENFECT]
What I can think is case is : 1 / \ 2 3 / \ 4 5 / \ \ 6 7 8 / \ \ 9 a b so from a-b is a-7-4-2-5-8-b On Sat, Jun 23, 2012 at 2:44 PM, Avinash jain.av...@gmail.com wrote: Some how I found that we need to run bfs twice to get the largest distance between any two nodes of a tree. Please explain me how it works. regards, avinash -- 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/-/jodahB_dChYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Vishal _ *http://wethecommonpeople.wordpress.com/ * *h**ttp://kumartechnicalarticles.wordpress.com/http://kumartechnicalarticles.wordpress.com/ * _ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Largest Path in Tree [SPOJ BENFECT]
you are just finding the diameter of the tree. Remember the graph I am talking about is weighted. So if two adjacent vertices has infinite weight than that would be the longest distance between any two vertices in the graph. e.g. In you diagram suppose the sum of weight of the edges from a-b is 30. But in the graph suppose the weight of the left most edge (i.e. 4-6) is 40 then 4-6 is the longest distance not a-b. Let me know if I am making sense. On Sat, Jun 23, 2012 at 3:51 PM, Kumar Vishal kumar...@gmail.com wrote: What I can think is case is : 10 / \ 6 13 / \ 4 5 / \ \ 6 7 8 / \ \ 9 a b so from a-b is a-7-4-2-5-8-b 1- Left Tree then 2- Right Tree add them On Sat, Jun 23, 2012 at 3:49 PM, Kumar Vishal kumar...@gmail.com wrote: What I can think is case is : 1 / \ 2 3 / \ 4 5 / \ \ 6 7 8 / \ \ 9 a b so from a-b is a-7-4-2-5-8-b On Sat, Jun 23, 2012 at 2:44 PM, Avinash jain.av...@gmail.com wrote: Some how I found that we need to run bfs twice to get the largest distance between any two nodes of a tree. Please explain me how it works. regards, avinash -- 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/-/jodahB_dChYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Vishal _ *http://wethecommonpeople.wordpress.com/ * *h**ttp://kumartechnicalarticles.wordpress.com/http://kumartechnicalarticles.wordpress.com/ * _ -- Regards Kumar Vishal _ *http://wethecommonpeople.wordpress.com/ * *h**ttp://kumartechnicalarticles.wordpress.com/http://kumartechnicalarticles.wordpress.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. -- Regards, avinash (+91) 9502681447 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Find the Max from each sub-array of size k
To do this question in O(n) time follow the post Segment trees in this post of topcoder http://community.topcoder.com/tc?module=Staticd1=tutorialsd2=lowestCommonAncestor Here in this given algorithm preprocessing time in O(n) and query time is O(log n). -- Akshat Sapra Under Graduation(B.Tech) IIIT-Allahabad(Amethi Campus) *--* sapraaks...@gmail.com akshatsapr...@gmail.com rit20009008@ rit20009...@gmail.comiiita.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Adobe interview question
yeah use pure virtual fxn.. On Fri, Jun 22, 2012 at 3:41 PM, himanshu kansal himanshukansal...@gmail.com wrote: i told the interviewer...bt he said thn the constt would not be accessible to derived class alsohe told me dt u shld make the constt. protecteddats why i ws confused... On Fri, Jun 22, 2012 at 2:38 PM, raghavan M peacelover1987...@yahoo.co.in wrote: Make all constructors private. -- *From:* himanshu kansal himanshukansal...@gmail.com *To:* Algorithm Geeks algogeeks@googlegroups.com *Sent:* Friday, 22 June 2012 1:44 PM *Subject:* [algogeeks] Adobe interview question How will u implement an abstract class in c++ w/o using pure virtual function??? will making all the constructors and assignment operators protected suffice??? i doubt since the derived classes will be able to create objects of that classand according to definition of abstract class, no object of it should be created... any other way?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+ unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Himanshu Kansal Msc Comp. sc. (University of 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] 4Sum
@ALL O(n^2 lg(n^2)) http://www.spoj.pl/problems/SUMFOUR/ my code : http://ideone.com/kAPNB plz. suggest some test case's : On Sat, Jun 23, 2012 at 6:59 AM, Amol Sharma amolsharm...@gmail.com wrote: @bhaskar,rammar: I don't think your algo willn not work for the following test case -- test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array -- Amol Sharma Final 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/http://facebook.com/amolsharma99 On Fri, Jun 22, 2012 at 11:45 PM, Bhaskar Kushwaha bhaskar.kushwaha2...@gmail.com wrote: We first compute the N^2 two sums, and sort the two sums. The for each TwoSum t, we check whether there is another two sum t' such that t.value + t'.value = target. The time complexity of this approach is O(N^2 logN) On Wed, Jun 20, 2012 at 1:36 AM, rammar getam...@gmail.com wrote: Lets see ur example... We can have two other arrays corresponding to our n^2 array. For every (target-arr[i]) which we search in our look up array, we can also search the components which were used to get that sum. This can be done in addition constant amount search. I hope we can still go with Hemesh's algo. Please let me know if it breaks somewhere... let's take a test case : arr: 2 4 68 arr[0]: 6 8 10 10 12 14 arr[1]: 2 22 4 46 arr[2]: 4 68 6 88 P.S. Can we do better? On Wednesday, June 20, 2012 12:22:52 AM UTC+5:30, Amol Sharma wrote: @rammar: can you please explain the case...which i took in the earlier post..with this method. -- Amol Sharma Final 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/http://facebook.com/amolsharma99 On Tue, Jun 19, 2012 at 11:27 PM, rammar getam...@gmail.com wrote: @Hemesh +1 Please correct me if i am wrong. Creation of our look up array a[n*n] - sum of all the pairs will take O(n^2). Search using binary sort or quick sort in O(n^2 log (n^2) ) == O(n^2 log n) We will traverse this array, and for every element we will find (target - a[i]) - This traversal will again take O(n^2). For every (target -a[i]) we will search it in our lookup array using binary search - This will take O(log n^2) = O(2log n) = O(log n) We will store all the matched for the target. Final complexity = O(n^2) + O(n^2 log n) + O(n^2)*O(log n) == O (n^2 log n) If the values of max of a[n] is not very high, we can go with a hash map. This will result in a quick look up. And we can get the answer in O(n^2). P.S. Can we do better? On Monday, June 18, 2012 6:10:33 PM UTC+5:30, Jalaj wrote: @KK and hemesh target is not a constant value , it can be any element in array , so you need to do binary search for all (array[i] - (a+b)) to find which increases the complexity to n^3logn. So, i think the n^3 approach which i gave before do it ?? -- Correct me if m wrong On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma amolsharm...@gmail.comwrote: @hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final 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/http://facebook.com/amolsharma99 On Mon, Jun 18, 2012 at 12:29 AM, KK kunalkapadi...@gmail.comwrote: @Hemesh : +1 @Jalaj : read Hemesh's solution again it is for 4sum. In short, make a new array having sum of each unique pair of given array. - O(n^2) sort it - O(n^2) for each number bi in new array, binary search (target - bi) in the same array - O(n^2) On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and
[algogeeks] Find peak element in log(n)
Given an array of integers find a peak element of array in log(n) time.
for example if A={3,4,6,5,10} then peak element is 6 ( 65 64 ).
Regards.
--
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/-/AQI6ahWgyOIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Find peak element in log(n)
This is a variation of binary search, the difference being that we have to
search for an element that is greater than its immediate left one and
lesser than its immediate right one. Just implement binary search with
these additional constraints, thereby giving O(log n).
In case of any difficulty/error, let me know.
On Sun, Jun 24, 2012 at 1:27 AM, Hassan Monfared hmonfa...@gmail.comwrote:
Given an array of integers find a peak element of array in log(n) time.
for example if A={3,4,6,5,10} then peak element is 6 ( 65 64 ).
Regards.
--
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/-/AQI6ahWgyOIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Find peak element in log(n)
As array is not sorted, how do you decide to move left or right ?
On Sun, Jun 24, 2012 at 12:41 AM, adarsh kumar algog...@gmail.com wrote:
This is a variation of binary search, the difference being that we have to
search for an element that is greater than its immediate left one and
lesser than its immediate right one. Just implement binary search with
these additional constraints, thereby giving O(log n).
In case of any difficulty/error, let me know.
On Sun, Jun 24, 2012 at 1:27 AM, Hassan Monfared hmonfa...@gmail.comwrote:
Given an array of integers find a peak element of array in log(n) time.
for example if A={3,4,6,5,10} then peak element is 6 ( 65 64 ).
Regards.
--
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/-/AQI6ahWgyOIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Find peak element in log(n)
@adarsh kumar
are u sure it's worst case will be O (log n) ??
i think iff array is fully sorted O(n) will be required to say NO
such element present
On Sat, Jun 23, 2012 at 1:11 PM, adarsh kumar algog...@gmail.com wrote:
This is a variation of binary search, the difference being that we have to
search for an element that is greater than its immediate left one and lesser
than its immediate right one. Just implement binary search with these
additional constraints, thereby giving O(log n).
In case of any difficulty/error, let me know.
On Sun, Jun 24, 2012 at 1:27 AM, Hassan Monfared hmonfa...@gmail.com
wrote:
Given an array of integers find a peak element of array in log(n) time.
for example if A={3,4,6,5,10} then peak element is 6 ( 65 64 ).
Regards.
--
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/-/AQI6ahWgyOIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] 4Sum
@sourabh: for this particular question.. in your code replace if(binary_search(c,c+size,-b[i])) count++; by count+=upper_bound(c,c+size,-b[i])-lower_bound(c,c+size,-b[i]); you are actually missing some of the quadruplesas there can be more than one element with value -b[i] in the array c and you are actually ignoring them. -- Amol Sharma Final 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/http://facebook.com/amolsharma99 On Sun, Jun 24, 2012 at 1:22 AM, Sourabh Singh singhsourab...@gmail.comwrote: @ALL O(n^2 lg(n^2)) http://www.spoj.pl/problems/SUMFOUR/ my code : http://ideone.com/kAPNB plz. suggest some test case's : On Sat, Jun 23, 2012 at 6:59 AM, Amol Sharma amolsharm...@gmail.comwrote: @bhaskar,rammar: I don't think your algo willn not work for the following test case -- test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array -- Amol Sharma Final 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/http://facebook.com/amolsharma99 On Fri, Jun 22, 2012 at 11:45 PM, Bhaskar Kushwaha bhaskar.kushwaha2...@gmail.com wrote: We first compute the N^2 two sums, and sort the two sums. The for each TwoSum t, we check whether there is another two sum t' such that t.value + t'.value = target. The time complexity of this approach is O(N^2 logN) On Wed, Jun 20, 2012 at 1:36 AM, rammar getam...@gmail.com wrote: Lets see ur example... We can have two other arrays corresponding to our n^2 array. For every (target-arr[i]) which we search in our look up array, we can also search the components which were used to get that sum. This can be done in addition constant amount search. I hope we can still go with Hemesh's algo. Please let me know if it breaks somewhere... let's take a test case : arr: 2 4 68 arr[0]: 6 8 10 10 12 14 arr[1]: 2 22 4 46 arr[2]: 4 68 6 88 P.S. Can we do better? On Wednesday, June 20, 2012 12:22:52 AM UTC+5:30, Amol Sharma wrote: @rammar: can you please explain the case...which i took in the earlier post..with this method. -- Amol Sharma Final 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/http://facebook.com/amolsharma99 On Tue, Jun 19, 2012 at 11:27 PM, rammar getam...@gmail.com wrote: @Hemesh +1 Please correct me if i am wrong. Creation of our look up array a[n*n] - sum of all the pairs will take O(n^2). Search using binary sort or quick sort in O(n^2 log (n^2) ) == O(n^2 log n) We will traverse this array, and for every element we will find (target - a[i]) - This traversal will again take O(n^2). For every (target -a[i]) we will search it in our lookup array using binary search - This will take O(log n^2) = O(2log n) = O(log n) We will store all the matched for the target. Final complexity = O(n^2) + O(n^2 log n) + O(n^2)*O(log n) == O (n^2 log n) If the values of max of a[n] is not very high, we can go with a hash map. This will result in a quick look up. And we can get the answer in O(n^2). P.S. Can we do better? On Monday, June 18, 2012 6:10:33 PM UTC+5:30, Jalaj wrote: @KK and hemesh target is not a constant value , it can be any element in array , so you need to do binary search for all (array[i] - (a+b)) to find which increases the complexity to n^3logn. So, i think the n^3 approach which i gave before do it ?? -- Correct me if m wrong On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma amolsharm...@gmail.com wrote: @hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final 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/http://facebook.com/amolsharma99 On Mon, Jun 18,
Re: [algogeeks] 4Sum
@ Amol Sharma thanx got it.. yup, overlooked those case's :-) my bad.. On Sat, Jun 23, 2012 at 1:31 PM, Amol Sharma amolsharm...@gmail.com wrote: @sourabh: for this particular question.. in your code replace if(binary_search(c,c+size,-b[i])) count++; by count+=upper_bound(c,c+size,-b[i])-lower_bound(c,c+size,-b[i]); you are actually missing some of the quadruplesas there can be more than one element with value -b[i] in the array c and you are actually ignoring them. -- Amol Sharma Final 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/http://facebook.com/amolsharma99 On Sun, Jun 24, 2012 at 1:22 AM, Sourabh Singh singhsourab...@gmail.comwrote: @ALL O(n^2 lg(n^2)) http://www.spoj.pl/problems/SUMFOUR/ my code : http://ideone.com/kAPNB plz. suggest some test case's : On Sat, Jun 23, 2012 at 6:59 AM, Amol Sharma amolsharm...@gmail.comwrote: @bhaskar,rammar: I don't think your algo willn not work for the following test case -- test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array -- Amol Sharma Final 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/http://facebook.com/amolsharma99 On Fri, Jun 22, 2012 at 11:45 PM, Bhaskar Kushwaha bhaskar.kushwaha2...@gmail.com wrote: We first compute the N^2 two sums, and sort the two sums. The for each TwoSum t, we check whether there is another two sum t' such that t.value + t'.value = target. The time complexity of this approach is O(N^2 logN) On Wed, Jun 20, 2012 at 1:36 AM, rammar getam...@gmail.com wrote: Lets see ur example... We can have two other arrays corresponding to our n^2 array. For every (target-arr[i]) which we search in our look up array, we can also search the components which were used to get that sum. This can be done in addition constant amount search. I hope we can still go with Hemesh's algo. Please let me know if it breaks somewhere... let's take a test case : arr: 2 4 68 arr[0]: 6 8 10 10 12 14 arr[1]: 2 22 4 46 arr[2]: 4 68 6 88 P.S. Can we do better? On Wednesday, June 20, 2012 12:22:52 AM UTC+5:30, Amol Sharma wrote: @rammar: can you please explain the case...which i took in the earlier post..with this method. -- Amol Sharma Final 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/http://facebook.com/amolsharma99 On Tue, Jun 19, 2012 at 11:27 PM, rammar getam...@gmail.com wrote: @Hemesh +1 Please correct me if i am wrong. Creation of our look up array a[n*n] - sum of all the pairs will take O(n^2). Search using binary sort or quick sort in O(n^2 log (n^2) ) == O(n^2 log n) We will traverse this array, and for every element we will find (target - a[i]) - This traversal will again take O(n^2). For every (target -a[i]) we will search it in our lookup array using binary search - This will take O(log n^2) = O(2log n) = O(log n) We will store all the matched for the target. Final complexity = O(n^2) + O(n^2 log n) + O(n^2)*O(log n) == O (n^2 log n) If the values of max of a[n] is not very high, we can go with a hash map. This will result in a quick look up. And we can get the answer in O(n^2). P.S. Can we do better? On Monday, June 18, 2012 6:10:33 PM UTC+5:30, Jalaj wrote: @KK and hemesh target is not a constant value , it can be any element in array , so you need to do binary search for all (array[i] - (a+b)) to find which increases the complexity to n^3logn. So, i think the n^3 approach which i gave before do it ?? -- Correct me if m wrong On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma amolsharm...@gmail.com wrote: @hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99
Re: [algogeeks] Find peak element in log(n)
@adarsh :its nt dat easy as u see it..
On Sun, Jun 24, 2012 at 1:45 AM, Sourabh Singh singhsourab...@gmail.comwrote:
@adarsh kumar
are u sure it's worst case will be O (log n) ??
i think iff array is fully sorted O(n) will be required to say NO
such element present
On Sat, Jun 23, 2012 at 1:11 PM, adarsh kumar algog...@gmail.com wrote:
This is a variation of binary search, the difference being that we have
to
search for an element that is greater than its immediate left one and
lesser
than its immediate right one. Just implement binary search with these
additional constraints, thereby giving O(log n).
In case of any difficulty/error, let me know.
On Sun, Jun 24, 2012 at 1:27 AM, Hassan Monfared hmonfa...@gmail.com
wrote:
Given an array of integers find a peak element of array in log(n) time.
for example if A={3,4,6,5,10} then peak element is 6 ( 65 64 ).
Regards.
--
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/-/AQI6ahWgyOIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Regards*
Mahendra Pratap Singh Sengar
B-tech 4/4
NIT Warangal.
Facebook ID http://www.facebook.com/mkingmahi
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Find peak element in log(n)
just found a good resource for 1d and 2D version :
http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
On Sun, Jun 24, 2012 at 3:31 AM, sengar.mahi sengar.m...@gmail.com wrote:
@adarsh :its nt dat easy as u see it..
On Sun, Jun 24, 2012 at 1:45 AM, Sourabh Singh
singhsourab...@gmail.comwrote:
@adarsh kumar
are u sure it's worst case will be O (log n) ??
i think iff array is fully sorted O(n) will be required to say NO
such element present
On Sat, Jun 23, 2012 at 1:11 PM, adarsh kumar algog...@gmail.com wrote:
This is a variation of binary search, the difference being that we have
to
search for an element that is greater than its immediate left one and
lesser
than its immediate right one. Just implement binary search with these
additional constraints, thereby giving O(log n).
In case of any difficulty/error, let me know.
On Sun, Jun 24, 2012 at 1:27 AM, Hassan Monfared hmonfa...@gmail.com
wrote:
Given an array of integers find a peak element of array in log(n) time.
for example if A={3,4,6,5,10} then peak element is 6 ( 65 64 ).
Regards.
--
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/-/AQI6ahWgyOIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Regards*
Mahendra Pratap Singh Sengar
B-tech 4/4
NIT Warangal.
Facebook ID http://www.facebook.com/mkingmahi
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Find peak element in log(n)
@Hassan Monfared
was reading that link only. it's strange how he assume's we can leave
half of element's ??
– If A[n/2-1]A[n/2] then search for a peak among A[1]… A[n/2-1] ?? why ??
eg. 12 12 12 11 1 2 5 3
m i missing something ??
On Sat, Jun 23, 2012 at 10:02 PM, Hassan Monfared hmonfa...@gmail.com wrote:
just found a good resource for 1d and 2D version :
http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
On Sun, Jun 24, 2012 at 3:31 AM, sengar.mahi sengar.m...@gmail.com wrote:
@adarsh :its nt dat easy as u see it..
On Sun, Jun 24, 2012 at 1:45 AM, Sourabh Singh singhsourab...@gmail.com
wrote:
@adarsh kumar
are u sure it's worst case will be O (log n) ??
i think iff array is fully sorted O(n) will be required to say NO
such element present
On Sat, Jun 23, 2012 at 1:11 PM, adarsh kumar algog...@gmail.com wrote:
This is a variation of binary search, the difference being that we have
to
search for an element that is greater than its immediate left one and
lesser
than its immediate right one. Just implement binary search with these
additional constraints, thereby giving O(log n).
In case of any difficulty/error, let me know.
On Sun, Jun 24, 2012 at 1:27 AM, Hassan Monfared hmonfa...@gmail.com
wrote:
Given an array of integers find a peak element of array in log(n)
time.
for example if A={3,4,6,5,10} then peak element is 6 ( 65 64 ).
Regards.
--
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/-/AQI6ahWgyOIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Mahendra Pratap Singh Sengar
B-tech 4/4
NIT Warangal.
Facebook ID
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Find peak element in log(n)
I was amazed too, but Idea is about :
--
Otherwise: locally rising on some side
• Must be a peak in that direction
• So can throw away rest of array,
leaving a[0-i] or a[i+1-n].
--
i'm not sure yet and need to test with a code.
On Sun, Jun 24, 2012 at 9:45 AM, Sourabh Singh singhsourab...@gmail.comwrote:
@Hassan Monfared
was reading that link only. it's strange how he assume's we can leave
half of element's ??
– If A[n/2-1]A[n/2] then search for a peak among A[1]… A[n/2-1] ?? why ??
eg. 12 12 12 11 1 2 5 3
m i missing something ??
On Sat, Jun 23, 2012 at 10:02 PM, Hassan Monfared hmonfa...@gmail.com
wrote:
just found a good resource for 1d and 2D version :
http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
On Sun, Jun 24, 2012 at 3:31 AM, sengar.mahi sengar.m...@gmail.com
wrote:
@adarsh :its nt dat easy as u see it..
On Sun, Jun 24, 2012 at 1:45 AM, Sourabh Singh
singhsourab...@gmail.com
wrote:
@adarsh kumar
are u sure it's worst case will be O (log n) ??
i think iff array is fully sorted O(n) will be required to say NO
such element present
On Sat, Jun 23, 2012 at 1:11 PM, adarsh kumar algog...@gmail.com
wrote:
This is a variation of binary search, the difference being that we
have
to
search for an element that is greater than its immediate left one and
lesser
than its immediate right one. Just implement binary search with these
additional constraints, thereby giving O(log n).
In case of any difficulty/error, let me know.
On Sun, Jun 24, 2012 at 1:27 AM, Hassan Monfared
hmonfa...@gmail.com
wrote:
Given an array of integers find a peak element of array in log(n)
time.
for example if A={3,4,6,5,10} then peak element is 6 ( 65 64 ).
Regards.
--
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/-/AQI6ahWgyOIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Mahendra Pratap Singh Sengar
B-tech 4/4
NIT Warangal.
Facebook ID
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Find peak element in log(n)
I think it can't be done in O(log n) as per given problem constraints.
It can be done in O(log n) if additional information that array is
bitonic is given.
--
Prakhar Jain
IIIT Allahabad
B.Tech IT 3rd Year
Mob no: +91 9454992196
E-mail: rit2009...@iiita.ac.in
jprakha...@gmail.com
On Sun, Jun 24, 2012 at 1:45 AM, Sourabh Singh singhsourab...@gmail.comwrote:
@adarsh kumar
are u sure it's worst case will be O (log n) ??
i think iff array is fully sorted O(n) will be required to say NO
such element present
On Sat, Jun 23, 2012 at 1:11 PM, adarsh kumar algog...@gmail.com wrote:
This is a variation of binary search, the difference being that we have
to
search for an element that is greater than its immediate left one and
lesser
than its immediate right one. Just implement binary search with these
additional constraints, thereby giving O(log n).
In case of any difficulty/error, let me know.
On Sun, Jun 24, 2012 at 1:27 AM, Hassan Monfared hmonfa...@gmail.com
wrote:
Given an array of integers find a peak element of array in log(n) time.
for example if A={3,4,6,5,10} then peak element is 6 ( 65 64 ).
Regards.
--
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/-/AQI6ahWgyOIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.
