[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.
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 dave_and_da...@juno.com 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 ashg...@gmail.com 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.
Re: [algogeeks] Re: Google Q
perfect. Thanks for the effort in explanation. On Sun, May 15, 2011 at 12:20 AM, Dave dave_and_da...@juno.com 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 :-) pacific4...@gmail.com 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 dave_and_da...@juno.com 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 ashg...@gmail.com 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: 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 dave_and_da...@juno.com 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 apoorvemo...@gmail.com wrote: @Dave: Can there be an in-place O(n) solution to this??? On Mon, May 9, 2011 at 7:01 PM, Dave dave_and_da...@juno.com 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 ashg...@gmail.com 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 dave_and_da...@juno.com 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 indexK, 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 amitjaspal...@gmail.com 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 this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan- 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
[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 akshatasharm...@gmail.com 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 dave_and_da...@juno.com 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 apoorvemo...@gmail.com wrote: @Dave: Can there be an in-place O(n) solution to this??? On Mon, May 9, 2011 at 7:01 PM, Dave dave_and_da...@juno.com 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 ashg...@gmail.com 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 dave_and_da...@juno.com 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 indexK, 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 amitjaspal...@gmail.com 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.-Hidequoted 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] 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 inta,const intb){
return (idistance[a]idistance[b]);
}
};
int prim(int s){
int u,v,i;
priority_queueint,vectorint,lesstQ;
idistance[s]=0;
Q.push(s);
for(i=0;in;++i){
if(i==s)continue;
idistance[i]=INF;
parent[i]=-1;
Q.push(i);
}
while(!Q.empty()){
u=Q.top();
rec[u]=1;
Q.pop();
for(v=0;vn;++v){
if(weights[u][v]==0);
else if(!rec[v] weights[u][v]idistance[v]){
parent[v]=u;
idistance[v]=weights[u][v];
}
}
}
return idistance[s];
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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
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 :-) pacific4...@gmail.com wrote: perfect. Thanks for the effort in explanation. On Sun, May 15, 2011 at 12:20 AM, Dave dave_and_da...@juno.com 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 :-) pacific4...@gmail.com 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 dave_and_da...@juno.com 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 ashg...@gmail.com 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.
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 anandut2...@gmail.com 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 :-) pacific4...@gmail.comwrote: perfect. Thanks for the effort in explanation. On Sun, May 15, 2011 at 12:20 AM, Dave dave_and_da...@juno.com 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 :-) pacific4...@gmail.com 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 dave_and_da...@juno.com 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 ashg...@gmail.com 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.
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]A[j]?? On Fri, May 13, 2011 at 1:54 AM, amit amitjaspal...@gmail.com wrote: Given an array A[i..j] find out maximum j-i such that A[i]a[j] in 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] 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.
