Re: [algogeeks] Re: Swap the bits
char a=10 01 11 01 a = a ^ ~ ( 0 ) //now a is 01 10 00 10 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Variant Of Dutch National Flag Problem
in place constraint is violated in radix sort -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find parent/grandparent relationship of nodes in binary tree in O(1) time
One possible soln is: Store the k ary- tree nodes in an array such that child of the ith node lies in index range from (k*i -1) to (k*i + k -2) range. This way child and grandchild index and corresponding items can be found in constant time. On Feb 5, 8:47 pm, Anurag Bhatia abhati...@gmail.com wrote: @Nirmal: Did you find a solution as yet? On Thu, Jan 28, 2010 at 6:40 PM, Nirmal nirm...@gmail.com wrote: I found this problem in one of the interview form, that it is interesting to discuss Problem : There are two nodes given in a tree(not binary tree). Find whether one node is parent/grand parent of other. order should be O(1). You are allowed to do any amount of preprocessing -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Interesting Algo for counting set bits in a number
This is the very efficient code for counting set bits. I am not able
to understand whats the algo/logic behind it. I tried running this
code, it gives correct output but don't know why and how?
Could anybody explain the logic with generic example?
int NumberOfSetBits(int i)
{
i = i - ((i 1) 0x);
i = (i 0x) + ((i 2) 0x);
return ((i + (i 4) 0xF0F0F0F) * 0x1010101) 24;
}
I am sorry for posting this C code here and many of you might not be
in touch with C. I would be happy to explain if any of the C related
stuff is troubling you in this question.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: sort the LL
Separate the ascending and descending lists. lets say ascending lists are l1,l2,l3 and l4 and descending lists are l5,l6,l7. Reverse all these descending list.(reverse(l5),reverse(l6) and reverse(l7)) Now keep on merging all these 7 sorted lists two at a time. Its of ~o(n)time and o(1)space -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Maintaining frequency of millions of user
We have a server hit by millions of users. Sever log files contains the user ids of all of them. How do we find the frequency of login of each user. What will the most efficient way to store the users, and access them to find their frequency(The log files are very huge!!) I thought of using B+ tree indexing with user ids as the key. Leaf nodes will have the pointers to bucket of user ids. One item of bucket will contain user id and frequency of this user. For insertion, search complexity will be ~O(logn) Any potential problem with approach? Are there any better approach to tackle this problem? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Kth element in BST without static/global variable or function argument
How to print the kth smallest element in Binary search tree without using any static/global variable. You can’t pass the value k to any function also. What comes to my mind is: Have an array which will contain the inorder traversal of binary search tree. Let the user input k and return kth element in array. Any non-trivial approach? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Maintaining frequency of millions of user
@Rohit. Fibonacci heap will not give optimal search performance for user id and corresponding frequency. I assume that heap will have user id as the key. If I want to search for some specific user id's and its frequency, worst case complexity is going to be O(n). Surely Insertion in O(1) will be a plus. Is there something else in your mind? On Dec 9, 4:31 pm, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @mayur: surely it would not be just for finding frequency. It's a server which may have to do insert/delete operation. A web server will have lot's of things to do and this is just a tiny part. I guess WORM is not apt for this... In general, a web server will have to maintain a queue or something similar. Rohit Saraf Sophomore Computer Science and Engineering IIT Bombay On Wed, Dec 9, 2009 at 4:49 PM, Mayur mayurhem...@gmail.com wrote: We have a server hit by millions of users. Sever log files contains the user ids of all of them. How do we find the frequency of login of each user. What will the most efficient way to store the users, and access them to find their frequency(The log files are very huge!!) I thought of using B+ tree indexing with user ids as the key. Leaf nodes will have the pointers to bucket of user ids. One item of bucket will contain user id and frequency of this user. For insertion, search complexity will be ~O(logn) Any potential problem with approach? Are there any better approach to tackle this problem? Not problems really, but opportunities. Here're a few things: 1. They're append-only (no inserts, no deletes). Why then have a B+ tree on the log file itself, which is a structure optimized for both retrieval and inserts? 2. If all that you want to query is the frequency of login of each user, one might ask the following questions: i) How often do you want this frequency data? Is the data required to be updated in real-time? ii) Is it okay to query this data each time your log's rotated? If you require the data as and when it's created (meaning as soon as it is logged), it may be a good idea to change the application receiving the call to explicitly update the frequency, in say, a database. On the other hand, if you want it periodically, you can simply run a script/program that takes the old size of the log file as input, and begins scanning the log from that offset, thus saving you time. The frequency data itself can be stored in a hash file / b+ tree or whatever else you'd like (so that it can be updated). If you still wish to index your log files, search for Write-Once Read-Many (WORM) data structures on the web. Apologies for the non-algorithmic nature of my response, if it isn't apt for the group. On Wed, Dec 9, 2009 at 3:54 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: if you don't know abt fibonacci heaps then check out http://en.wikipedia.org/wiki/Fibonacci_heap Rohit Saraf Sophomore Computer Science and Engineering IIT Bombay -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Y shaped linklist
Correct. It will not be exactly one traversal of each list. More precisely, in worst case each pointer will traverse one list completely and then another list from beginning to intersection point. On Oct 11, 12:49 pm, ankur aggarwal ankur.mast@gmail.com wrote: *...@manisha one traversal for each of the lists * --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: optimum algo for second largest
First find out the largest element and it requires n-1 comparison. Lets say we have 8 elements then we need 7 comparison to decide largest. Imagine the tree structure that you will use to find out largest. 21 15 21 9 15 8 21 2 9 11 15 7 89 21 Notice that second largest will be be smaller than largest and larger than any other item in the list. So it is sure that second largest will loose in comparison with largest. Hence Second largest will be searched only with the items that got compared with largest item. Number of items that got compared with largest is logn(height of tree). logn-1 comparison is needed to find largest among them. Total comparison to find second largest = (n-1) + (logn-1) On Oct 10, 11:52 pm, sankalp sankalpmishr...@gmail.com wrote: can anyone give me algorithm for finding the second largest element in array using tournament method requiring n+logn-2 compariso --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Y shaped linklist
@sandeep notice that solution given on the given link doesn't satisfy the conditions given in the above question. @sharad Both lists may have duplicate values. So in this case it will better to hash the address of node instead of values. One other way is to maintain a flag in each of the node. In the begining flag will be 0 for all the items in both list. While traversing the first list, set the flags to 1. While traversing the seconds list,look for the item for which flag has been set. But this will also take additional o(n) space. I was thinking in line of reversing the first list while traversing it (it will use recursion). However, I couldn't make it work. Any thoughts? On Oct 10, 3:02 am, sandeep jain jainsandee...@gmail.com wrote: Here is one solutionhttp://geeksforgeeks.org/?p=2405 On Fri, Oct 9, 2009 at 9:00 AM, sharad kumar aryansmit3...@gmail.comwrote: space comp O(n) time o(2n) both in terms of worst case On Fri, Oct 9, 2009 at 8:46 PM, ankur aggarwal ankur.mast@gmail.comwrote: @sharad wat about space ?? extra space ? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Interesting array multiplication problem
There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n). --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Find the Grid row containing all 1's except intersection point in constant time
There is a n x n grid of 1's and 0's. Find the i, where i is the row containing all 1's, except the intersection point. Should do it in less than 25 comparisons? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Y shaped linklist
One other way will be using two pointers. step1) Take two pointers(p1 and p2 ), pointing to the beginning of list L1 and L2. step2) Now start moving both the pointers simultaneously and check whether they point to same node. If not, then move both pointers to next node. Step3) If any of pointer becomes NULL then set it to the beginning of another list. Lets say p1 becomes NULL, then set p1 to point to L2. Step4) Repeat the step2 After two traversals, both pointers will surely meet at intersection point. On Oct 10, 3:24 pm, Manisha pgo...@gmail.com wrote: @sandeep notice that solution given on the given link doesn't satisfy the conditions given in the above question. @sharad Both lists may have duplicate values. So in this case it will better to hash the address of node instead of values. One other way is to maintain a flag in each of the node. In the begining flag will be 0 for all the items in both list. While traversing the first list, set the flags to 1. While traversing the seconds list,look for the item for which flag has been set. But this will also take additional o(n) space. I was thinking in line of reversing the first list while traversing it (it will use recursion). However, I couldn't make it work. Any thoughts? On Oct 10, 3:02 am, sandeep jain jainsandee...@gmail.com wrote: Here is one solutionhttp://geeksforgeeks.org/?p=2405 On Fri, Oct 9, 2009 at 9:00 AM, sharad kumar aryansmit3...@gmail.comwrote: space comp O(n) time o(2n) both in terms of worst case On Fri, Oct 9, 2009 at 8:46 PM, ankur aggarwal ankur.mast@gmail.comwrote: @sharad wat about space ?? extra space ? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find the Grid row containing all 1's except intersection point in constant time
By intersection point, I mean intersection of ith row and ith coulmn. For instance, 1 0 0 1 1 1 1 1 0 Here the answer should be 3 as 3rd row contain all 1's except(3,3). On Oct 10, 9:15 pm, Ramaswamy R ramaswam...@gmail.com wrote: Whats with the intersection point? Intersection of what two things are we talking about here? Row of 1s and column of 1s? On Sat, Oct 10, 2009 at 3:47 AM, Manisha pgo...@gmail.com wrote: There is a n x n grid of 1's and 0's. Find the i, where i is the row containing all 1's, except the intersection point. Should do it in less than 25 comparisons? -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Design a stack to perform push(), pop() and retrieve minimum in constant time.
@harit Maintaining only one data member, minimum will not suffice. As we may call min() any number of time and every time it should return the minimum of all data members. @sharad Thanks for direction. In your implementation, stack.top() and stack.pop() are going to return same value. So min() and pop() will return the same value that is not correct. Lets say we have to push 2 items in stack , 2 5 respectively. It will be maintained as, 2 2 5 5 Now min() will return 2 but pop() will also return 2. While pop() must return 5. I guess, little variation of your code will work fine. I will work it out. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Design a stack to perform push(), pop() and retrieve minimum in constant time.
@harit o..Got it now. Thanks a lot for detailed explanation. On Oct 8, 4:15 pm, harit agarwal agarwalha...@gmail.com wrote: @manisha i think u didn't get my point every time it will return the different value ex values to be pushed 6,5,10,3,9,1 now push(a,b) a=element b=minimum value pushed till now (6,6) (6,6),(5,5) (6,6),(5,5),(10,5) (6,6),(5,5),(10,5),(3,3) (6,6),(5,5),(10,5),(3,3),(9,3) (6,6),(5,5),(10,5),(3,3),(9,3),(1,1) now start popping (1,1) min in stack=1 (9,3) min in stack =3 similarly last (6,6) min in stack=6 so everytime u get min in O(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 -~--~~~~--~~--~--~---
[algogeeks] Design a stack to perform push(), pop() and retrieve minimum in constant time.
I found this question in a interview blog. http://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html Question No. 19 My understanding for retrieve minimum in constant time is, we should be able to find the minimum element in stack and to remove (pop) it in constant time. Correct me if I am wrong. My idea is to maintain a sorted linked list of items so that we can return the minimum and delete it from linked list in o(1) time. Push operation: Whenever a new items come, I will find the correct location for this new item in the sorted linked list and insert this item in linked list. Now I will take the address of this linked list item and push it on stack. Pop operation: I will take the linked list item address stored at stack[tos]. As I have address, I can delete the node from linked list as well. Retrieving minimum: Return the first item from the sorted linked list. o(1) But for popping this item address from stack, I need to reorganize the complete stack. It will have o(n) time and space complexity. Is there any way to improve it or other ways of solving 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Traversing a binary tree from bottom to top
Thanks a Ton everybody! --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Traversing a binary tree from bottom to top
Traversing a binary tree from bottom to top The only way I could think of is: Traverse the binary tree from top to bottom, level by level with the help of queue. For a tree like: a b c d e g The Queue will be something like: a b c d e g Now de-queue the element one be one from queue and push on stack. Pop the stack one by one to get deserved output: g e d c b a This will take o(n) space and o(n)time. Is there any better way of doing 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 -~--~~~~--~~--~--~---
