[algogeeks] Maximum size binary search tree
Find the maximum size Binary search tree in a binary tree?? -- 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] Maximum number of collinear points
In a plane given n points (x1,y1) (x2,y2)(xn,yn), find the the maximum number of collinear points. -- 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] Next higher element
Design a data structure to find the next higher element for each element in an array. For e.g. if array is 1 2 3 4 5 8 6 o/p should be (element) (next higher element) 1 2 2 3 3 4 4 5 5 8 8 nothing 6 nothing The array need not be sorted. Constraints-O(n) time complexity -- 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] triplets summing to zero
Given a list of n integers?(negative and positive), not sorted and duplicates allowed, you have to output the triplets which sum upto 0. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: 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.
[algogeeks] Re: Swap the bits
Manisha, this is not the desired result. -- Dave On Jun 23, 6:26 am, manisha nandal manisha04.nan...@gmail.com wrote: 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.
[algogeeks] Maximum subset of cuboid boxes
Given a lot of cuboid boxes with different length, breadth and height. We need to find the maximum subset which can fit into each other. For example: If Box 1 has LBH as 7 8 9 If Box 2 has LBH as 5 6 8 If Box 3 has LBH as 5 8 7 If Box 4 has LBH as 4 4 4 then answer is 1,2,4 A box can fit into another only and only if all dimensions of that is less than the bigger box.Rotation of boxes is not possible. My approach: Constructing trees... Box 1 dim: 7,8,9 Make it as root1. The root also has a counter associated with it. Now count1=1. Then Box 2 dim: 5,6,8 7,8,9. Make it as a left child of root1 and count1=2. Box 3 dim: 5,8,7 doesn't fit in any and hence make it a tree by itself i.e root2 its count2=1. Box 4 dim: 4,4,4 it can be made as the left child of box 2 as well as Box 3. count1=3, count2=2. Print the reverse inorder traversal of the highest counter valued tree. Please correct me if I'm wrong. -- 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] 23 candies among 7 kids
it is 29! / 23! -- 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] Next higher element
hi the number should be just next higher element or any higher element like if my arr is like arr= 2 5 1 3 7 6 the next higher element for 5 should be what (7 or 6 ) because 6 is more closer to 7 but 7 comes first in arr On Wed, Jun 23, 2010 at 11:18 AM, Raj N rajn...@gmail.com wrote: Design a data structure to find the next higher element for each element in an array. For e.g. if array is 1 2 3 4 5 8 6 o/p should be (element) (next higher element) 1 2 2 3 3 4 4 5 5 8 8 nothing 6 nothing The array need not be sorted. Constraints-O(n) time complexity -- 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. -- Kumar Vishal StAy HunGrY , StAy fOOlisH Contact No:- 09560193839 -- 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] Max(Xor (X([i],X[j]))
Given a list of numbers , How to find the max(x[i] XOR x[j]) in the list. Any solution less than O(n^2)? -- 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: There is an array of odd and even numbers. Now, sort them in such a way that the top portion of the array contains odd numbers, bottom portion contains even numbers
Why not just change the definition of when one number is bigger than another and do normal sort ? I guess that is better and simpler. Normal sort takes O(n log n), while Anurag's algo is O(n). Regards, Jagadish http://www.cse.iitb.ac.in/~jagadish On Jun 20, 2:18 pm, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Why not just change the definition of when one number is bigger than another and do normal sort ? I guess that is better and simpler. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 20, 2010 at 7:52 AM, Anurag Sharma anuragvic...@gmail.comwrote: Keep 2 pointers 'start' and 'end' and make them point to start and beginning of the array. Now keep decresing *end* pointer until an odd element is found Keep increasing the *start* pointer until an even element is found swap the elements at start and end Continue the above 3 steps till startend Now the start/end points to a border element which divides the array in 2 parts, 1st have having all odd numbers and 2nd half with all even numbers. Now use any inplace sorting algorithm to sort in descending order the portion containing all odd numbers and in increasing order the portion containing all even numbers. Hope its clear. Anurag Sharma On Sun, Jun 20, 2010 at 2:15 AM, vijay auvija...@gmail.com wrote: There is an array of odd and even numbers. Now, sort them in such a way that the top portion of the array contains odd numbers, bottom portion contains even numbers. The odd numbers are to be sorted in descending order and the even numbers in ascending order. You are not allowed to use any extra array and it has to use a conventional sorting mechanism and should not do any pre or post processing -- 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] getting smallest 1 million numbers....
Given a set of 1 Trillion integers on hard disk, find the smallest 1 million of them. You can fit at most 1 million integers in memory at a time. State the fastest solution you can think of. -- 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] Where to Set the POST-OFFICE
There are N points on a LINE. U neeed to place a post office such that its total distance from each of the N points is minimised. The post office need not necessarily be on one of the N Points. -- 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] linked list
if we dont want to change original list.. is there ny efficient method for that? On 23 June 2010 06:49, ANUJ KUMAR kumar.anuj...@gmail.com wrote: reverse one of the linked lists in O(n) time and then see if the resulting one is same as the other one On Wed, Jun 23, 2010 at 1:56 AM, divya sweetdivya@gmail.com wrote: Two link lists are given ...check if one is reverse of other. Do it without using 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 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] Find the next number for a given number without using any arithmetic operators(use bit operations)
Find the next number for a given number without using any arithmetic operators(use bit operations) -- 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] linked list
this is same as finding palindrome in a given linked list.. it may help http://geeksforgeeks.org/?p=1072 On Wed, Jun 23, 2010 at 6:00 PM, divya jain sweetdivya@gmail.comwrote: if we dont want to change original list.. is there ny efficient method for that? On 23 June 2010 06:49, ANUJ KUMAR kumar.anuj...@gmail.com wrote: reverse one of the linked lists in O(n) time and then see if the resulting one is same as the other one On Wed, Jun 23, 2010 at 1:56 AM, divya sweetdivya@gmail.com wrote: Two link lists are given ...check if one is reverse of other. Do it without using 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 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: no of bits
@Dave I tried your logic on 15 it got converted to 10, 4, 4,4. But still
could not understand the logic could you please explain?
On Tue, Jun 22, 2010 at 9:34 PM, Dave dave_and_da...@juno.com wrote:
Did you actually try the code by hand on a number to see what it does?
If you do, you will see that the first statement replaces the bits in
each pair of bit positions with the number of bits in those positions.
The second adds the bits in each pair of pairs, replacing each nibble
with the number of bits originally set in that nibble. Etc.
Dave
On Jun 22, 10:54 am, divya jain sweetdivya@gmail.com wrote:
@ dave
how did u come to this formula... m nt getting the logic..
@ sathaiah
yes u r rite
On 22 June 2010 19:32, chitta koushik koushik.infin...@gmail.com
wrote:
For more such problems and solns
http://graphics.stanford.edu/~seander/bithacks.htmlhttp://graphics.stanford.edu/%7Eseander/bithacks.html
http://graphics.stanford.edu/%7Eseander/bithacks.html
for (c = 0; v; c++)
{
v = v - 1; // clear the least significant bit set
}
O(k) -- no. of bits set in the number
--Koushik C
On Tue, Jun 22, 2010 at 7:16 PM, Dave dave_and_da...@juno.com wrote:
Assuming 32 bit integers:
n = ((x 1) 0x) + (x 0x)
n = ((n 2) 0x) + (n % 0x)
n = ((n 4) 0x0F0F0F0F) + (n 0x0F0F0F0F)
n = ((n 8) 0x00FF00FF) + (n 0x00FF00FF)
n = ((n 16) 0x) + (n 0x)
n now is the number of bits set in x. Time is O(1).
Dave
On Jun 22, 6:26 am, divya sweetdivya@gmail.com wrote:
find the no. of bits set in a no. in logn time
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@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 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: There is an array of odd and even numbers. Now, sort them in such a way that the top portion of the array contains odd numbers, bottom portion contains even numbers
No, Jagadish. You missed the statement Now use any inplace sorting algorithm in Anurag's posting, which makes his algorithm also O(n log n), and both Anurag and you missed the statement should not do any pre or post processing. Dave On Jun 23, 8:52 am, Jagadish M jagadis...@gmail.com wrote: Why not just change the definition of when one number is bigger than another and do normal sort ? I guess that is better and simpler. Normal sort takes O(n log n), while Anurag's algo is O(n). Regards, Jagadishhttp://www.cse.iitb.ac.in/~jagadish On Jun 20, 2:18 pm, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Why not just change the definition of when one number is bigger than another and do normal sort ? I guess that is better and simpler. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 20, 2010 at 7:52 AM, Anurag Sharma anuragvic...@gmail.comwrote: Keep 2 pointers 'start' and 'end' and make them point to start and beginning of the array. Now keep decresing *end* pointer until an odd element is found Keep increasing the *start* pointer until an even element is found swap the elements at start and end Continue the above 3 steps till startend Now the start/end points to a border element which divides the array in 2 parts, 1st have having all odd numbers and 2nd half with all even numbers. Now use any inplace sorting algorithm to sort in descending order the portion containing all odd numbers and in increasing order the portion containing all even numbers. Hope its clear. Anurag Sharma On Sun, Jun 20, 2010 at 2:15 AM, vijay auvija...@gmail.com wrote: There is an array of odd and even numbers. Now, sort them in such a way that the top portion of the array contains odd numbers, bottom portion contains even numbers. The odd numbers are to be sorted in descending order and the even numbers in ascending order. You are not allowed to use any extra array and it has to use a conventional sorting mechanism and should not do any pre or post processing -- 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.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: check divisibility
In step 3, if n m, then n can be written in the form i * 2^k + j, where i 0 and 0 = j = m. Then, step 3 replaces n by i + j. Note that (i * 2^k + j) - (i + j) = i * (2^k - 1) = i * m. Therefore, the step replaces any number greater than m by a small number that differs from it by a multiple of m. Thus, if the original number is divisible by m, the sequence of smaller numbers produced by the algorithm will also be divisible by m, and conversely, if the original number is not divisible by m, the smaller numbers also will not be divisible by m. Dave On Jun 23, 1:33 pm, Anand anandut2...@gmail.com wrote: @Dave Logic is good. could not understand how does it works. Could you please explain On Tue, Jun 22, 2010 at 9:16 PM, Dave dave_and_da...@juno.com wrote: Let m = 2^k - 1. To check divisibility of n by m, 1. If n is zero, return true. 2. If n is negative, replace n with -n. 3. While n m, replace n with (n k) + (n m). 4. Return (n == m). This is equivalent to the casting out nines algorithm to determine if a number is a multiple of 9. Dave On Jun 22, 3:37 pm, divya sweetdivya@gmail.com wrote: u are given any binary no.. u have to check its divisbility by 3,7,15, 31..(any no. of the form 2^x-1) .u cant use any division and modulo operator for that. -- 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.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
