Re: [algogeeks] [Google question]
seems like Hungarian algorithm will work . On Wed, Aug 1, 2012 at 12:18 PM, vikas rai vikasloves...@gmail.com wrote: There is a set of 9 students and 3 schools Every school can be alloted atmax 3 students .Every school and student has its coordinates .Now we have to allot student in such a way that the sum of distance from all the student to the school should be minimum. We have to solve this in less than O(n^3) . -- 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?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 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?hl=en.
Re: [algogeeks] Google Question Invoice -bills
the DP is not clear, can you give example on how this DP would work for n invoices and k bills? Why is F(0,k) = 1? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Mar 26, 2012 at 2:16 PM, atul anand atul.87fri...@gmail.com wrote: it is similar to sum-subset problem following recurrance will solve this problem , you need to run algo for each invoice to find all combination F(n,k) = F(n,k-1) or F(n - a[k], k-1) base case :F(0,k)=1 for k=0 F(n,0)= 0 for n0. On Mon, Mar 26, 2012 at 1:34 PM, Ankush Bagotra ankush.bago...@gmail.comwrote: There are 210 Invoices and 1700 bills – these bills add up to these invoices The association between bills and invoices is lost . The only way to match them is by adding them up to correct amounts that are equal to the invoices. For Example : there were 2 invoices for 80, 210 and you have bills for these 50, 10 ,10, 30 , 20, 70, 100 values One of the possible solution is : 80=50 + 30 210= 10 + 10 +20 + 70 + 100 Other possible solution is 80=50 + 10 + 20 210= 30 +20 + 70 + 100 What is the best possible way to get all solutions ? Remember you are dealing with big datasets -Kabir -- 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?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 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?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 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?hl=en.
Re: [algogeeks] Google Question Invoice -bills
it is similar to sum-subset problem following recurrance will solve this problem , you need to run algo for each invoice to find all combination F(n,k) = F(n,k-1) or F(n - a[k], k-1) base case :F(0,k)=1 for k=0 F(n,0)= 0 for n0. On Mon, Mar 26, 2012 at 1:34 PM, Ankush Bagotra ankush.bago...@gmail.comwrote: There are 210 Invoices and 1700 bills – these bills add up to these invoices The association between bills and invoices is lost . The only way to match them is by adding them up to correct amounts that are equal to the invoices. For Example : there were 2 invoices for 80, 210 and you have bills for these 50, 10 ,10, 30 , 20, 70, 100 values One of the possible solution is : 80=50 + 30 210= 10 + 10 +20 + 70 + 100 Other possible solution is 80=50 + 10 + 20 210= 30 +20 + 70 + 100 What is the best possible way to get all solutions ? Remember you are dealing with big datasets -Kabir -- 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?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 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?hl=en.
Re: [algogeeks] Google Question Invoice -bills
Ok now you have combination of each invoice . What is the approach to take mutual exclusive combinations for so that sum of all bills equals sum of all invoices On Mon, Mar 26, 2012 at 2:16 PM, atul anand atul.87fri...@gmail.com wrote: it is similar to sum-subset problem following recurrance will solve this problem , you need to run algo for each invoice to find all combination F(n,k) = F(n,k-1) or F(n - a[k], k-1) base case :F(0,k)=1 for k=0 F(n,0)= 0 for n0. On Mon, Mar 26, 2012 at 1:34 PM, Ankush Bagotra ankush.bago...@gmail.com wrote: There are 210 Invoices and 1700 bills – these bills add up to these invoices The association between bills and invoices is lost . The only way to match them is by adding them up to correct amounts that are equal to the invoices. For Example : there were 2 invoices for 80, 210 and you have bills for these 50, 10 ,10, 30 , 20, 70, 100 values One of the possible solution is : 80=50 + 30 210= 10 + 10 +20 + 70 + 100 Other possible solution is 80=50 + 10 + 20 210= 30 +20 + 70 + 100 What is the best possible way to get all solutions ? Remember you are dealing with big datasets -Kabir -- 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?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 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?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 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?hl=en.
Re: [algogeeks] Google Question Invoice -bills
one way to do it , is say first combination for invoice 80= 50 + 30 now remove 80 and 30 from the input bills while finding combination from 210 , check if it is possible if yes , we got one solution not select another invoice combination 80= 50 + 10 + 20 now dont consider these values while find combination for 210. i guess there can be better way to solve this.. On Mon, Mar 26, 2012 at 2:36 PM, Ankush Bagotra ankush.bago...@gmail.comwrote: Ok now you have combination of each invoice . What is the approach to take mutual exclusive combinations for so that sum of all bills equals sum of all invoices On Mon, Mar 26, 2012 at 2:16 PM, atul anand atul.87fri...@gmail.com wrote: it is similar to sum-subset problem following recurrance will solve this problem , you need to run algo for each invoice to find all combination F(n,k) = F(n,k-1) or F(n - a[k], k-1) base case :F(0,k)=1 for k=0 F(n,0)= 0 for n0. On Mon, Mar 26, 2012 at 1:34 PM, Ankush Bagotra ankush.bago...@gmail.com wrote: There are 210 Invoices and 1700 bills – these bills add up to these invoices The association between bills and invoices is lost . The only way to match them is by adding them up to correct amounts that are equal to the invoices. For Example : there were 2 invoices for 80, 210 and you have bills for these 50, 10 ,10, 30 , 20, 70, 100 values One of the possible solution is : 80=50 + 30 210= 10 + 10 +20 + 70 + 100 Other possible solution is 80=50 + 10 + 20 210= 30 +20 + 70 + 100 What is the best possible way to get all solutions ? Remember you are dealing with big datasets -Kabir -- 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?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 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?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 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?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 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?hl=en.
Re: [algogeeks] Google Question Invoice -bills
Well, they have specified in the question that you are dealing with big-data sets. So, recursion won't be a good option I guess. Can we solve it with dynamic programming technique? On Mon, Mar 26, 2012 at 2:24 PM, atul anand atul.87fri...@gmail.com wrote: one way to do it , is say first combination for invoice 80= 50 + 30 now remove 80 and 30 from the input bills while finding combination from 210 , check if it is possible if yes , we got one solution not select another invoice combination 80= 50 + 10 + 20 now dont consider these values while find combination for 210. i guess there can be better way to solve this.. On Mon, Mar 26, 2012 at 2:36 PM, Ankush Bagotra ankush.bago...@gmail.comwrote: Ok now you have combination of each invoice . What is the approach to take mutual exclusive combinations for so that sum of all bills equals sum of all invoices On Mon, Mar 26, 2012 at 2:16 PM, atul anand atul.87fri...@gmail.com wrote: it is similar to sum-subset problem following recurrance will solve this problem , you need to run algo for each invoice to find all combination F(n,k) = F(n,k-1) or F(n - a[k], k-1) base case :F(0,k)=1 for k=0 F(n,0)= 0 for n0. On Mon, Mar 26, 2012 at 1:34 PM, Ankush Bagotra ankush.bago...@gmail.com wrote: There are 210 Invoices and 1700 bills – these bills add up to these invoices The association between bills and invoices is lost . The only way to match them is by adding them up to correct amounts that are equal to the invoices. For Example : there were 2 invoices for 80, 210 and you have bills for these 50, 10 ,10, 30 , 20, 70, 100 values One of the possible solution is : 80=50 + 30 210= 10 + 10 +20 + 70 + 100 Other possible solution is 80=50 + 10 + 20 210= 30 +20 + 70 + 100 What is the best possible way to get all solutions ? Remember you are dealing with big datasets -Kabir -- 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?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 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?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 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?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 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?hl=en. -- Umer -- 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?hl=en.
Re: [algogeeks] Google Question Invoice -bills
@umer : dp approach is given in above post. On Mon, Mar 26, 2012 at 4:11 PM, Umer Farooq the.um...@gmail.com wrote: Well, they have specified in the question that you are dealing with big-data sets. So, recursion won't be a good option I guess. Can we solve it with dynamic programming technique? On Mon, Mar 26, 2012 at 2:24 PM, atul anand atul.87fri...@gmail.comwrote: one way to do it , is say first combination for invoice 80= 50 + 30 now remove 80 and 30 from the input bills while finding combination from 210 , check if it is possible if yes , we got one solution not select another invoice combination 80= 50 + 10 + 20 now dont consider these values while find combination for 210. i guess there can be better way to solve this.. On Mon, Mar 26, 2012 at 2:36 PM, Ankush Bagotra ankush.bago...@gmail.com wrote: Ok now you have combination of each invoice . What is the approach to take mutual exclusive combinations for so that sum of all bills equals sum of all invoices On Mon, Mar 26, 2012 at 2:16 PM, atul anand atul.87fri...@gmail.com wrote: it is similar to sum-subset problem following recurrance will solve this problem , you need to run algo for each invoice to find all combination F(n,k) = F(n,k-1) or F(n - a[k], k-1) base case :F(0,k)=1 for k=0 F(n,0)= 0 for n0. On Mon, Mar 26, 2012 at 1:34 PM, Ankush Bagotra ankush.bago...@gmail.com wrote: There are 210 Invoices and 1700 bills – these bills add up to these invoices The association between bills and invoices is lost . The only way to match them is by adding them up to correct amounts that are equal to the invoices. For Example : there were 2 invoices for 80, 210 and you have bills for these 50, 10 ,10, 30 , 20, 70, 100 values One of the possible solution is : 80=50 + 30 210= 10 + 10 +20 + 70 + 100 Other possible solution is 80=50 + 10 + 20 210= 30 +20 + 70 + 100 What is the best possible way to get all solutions ? Remember you are dealing with big datasets -Kabir -- 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?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 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?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 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?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 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?hl=en. -- Umer -- 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?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 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?hl=en.
Re: [algogeeks] Google Question Invoice -bills
You can use dp to find subsets . But how is dp used for the overall probkem Sent from BlackBerry® on Airtel -Original Message- From: atul anand atul.87fri...@gmail.com Sender: algogeeks@googlegroups.com Date: Mon, 26 Mar 2012 16:52:08 To: algogeeks@googlegroups.com Reply-To: algogeeks@googlegroups.com Subject: Re: [algogeeks] Google Question Invoice -bills @umer : dp approach is given in above post. On Mon, Mar 26, 2012 at 4:11 PM, Umer Farooq the.um...@gmail.com wrote: Well, they have specified in the question that you are dealing with big-data sets. So, recursion won't be a good option I guess. Can we solve it with dynamic programming technique? On Mon, Mar 26, 2012 at 2:24 PM, atul anand atul.87fri...@gmail.comwrote: one way to do it , is say first combination for invoice 80= 50 + 30 now remove 80 and 30 from the input bills while finding combination from 210 , check if it is possible if yes , we got one solution not select another invoice combination 80= 50 + 10 + 20 now dont consider these values while find combination for 210. i guess there can be better way to solve this.. On Mon, Mar 26, 2012 at 2:36 PM, Ankush Bagotra ankush.bago...@gmail.com wrote: Ok now you have combination of each invoice . What is the approach to take mutual exclusive combinations for so that sum of all bills equals sum of all invoices On Mon, Mar 26, 2012 at 2:16 PM, atul anand atul.87fri...@gmail.com wrote: it is similar to sum-subset problem following recurrance will solve this problem , you need to run algo for each invoice to find all combination F(n,k) = F(n,k-1) or F(n - a[k], k-1) base case :F(0,k)=1 for k=0 F(n,0)= 0 for n0. On Mon, Mar 26, 2012 at 1:34 PM, Ankush Bagotra ankush.bago...@gmail.com wrote: There are 210 Invoices and 1700 bills – these bills add up to these invoices The association between bills and invoices is lost . The only way to match them is by adding them up to correct amounts that are equal to the invoices. For Example : there were 2 invoices for 80, 210 and you have bills for these 50, 10 ,10, 30 , 20, 70, 100 values One of the possible solution is : 80=50 + 30 210= 10 + 10 +20 + 70 + 100 Other possible solution is 80=50 + 10 + 20 210= 30 +20 + 70 + 100 What is the best possible way to get all solutions ? Remember you are dealing with big datasets -Kabir -- 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?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 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?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 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?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 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?hl=en. -- Umer -- 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?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 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?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 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?hl=en.
Re: [algogeeks] Google Question Invoice -bills
@ankush: i told one approach above , but may i want clear . i am not saying this is the best approach to do so but it is one naive soln i came up with. so find all possible combination for each invoice and save it in some data structure. now start from 1st invoice and select 1st invoice combination say for invoice 80 = 50 + 30 now search in next invoice(210) combination , if there is any combination for this invoice which does not include 50 and 30 if yes there is one say 210= 10 + 10 +20 + 70 + 100 , we have a hit and do similar with other invoice . every time you move fwd make sure that you should search for combination which does not include any of those bill used in prev finding. if no, then we know that there is no point of moving fwd , so select another combination from prev invoice in this case its 80 and follow same as above. On Mon, Mar 26, 2012 at 5:56 PM, ankush.bago...@gmail.com wrote: ** You can use dp to find subsets . But how is dp used for the overall probkem Sent from BlackBerry® on Airtel -- *From: * atul anand atul.87fri...@gmail.com *Sender: * algogeeks@googlegroups.com *Date: *Mon, 26 Mar 2012 16:52:08 +0530 *To: *algogeeks@googlegroups.com *ReplyTo: * algogeeks@googlegroups.com *Subject: *Re: [algogeeks] Google Question Invoice -bills @umer : dp approach is given in above post. On Mon, Mar 26, 2012 at 4:11 PM, Umer Farooq the.um...@gmail.com wrote: Well, they have specified in the question that you are dealing with big-data sets. So, recursion won't be a good option I guess. Can we solve it with dynamic programming technique? On Mon, Mar 26, 2012 at 2:24 PM, atul anand atul.87fri...@gmail.comwrote: one way to do it , is say first combination for invoice 80= 50 + 30 now remove 80 and 30 from the input bills while finding combination from 210 , check if it is possible if yes , we got one solution not select another invoice combination 80= 50 + 10 + 20 now dont consider these values while find combination for 210. i guess there can be better way to solve this.. On Mon, Mar 26, 2012 at 2:36 PM, Ankush Bagotra ankush.bago...@gmail.com wrote: Ok now you have combination of each invoice . What is the approach to take mutual exclusive combinations for so that sum of all bills equals sum of all invoices On Mon, Mar 26, 2012 at 2:16 PM, atul anand atul.87fri...@gmail.com wrote: it is similar to sum-subset problem following recurrance will solve this problem , you need to run algo for each invoice to find all combination F(n,k) = F(n,k-1) or F(n - a[k], k-1) base case :F(0,k)=1 for k=0 F(n,0)= 0 for n0. On Mon, Mar 26, 2012 at 1:34 PM, Ankush Bagotra ankush.bago...@gmail.com wrote: There are 210 Invoices and 1700 bills – these bills add up to these invoices The association between bills and invoices is lost . The only way to match them is by adding them up to correct amounts that are equal to the invoices. For Example : there were 2 invoices for 80, 210 and you have bills for these 50, 10 ,10, 30 , 20, 70, 100 values One of the possible solution is : 80=50 + 30 210= 10 + 10 +20 + 70 + 100 Other possible solution is 80=50 + 10 + 20 210= 30 +20 + 70 + 100 What is the best possible way to get all solutions ? Remember you are dealing with big datasets -Kabir -- 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?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 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?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 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?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 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?hl=en. -- Umer -- 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
Re: [algogeeks] google question
i guess this would work...
n=number of nodes
h=height;
pour=quantity poured;
capacity = capacity of each cup
n=pow(2,h+1) -1;
call(capacity,pour,0,n)
node* fillCup(float capacity,float pour,int left,int right)
{
node *root;
int mid;
if(left right)
return NULL;
root=(node *)malloc(sizeof(node));
if(left==right)
{
if(pour =capacity)
root-data=capacity;
else
root-data=pour;
root-left=root-right=NULL;
}
else
{
mid=left+(right-left)/2;
if(pour = capacity)
{
root-data=capacity;
pour=pour-capacity;
pour=pour/2;
}
else
{
root-data=pour;
root-left=root-right=NULL;
return root;
}
root-left=fillCup(capacity,pour,left,mid-1);
root-right=fillCup(capacity,pour,mid+1,right);
}
return root;
}
On Sat, Feb 25, 2012 at 5:05 PM, Ravi Ranjan ravi.cool2...@gmail.comwrote:
|_|
|_| |_|
|_| |_| |_|
|_| |_| |_| |_|
|_| |_| |_| |_| |_|
Each cup has capacity C and once a cup gets full, it drops half extra
amount to left child and half extra amount to right child
for Eg : let' first cups get 2C amount of liquid then extra amount C(2C-C)
will be divided equally to left and right child cup of next level
i.e. C/2 to left child and C/2 to right child
Write a function which takes input parameter as amount of liquid poured at
top (L) and height of particular cup (h) index of that cup (i) and it
should return amount of liquid absorbed in that cup.
source
http://www.careercup.com/question?id=12770661
whats exactly the qestion???
--
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?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 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?hl=en.
Re: [algogeeks] Google Question--Suggest Algo
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0] Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3 why this is not the optimal split??? On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com wrote: You have an array with *n* elements. The elements are either 0 or 1. You want to *split the array into kcontiguous subarrays*. The size of each subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that k n. After you split the array into k subarrays. One element of each subarray will be randomly selected. Devise an algorithm for maximizing the sum of the randomly selected elements from the k subarrays. Basically means that we will want to split the array in such way such that the sum of all the expected values for the elements selected from each subarray is maximum. You can assume that n is a power of 2. Example: Array: [0,0,1,1,0,0,1,1,0,1,1,0] n = 12 k = 3 Size of subarrays can be: 2,3,4,5,6 Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0] Expected Value of the sum of the elements randomly selected from the subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433 Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0] Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333 Source - http://stackoverflow.com/questions/8189334/google-combinatorial-optimization-interview-problm -- 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?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 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?hl=en.
Re: [algogeeks] Google Question
google this question!! On Fri, Jul 8, 2011 at 11:47 AM, priyanshu priyanshuro...@gmail.com wrote: How to find the number users connected to the web?? -- 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?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 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?hl=en.
Re: [algogeeks] Google Question
may be by checking the server logs !! On Fri, Jul 8, 2011 at 11:48 AM, Vishal Thanki vishaltha...@gmail.comwrote: google this question!! On Fri, Jul 8, 2011 at 11:47 AM, priyanshu priyanshuro...@gmail.com wrote: How to find the number users connected to the web?? -- 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?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 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?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 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?hl=en.
Re: [algogeeks] Google Question
if no of waiting process is required, it can be obtained by length of listen queue on server. if no of running process is required , it can be done by getting process id's currently running, if no of hits in a time range is required, it can be done by server log as well. -- Best Wishes Sachin Sharma University of Delhi. -- 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?hl=en.
Re: [algogeeks] GOOGLE QUESTION
go through the archives you will definitely find the answer :) On Wed, Jun 29, 2011 at 6:05 PM, MONSIEUR monsieur@gmail.com wrote: What is the most efficient way, memory-wise, to store 1 million phone numbers? -- 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?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 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?hl=en.
Re: [algogeeks] GOOGLE QUESTION
USE TRIE On Wed, Jun 29, 2011 at 6:10 PM, shady sinv...@gmail.com wrote: go through the archives you will definitely find the answer :) On Wed, Jun 29, 2011 at 6:05 PM, MONSIEUR monsieur@gmail.com wrote: What is the most efficient way, memory-wise, to store 1 million phone numbers? -- 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?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 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?hl=en. -- Thanks and Regards chigullapallysudh...@gmail.com Sudheer -- 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?hl=en.
Re: [algogeeks] GOOGLE QUESTION
How we will get phone number of a particular person? Thanks Regards, Anantha Krishnan On Wed, Jun 29, 2011 at 6:22 PM, sudheer kumar chigullapallysudh...@gmail.com wrote: USE TRIE On Wed, Jun 29, 2011 at 6:10 PM, shady sinv...@gmail.com wrote: go through the archives you will definitely find the answer :) On Wed, Jun 29, 2011 at 6:05 PM, MONSIEUR monsieur@gmail.com wrote: What is the most efficient way, memory-wise, to store 1 million phone numbers? -- 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?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 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?hl=en. -- Thanks and Regards chigullapallysudh...@gmail.com Sudheer -- 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?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 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?hl=en.
Re: [algogeeks] GOOGLE QUESTION
@MONSIEUR Use Binary Search Tree as the data Structure to store the values for the Phone numbers because insertion and deletion is easy plus you will get the additional advantage of sorted list of phone numbers . So Binary search tree is better than using hash data structure . Regards Rajeev N B I Blog @ www.opensourcemania.co.cc On Wed, Jun 29, 2011 at 6:27 PM, Anantha Krishnan ananthakrishnan@gmail.com wrote: How we will get phone number of a particular person? Thanks Regards, Anantha Krishnan On Wed, Jun 29, 2011 at 6:22 PM, sudheer kumar chigullapallysudh...@gmail.com wrote: USE TRIE On Wed, Jun 29, 2011 at 6:10 PM, shady sinv...@gmail.com wrote: go through the archives you will definitely find the answer :) On Wed, Jun 29, 2011 at 6:05 PM, MONSIEUR monsieur@gmail.comwrote: What is the most efficient way, memory-wise, to store 1 million phone numbers? -- 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?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 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?hl=en. -- Thanks and Regards chigullapallysudh...@gmail.com Sudheer -- 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?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 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?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 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?hl=en.
Re: [algogeeks] GOOGLE QUESTION
Hey guys, phone usually has comparatively very less memory. So, we can't afford to have pointers for each phone no. So, the idea of having a tree is rooted out. The best way can be to use a fixed array with circular indexing which is sorted by name, because the most frequent query is to search a person by name. Though the addition and deletion are expensive, but these are operations are very rare. On Wed, Jun 29, 2011 at 7:25 AM, rajeev bharshetty rajeevr...@gmail.com wrote: @MONSIEUR Use Binary Search Tree as the data Structure to store the values for the Phone numbers because insertion and deletion is easy plus you will get the additional advantage of sorted list of phone numbers . So Binary search tree is better than using hash data structure . Regards Rajeev N B I Blog @ www.opensourcemania.co.cc On Wed, Jun 29, 2011 at 6:27 PM, Anantha Krishnan ananthakrishnan@gmail.com wrote: How we will get phone number of a particular person? Thanks Regards, Anantha Krishnan On Wed, Jun 29, 2011 at 6:22 PM, sudheer kumar chigullapallysudh...@gmail.com wrote: USE TRIE On Wed, Jun 29, 2011 at 6:10 PM, shady sinv...@gmail.com wrote: go through the archives you will definitely find the answer :) On Wed, Jun 29, 2011 at 6:05 PM, MONSIEUR monsieur@gmail.com wrote: What is the most efficient way, memory-wise, to store 1 million phone numbers? -- 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?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 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?hl=en. -- Thanks and Regards chigullapallysudh...@gmail.com Sudheer -- 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?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 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?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 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?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 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?hl=en.
Re: [algogeeks] Google Question
This question has been discussed over here once...It was concluded that this can be solved in O(n) if we know there is a fixed range up to which the elements keep on increasing and decreasing..for example in an array of 12 elements, we know 3 elements keep on increasing monotonically, then 3 elements keep on decreasing monotonically and so on On 6/22/11, chirag ahuja sparkle.chi...@gmail.com wrote: Given an array of size n wherein elements keep on increasing monotonically upto a certain location after which they keep on decreasing monotonically, then again keep on increasing, then decreasing again and so on. Sort the array in O(n) and O(1). I didn't understand the question, any array of n elements will be like this except when first there is a decrese from index 0 to a higher index. Any ideas about how to solve it in given constraints?? -- 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?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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?hl=en.
Re: [algogeeks] Google Question
Why to do hashing?? rather generate a unique id everytime... On Fri, Jun 3, 2011 at 9:50 PM, Nate nate.archibal...@gmail.com wrote: How will you design a site similar to tinyurl.com? Simple hashing may require a lot of space, and collisions is another issue. Any other approch other than just hashing? -- 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?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 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?hl=en.
Re: [algogeeks] Google Question
hashing for lookup. where key will be the tinyurl generated and value will be the actual url. We need to lookup the actual url everytime a client queries with a tinyurl. The question is how will you make this search faster. On Fri, Jun 3, 2011 at 10:17 PM, vaibhav agrawal agrvaib...@gmail.comwrote: Why to do hashing?? rather generate a unique id everytime... On Fri, Jun 3, 2011 at 9:50 PM, Nate nate.archibal...@gmail.com wrote: How will you design a site similar to tinyurl.com? Simple hashing may require a lot of space, and collisions is another issue. Any other approch other than just hashing? -- 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?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 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?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 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?hl=en.
Re: [algogeeks] Google Question
regarding doenloads folder..tiger tree hash(TTH) as we use it in file sharing (DC++) might help look this - http://www.dslreports.com/faq/9677 Once DC++ hashes all of your share (yes, this *will* take a while), it will only hash new files. The hashing thread in DC++ is set to low priority, so it shouldn't interfere too badly. There are several benefits of file hashing: No longer does one need to pay attention to the name of the file when looking for alternative sources. If the files are the same, they will have the same hash and can thus be chosen as an alternative source. Just because two files are the exact same size does *not* mean they are the same bitwise! On Fri, Jun 3, 2011 at 10:01 AM, Nate Archibald nate.archibal...@gmail.comwrote: hashing for lookup. where key will be the tinyurl generated and value will be the actual url. We need to lookup the actual url everytime a client queries with a tinyurl. The question is how will you make this search faster. On Fri, Jun 3, 2011 at 10:17 PM, vaibhav agrawal agrvaib...@gmail.comwrote: Why to do hashing?? rather generate a unique id everytime... On Fri, Jun 3, 2011 at 9:50 PM, Nate nate.archibal...@gmail.com wrote: How will you design a site similar to tinyurl.com? Simple hashing may require a lot of space, and collisions is another issue. Any other approch other than just hashing? -- 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?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 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?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 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?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 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?hl=en.
Re: [algogeeks] Google Question
No special approach is needed. In O(log n), you can find the minimum element of the array which makes your circular array - normal array. -- 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?hl=en.
Re: [algogeeks] Google Question
It will be like a circularly sorted array.There exists a binary search type divide and conquer mechanism to find a specific number in such type of arrays. -- 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?hl=en.
Re: [algogeeks] Google Question: Find kth largest of sum of elements in 2 array
Let S(k) indicate the kth largest sum as per the question. We can also say that every S corresponds to a pair, (u,v) such that S=a[u]+b[v]. Now the idea is to keep track of two previous S's (in turn two pairs) such that one pair has the greatest 'u' of all so-far pairs. That is, this pair has most advanced on array a. And the other has the highest 'v' of all. This pair has advanced most on array b. Sometimes the same pair may top in both u and v. Then finding the next S would be simple. Assume we are to find S( j ), and that S(h) and S(i), where h,i j k, have advanced most on array a and b respectively. If S(h)= a[p]+b[q] and S(i)= a[r]+b[s], then obviously p = r and q =s, and we have four candidate pairs for S(j): (p,q+1), (p+1,q), (r,s+1) and (r+1,s). Now S(j) is calculated as S(j)= max( a[p]+b[q+1], a[p+1]+b[q], a[r]+b[s+1], a[r+1]+b[s] ). We should update S(h) and S(i) based on which of these is maximum. Complexity is in O(m+n) i think. On Wed, Oct 6, 2010 at 4:04 PM, sourav souravs...@gmail.com wrote: you are given 2 arrays sorted in decreasing order of size m and n respectively. Input: a number k = m*n and = 1 Output: the kth largest sum(a+b) possible. where a (any element from array 1) b (any element from array 2) The Brute force approach will take O(n*n). can anyone find a better logic. thnkx in advance. -- 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] Google Question: Find kth largest of sum of elements in 2 array
Correction: On Thu, Oct 7, 2010 at 11:12 AM, sumant hegde sumant@gmail.com wrote: If S(h)= a[p]+b[q] and S(i)= a[r]+b[s], then obviously p = r and q= s, .. then p = r and q = s.. -- 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.
