Re: [algogeeks] Array problem
how about this??
*int maxinterval(int a[],int i,int j)
{
if(i==j)
return 0;
int max1 = 0,max2;
max2 = maxinterval(a,i+1,j);
while(imax1)
max1 =j-i;
}
i++;
}
return(max1>max2?max1:max2);
}
*
On Mon, May 16, 2011 at 11:36 AM, anuj agarwal wrote:
> How about create a BST and then, for each node find the difference between
> the node and its child and do this for all except leaf nodes.
> If u want i will write the code for the same.
>
> Anuj Agarwal
>
> Engineering is the art of making what you want from things you can get.
>
>
> On Mon, May 16, 2011 at 11:20 AM, anshu mishra > wrote:
>
>> @amit ur code is wrong. just check it for this {5, 4, 1, 8, 4, 4};
>>
>> --the
>> You received this message because you are subscribed to the Google
>> Groups "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
PIYUSH SINHA
9936757773
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Array problem
How about create a BST and then, for each node find the difference between
the node and its child and do this for all except leaf nodes.
If u want i will write the code for the same.
Anuj Agarwal
Engineering is the art of making what you want from things you can get.
On Mon, May 16, 2011 at 11:20 AM, anshu mishra wrote:
> @amit ur code is wrong. just check it for this {5, 4, 1, 8, 4, 4};
>
> --the
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Array problem
@amit ur code is wrong. just check it for this {5, 4, 1, 8, 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.
Re: [algogeeks] Array problem
@amit jaspal I have doubt with your question...in the maximum window found i.e. A[i..j]...the elements should be in increasing order or only the end elements should have the relation of A[i] wrote: > Given an array A[i..j] find out maximum j-i such that A[i] O(n) time. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- PIYUSH SINHA 9936757773 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Google Q
@Anand: if the stream is let 1,2,3,4,6,7,9 and let we choose k=3 then your algo is giving 7 as the median. On Mon, May 16, 2011 at 4:39 AM, Anand wrote: > Complexity will be O(logK) to insert, delete and finding the predecessor or > successor of current median value in the BST. > > > On Sun, May 15, 2011 at 4:08 PM, Anand wrote: > >> 1. Create a BST for first K elements of the running stream. >> 2. Find the median of first K elements. >> 3. With every new element from the stream, Insert the new element in >> Binary search Tree. >> 4. Delete the first element from BST. >> 5. if the new element is greater than the current median value, find the >> successor of current median value. >> 6. else if the new elment is less than the current median value, find the >> predecessor of the currend median value in BST. >> >> >> >> On Sun, May 15, 2011 at 2:51 AM, pacific :-) wrote: >> >>> perfect. >>> >>> Thanks for the effort in explanation. >>> >>> >>> On Sun, May 15, 2011 at 12:20 AM, Dave wrote: >>> @Pacific: A balanced binary tree is commonly defined as a binary tree in which the height of the two subtrees of every node never differ by more than 1. Thus, there could be more nodes in one subtree than in the other. E.g., a balanced binary tree with 11 nodes could have 7 nodes in the left subtree and only 3 nodes in the right subtree. Thus, the root would not be the median. An additional condition is needed: the number of nodes in the left subtree differs by at most one from the number of nodes in the right subtree. In fact, given that the heap structure is a balanced binary tree structure with implicit pointers to the left and right subtrees, the two-heap algorithm I described results in a balanced binary tree satisfying this additional condition, with an implicit root node equal to the median. Dave On May 14, 11:55 am, "pacific :-)" wrote: > Will not a balanced binary tree do the job ? if we will pick the root each > time for the median. > > > > > > On Sat, May 14, 2011 at 9:10 PM, Dave wrote: > > @Ashish: The idea is to keep two heaps, a max-heap of the smallest > > half of the elements and a min-heap of the largest elements. You > > insert incoming elements into the appropriate heap. If the result is > > that the number of elements in the two heaps differs by more than 1, > > then you move the top element from the longer heap into the other one, > > thereby equalzing the number of elements. Thus, inserting an element > > is an O(log n) operation. To get the median, it is the top element of > > the longer heap, or, if the heaps are of equal length, it is the > > average of the two top elements. This is O(1). > > > Dave > > > On May 14, 8:34 am, Ashish Goel wrote: > > > not clear, can u elaborate.. > > > > Best Regards > > > Ashish Goel > > > "Think positive and find fuel in failure" > > > +919985813081 > > > +919966006652 > > > > On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal < agr.bhav...@gmail.com > > >wrote: > > > > > This problem can be solved using 2 heaps and the median can always be > > > > accessed in O(1) time ,the first node. > > > > > -- > > > > You received this message because you are subscribed to the Google > > Groups > > > > "Algorithm Geeks" group. > > > > To post to this group, send email to algogeeks@googlegroups.com . > > > > To unsubscribe from this group, send email to > > > > algogeeks+unsubscr...@googlegroups.com. > > > > For more options, visit this group at > > > >http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - > > > > - Show quoted text - > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > regards, > chinna.- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. >>> >>> >>> -- >>> regards, >>> chinna. >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" g
Re: [algogeeks] Re: Google Q
Complexity will be O(logK) to insert, delete and finding the predecessor or successor of current median value in the BST. On Sun, May 15, 2011 at 4:08 PM, Anand wrote: > 1. Create a BST for first K elements of the running stream. > 2. Find the median of first K elements. > 3. With every new element from the stream, Insert the new element in Binary > search Tree. > 4. Delete the first element from BST. > 5. if the new element is greater than the current median value, find the > successor of current median value. > 6. else if the new elment is less than the current median value, find the > predecessor of the currend median value in BST. > > > > On Sun, May 15, 2011 at 2:51 AM, pacific :-) wrote: > >> perfect. >> >> Thanks for the effort in explanation. >> >> >> On Sun, May 15, 2011 at 12:20 AM, Dave wrote: >> >>> @Pacific: A balanced binary tree is commonly defined as a binary tree >>> in which the height of the two subtrees of every node never differ by >>> more than 1. Thus, there could be more nodes in one subtree than in >>> the other. E.g., a balanced binary tree with 11 nodes could have 7 >>> nodes in the left subtree and only 3 nodes in the right subtree. Thus, >>> the root would not be the median. >>> >>> An additional condition is needed: the number of nodes in the left >>> subtree differs by at most one from the number of nodes in the right >>> subtree. >>> >>> In fact, given that the heap structure is a balanced binary tree >>> structure with implicit pointers to the left and right subtrees, the >>> two-heap algorithm I described results in a balanced binary tree >>> satisfying this additional condition, with an implicit root node equal >>> to the median. >>> >>> Dave >>> >>> On May 14, 11:55 am, "pacific :-)" wrote: >>> > Will not a balanced binary tree do the job ? if we will pick the root >>> each >>> > time for the median. >>> > >>> > >>> > >>> > >>> > >>> > On Sat, May 14, 2011 at 9:10 PM, Dave wrote: >>> > > @Ashish: The idea is to keep two heaps, a max-heap of the smallest >>> > > half of the elements and a min-heap of the largest elements. You >>> > > insert incoming elements into the appropriate heap. If the result is >>> > > that the number of elements in the two heaps differs by more than 1, >>> > > then you move the top element from the longer heap into the other >>> one, >>> > > thereby equalzing the number of elements. Thus, inserting an element >>> > > is an O(log n) operation. To get the median, it is the top element of >>> > > the longer heap, or, if the heaps are of equal length, it is the >>> > > average of the two top elements. This is O(1). >>> > >>> > > Dave >>> > >>> > > On May 14, 8:34 am, Ashish Goel wrote: >>> > > > not clear, can u elaborate.. >>> > >>> > > > Best Regards >>> > > > Ashish Goel >>> > > > "Think positive and find fuel in failure" >>> > > > +919985813081 >>> > > > +919966006652 >>> > >>> > > > On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal < >>> agr.bhav...@gmail.com >>> > > >wrote: >>> > >>> > > > > This problem can be solved using 2 heaps and the median can >>> always be >>> > > > > accessed in O(1) time ,the first node. >>> > >>> > > > > -- >>> > > > > You received this message because you are subscribed to the >>> Google >>> > > Groups >>> > > > > "Algorithm Geeks" group. >>> > > > > To post to this group, send email to algogeeks@googlegroups.com. >>> > > > > To unsubscribe from this group, send email to >>> > > > > algogeeks+unsubscr...@googlegroups.com. >>> > > > > For more options, visit this group at >>> > > > >http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text >>> - >>> > >>> > > > - Show quoted text - >>> > >>> > > -- >>> > > You received this message because you are subscribed to the Google >>> Groups >>> > > "Algorithm Geeks" group. >>> > > To post to this group, send email to algogeeks@googlegroups.com. >>> > > To unsubscribe from this group, send email to >>> > > algogeeks+unsubscr...@googlegroups.com. >>> > > For more options, visit this group at >>> > >http://groups.google.com/group/algogeeks?hl=en. >>> > >>> > -- >>> > regards, >>> > chinna.- Hide quoted text - >>> > >>> > - Show quoted text - >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> >> >> -- >> regards, >> chinna. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- You received this message because you are s
Re: [algogeeks] Re: Google Q
1. Create a BST for first K elements of the running stream. 2. Find the median of first K elements. 3. With every new element from the stream, Insert the new element in Binary search Tree. 4. Delete the first element from BST. 5. if the new element is greater than the current median value, find the successor of current median value. 6. else if the new elment is less than the current median value, find the predecessor of the currend median value in BST. On Sun, May 15, 2011 at 2:51 AM, pacific :-) wrote: > perfect. > > Thanks for the effort in explanation. > > > On Sun, May 15, 2011 at 12:20 AM, Dave wrote: > >> @Pacific: A balanced binary tree is commonly defined as a binary tree >> in which the height of the two subtrees of every node never differ by >> more than 1. Thus, there could be more nodes in one subtree than in >> the other. E.g., a balanced binary tree with 11 nodes could have 7 >> nodes in the left subtree and only 3 nodes in the right subtree. Thus, >> the root would not be the median. >> >> An additional condition is needed: the number of nodes in the left >> subtree differs by at most one from the number of nodes in the right >> subtree. >> >> In fact, given that the heap structure is a balanced binary tree >> structure with implicit pointers to the left and right subtrees, the >> two-heap algorithm I described results in a balanced binary tree >> satisfying this additional condition, with an implicit root node equal >> to the median. >> >> Dave >> >> On May 14, 11:55 am, "pacific :-)" wrote: >> > Will not a balanced binary tree do the job ? if we will pick the root >> each >> > time for the median. >> > >> > >> > >> > >> > >> > On Sat, May 14, 2011 at 9:10 PM, Dave wrote: >> > > @Ashish: The idea is to keep two heaps, a max-heap of the smallest >> > > half of the elements and a min-heap of the largest elements. You >> > > insert incoming elements into the appropriate heap. If the result is >> > > that the number of elements in the two heaps differs by more than 1, >> > > then you move the top element from the longer heap into the other one, >> > > thereby equalzing the number of elements. Thus, inserting an element >> > > is an O(log n) operation. To get the median, it is the top element of >> > > the longer heap, or, if the heaps are of equal length, it is the >> > > average of the two top elements. This is O(1). >> > >> > > Dave >> > >> > > On May 14, 8:34 am, Ashish Goel wrote: >> > > > not clear, can u elaborate.. >> > >> > > > Best Regards >> > > > Ashish Goel >> > > > "Think positive and find fuel in failure" >> > > > +919985813081 >> > > > +919966006652 >> > >> > > > On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal < >> agr.bhav...@gmail.com >> > > >wrote: >> > >> > > > > This problem can be solved using 2 heaps and the median can always >> be >> > > > > accessed in O(1) time ,the first node. >> > >> > > > > -- >> > > > > You received this message because you are subscribed to the Google >> > > Groups >> > > > > "Algorithm Geeks" group. >> > > > > To post to this group, send email to algogeeks@googlegroups.com. >> > > > > To unsubscribe from this group, send email to >> > > > > algogeeks+unsubscr...@googlegroups.com. >> > > > > For more options, visit this group at >> > > > >http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - >> > >> > > > - Show quoted text - >> > >> > > -- >> > > You received this message because you are subscribed to the Google >> Groups >> > > "Algorithm Geeks" group. >> > > To post to this group, send email to algogeeks@googlegroups.com. >> > > To unsubscribe from this group, send email to >> > > algogeeks+unsubscr...@googlegroups.com. >> > > For more options, visit this group at >> > >http://groups.google.com/group/algogeeks?hl=en. >> > >> > -- >> > regards, >> > chinna.- Hide quoted text - >> > >> > - Show quoted text - >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > regards, > chinna. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] prim problem
Hi, this should be working, where is the problem?
const int INF=99;
int n=6;
int weights[6][6];
int parent[6];
int idistance[6];
int rec[6];
struct lesst{
bool operator()(const int&a,const int&b){
return (idistance[a]>idistance[b]);
}
};
int prim(int s){
int u,v,i;
priority_queue,lesst>Q;
idistance[s]=0;
Q.push(s);
for(i=0;ihttp://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Extract Top K elements from a List of N elements based on frequency
@Akshata: Yes. In my response of May 7, I proposed an algorithm using hashing. On May 9, Apoorve asked if there was an in-place O(n) solution. I take it that in-place means with only O(1) extra space. That is the question to which I was responding. Your suggestion of using a hashmap is non-responsive since it uses more than O(1) extra space. Dave On May 15, 9:49 am, Akshata Sharma wrote: > hash all the elements. Keys are stored in hashmap in sorted order based on > values. just iterate thru the hashmap extracting the first k keys. > m I missing something? > > > > On Thu, May 12, 2011 at 2:50 AM, Dave wrote: > > @Apoorve: I don't believe that you can determine the frequency counts > > in-place in O(n). > > > Dave > > > On May 9, 8:42 am, Apoorve Mohan wrote: > > > @Dave: Can there be an in-place O(n) solution to this??? > > > > On Mon, May 9, 2011 at 7:01 PM, Dave wrote: > > > > @Ashish: By compress, I meant to transfer the active entries in the > > > > hash table into contiguous elements of an array. Since the hash table > > > > itself is probably stored in an array, it just means to go through the > > > > hash table array and move the active entries to the front of the > > > > array. > > > > > Dave > > > > > On May 9, 1:14 am, Ashish Goel wrote: > > > > > Dave, > > > > > w.r.t statement, After all integers are processed, compress out the > > > > unused > > > > > hash table > > > > > entries and find the Kth largest element, > > > > > > I could not understand the compress concept...are you saying > > something on > > > > > counting sort philosophy? > > > > > say the list is > > > > > > 5 > > > > > 4 > > > > > 4 > > > > > 3 > > > > > 3 > > > > > 3 > > > > > 2 > > > > > 2 > > > > > 2 > > > > > 2 > > > > > 1 > > > > > 1 > > > > > 1 > > > > > 1 > > > > > 1 > > > > > > so the hash map will have > > > > > > 5,1 <5 is 1 time> > > > > > 4,2,<4 is two time> > > > > > 3,3,... > > > > > 2,4,... > > > > > 1,5... > > > > > > so if the question is to find say 3rd largest element based on > > frequency, > > > > it > > > > > would be 4 > > > > > This essentially means that we probably need dynamic order statistics > > > > where > > > > > the node contains the starting rank for a particular entry in the > > RBTree. > > > > > Each RBTree node contains the number, its frequency and rank. then > > this > > > > > becomes O(n) +O(lgn) i.e. O(n) > > > > > > Best Regards > > > > > Ashish Goel > > > > > "Think positive and find fuel in failure" > > > > > +919985813081 > > > > > +919966006652 > > > > > > On Sat, May 7, 2011 at 11:03 PM, Dave > > wrote: > > > > > > @Gaurav: As I understand your solution, you are finding the K > > largest > > > > > > integers based on value, rather than the K with the highest > > frequency > > > > > > of occurrence. > > > > > > > @Amit: Hash the integers into a hash table that includes a field > > for > > > > > > the frequency count. When a new entry is made, set the frequency > > count > > > > > > to 1. When an integer already is in the table, increment its count. > > > > > > After all integers are processed, compress out the unused hash > > table > > > > > > entries and find the Kth largest element. The overall algorithm can > > be > > > > > > done in O(n). > > > > > > > Dave > > > > > > > On May 7, 12:06 pm, Gaurav Aggarwal <0007gau...@gmail.com> wrote: > > > > > > > It can be done without sorting. Take the first element as pivot > > > > > > > element. Calculate its position using Partition algorithm. > > > > > > > If its new index is K, then on left side are top K integers. If > > > > index>K, > > > > > > > apply algo on left side Else apply algo on right side. > > > > > > > > Best Case: O(1) > > > > > > > Worst Case: O(n^2) > > > > > > > > But there are very less chances of worst case. It is when the > > list is > > > > > > > already sorted. > > > > > > > > On Thu, May 5, 2011 at 1:06 AM, amit > > > > wrote: > > > > > > > > Hi , > > > > > > > > > We are give a list of integers now our task is to find the top > > K > > > > > > > > integers in the list based on frequency. > > > > > > > > > Apart from sorting the data can there be any other algorithm? > > > > > > > > > -- > > > > > > > > You received this message because you are subscribed to the > > Google > > > > > > Groups > > > > > > > > "Algorithm Geeks" group. > > > > > > > > To post to this group, send email to > > algogeeks@googlegroups.com. > > > > > > > > To unsubscribe from this group, send email to > > > > > > > > algogeeks+unsubscr...@googlegroups.com. > > > > > > > > For more options, visit this group at > > > > > > > >http://groups.google.com/group/algogeeks?hl=en. > > > > > > > > -- > > > > > > > Gaurav Aggarwal > > > > > > > SCJP- Hide quoted text - > > > > > > > > - Show quoted text - > > > > > > > -- > > > > > > You received this message because you are subscribed to the Google > > > > Groups > > > > > > "Algorithm Geeks" group. > > > > > > To post to this group, send email to algogeeks@googlegroups.com. > > > > > > To
Re: [algogeeks] Re: Extract Top K elements from a List of N elements based on frequency
hash all the elements. Keys are stored in hashmap in sorted order based on values. just iterate thru the hashmap extracting the first k keys. m I missing something? On Thu, May 12, 2011 at 2:50 AM, Dave wrote: > @Apoorve: I don't believe that you can determine the frequency counts > in-place in O(n). > > Dave > > On May 9, 8:42 am, Apoorve Mohan wrote: > > @Dave: Can there be an in-place O(n) solution to this??? > > > > > > > > > > > > On Mon, May 9, 2011 at 7:01 PM, Dave wrote: > > > @Ashish: By compress, I meant to transfer the active entries in the > > > hash table into contiguous elements of an array. Since the hash table > > > itself is probably stored in an array, it just means to go through the > > > hash table array and move the active entries to the front of the > > > array. > > > > > Dave > > > > > On May 9, 1:14 am, Ashish Goel wrote: > > > > Dave, > > > > w.r.t statement, After all integers are processed, compress out the > > > unused > > > > hash table > > > > entries and find the Kth largest element, > > > > > > I could not understand the compress concept...are you saying > something on > > > > counting sort philosophy? > > > > say the list is > > > > > > 5 > > > > 4 > > > > 4 > > > > 3 > > > > 3 > > > > 3 > > > > 2 > > > > 2 > > > > 2 > > > > 2 > > > > 1 > > > > 1 > > > > 1 > > > > 1 > > > > 1 > > > > > > so the hash map will have > > > > > > 5,1 <5 is 1 time> > > > > 4,2,<4 is two time> > > > > 3,3,... > > > > 2,4,... > > > > 1,5... > > > > > > so if the question is to find say 3rd largest element based on > frequency, > > > it > > > > would be 4 > > > > This essentially means that we probably need dynamic order statistics > > > where > > > > the node contains the starting rank for a particular entry in the > RBTree. > > > > Each RBTree node contains the number, its frequency and rank. then > this > > > > becomes O(n) +O(lgn) i.e. O(n) > > > > > > Best Regards > > > > Ashish Goel > > > > "Think positive and find fuel in failure" > > > > +919985813081 > > > > +919966006652 > > > > > > On Sat, May 7, 2011 at 11:03 PM, Dave > wrote: > > > > > @Gaurav: As I understand your solution, you are finding the K > largest > > > > > integers based on value, rather than the K with the highest > frequency > > > > > of occurrence. > > > > > > > @Amit: Hash the integers into a hash table that includes a field > for > > > > > the frequency count. When a new entry is made, set the frequency > count > > > > > to 1. When an integer already is in the table, increment its count. > > > > > After all integers are processed, compress out the unused hash > table > > > > > entries and find the Kth largest element. The overall algorithm can > be > > > > > done in O(n). > > > > > > > Dave > > > > > > > On May 7, 12:06 pm, Gaurav Aggarwal <0007gau...@gmail.com> wrote: > > > > > > It can be done without sorting. Take the first element as pivot > > > > > > element. Calculate its position using Partition algorithm. > > > > > > If its new index is K, then on left side are top K integers. If > > > index>K, > > > > > > apply algo on left side Else apply algo on right side. > > > > > > > > Best Case: O(1) > > > > > > Worst Case: O(n^2) > > > > > > > > But there are very less chances of worst case. It is when the > list is > > > > > > already sorted. > > > > > > > > On Thu, May 5, 2011 at 1:06 AM, amit > > > wrote: > > > > > > > Hi , > > > > > > > > > We are give a list of integers now our task is to find the top > K > > > > > > > integers in the list based on frequency. > > > > > > > > > Apart from sorting the data can there be any other algorithm? > > > > > > > > > -- > > > > > > > You received this message because you are subscribed to the > Google > > > > > Groups > > > > > > > "Algorithm Geeks" group. > > > > > > > To post to this group, send email to > algogeeks@googlegroups.com. > > > > > > > To unsubscribe from this group, send email to > > > > > > > algogeeks+unsubscr...@googlegroups.com. > > > > > > > For more options, visit this group at > > > > > > >http://groups.google.com/group/algogeeks?hl=en. > > > > > > > > -- > > > > > > Gaurav Aggarwal > > > > > > SCJP- Hide quoted text - > > > > > > > > - Show quoted text - > > > > > > > -- > > > > > You received this message because you are subscribed to the Google > > > Groups > > > > > "Algorithm Geeks" group. > > > > > To post to this group, send email to algogeeks@googlegroups.com. > > > > > To unsubscribe from this group, send email to > > > > > algogeeks+unsubscr...@googlegroups.com. > > > > > For more options, visit this group at > > > > >http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - > > > > > > - Show quoted text - > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algogeeks@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com. > > > For more options, visit thi
Re: [algogeeks] Re: Google Q
perfect. Thanks for the effort in explanation. On Sun, May 15, 2011 at 12:20 AM, Dave wrote: > @Pacific: A balanced binary tree is commonly defined as a binary tree > in which the height of the two subtrees of every node never differ by > more than 1. Thus, there could be more nodes in one subtree than in > the other. E.g., a balanced binary tree with 11 nodes could have 7 > nodes in the left subtree and only 3 nodes in the right subtree. Thus, > the root would not be the median. > > An additional condition is needed: the number of nodes in the left > subtree differs by at most one from the number of nodes in the right > subtree. > > In fact, given that the heap structure is a balanced binary tree > structure with implicit pointers to the left and right subtrees, the > two-heap algorithm I described results in a balanced binary tree > satisfying this additional condition, with an implicit root node equal > to the median. > > Dave > > On May 14, 11:55 am, "pacific :-)" wrote: > > Will not a balanced binary tree do the job ? if we will pick the root > each > > time for the median. > > > > > > > > > > > > On Sat, May 14, 2011 at 9:10 PM, Dave wrote: > > > @Ashish: The idea is to keep two heaps, a max-heap of the smallest > > > half of the elements and a min-heap of the largest elements. You > > > insert incoming elements into the appropriate heap. If the result is > > > that the number of elements in the two heaps differs by more than 1, > > > then you move the top element from the longer heap into the other one, > > > thereby equalzing the number of elements. Thus, inserting an element > > > is an O(log n) operation. To get the median, it is the top element of > > > the longer heap, or, if the heaps are of equal length, it is the > > > average of the two top elements. This is O(1). > > > > > Dave > > > > > On May 14, 8:34 am, Ashish Goel wrote: > > > > not clear, can u elaborate.. > > > > > > Best Regards > > > > Ashish Goel > > > > "Think positive and find fuel in failure" > > > > +919985813081 > > > > +919966006652 > > > > > > On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal < > agr.bhav...@gmail.com > > > >wrote: > > > > > > > This problem can be solved using 2 heaps and the median can always > be > > > > > accessed in O(1) time ,the first node. > > > > > > > -- > > > > > You received this message because you are subscribed to the Google > > > Groups > > > > > "Algorithm Geeks" group. > > > > > To post to this group, send email to algogeeks@googlegroups.com. > > > > > To unsubscribe from this group, send email to > > > > > algogeeks+unsubscr...@googlegroups.com. > > > > > For more options, visit this group at > > > > >http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - > > > > > > - Show quoted text - > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algogeeks@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > > > -- > > regards, > > chinna.- Hide quoted text - > > > > - Show quoted text - > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- regards, chinna. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Google Q
@Dave:
without using comparison operator,
int sign = (a >> (sizeof(int) * CHAR_BIT - 1));
sign=0 if a is +ive or 0
else sign=-1;
int mult(int x, int y)
{
int p = 0, s = y;
int sign = (y >> (sizeof(int) * CHAR_BIT - 1));
if(sign) y = add(~y,1);
while(y)
{
if(y & 1) p = add(x, p);
x <<= 1;
y >>= 1;
}
sign=(s>>(sizeof(int)*CHAR_BIT - 1));
if(sign) p = add(~p,1);
return(p);
}
On Sat, May 14, 2011 at 2:28 AM, Dave wrote:
> @Ashish: Here's addition, subtraction, and multiplication with bit
> manipulation and comparisons. I doubt if you can do them without
> comparisons.
>
> int add(int x, int y)
> {
>int c;
>while(y)
>{
>c = x & y;
>x ^= y;
>y = c << 1;
>}
>return(x);
> }
>
> int sub(int x, int y)
> {
>return(add(x,add(~y,1));
> }
>
> int mult(int x, int y)
> {
>int p = 0, s = y;
>if(y < 0) y = add(~y,1);
>while(y)
>{
>if(y & 1) p = add(x, p);
>x <<= 1;
>y >>= 1;
>}
>if(s < 0) p = add(~p,1);
>return(p);
> }
>
> Dave
>
> On May 12, 10:03 pm, Ashish Goel wrote:
> > Using bit manipulation, implement add, subtract and multiply on two
> > integers. You cannot use any arithmetic operations, such as +, - or *.
> >
> > Best Regards
> > Ashish Goel
> > "Think positive and find fuel in failure"
> > +919985813081
> > +919966006652
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Popular Puzzle of the week
*Hi,* * * *Based on most comments, The popular puzzle of the last week is* * http://dailybrainteaser.blogspot.com/2011/05/maths-trick-teaser-9-may.html?lavesh=lavesh * *Please subscribe and follow this blog to show your liking to the blog.* * * -- "Never explain yourself. Your friends don’t need it and your enemies won’t believe 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.
