Re: [algogeeks] BST Question
@nishaanth: wat if the left child of the right node has a negative value On Thu, Oct 14, 2010 at 11:12 AM, nishaanth nishaant...@gmail.com wrote: Just see the value of the node at every point, if it is greater than zero dont recurse the right sub-tree, as simple as it is.print the node u inspected if it is less than zero. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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. -- By B. Praveen -- 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: Least fare for a return trip Algorithm
@Dave 1. should it not be O(k + klogk) ?? 2. but u are not considering all the possible values... let k =3 like i. a1+b1 ii. min( a1+b2, a2+b1) upto these fine one of them will be chosen ...either ia or ib will increase. iii. but know we have to take remaining of step ii in to consideration along with a1+b3,a3+b1,a2+b3,a3+b2 ... On Fri, Oct 15, 2010 at 8:20 PM, Dave dave_and_da...@juno.com wrote: @Coolfrog$: You don't have to sort the arrays. You only have to find the k smallest elements in each and sort those k entries. This can be done in O(n + k log k). Algorithm: find the smallest k elements of A and sort them into ascending order. find the smallest k elements of B and sort them into ascending order. ia = 1 ib = 1 output ia, ib, A(ia)+B(ib) for n = 1 to k do if A(ia + 1) + B(ib) A(ia) + B(ib + 1) then ia = ia + 1 else ib = ib + 1 end if output ia, ib, A(ia)+B(ib) end for Complexity O(n + k log k). Dave On Oct 15, 4:00 am, coolfrog$ dixit.coolfrog.div...@gmail.com wrote: @amod as given A-B andB-A are in sorted form...if not sort them in O(n log n). then first suggestion A1+B1 second suggestion MIN( A1+B2 , B1+A2) === let it be B1+A2 third suggestion MIN( A1+B2 , A1+B3, A3+B1,A2+B3, A3+B2) let it be A2+B3 and so on... @Dave what will be complexity of above solution...? i think O(n log n) for sorting and second part (suggestions) O(n).. Guys do correct me plz... On Thu, Oct 14, 2010 at 11:10 AM, Amod gam...@gmail.com wrote: @Dave You are partly correct. If i ask for four minimum fares for the round trip then first suggestion is what u said : sum the sum of the minimum cost from A to B and the minimum cost from B to A after that we have to see which combination from both costs, sums up least On Oct 14, 9:55 am, Dave dave_and_da...@juno.com wrote: @Amod. Isn't the minimum sum the sum of the minimum cost from A to B and the minimum cost from B to A? What am I missing? Dave On Oct 13, 11:06 pm, Amod gam...@gmail.com wrote: Hi I think I forgot to mention that the SUM of the ROUND trip i.e. A-B-A (sum = going + returning) should be least. Please don't take into account any other thing like time and availability. So solution is not that straightforward. Its like we have two arrays and we have to return least k sum from the given arrays where we take one element from the first and one from second in the sum. Cheers Amod On Oct 13, 2:26 pm, Shiyam code_for_life mailshyamh...@gmail.com wrote: When a user wants to choose to fly from A to B, suggest the flight with lowest fare that's available, here its A1, if A1 is busy then A2 and so on Repeat the same for B to A. Am I missing something here? Complexity is O( (number of flights from A to B) + number of flights from B to A) ) Cheers 'Coding is an art'- 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 algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Divesh* (¨`·.·´¨) Always `·.¸(¨`·.·´¨ ) Keep (¨`·.·´¨)¸.·´Smiling! `·.¸.·´ Life can give u 100's of reason 2cry,but u can give life 1000's of reasons 2Smile- 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. -- *Divesh* (¨`·.·´¨) Always `·.¸(¨`·.·´¨ ) Keep (¨`·.·´¨)¸.·´Smiling! `·.¸.·´ Life can give u 100's of reason 2cry,but u can give life 1000's of reasons 2Smile -- 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] MS
Given a text file, implement a solution to find out if a pattern similar to wild cards can be detected. for example find if a*b*cd*, or *win or *def* exists in the text. how to take care of wild cards? -- Harshal Choudhary -- 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: Least fare for a return trip Algorithm
@Coolfrog$: 1. No. It should be O(n + k log k) because finding the kth smallest element of an array of size n is O(n), using the Median of Medians algorithm; see http://en.wikipedia.org/wiki/Median_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm. 2. Assuming that the entries in A are distinct and so are the entries in B, we can handle the equality of sums case: find the smallest k elements of A and sort them into ascending order. find the smallest k elements of B and sort them into ascending order. ia = 1 ib = 1 output ia, ib, A(ia)+B(ib) for n = 1 to k do if A(ia + 1) + B(ib) A(ia) + B(ib + 1) then ia = ia + 1 output ia, ib, A(ia)+B(ib) else if A(ia + 1) + B(ib) A(ia) + B(ib + 1) then ib = ib + 1 output ia, ib, A(ia)+B(ib) else // equality case ia = ia + 1 ib = ib + 1 output ia-1, ib, A(ia-1)+B(ib) output ia, ib-1, A(ia)+B(ib-1) end if end for Dave On Oct 16, 6:20 am, coolfrog$ dixit.coolfrog.div...@gmail.com wrote: @Dave 1. should it not be O(k + klogk) ?? 2. but u are not considering all the possible values... let k =3 like i. a1+b1 ii. min( a1+b2, a2+b1) upto these fine one of them will be chosen ...either ia or ib will increase. iii. but know we have to take remaining of step ii in to consideration along with a1+b3,a3+b1,a2+b3,a3+b2 ... On Fri, Oct 15, 2010 at 8:20 PM, Dave dave_and_da...@juno.com wrote: @Coolfrog$: You don't have to sort the arrays. You only have to find the k smallest elements in each and sort those k entries. This can be done in O(n + k log k). Algorithm: find the smallest k elements of A and sort them into ascending order. find the smallest k elements of B and sort them into ascending order. ia = 1 ib = 1 output ia, ib, A(ia)+B(ib) for n = 1 to k do if A(ia + 1) + B(ib) A(ia) + B(ib + 1) then ia = ia + 1 else ib = ib + 1 end if output ia, ib, A(ia)+B(ib) end for Complexity O(n + k log k). Dave On Oct 15, 4:00 am, coolfrog$ dixit.coolfrog.div...@gmail.com wrote: @amod as given A-B and B-A are in sorted form...if not sort them in O(n log n). then first suggestion A1+B1 second suggestion MIN( A1+B2 , B1+A2) === let it be B1+A2 third suggestion MIN( A1+B2 , A1+B3, A3+B1,A2+B3, A3+B2) let it be A2+B3 and so on... @Dave what will be complexity of above solution...? i think O(n log n) for sorting and second part (suggestions) O(n).. Guys do correct me plz... On Thu, Oct 14, 2010 at 11:10 AM, Amod gam...@gmail.com wrote: @Dave You are partly correct. If i ask for four minimum fares for the round trip then first suggestion is what u said : sum the sum of the minimum cost from A to B and the minimum cost from B to A after that we have to see which combination from both costs, sums up least On Oct 14, 9:55 am, Dave dave_and_da...@juno.com wrote: @Amod. Isn't the minimum sum the sum of the minimum cost from A to B and the minimum cost from B to A? What am I missing? Dave On Oct 13, 11:06 pm, Amod gam...@gmail.com wrote: Hi I think I forgot to mention that the SUM of the ROUND trip i.e. A-B-A (sum = going + returning) should be least. Please don't take into account any other thing like time and availability. So solution is not that straightforward. Its like we have two arrays and we have to return least k sum from the given arrays where we take one element from the first and one from second in the sum. Cheers Amod On Oct 13, 2:26 pm, Shiyam code_for_life mailshyamh...@gmail.com wrote: When a user wants to choose to fly from A to B, suggest the flight with lowest fare that's available, here its A1, if A1 is busy then A2 and so on Repeat the same for B to A. Am I missing something here? Complexity is O( (number of flights from A to B) + number of flights from B to A) ) Cheers 'Coding is an art'- 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 algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Divesh* (¨`·.·´¨) Always `·.¸(¨`·.·´¨ ) Keep (¨`·.·´¨)¸.·´Smiling! `·.¸.·´ Life can give u 100's of reason 2cry,but u can give life 1000's of reasons 2Smile- Hide quoted text - - Show quoted text - -- You received this
Re: [algogeeks] Re: BiasedRandom fron unbiasedRandom.
@snehal...a simple way to do it is.. create an array of lets say 1000... fill in 1000* p elements with 0 and the rem with 1 now use rand() and generate the index..and return arr[index] On Fri, Oct 8, 2010 at 8:49 PM, Dave dave_and_da...@juno.com wrote: @Snehal: If p has a finite binary representation, of say n bits, then generate a sequence of up to n unbiased random numbers, continuing the sequence as long as the ith random number agrees with the ith bit to the right of the binary point. When the ith number disagrees with the ith bit, return that ith number. If the computation continues until even the nth number matches the nth bit, then start over. Example: Suppose that the binary representation of p is 0.101101. If the first unbiased random number is 1, generate the second number. If the second number is 0, continue to the third number. If the third number is 0, return 0. If p does not have a finite binary representation, e.g., if p = 1/3 or sqrt(1/2) and you are not using a finite precision floating point representation, then the algorithm will terminate with probability 1. Dave On Oct 8, 2:44 am, snehal jain learner@gmail.com wrote: Given a unbiased function that generates 0 and 1 with equal probability write a function biasedrandom that genreates 0 with probability p and 1 with probability 1-p. -- 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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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] MS
Hi Harshal, The question is a bit unclear, especially given the *win and *def* pattern. Does it mean anything before win is acceptable or anything before and after def is acceptable? or is it like 'a' repeated any number of times followed by 'b' repeated any number of times... in a*b*cd*? I am assuming the pattern match has to looking for any character wherever '*' is given. Thats the first one I mentioned above. The solution to the second kind will be a little more involved. This is how I would think of implementing it: we should have a list of wildcards we support, suppose for now we support only '*' 1. The search string can be called our query. 2. the query can be splitted into substrings whereever a wild card appears. special cases include it appears in beginning and end. 3. we need to find the splitted strings, if they appear in the same order in the as they appear in the query for doing this we could have an array of the substrings and the indexes at which they appear in the text, if the indexes of appearances are in ascending order we know the substrings exist. the index of appearance of first and last substring might be needed in the final response if we need to tell where exactly the string appears. For now this will be able to handle only one occurrence of the pattern and can be reformed to include more than one occurrences. 4. our next step includes matching to see if they fit as per our wild cards. for * in beginning the of query the start index of the response could be the beginning of the text similarly for end it could be the end of text given step 3 returned a positive response, i.e substrings exist in order. if other wildcards are involved we can think of checking the behaviour differently. If we assume '*' means repetition of the previous char given: 1. we will have to start the parse the text along with the query. 2. looking for the first char (having a * in beginning doesnt make sense in this case) in the query in the text. if there is a wild card, we look for the wild card behavior in the text, repetition, etc.wherever the behavior seems to end we look ahead in the query to see which is the character after the wild card in the query if it matches with the character in text we move further on the query and text or reset the query parse pointer to point to beginning of query string. if the second character is not a wild card, we just do a match and move forward if we find it in text or reset query parsing pointer. 3. in the end if the query matches the text at any place we can fill the response start and end pointers. for multiple occurrences if we havent reached end of file we can reset query pointer and start finding the complete match again. ** cases like a*ab*c may not be handled by this. -V On Sat, Oct 16, 2010 at 6:21 PM, Harshal hc4...@gmail.com wrote: Given a text file, implement a solution to find out if a pattern similar to wild cards can be detected. for example find if a*b*cd*, or *win or *def* exists in the text. how to take care of wild cards? -- Harshal Choudhary -- 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: Least fare for a return trip Algorithm
@Dave input: k=3 AB 16 37 69 output should be (1,1,7), (1,2,8), (2,1,9) im getting output form above code (1,1,7) (2,1,9) (3,1,12) Dave i am still learning algorithms .. so if i am wrong.. don't be annoyed plz thankyou in advance... take care.. On Sat, Oct 16, 2010 at 6:21 PM, Dave dave_and_da...@juno.com wrote: @Coolfrog$: 1. No. It should be O(n + k log k) because finding the kth smallest element of an array of size n is O(n), using the Median of Medians algorithm; see http://en.wikipedia.org/wiki/Median_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm . 2. Assuming that the entries in A are distinct and so are the entries in B, we can handle the equality of sums case: find the smallest k elements of A and sort them into ascending order. find the smallest k elements of B and sort them into ascending order. ia = 1 ib = 1 output ia, ib, A(ia)+B(ib) for n = 1 to k do if A(ia + 1) + B(ib) A(ia) + B(ib + 1) then ia = ia + 1 output ia, ib, A(ia)+B(ib) else if A(ia + 1) + B(ib) A(ia) + B(ib + 1) then ib = ib + 1 output ia, ib, A(ia)+B(ib) else // equality case ia = ia + 1 ib = ib + 1 output ia-1, ib, A(ia-1)+B(ib) output ia, ib-1, A(ia)+B(ib-1) end if end for Dave On Oct 16, 6:20 am, coolfrog$ dixit.coolfrog.div...@gmail.com wrote: @Dave 1. should it not be O(k + klogk) ?? 2. but u are not considering all the possible values... let k =3 like i. a1+b1 ii. min( a1+b2, a2+b1) upto these fine one of them will be chosen ...either ia or ib will increase. iii. but know we have to take remaining of step ii in to consideration along with a1+b3,a3+b1,a2+b3,a3+b2 ... On Fri, Oct 15, 2010 at 8:20 PM, Dave dave_and_da...@juno.com wrote: @Coolfrog$: You don't have to sort the arrays. You only have to find the k smallest elements in each and sort those k entries. This can be done in O(n + k log k). Algorithm: find the smallest k elements of A and sort them into ascending order. find the smallest k elements of B and sort them into ascending order. ia = 1 ib = 1 output ia, ib, A(ia)+B(ib) for n = 1 to k do if A(ia + 1) + B(ib) A(ia) + B(ib + 1) then ia = ia + 1 else ib = ib + 1 end if output ia, ib, A(ia)+B(ib) end for Complexity O(n + k log k). Dave On Oct 15, 4:00 am, coolfrog$ dixit.coolfrog.div...@gmail.com wrote: @amod as given A-B andB-A are in sorted form...if not sort them in O(n log n). then first suggestion A1+B1 second suggestion MIN( A1+B2 , B1+A2) === let it be B1+A2 third suggestion MIN( A1+B2 , A1+B3, A3+B1,A2+B3, A3+B2) let it be A2+B3 and so on... @Dave what will be complexity of above solution...? i think O(n log n) for sorting and second part (suggestions) O(n).. Guys do correct me plz... On Thu, Oct 14, 2010 at 11:10 AM, Amod gam...@gmail.com wrote: @Dave You are partly correct. If i ask for four minimum fares for the round trip then first suggestion is what u said : sum the sum of the minimum cost from A to B and the minimum cost from B to A after that we have to see which combination from both costs, sums up least On Oct 14, 9:55 am, Dave dave_and_da...@juno.com wrote: @Amod. Isn't the minimum sum the sum of the minimum cost from A to B and the minimum cost from B to A? What am I missing? Dave On Oct 13, 11:06 pm, Amod gam...@gmail.com wrote: Hi I think I forgot to mention that the SUM of the ROUND trip i.e. A-B-A (sum = going + returning) should be least. Please don't take into account any other thing like time and availability. So solution is not that straightforward. Its like we have two arrays and we have to return least k sum from the given arrays where we take one element from the first and one from second in the sum. Cheers Amod On Oct 13, 2:26 pm, Shiyam code_for_life mailshyamh...@gmail.com wrote: When a user wants to choose to fly from A to B, suggest the flight with lowest fare that's available, here its A1, if A1 is busy then A2 and so on Repeat the same for B to A. Am I missing something here? Complexity is O( (number of flights from A to B) + number of flights from B to A) ) Cheers 'Coding is an art'- 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
[algogeeks] Re: Modify Queue Data Structure which returns min in O(1) time.
Suppose you have a stack data structure which has additional operation findMin() - returns smallest element on the stack. This can be easily updated in O(1) while pushing new element onto the stack. It is known that queue DS can be simulated by using two stacks (here we use stacks which have findMin routine). From this point we are able to retrieve smallest element from the queue in O(1). On 13 окт, 22:22, malli mallesh...@gmail.com wrote: A queue data structure has functions enqueue(int x) ( inserts element in right end), dequeue() ( deletes element from left end) functions. These operations take O(1) time. Modify this queue data structure, so that it supports findmin() which returns minimum element of stack in O(1) 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: google
Keep priority queue of pairs - sum and respective indices in the
arrays.
Start from pair (a[0] + b[0], (0, 0)).
while (queue is not empty n 0) {
retrieve largest sum from the queue, (sum, (i, j))
add sum to the result array
--n;
add pairs (a[i + 1] + b[j], (i + 1, j)) and (a[i] + b[j + 1], (i, j
+ 1)) if it is possible due the boundings;
}
The additional care should be taken to avoid processing pair of
indices twice.
On 14 окт, 11:55, Harshal hc4...@gmail.com wrote:
Given two sorted postive integer arrays A[n] and B[n] (W.L.O.G, let's
say they are decreasingly sorted), we define a set S = {(a,b) | a \in A
and b \in B}. Obviously there are n^2 elements in S. The value of such
a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs
from S with largest values. The tricky part is that we need an O(n)
algorithm.
--
Harshal Choudhary,
III Year B.Tech Undergraduate,
Computer Engineering Department,
National Institute of Technology Surathkal, Karnataka
India.
--
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] MS
thanks for a detailed approach to the solution. :) - Harshal -- 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] Algorithm to determine the largest number of envelopes that can be nested inside one another.
ya...finding the longest subsequence is the simplest method...and its nlogn.. It works...it similar to box stacking problem On Fri, Oct 1, 2010 at 6:00 AM, adit.sh...@gmail.com adit.sh...@gmail.comwrote: The problem here is more about finding the most optimal solution and not just solution. Rgds Adi -Original Message- From: Sathaiah Dontula Sent: 29/09/2010, 09:25 To: algogeeks@googlegroups.com Subject: Re: [algogeeks] Algorithm to determine the largest number of envelopes that can be nested inside one another. I think we can do like this, 1. Sort all the xi's in ascending order - nlog(n) 2. Then find the longest increasing sequence of yi's - nlog(n) 3. complexity will be nlog(n). Thanks, Sathaiah Dontula On Tue, Sep 28, 2010 at 11:37 PM, Prashant Kulkarni prashant.r.k...@gmail.com wrote: i think it is similar to finding max in a list O(n) or sorting algorithm O(n log n) -- Prashant Kulkarni On Tue, Sep 28, 2010 at 11:33 PM, Rahul Singal rahulsinga...@gmail.com wrote: A possible solution i can think is create a directed graph where each vertex is a envelope and edges are from a bigger envelope to smaller envelope ( one which can fit in bigger envelope ) . Now the problem is reduce to finding longest path in the graph . Regards Rahul -- 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.comalgogeeks%252bunsubscr...@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.comalgogeeks%252bunsubscr...@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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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: google
like i said before, draw a table w/ x=a and y=b
come out w/ the matrix and you would see a patten
30 29 4 3 2 1
30 60 59 34 33 32 31
29 59 58 33 32 31 30
434 338 7 6 5
333 327 6 5 4
232 316 5 4 3
131 305 4 3 2
you start from a[0] and b[0], compare them, take the bigger one, set
the smaller one(for next iteration) and set a limit.
for instance, in this case, either one works. let's say a[0] is
bigger, the limit will be a[1]+b[0]. limit is always the element next
to the bigger one in array, plus the biggest in another array.
you loop through a[0]+b[i] where i=0 to length of b. stop when the
outcome is less than limit.
now you take what is stored(the smaller one) to start the next
iteration(steps above)
On Oct 15, 7:56 pm, Gene gene.ress...@gmail.com wrote:
Hi Arun. Last time we discussed this problem I came up with the same
idea. Unfortunately it doesn't work. The problem is that in order
for the merge to be correct, each pair of pointers must be
guarenteed to produce sums that are in non-increasing order. They
don't. For example, if you run your program with
int a[N] = { 1, 2, 3, 4,29,30};
int b[N] = { 1, 2, 3, 4,29,30};
It will produce
(30,30)= 60 (30,29)= 59 (29,30)= 59 (30,4)= 34 (4,30)= 34
(30,3)= 33
This is wrong because the 4th pair should be (29,29) = 58.
In fact, niether here nor in the previous discussion did we ever get a
correct solution.
If you figure it out, please post.
On Oct 14, 5:54 am, arun raghavendar arun.s...@gmail.com wrote:
Start merging A and B from the tail end for N elements, just like the way
you would do it for a merge sort but with a different constraint based on
the sum a[i] and b[i]
This should work for any value of N, I just hard-coded it for simplicity.
#includestdio.h
#define N 6
struct OutputType {
int a;
int b;
int value;
};
int main() {
int a[N] = {1,8,13,24,25,30};
int b[N] = {5,6,17,28,29,29};
struct OutputType s[N];
int i, a_candidate_1 = N-1, a_candidate_2=N-2, b_candidate_1=N-1,
b_candidate_2=N-2;
s[0].a = a[N-1];
s[0].b = b[N-1];
s[0].value = a[N-1] + b[N-1];
for (i=1;iN;i++) {
if ((a[a_candidate_1]+b[b_candidate_2]) =
(a[a_candidate_2]+b[b_candidate_1])) {
s[i].a = a[a_candidate_1];
s[i].b = b[b_candidate_2];
s[i].value = a[a_candidate_1]+b[b_candidate_2];
b_candidate_2--;
if (b_candidate_2 0) { a_candidate_1--; }
} else {
s[i].a = a[a_candidate_2];
s[i].b = b[b_candidate_1];
s[i].value = a[a_candidate_2]+b[b_candidate_1];
a_candidate_2--;
if (a_candidate_2 0) { b_candidate_1--; }
}
}
for (i=0;iN;i++) printf((%d,%d)=%3d , s[i].a, s[i].b,
s[i].value);
return 0;
}
-Arun
On Thu, Oct 14, 2010 at 1:25 PM, Harshal hc4...@gmail.com wrote:
Given two sorted postive integer arrays A[n] and B[n] (W.L.O.G, let's
say they are decreasingly sorted), we define a set S = {(a,b) | a \in A
and b \in B}. Obviously there are n^2 elements in S. The value of such
a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs
from S with largest values. The tricky part is that we need an O(n)
algorithm.
--
Harshal Choudhary,
III Year B.Tech Undergraduate,
Computer Engineering Department,
National Institute of Technology Surathkal, Karnataka
India.
--
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: Duplicate in an array
@Mukesh what's not known? in the problem, it stated an array of positive numbers On Oct 6, 11:47 am, Mukesh Gupta mukeshgupta.2...@gmail.com wrote: @Ankit: Insertion in hashmap in O(n) in worst case. As long as range of the numbers is not known we cannot predict whether the algo will run in linear time. Any other idea for O(n)?? Mukesh Gupta Delhi College of Engineering On Wed, Oct 6, 2010 at 4:32 PM, sourav souravs...@gmail.com wrote: @Mukesh Thanks for your attempt. But the question asks for liner or sublinear solution. Sourav On Oct 6, 3:50 pm, Mukesh Gupta mukeshgupta.2...@gmail.com wrote: Keep inserting elements in a binary search tree and break once you get the find the element in the tree. Complexity=O(n log n) On 10/5/10, sourav souravs...@gmail.com wrote: You are given an array of positive numbers in which one number is repeated. Rest all are present only once. Find the duplicate number in linear or sub linear 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 . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mukesh Gupta Delhi College of Engineering -- 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: Duplicate in an array
@nishaanth hashing=O(n^2)? what kinda of hashing are we talking about? array w/ range of the numbers? you meant smallest and the biggest? so you have to scan through the given numbers first to find the range. if you scanned, why not find the duplication in the first place? okay, lets say you are given the smallest and the biggest. 4 and 44, you would have an array size that's more than the size of given numbers. what if the given set is 1, 100, 1? On Oct 15, 12:53 pm, nishaanth nishaant...@gmail.com wrote: @ankit and lingerdave How does hashing help here ?? i say we have to create an array size which is there range of the numbers...else it cant be solved in O(n) Hashing is not helpful here in worst case hashing may lead to a O(n2) solution as all the keys may hash into the same place eg.. 4,14,24,34,44,4 if h(n)= n mod 100 On Sun, Oct 10, 2010 at 5:51 PM, Mridul Malpani malpanimri...@gmail.comwrote: can this problem be solved in O(n) time and in O(1) space? On Oct 6, 10:41 pm, ligerdave david.c...@gmail.com wrote: @mukesh, nope, you do not need to know the range. are you thinking about array? ankit's solution is the implementation of bucket logic. On Oct 6, 11:47 am, Mukesh Gupta mukeshgupta.2...@gmail.com wrote: @Ankit: Insertion in hashmap in O(n) in worst case. As long as range of the numbers is not known we cannot predict whether the algo will run in linear time. Any other idea for O(n)?? Mukesh Gupta Delhi College of Engineering On Wed, Oct 6, 2010 at 4:32 PM, sourav souravs...@gmail.com wrote: @Mukesh Thanks for your attempt. But the question asks for liner or sublinear solution. Sourav On Oct 6, 3:50 pm, Mukesh Gupta mukeshgupta.2...@gmail.com wrote: Keep inserting elements in a binary search tree and break once you get the find the element in the tree. Complexity=O(n log n) On 10/5/10, sourav souravs...@gmail.com wrote: You are given an array of positive numbers in which one number is repeated. Rest all are present only once. Find the duplicate number in linear or sub linear 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. -- Mukesh Gupta Delhi College of Engineering -- 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 . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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: linked lists
@Snehal...wat ligerdave says is have ptr1 for list1 and ptr2 for list2. if(ptr1-data==ptr2-data)increment both ptr1 and ptr2 else reset ptr2 to the head of list2 , increment ptr1 ptr2 position gives from where we need to concatenate. On Sat, Oct 9, 2010 at 12:21 AM, ashita dadlani ash@gmail.com wrote: I think we can use KMP string matching algorithm. On Fri, Oct 8, 2010 at 6:40 PM, shashank jain shashankg...@gmail.comwrote: there are 2 unsorted array we have to want a third array in sorted form in mininmum time complexicity answer can like be this merge the two array in 3rd array then sort the array or sort the individual array and then merge if feel first one is better can any one can help On 10/8/10, snehal jain learner@gmail.com wrote: @ligerdave m nt getting ur algo..can u explain with an example On 10/8/10, snehal jain learner@gmail.com wrote: @neeraj ur worst case complexity will be O(mn) On 10/8/10, snehal jain learner@gmail.com wrote: @tech the ouput will be abhgrtsghgrthswert as no suffix of 1st matches with prefix of 2nd On 10/7/10, ligerdave david.c...@gmail.com wrote: use pointer. shift to left if one more leading char has been found. any unmatched char resets the pointer to first char once you went through the entire list(first one), the pointer on the second list tells you where to concatenate that gives you O(n) where n is the length of first list On Oct 7, 3:52 am, snehal jain learner@gmail.com wrote: There are two linked list, both containing a character in each node. If one linked list contain characters o x e n c and second contain characters e n c a r t a then the final linked list should contain o x e n c a r t ai.e. if the end of one list is same as the start of second then those characters should come only once. can we do it in O(n+m) where n and m are the length of list. both are singly link list. -- 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.comalgogeeks%252bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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.
