Re: [algogeeks] Re: Least fare for a return trip Algorithm
@amod I am not sure I understand what you are saying. It is assumed that the K smallest Items(from both list A B) are identified and arranged in increasing order as the first step. Now A(1) and B(1) constitute the least fare round trip(since the list is sorted) and we include that combination into our list of selected round trips with minimal fare. Then we proceed by either including A(1)-B(2) or A(2)-B(1) or both (if they add up to an equal value) I am not clear about what you mean by reuse of elements. Am I missing anything here ? If so a more clear example would help ! On Thu, Oct 28, 2010 at 10:26 AM, Amod gam...@gmail.com wrote: @Algoose Yes, but the algoritm is not correct since we are not covering the condition where element is reused. Ex ia=1 and ib=1 If we increment ia to 2 then there may be a case where A(1)+B(1) is less than A(2)+B(1) but since 1 was denoted by ia which is now 2 hence we will never be able to check this. So algorithm ignores reuse of elements. On Oct 27, 5:06 pm, Algoose chase harishp...@gmail.com wrote: @Dave, I believe in the first if clause ib must be incremented in the else if clause ia must be incremented. is that right ? 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_selectio. .. . 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
[algogeeks] Re: Least fare for a return trip Algorithm
@Dave I tried to run your algorithm but I am not getting the desired results Taking inputs as given by @coolfrog AB 16 37 69 I am getting AB Sum 167 369 66 12 96 15 and the desired output would have been 1 6 7 1 7 8 3 6 9 1 9 10 6 6 12 I think we are not covering the point where index is reused. If we increment the index by one the the condition like 1 7 8 will not occur. Please suggest. Amod On Oct 16, 5:51 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; seehttp://en.wikipedia.org/wiki/Median_algorithm#Linear_general_selectio 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
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] 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: 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: Least fare for a return trip Algorithm
@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 . 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.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
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' -- 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
Although no inputs are given on flight timing (date and time) front but that is one more factor that should be considered while scheduling the cheapest round trip journey as it happens on travel sites normally On Wed, Oct 13, 2010 at 2:56 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' -- 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: Least fare for a return trip Algorithm
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' -- 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
@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.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
sorting is absolutely required. w/o the sorting, how are you going to find the min? comparison is also a sorting algorithm. it also depends on how many suggestions you wanna have. if it's just the best deal, you can complete this in O(n+m) where n is the number of different fares of trip to and m is the trip back On Oct 12, 9:06 am, Amod gam...@gmail.com wrote: Suppose there are 100 flights from A to B and 1000 flights from B to A. Now a user selects the round trip from A to B and back to A, the site presents suggestions based on the least fare of the return journey. Could someone please help me to device and algorithm where based on number of suggestions the results are displayed. ex A-B B-A A1 1 B1 1 A2 2 B2 3 A3 4 B3 5 A4 6 B4 8 So if i want four suggestions then A1+B1, A2+B1, A1+B2, A2+B2 Please also suggest whether sorting based on fares is required or not -- 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
Could you please elaborate on O(n+m) algorithm that you have used On Oct 12, 6:43 pm, ligerdave david.c...@gmail.com wrote: sorting is absolutely required. w/o the sorting, how are you going to find the min? comparison is also a sorting algorithm. it also depends on how many suggestions you wanna have. if it's just the best deal, you can complete this in O(n+m) where n is the number of different fares of trip to and m is the trip back On Oct 12, 9:06 am, Amod gam...@gmail.com wrote: Suppose there are 100 flights from A to B and 1000 flights from B to A. Now a user selects the round trip from A to B and back to A, the site presents suggestions based on the least fare of the return journey. Could someone please help me to device and algorithm where based on number of suggestions the results are displayed. ex A-B B-A A1 1 B1 1 A2 2 B2 3 A3 4 B3 5 A4 6 B4 8 So if i want four suggestions then A1+B1, A2+B1, A1+B2, A2+B2 Please also suggest whether sorting based on fares is required or not -- 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.
