Re: [algogeeks] Print binary tree in spiral
I've done this before with a deque although I don't remember the implementation details off my head. Since a deque allow insertion and removal at both ends what we need to do is decide which end we starting consuming node and which end we add the queues of the next level. For every level we maintain the count of nodes to be processes. Every time this count hits zero we reverse the direction from which we process / add nodes. This is just a simple extension of using queue for doing a BFS traversal. This method would have the same complexity as would BFS using a queue. The above method does not incur any addition overhead. Swamy On Tue, Nov 17, 2009 at 6:35 PM, Nayn nayanish.hi...@gmail.com wrote: Hi guys, Recently I came across a problem. We've to display a binary tree in spiral. 1. We need to print the nodes in BFS manner. 2. The nodes should be displayed in alternate direction; in one level from left to right and in next level right to left. Needless to mention, we need least time complex solution. Thanks Nayn -- 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=. -- 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 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 the Grid row containing all 1's except intersection point in constant time
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: Find the Grid row containing all 1's except intersection point in constant time
On another thought, constant time complexity would not be possible with no constraints on the size of the matrix or any limitation on what possible data it would have. It wouldn't be possible to do it in 25 comparisons for a 1 Million x 1 Million grid. If there is no restriction on the data as well then we would be forced to scan through (in whatever way) all the n^2 values. 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.
The basic idea would be to do push / pop the minimum in stack along with the push / pop elements. It is like maintaining a parallel stack of minimums. A naive implementation would involve two stacks. All operations should be O(1) time complexity. On Tue, Oct 6, 2009 at 1:31 PM, Manisha pgo...@gmail.com wrote: 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? -- 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: Array Repeated Element O(n)
Use a bit-field of M bits to keep track of the presence of X..X+M-1. We can do 2^32/M passes (if the elements are 32-bit size) to check for numbers in a range. Depending on the memory footprint and speed the app would want we can find a soft spot for X. On Sun, Oct 4, 2009 at 9:39 PM, Amit Chandak me.amitchan...@gmail.comwrote: Hi Friends, Given an array in which all the elements are unique except one element which occurs 'twice'. How can we find this repeated element in O(n) time and constant space? Regards, Amit. -- 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: Traversing a binary tree from bottom to top
We could do in O(log n) space and O(nlog n) time complexity. Traverse once to find the maximum depth d ~= log n keeping track of the trail upto root (just as with any recursive traversal). Then traverse d times but visit nodes at depth d, d-1 ... 1 in each traversal. We could optimize the implementation (such as not traversing node below those at the depth we are processing) but the complexity will remain. If the tree nodes had parent pointer (or sibling pointers) then we can traverse with O(1) space complexity. But asking for such a pointer is by itself asking for O(n) space. On Fri, Oct 2, 2009 at 7:07 AM, Manisha pgo...@gmail.com wrote: 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? -- 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: Form of 3^n
Can we evaluate the logarithm any more efficiently that repeated division by 3? On Tue, Sep 22, 2009 at 12:27 PM, Dave dave_and_da...@juno.com wrote: You could compute the logarithm of the number to the base 3 and see if the result is an integer. Dave On Sep 21, 12:22 pm, Anshya Aggarwal anshya.aggar...@gmail.com wrote: how to find that whether the given number was of the form 3^n. ( i.e. 3 to the power n). one way is to recursively divide the number by 3 and check the remainder. Is there any other way using bit manipulation or anything else?? -- Anshya Aggarwal -- 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: What algorithm can be used to decide the denomination of notes in an ATM machine?
I don't quite get the if possible clause.
But here is what we can do. Have an array C[i] with counts correspondint to
denominations in D[i] (ordered).
From the lowest denomination assign 1 of each until the total doesn't exceed
the required amount. Once that is done, from the highest denomination (that
was assigned) to the lowest keep incrementing the count until the total
doesn't exceed the required amount.
On Mon, Sep 21, 2009 at 3:40 AM, Nagendra Kumar nagendra@gmail.comwrote:
idea is to give note of each denomination at least once (if possible).
On Mon, Sep 21, 2009 at 10:59 AM, Shishir Mittal
1987.shis...@gmail.comwrote:
Let the denominations be D[] = {1000,500,100},
and amount be N.
Let C[] , denotes the count of each denomination.
for ( i=0 ; i 2 ; i++) {
C[i] = (N-1)/D[i] ;
N = N - D[i]*C[i] ;
}
C[2] = N/D[2] ;
For N=4800, C[] = {4, 1, 8}
For N= 2000, C[] = {1, 1, 5}, as required.
Nice observation :) .
PS: Its the Newton who appreciated the falling apple. There aren't many
who really appreciate the happenings from our normal life. [?]
On Sat, Sep 19, 2009 at 11:50 PM, eSKay catchyouraak...@gmail.comwrote:
for example: if I draw 2000, what I get is
1000+500+100+100+100+100+100.
What algorithm can be used to decide how to break up the entered
amount?
--
Shishir Mittal
Ph: +91 9936 180 121
--
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
-~--~~~~--~~--~--~---
inline: 329.gif
[algogeeks] Re: max product of any three nos in an array of signed integers
Agreed finding the largest is O(n). Finding the largest k will be O(n log k). Just coz we don't have loops it doesn't mean the op is O(1). Product of largest 3 does not guarantee largest product! (Take for e.g. -10, 5, 0, -20, 8. The max product is 1600, not 0. On Wed, Sep 16, 2009 at 2:48 AM, Prashant prashant.r.k...@gmail.com wrote: hi all, i think we can use kth smallest algorithm (from cormen book) to find three largest numbers from given and multiplication of these number will leads to max product. time complexity will be 3*O(n) 3-for finding three largest numbers O(n)-time complexity of Kth Smallest algorithm On Wed, Sep 16, 2009 at 3:11 PM, manish bhatia mb_mani...@yahoo.comwrote: This one is better than what I suggested before. Doable in O(n)! On Sep 13, 10:10 pm, Dave dave_and_da...@juno.com wrote: The following assumest that n = 5. Find the 3 largest positive numbers and the two largest-in-magnitude negative numbers (i.e., the two smallest signed numbers). If there are not two negative numbers, the 3 largest positive numbers are the answer. Otherwise, if there are only one or two positive numbers, the largest positive number and the two largest-in-magnitude negative numbers are the answer. Otherwise, compare the product of the three largest positive numbers with the product of the largest positive number and the two largest-in- magnitude negative numbers. The answer is whichever set produces the largest product. If the product of the answer set is zero, the answer will not be uniquely determined. This can be done in O(n) time and O(1) extra space. Dave On Sep 13, 8:34 am, SP Praveen praveen.sel...@gmail.com wrote: Given an array of integers (signed integers), find three numbers in that array which form the maximum product. -- Keep up with people you care about with Yahoo! India Mail. Learn howhttp://in.rd.yahoo.com/tagline_galaxy_1/*http://in.overview.mail.yahoo.com/connectmore . -- Prashant Kulkarni -- 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: Z[n^2]={such that z belongs to X+Y
I am not sure if constant space requirement is possible. But we can do it
with O(k) space complexity.
Maintain a max heap of k elements. For each of the n*m sums add it to the
heap (if it ain't full with k elements) or replace the root and heapify if
the sum is lesser than the root.
Finally the root will have the k'th smallest sum.
But this would require O(n*m*log k) time complexity.
On Sat, Sep 5, 2009 at 5:10 AM, ankur aggarwal ankur.mast@gmail.comwrote:
@dufus..
if there is constant space requirement then ??
wat will be your soln ??
On Sat, Sep 5, 2009 at 12:35 PM, Dufus rahul.dev.si...@gmail.com wrote:
It seems EXTRACT_MIN for Z[n^2] can be done in O(n) time.
http://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pdfhttp://lyle.smu.edu/%7Esaad/courses/cse3358/ps5/problemset5sol.pdf
Then using it we can find the kth smallest element in O(nk) time.
_dufus
On Sep 4, 10:03 pm, ankur aggarwal ankur.mast@gmail.com wrote:
Find nth smallest inO(n) Given two arrays of length n in sorted order
X[n] Y[n].
Now make another array Z[n^2]={such that z belongs to X+Y}.
AS all possible sum of x+y is there in Z. You have to give the nth
smallest
no of Z in O(n) time.
Space complexity : No bound on it. But try to optimize it if possible.
--
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: Z[n^2]={such that z belongs to X+Y
Extracting the smallest from the young tableau takes O(1) and and restoring
its properties takes O(m+n) (where m n and the number of rows and
columns). This is much like extracting the max from a max-heap. So
extracting the kth element would be k*O(n+m) ~ k*O(2n) (when m=n as in this
problem) ~ O(k * n).
On Mon, Sep 14, 2009 at 11:19 PM, Anil C R cr.a...@gmail.com wrote:
@dufus
if extracting the kth smallest element would tske O(kn) then extracing the
nth element would take O(n^2) right?
On 9/14/09, Ramaswamy R ramaswam...@gmail.com wrote:
I am not sure if constant space requirement is possible. But we can do it
with O(k) space complexity.
Maintain a max heap of k elements. For each of the n*m sums add it to the
heap (if it ain't full with k elements) or replace the root and heapify if
the sum is lesser than the root.
Finally the root will have the k'th smallest sum.
But this would require O(n*m*log k) time complexity.
On Sat, Sep 5, 2009 at 5:10 AM, ankur aggarwal
ankur.mast@gmail.comwrote:
@dufus..
if there is constant space requirement then ??
wat will be your soln ??
On Sat, Sep 5, 2009 at 12:35 PM, Dufus rahul.dev.si...@gmail.comwrote:
It seems EXTRACT_MIN for Z[n^2] can be done in O(n) time.
http://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pdfhttp://lyle.smu.edu/%7Esaad/courses/cse3358/ps5/problemset5sol.pdf
Then using it we can find the kth smallest element in O(nk) time.
_dufus
On Sep 4, 10:03 pm, ankur aggarwal ankur.mast@gmail.com wrote:
Find nth smallest inO(n) Given two arrays of length n in sorted order
X[n] Y[n].
Now make another array Z[n^2]={such that z belongs to X+Y}.
AS all possible sum of x+y is there in Z. You have to give the nth
smallest
no of Z in O(n) time.
Space complexity : No bound on it. But try to optimize it if possible.
--
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
--
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: max product of any three nos in an array of signed integers
Still incomplete. In summary we go in the following order 1) Positive product (3 largest positives or largest positive and 2 smallest negative numbers) 2) ZERO 3) Negative product (3 largest negatives or largest negative and 2 smallest positive) I am not sure if we can find the largest k of n numbers of O(n) for the simple reason that we'd have to maintain sorted list of k elements. If the list exhibits O(1) insertion then we can do each insertion with O(log k) complexity. We would be able to do the same using max heap (for finding smallest k element) or min heap (for finding greatest k elements). Not writing a loop and maintaining k locals would entail the same complexity if not more. @Dufus: Does your approach find k largest / smallest elements in O(n) time and O(1) space complexity? On Mon, Sep 14, 2009 at 10:49 AM, Ramaswamy R ramaswam...@gmail.com wrote: We probably missed just one case here. All numbers being negative, in which case the ans would be the product of the greatest 3 negative numbers. On Sun, Sep 13, 2009 at 10:10 AM, Dave dave_and_da...@juno.com wrote: The following assumest that n = 5. Find the 3 largest positive numbers and the two largest-in-magnitude negative numbers (i.e., the two smallest signed numbers). If there are not two negative numbers, the 3 largest positive numbers are the answer. Otherwise, if there are only one or two positive numbers, the largest positive number and the two largest-in-magnitude negative numbers are the answer. Otherwise, compare the product of the three largest positive numbers with the product of the largest positive number and the two largest-in- magnitude negative numbers. The answer is whichever set produces the largest product. If the product of the answer set is zero, the answer will not be uniquely determined. This can be done in O(n) time and O(1) extra space. Dave On Sep 13, 8:34 am, SP Praveen praveen.sel...@gmail.com wrote: Given an array of integers (signed integers), find three numbers in that array which form the maximum product. -- 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 -- 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: Z[n^2]={such that z belongs to X+Y
The order does not matter! When you keep feeding a max heap with N values (replacing the root and heapifying if the value is smaller than root) in this case the sums, you end up with the least k sums encountered. And the root would be the kth sum in increasing order. We feel all n*m values and order doesn't matter. Only, this algo doesn't take advantage of the sorted property of the 2 inut arrays. On Mon, Sep 14, 2009 at 11:16 PM, ankur aggarwal ankur.mast@gmail.comwrote: *For each of the n*m sums add it to the heap (if it ain't full with k elements) or replace the root and heapify if the sum is lesser than the root.* how u can judge which is the next value to be added.. try your algo at array a 1 2 3 4 5 7 9 and array b 2 3 5 6 7 -- 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: max product of any three nos in an array of signed integers
We probably missed just one case here. All numbers being negative, in which case the ans would be the product of the greatest 3 negative numbers. On Sun, Sep 13, 2009 at 10:10 AM, Dave dave_and_da...@juno.com wrote: The following assumest that n = 5. Find the 3 largest positive numbers and the two largest-in-magnitude negative numbers (i.e., the two smallest signed numbers). If there are not two negative numbers, the 3 largest positive numbers are the answer. Otherwise, if there are only one or two positive numbers, the largest positive number and the two largest-in-magnitude negative numbers are the answer. Otherwise, compare the product of the three largest positive numbers with the product of the largest positive number and the two largest-in- magnitude negative numbers. The answer is whichever set produces the largest product. If the product of the answer set is zero, the answer will not be uniquely determined. This can be done in O(n) time and O(1) extra space. Dave On Sep 13, 8:34 am, SP Praveen praveen.sel...@gmail.com wrote: Given an array of integers (signed integers), find three numbers in that array which form the maximum product. -- 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: random number...
Generate the random number 7 times. Sum them all and divide by 5. Theoritically it should be evenly distributed over 1-7. But owing to random number generators characteristics the sum of rand(5) called 7 times may not be perfectly evenly distributed over 1-7. A nice discussion on some neat options is available here - http://stackoverflow.com/questions/137783/given-a-function-which-produces-a-random-integer-in-the-range-1-to-5-write-a-fun Rejection technique is pretty standard for this and yet simple. On Mon, Sep 7, 2009 at 8:56 AM, ankur aggarwal ankur.mast@gmail.comwrote: Given a random number generator that generates numbers in the range 1 to 5, how can u create a random number generator to generate numbers in the range 1 to 7. (remember that the generated random numbers should follow a uniform distribution in the corresponding range) -- 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: n balls having k colors
If you have just two colors then this is possible in O(N). But since the problem says K colors, this would effectively be sorting of K numbers. If K is limited (N) then we could use counting sort and such algo's to do it in near O(N) (with O(K) storage as well). If K can be unlimited and the input size can be HUGE then we rather resort to one of the in-place sort in O(N log N) complexity. On Sun, Sep 6, 2009 at 1:06 AM, ankur aggarwal ankur.mast@gmail.comwrote: You have N balls having one of K colors. Arrange them into groups of same colors. e.g. RRGRG can be arranged as RRRGG (Answer) GGRRR -- 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: possible in logn
What was I thinking! It has the same problem as before. *g*.
AFA I can see this can't be done in log N. Even if we split the problem
space into two we would still have to inspect each to its guts.
On Wed, Sep 2, 2009 at 7:32 PM, ankur aggarwal ankur.mast@gmail.comwrote:
@rama
then this ques cannot be solved in log n
as
i made only 1 change in the whole array of sorted millions number
1,2,3,4,5,6,...,1,10010,1001,110001...
how will u do that ..
On Wed, Sep 2, 2009 at 11:50 PM, Ramaswamy R ramaswam...@gmail.comwrote:
On Tue, Sep 1, 2009 at 5:58 AM, ankur aggarwal
ankur.mast@gmail.comwrote:
it is a jus a try
i=1,j=2;
while (a[i]a[j])
{
j=i;
i=i*2;
}
now we have i and j and we know that in between these indexes we have a
point z (n as u say) where
Not necessarily. The problem only states that the 1st n elements are
sorted. Not that the the 1st n elements are the least of those in the array.
So if every element at even location is greater than the previous, then
the n need not fall withing [i, j].
a[z-1]a[z]
and a[z][z+1]
now apply the abive procedure between i and j
(its like binary search)
eg we have m=50 and let n=24 (we dont know this value)
then for i=16 and j=32 this condition will break ..
now apply this logic in between 16 and 32.
if u find z(or say n) then we can find x easily..
i think i made my logic clear..
comment plz .
--
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
--
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: possible in logn
It is possible. This will be a binary search as well. Only instead of matching the value with the mid value you'd check the following bool c1 = array[left] array[mid] bool c2 = array[mid] array[right] if both the conditions are true then, then the entire range is sorted if c1 is true and c2 is NOT true, then search for it in mid-right range else search for it in left - mid Just like in binary search we'd reduce the problem space by 2 in every step resulting in O(log N) complexity. On Mon, Aug 31, 2009 at 9:18 AM, shashi @mnnit shashikantkoshta1...@gmail.com wrote: there is an array with m elements... it is known that first n elements are sorted... but dont know what is 'n' nm given an element x find whether x is there in sorted elements. Can this be done in O(log n)?? -- 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: possible in logn
On Tue, Sep 1, 2009 at 5:58 AM, ankur aggarwal ankur.mast@gmail.comwrote:
it is a jus a try
i=1,j=2;
while (a[i]a[j])
{
j=i;
i=i*2;
}
now we have i and j and we know that in between these indexes we have a
point z (n as u say) where
Not necessarily. The problem only states that the 1st n elements are sorted.
Not that the the 1st n elements are the least of those in the array.
So if every element at even location is greater than the previous, then the
n need not fall withing [i, j].
a[z-1]a[z]
and a[z][z+1]
now apply the abive procedure between i and j
(its like binary search)
eg we have m=50 and let n=24 (we dont know this value)
then for i=16 and j=32 this condition will break ..
now apply this logic in between 16 and 32.
if u find z(or say n) then we can find x easily..
i think i made my logic clear..
comment plz .
--
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: minimum difference.
Brute force, pick all combinations and keep track of minimum difference. Complexity: O(n^2) - (n-1)+(n-2)+(n-3) ... 1 A little better, use any of the O(nlog n) sorting algorithm. In O(n) compare adjacent pairs and find the minimum difference. Complexity O(nlog n). On Tue, Sep 1, 2009 at 6:05 AM, ankur aggarwal ankur.mast@gmail.comwrote: given a array of length n. find 2 number such that their differnce is minimum. -- 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: N-Ary Tree and Resource management
To begin with I find the invariant doesn't hold in the system progressively. Forget about islock and assume that we only do lock / unlock. Given that a node cannot be locked if any of its descendants / ancestors is locked. It is never possible for the tree to enter a state where any of the descendant of a locked node is locked. If that invariant holds then all we need to check is if any of the ancestors are locked, which is O(log n). O(1) would either require hash table (and O(n) storage) unless we choose to replicate the lock state in all of the ancestors as well (which is a pretty ugly solution considering what unlock would have to do). If we can supplement the tree node with a lock status and pointer to child (only used while unlocking) which is locked we should be able to do it all in the asked for complexities :). Ugly but possible. Of course there is an O(n) extra storage. On Sat, Aug 29, 2009 at 11:05 AM, nagendra kumar nagendra@gmail.comwrote: Given a n-ary tree of resources arranged hierarchically. A process needs to lock a resource node in order to use it. But, A node cannot be locked if any of its descendant or ancestor is locked. I was supposed to - write the structure of node - write codes for - islock()- returns true if a given node is locked and false if it is not - lock()- locks the given node if possible and updates lock information - unlock()- unlocks the node and updates information. Codes should be : Islock –O(1) Lock()- O(log n) unLock()- O(log n) -- 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: N-Ary Tree and Resource management
When we talk of a binary search tree having O(log n) complexity for search, that does assume that the tree is fairly balanced. And of course the that fact we talk of average case. For any tree the worst case would be at least O(n). The whole advantage of using a tree in the 1st place lies in the fact that operations can be done in O(log n) in average case. I don't know of any algo that can do it in O(log n) worst case! :) On Sun, Aug 30, 2009 at 5:05 PM, Dave dave_and_da...@juno.com wrote: When you say that checking if any of the ancestors is O(n log n) are you assuming that the tree is balanced? It wouldn't be O(n log n) if the tree degenerates into a linked list, would it? So what is your justification in assuming balance? Dave On Aug 30, 6:01 pm, Ramaswamy R ramaswam...@gmail.com wrote: To begin with I find the invariant doesn't hold in the system progressively. Forget about islock and assume that we only do lock / unlock. Given that a node cannot be locked if any of its descendants / ancestors is locked. It is never possible for the tree to enter a state where any of the descendant of a locked node is locked. If that invariant holds then all we need to check is if any of the ancestors are locked, which is O(log n). O(1) would either require hash table (and O(n) storage) unless we choose to replicate the lock state in all of the ancestors as well (which is a pretty ugly solution considering what unlock would have to do). If we can supplement the tree node with a lock status and pointer to child (only used while unlocking) which is locked we should be able to do it all in the asked for complexities :). Ugly but possible. Of course there is an O(n) extra storage. On Sat, Aug 29, 2009 at 11:05 AM, nagendra kumar nagendra@gmail.com wrote: Given a n-ary tree of resources arranged hierarchically. A process needs to lock a resource node in order to use it. But, A node cannot be locked if any of its descendant or ancestor is locked. I was supposed to - write the structure of node - write codes for - islock()- returns true if a given node is locked and false if it is not - lock()- locks the given node if possible and updates lock information - unlock()- unlocks the node and updates information. Codes should be : Islock –O(1) Lock()- O(log n) unLock()- O(log n) -- 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- Hide quoted text - - Show quoted text - -- 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: Algo to find all the possible subsets in a set
The following will generate an output like this - 0
0 1
0 1 2
0 1 2 3
0 1 3
0 2 3
0 3
1
1 2
1 2 3
1 3
2
2 3
3
using these indices you can generate from any given set.
class SetGenerator
{
public:
SetGenerator(size_t length)
: LENGTH(length)
{ indices.reserve(length);}
const vectorsize_t generate_set()
{
if ( indices.empty() )
indices.push_back(0);
else if ( (LENGTH - 1) == indices[0])
{
indices.clear();
}
else
{
if ( LENGTH != (indices.back() + 1) )
{
indices.push_back(indices.back() + 1);
}
else
{
if ( (LENGTH-1) == ++indices.at(indices.size() - 2) || 2
== indices.size() )
indices.pop_back();
}
}
return indices;
}
private:
const size_tLENGTH;
vectorsize_t indices;
};
...
SetGenerator gen(5);
do
{
const vectorsize_t idxs = gen.generate_set();
if ( idxs.empty() )
break;
copy(idxs.begin(), idxs.end(), ostream_iteratorsize_t(cout, ));
cout'\n';
} while( true );
On Wed, Aug 26, 2009 at 12:20 PM, AKS abhijeet.k.s...@gmail.com wrote:
Hello fellas,
i am lookin for an algorithm to find all the possible subsets in a
given set
So, if the Set is say, A={a,b,c} omit the null set
o/p: --- {a} {b} {c} {a,b} {b,c} {a,c} {a,b,c} omit the
null set
regards,
Abhijeet
--
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: Algo to find all the possible subsets in a set
You just gt generate this pattern of indices into the set - 0 0 1 0 1 2 0 1 2 3 0 1 3 0 2 3 0 3 1 1 2 1 2 3 1 3 2 2 3 3 just figure out the conditions to generate the above yourself ... and you'll figure out what the code does On Wed, Aug 26, 2009 at 10:01 PM, Abhijeet Kumar abhijeet.k.s...@gmail.comwrote: can i have the algorithm only in plain simple english rather than havin the whole code ??? it ll be really helpful if u tell me the logic -- 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: Find SquareRoot of a number
Bisection and Newton raphson method are a couple of simple way to do it.You can check up for these on any book on numerical methods. On Mon, Feb 9, 2009 at 9:42 AM, rakesh sathu rakesh2...@gmail.com wrote: Can anybody help me for writing code in 'c'-language to find the square root of a number? Plz dont suggest me to use 'sqrt()' function -- Thank you, Rakesh Reddy.S -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://ramaswamy.r.googlepages.com --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: find the output
bottomline - bad code!
The pointer returned by modify() is not guranteed (although it may depending
on compiler implementation) to hold good as the local array goes out of
scope once the function returns!
The output of the 2nd printf is undefined.
On Mon, Jan 5, 2009 at 1:18 PM, tania hamid tan3...@gmail.com wrote:
Plz indicate the output of the following code and explain why is it so..
*char *modify (char *s)
{
#define MAX 15
char buffer[MAX];
strcpy (buffer, s);
buffer[0] = 'H';
return buffer;
}
int
main ()
{
printf (hello!!!);
printf (%s , modify (hello!!!));
}*
--
Yesterday is History.
Tomorrow is a Mystery.
Today is a Gift! That is why it is called the Present :).
http://ramaswamy.r.googlepages.com
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Traversing Doubly Linked N-Tree
Use Depth first search or Breath First Search. As long as it not a graph a
recursive algorithm in either should work easy. If not you'd have to
maintain visited nodes by some means.
If order is not of concern then DFS should be easier. BFS would require
maintaining nodes to be visited although it shouldn't be a major overhead
with just 20-25 nodes.
Cheerios
Ramaswamy
On Wed, Aug 27, 2008 at 5:52 AM, Pavo [EMAIL PROTECTED] wrote:
Hi,
I am trying to traverse a doubly linked n-tree, where n is 4. One node
has 4 neighbors say East, West, South and North, they are doubly
linked. For e.g. one node's east linked node has information that its
west link is the former. I need to traverse this tree by visiting each
node only once. How will the algorithm for this look like? For my
application it will have only maximum of around 20 to 25 nodes, so
recursive algorithms are not a problem.
Please help, any response greatly appreciated.
I have an algorithm (its in C/C++), but not seems to a concise one, if
you are interested its at the end of this mail.
Thanks,
Kannan
void PrintNodes( Node n )
{
coutn.valendl;
if( n.e != NULL )
PrintENodes( *(n.e) );
if( n.s != NULL )
PrintSNodes( *(n.s) );
if( n.w != NULL )
PrintWNodes( *(n.w) );
if( n.n != NULL )
PrintNNodes( *(n.n) );
}
//No West links are traversed here
void PrintENodes( Node n )
{
coutn.valendl;
if( n.e != NULL )
PrintENodes( *(n.e) );
if( n.s != NULL )
PrintSNodes( *(n.s) );
if( n.n != NULL )
PrintNNodes( *(n.n) );
}
//No North links are traversed here
void PrintSNodes( Node n )
{
coutn.valendl;
if( n.s != NULL )
PrintSNodes( *(n.s) );
if( n.w != NULL )
PrintWNodes( *(n.w) );
if( n.e != NULL )
PrintENodes( *(n.e) );
}
//No East links are traversed here
void PrintWNodes( Node n )
{
coutn.valendl;
if( n.w != NULL )
PrintWNodes( *(n.w) );
if( n.n != NULL )
PrintNNodes( *(n.n) );
if( n.s != NULL )
PrintSNodes( *(n.s) );
}
//No South links are traversed here
void PrintNNodes( Node n )
{
coutn.valendl;
if( n.n != NULL )
PrintNNodes( *(n.n) );
if( n.e != NULL )
PrintENodes( *(n.e) );
if( n.w != NULL )
PrintWNodes( *(n.w) );
--
Yesterday is History.
Tomorrow is a Mystery.
Today is a Gift! That is why it is called the Present :).
http://ramaswamy.r.googlepages.com
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: In-place Counting Sort
Counting sort doesn't work that way. The algo inherently requires O(N) storage for the counting array which effectively makes the algorithm running time O(N). If the range of values were known before hand, then the counting array would be of fixed size thus catering to what you need. But if the range of value is unknown and the algo determines it before sorting, then I believe we'r out of luck. Cheerios Ramaswamy On 8/30/07, Ravi [EMAIL PROTECTED] wrote: How to modify counting sort so that it sorts the elements in place, i.e. using extra amount of memory that is constant and independent of the size of the input. -- Its wierd, but sometime you find things that are more important to you than things you think that are important. You know what I mean? Maybe its just getting older ;) http://ramaswamy.r.googlepages.com --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Help! - rectangle packing problem
I am not sure of a solution for this, but ain't this an NP-complete problem? On 6/19/07, ihinayana [EMAIL PROTECTED] wrote: Description: Given a group of rectangles with different integer width and height,such as 5*4, 2*3,1*7,etc. The total number of rectangles is like 10 or more.The problem is how to find a bigger rectangle with a minimal area which can hold all those given ones. To fix them in,those rectangles can be rotated with 90 degree and the order is regardless. Did anybody solve a similar problem? -- Chaos is the rule in nature, not an exception http://ramaswamy.r.googlepages.com --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: geometry problem
On 6/14/07, Monu Rathour [EMAIL PROTECTED] wrote: There are some rectangles and some pin-vertices's in a two dimensional plane. I have to join pin-vertices's such that lines are rectilinear and line should not cross over the rectangles. How to write a mathematical formula for calculating path length ? If the two points can be connected by lines taking only two fixed directions alternately, then the distance b/w them is the sum of the distances of the x coordinate and y coordinate. This can be easily understood by considering a chess board and trying to reach from lower-left to upper-right only moving up/right :). This can be verified by starting with a line that directly connects the two and for every intersection with rectangles break the line into two or more. But if the lines could be winding (with U shapes) then I guess it gets more complex and you'd have to determine the individual segments and then evaluate the distance. Still thinking to find an easier means to quantify this :-?. Cheerios Ramaswamy -- Chaos is the rule in nature, not an exception http://ramaswamy.r.googlepages.com --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: reversing strings using array
Write a function strrev(char *str) to reverse the contents of a string
in-place (in case you aint't supposed to use the library function).
//--
void strreverse(char* str)
{
char* end = str;
while( '\0' != *end )
++end;
--end;
while( str end )
{
char temp = *str;
*str = *end;
*end = temp;
++str;
--end;
}
}
//--
Call this function on the entire string. This will ensure that the spaces
are in their correct locations.
Then keep a char pointer to a start of the word and another pointer for the
end of the word (a space / null). Replace the end with null and call strrev
on the pointer that represents the start location. Replace the null with the
original end character. Voila.
//--
void reverse_words(char* str)
{
strreverse(str);
char *wstart = str, *wend, cache;
do
{
wend = wstart;
while( ' ' != *wend '\0' != *wend )
++wend;
cache = *wend;
*wend = '\0';
{
strreverse(wstart);
}
*wend = cache;
if ( '\0' == cache )
break;
else
wstart = wend + 1;
} while( 1 );
}
//--
Hope this helps.
Cheerios
On 6/16/07, Misty [EMAIL PROTECTED] wrote:
Hello friends,
i want 2 know how to write a program to reverse strings for instance a
string is hello world, i need to print it as world hello. please post
your answers as soon as possible.
--
Chaos is the rule in nature, not an exception
http://ramaswamy.r.googlepages.com
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
