|
ms
newsgroups
|
|||||||||||||||||||||||
|
|||||||||||||||||||||||
Simple but confusing algorith questionI was asked this question in an interview recently: Suppose you have the method signature bool MyPairSum(int [] array, int sum) the array has all unique values (no repeats), your task is to find two indices in the array whose sum equals the input parameter sum. If there exists two entries in the array that sum together to equal the input parameter of sum, then return true, otherwise return false. what's the most efficient implementation? My question is can we have a better worse case runtime of O(n²) ?? I'm thinking that in the worse case, you'd have to compare each index against all the other indices and test each sum until you find one that matches the input sum. In the worse case, there will be no pair of indices that equal the input sum parameter. Am I overlooking a very basic trick? I figured with all the sharp people in here, somebody can discern whether I'm off base or not :) Here's the sample implementation I was thinking of: bool MyPairSum(int [] array, int sum) { for (int i = 0; i < array.Length; i++) { for (int j = i + 1; j < array.Length; j++) { if ( array[i] + array[j] == sum) return true; } } return false; } Tks, Karan S. If the data were sorted you could do much better. If they are not sorted you
would have n^2 as your worst case as you have to check every index of the array for each value. even so you could still do slightly better by only issuing a single add/sub instead of a operation on every iteration ... see example. bool MyPairSum(int [] array, int sum) { for (int i = 0; i < array.Length; i++) { int need = sum - array[j]; for (int j = 0; j < array.Length; j++) { if (array[j] == sum) return true; } } return false; } Also your code has failure modes because int j = i + 1 ... what about the following data? array 0,1,2 sum = 3 by using i+1 you say it doesn't exist. Another quick question ... what should the behavior be for the following? array 1,2,3,4 sum = 5 Cheers, Greg <karan.sha***@gmail.com> wrote in message news:1146101141.203814.21600@i39g2000cwa.googlegroups.com... I was asked this question in an interview recently:Hey all, Suppose you have the method signature bool MyPairSum(int [] array, int sum) the array has all unique values (no repeats), your task is to find two indices in the array whose sum equals the input parameter sum. If there exists two entries in the array that sum together to equal the input parameter of sum, then return true, otherwise return false. what's the most efficient implementation? My question is can we have a better worse case runtime of O(n²) ?? I'm thinking that in the worse case, you'd have to compare each index against all the other indices and test each sum until you find one that matches the input sum. In the worse case, there will be no pair of indices that equal the input sum parameter. Am I overlooking a very basic trick? I figured with all the sharp people in here, somebody can discern whether I'm off base or not :) Here's the sample implementation I was thinking of: bool MyPairSum(int [] array, int sum) { for (int i = 0; i < array.Length; i++) { for (int j = i + 1; j < array.Length; j++) { if ( array[i] + array[j] == sum) return true; } } return false; } Tks, Karan S. This is Sorted
array 1,2,3,4 sum = 5 This is not Sorted array 1,4,2,3 sum = 5 Which one is faster?? SA Show quoteHide quote "Greg Young [MVP]" <DruckDruckGo***@hotmail.com> wrote in message news:OMlt4xZaGHA.440@TK2MSFTNGP05.phx.gbl... > If the data were sorted you could do much better. If they are not sorted > you > would have n^2 as your worst case as you have to check every index of the > array for each value. > > even so you could still do slightly better by only issuing a single > add/sub > instead of a operation on every iteration ... see example. > > bool MyPairSum(int [] array, int sum) > { > for (int i = 0; i < array.Length; i++) > { > int need = sum - array[j]; > for (int j = 0; j < array.Length; j++) > { > if (array[j] == sum) > return true; > } > } > return false; > } > > Also your code has failure modes because int j = i + 1 ... what about the > following data? > > array 0,1,2 sum = 3 by using i+1 you say it doesn't exist. > > Another quick question ... what should the behavior be for the following? > > array 1,2,3,4 sum = 5 > > Cheers, > > Greg > > <karan.sha***@gmail.com> wrote in message > news:1146101141.203814.21600@i39g2000cwa.googlegroups.com... > Hey all, > > > I was asked this question in an interview recently: > > Suppose you have the method signature > > bool MyPairSum(int [] array, int sum) > > the array has all unique values (no repeats), your task is to find two > indices in the array whose sum equals the input parameter sum. If there > exists two entries in the array that sum together to equal the input > parameter of sum, then return true, otherwise return false. what's the > most efficient implementation? > > My question is can we have a better worse case runtime of O(n²) ?? > I'm thinking that in the worse case, you'd have to compare each index > against all the other indices and test each sum until you find one that > matches the input sum. In the worse case, there will be no pair of > indices that equal the input sum parameter. Am I overlooking a very > basic trick? I figured with all the sharp people in here, somebody can > discern whether I'm off base or not :) > > Here's the sample implementation I was thinking of: > > > bool MyPairSum(int [] array, int sum) > { > for (int i = 0; i < array.Length; i++) > { > for (int j = i + 1; j < array.Length; j++) > { > if ( array[i] + array[j] == sum) > return true; > } > } > return false; > } > > > Tks, Karan S. > > If you can count on sorted data you can make assumptions in your looping and
get your worst case a whole lot better than O(n^2) i.e if current + array[i] > sum { //skip rest of list } Show quoteHide quote "MSDN" <sql_agent***@hotmail.com> wrote in message news:%23EwKSEaaGHA.4564@TK2MSFTNGP03.phx.gbl... > This is Sorted > array 1,2,3,4 sum = 5 > > This is not Sorted > array 1,4,2,3 sum = 5 > > Which one is faster?? > > SA > > "Greg Young [MVP]" <DruckDruckGo***@hotmail.com> wrote in message > news:OMlt4xZaGHA.440@TK2MSFTNGP05.phx.gbl... >> If the data were sorted you could do much better. If they are not sorted >> you >> would have n^2 as your worst case as you have to check every index of the >> array for each value. >> >> even so you could still do slightly better by only issuing a single >> add/sub >> instead of a operation on every iteration ... see example. >> >> bool MyPairSum(int [] array, int sum) >> { >> for (int i = 0; i < array.Length; i++) >> { >> int need = sum - array[j]; >> for (int j = 0; j < array.Length; j++) >> { >> if (array[j] == sum) >> return true; >> } >> } >> return false; >> } >> >> Also your code has failure modes because int j = i + 1 ... what about the >> following data? >> >> array 0,1,2 sum = 3 by using i+1 you say it doesn't exist. >> >> Another quick question ... what should the behavior be for the following? >> >> array 1,2,3,4 sum = 5 >> >> Cheers, >> >> Greg >> >> <karan.sha***@gmail.com> wrote in message >> news:1146101141.203814.21600@i39g2000cwa.googlegroups.com... >> Hey all, >> >> >> I was asked this question in an interview recently: >> >> Suppose you have the method signature >> >> bool MyPairSum(int [] array, int sum) >> >> the array has all unique values (no repeats), your task is to find two >> indices in the array whose sum equals the input parameter sum. If there >> exists two entries in the array that sum together to equal the input >> parameter of sum, then return true, otherwise return false. what's the >> most efficient implementation? >> >> My question is can we have a better worse case runtime of O(n²) ?? >> I'm thinking that in the worse case, you'd have to compare each index >> against all the other indices and test each sum until you find one that >> matches the input sum. In the worse case, there will be no pair of >> indices that equal the input sum parameter. Am I overlooking a very >> basic trick? I figured with all the sharp people in here, somebody can >> discern whether I'm off base or not :) >> >> Here's the sample implementation I was thinking of: >> >> >> bool MyPairSum(int [] array, int sum) >> { >> for (int i = 0; i < array.Length; i++) >> { >> for (int j = i + 1; j < array.Length; j++) >> { >> if ( array[i] + array[j] == sum) >> return true; >> } >> } >> return false; >> } >> >> >> Tks, Karan S. >> >> > > "Greg Young [MVP]" <DruckDruckGo***@hotmail.com> wrote: I think it's O(n) if the list is sorted...>If you can count on sorted data you can make assumptions in your looping and >get your worst case a whole lot better than O(n^2) (1) Sort the list from smallest to largest (2) Have two pointers, "left" at the start of the list, "right" at the end. (3) If the sum of your two pointers is too big, then "right" has to move left (4) If the sum is too small, then "left" has to move right (5) If the two pointers meet then there is no solution Proof: suppose there exists a solution x+y where x is smaller. If left<x and right>y then any move we can make is acceptable. If left=x then no move will make right<y. Similarly if right=y then no move will make left>x. -- Lucian Also O(n^2) is talking about the worst case ... you have provided the best
case as a comparison ... to compare the worst case in this problem you would actually be looking at iterations on a miss .. array 1,2,3,4 sum 12 array 3,2,1,4 sum 12 in the onsorted case you have O^2 (loop through all twice) .. 16 in the sorted case you would be with almost no effort at 9 comparisons on the worst case as it would allow you to do the simple change in the original code (use i+1 for j instead of 0) Show quoteHide quote "MSDN" <sql_agent***@hotmail.com> wrote in message news:%23EwKSEaaGHA.4564@TK2MSFTNGP03.phx.gbl... > This is Sorted > array 1,2,3,4 sum = 5 > > This is not Sorted > array 1,4,2,3 sum = 5 > > Which one is faster?? > > SA > > "Greg Young [MVP]" <DruckDruckGo***@hotmail.com> wrote in message > news:OMlt4xZaGHA.440@TK2MSFTNGP05.phx.gbl... >> If the data were sorted you could do much better. If they are not sorted >> you >> would have n^2 as your worst case as you have to check every index of the >> array for each value. >> >> even so you could still do slightly better by only issuing a single >> add/sub >> instead of a operation on every iteration ... see example. >> >> bool MyPairSum(int [] array, int sum) >> { >> for (int i = 0; i < array.Length; i++) >> { >> int need = sum - array[j]; >> for (int j = 0; j < array.Length; j++) >> { >> if (array[j] == sum) >> return true; >> } >> } >> return false; >> } >> >> Also your code has failure modes because int j = i + 1 ... what about the >> following data? >> >> array 0,1,2 sum = 3 by using i+1 you say it doesn't exist. >> >> Another quick question ... what should the behavior be for the following? >> >> array 1,2,3,4 sum = 5 >> >> Cheers, >> >> Greg >> >> <karan.sha***@gmail.com> wrote in message >> news:1146101141.203814.21600@i39g2000cwa.googlegroups.com... >> Hey all, >> >> >> I was asked this question in an interview recently: >> >> Suppose you have the method signature >> >> bool MyPairSum(int [] array, int sum) >> >> the array has all unique values (no repeats), your task is to find two >> indices in the array whose sum equals the input parameter sum. If there >> exists two entries in the array that sum together to equal the input >> parameter of sum, then return true, otherwise return false. what's the >> most efficient implementation? >> >> My question is can we have a better worse case runtime of O(n²) ?? >> I'm thinking that in the worse case, you'd have to compare each index >> against all the other indices and test each sum until you find one that >> matches the input sum. In the worse case, there will be no pair of >> indices that equal the input sum parameter. Am I overlooking a very >> basic trick? I figured with all the sharp people in here, somebody can >> discern whether I'm off base or not :) >> >> Here's the sample implementation I was thinking of: >> >> >> bool MyPairSum(int [] array, int sum) >> { >> for (int i = 0; i < array.Length; i++) >> { >> for (int j = i + 1; j < array.Length; j++) >> { >> if ( array[i] + array[j] == sum) >> return true; >> } >> } >> return false; >> } >> >> >> Tks, Karan S. >> >> > > It does seem like there's no way around checking all possibilties
unless some other data structure was involved. I was trying to cut down on comparisons/summations by eliminating the first element, then the second, so the over run time would be on the order of n ( n - 1 ) ---------------- 2 in the worse case, which basically is O(n²). like from your example comparisons: 1 with 2, 1 with 3, 1 with 4, 2 with 3, 2 with 4, 3 with 4 (done, all combos tested). You wouldn't compare 1 with 1, 2 with 2, and the like since they're not different indexes. worse case runtime = 1/2 n² which amounts to O(n²) unfortunately. Thanks for your reply Greg Young [MVP] wrote: Show quoteHide quote > Also O(n^2) is talking about the worst case ... you have provided the best > case as a comparison ... > > to compare the worst case in this problem you would actually be looking at > iterations on a miss .. > > array 1,2,3,4 sum 12 > array 3,2,1,4 sum 12 > > in the onsorted case you have O^2 (loop through all twice) .. 16 > > in the sorted case you would be with almost no effort at 9 comparisons on > the worst case as it would allow you to do the simple change in the original > code (use i+1 for j instead of 0) > > > "MSDN" <sql_agent***@hotmail.com> wrote in message > news:%23EwKSEaaGHA.4564@TK2MSFTNGP03.phx.gbl... > > This is Sorted > > array 1,2,3,4 sum = 5 > > > > This is not Sorted > > array 1,4,2,3 sum = 5 > > > > Which one is faster?? > > > > SA > > > > "Greg Young [MVP]" <DruckDruckGo***@hotmail.com> wrote in message > > news:OMlt4xZaGHA.440@TK2MSFTNGP05.phx.gbl... > >> If the data were sorted you could do much better. If they are not sorted > >> you > >> would have n^2 as your worst case as you have to check every index of the > >> array for each value. > >> > >> even so you could still do slightly better by only issuing a single > >> add/sub > >> instead of a operation on every iteration ... see example. > >> > >> bool MyPairSum(int [] array, int sum) > >> { > >> for (int i = 0; i < array.Length; i++) > >> { > >> int need = sum - array[j]; > >> for (int j = 0; j < array.Length; j++) > >> { > >> if (array[j] == sum) > >> return true; > >> } > >> } > >> return false; > >> } > >> > >> Also your code has failure modes because int j = i + 1 ... what about the > >> following data? > >> > >> array 0,1,2 sum = 3 by using i+1 you say it doesn't exist. > >> > >> Another quick question ... what should the behavior be for the following? > >> > >> array 1,2,3,4 sum = 5 > >> > >> Cheers, > >> > >> Greg > >> > >> <karan.sha***@gmail.com> wrote in message > >> news:1146101141.203814.21600@i39g2000cwa.googlegroups.com... > >> Hey all, > >> > >> > >> I was asked this question in an interview recently: > >> > >> Suppose you have the method signature > >> > >> bool MyPairSum(int [] array, int sum) > >> > >> the array has all unique values (no repeats), your task is to find two > >> indices in the array whose sum equals the input parameter sum. If there > >> exists two entries in the array that sum together to equal the input > >> parameter of sum, then return true, otherwise return false. what's the > >> most efficient implementation? > >> > >> My question is can we have a better worse case runtime of O(n²) ?? > >> I'm thinking that in the worse case, you'd have to compare each index > >> against all the other indices and test each sum until you find one that > >> matches the input sum. In the worse case, there will be no pair of > >> indices that equal the input sum parameter. Am I overlooking a very > >> basic trick? I figured with all the sharp people in here, somebody can > >> discern whether I'm off base or not :) > >> > >> Here's the sample implementation I was thinking of: > >> > >> > >> bool MyPairSum(int [] array, int sum) > >> { > >> for (int i = 0; i < array.Length; i++) > >> { > >> for (int j = i + 1; j < array.Length; j++) > >> { > >> if ( array[i] + array[j] == sum) > >> return true; > >> } > >> } > >> return false; > >> } > >> > >> > >> Tks, Karan S. > >> > >> > > > > It does seem like there's no way around checking all possibilties
unless some other data structure was involved. I was trying to cut down on comparisons/summations by eliminating the first element, then the second, so the over run time would be on the order of n ( n - 1 ) ---------------- 2 in the worse case, which basically is O(n²). like from your example comparisons: 1 with 2, 1 with 3, 1 with 4, 2 with 3, 2 with 4, 3 with 4 (done, all combos tested). You wouldn't compare 1 with 1, 2 with 2, and the like since they're not different indexes. worse case runtime = 1/2 n² which amounts to O(n²) unfortunately. Thanks for your reply Greg Young [MVP] wrote: Show quoteHide quote > Also O(n^2) is talking about the worst case ... you have provided the best > case as a comparison ... > > to compare the worst case in this problem you would actually be looking at > iterations on a miss .. > > array 1,2,3,4 sum 12 > array 3,2,1,4 sum 12 > > in the onsorted case you have O^2 (loop through all twice) .. 16 > > in the sorted case you would be with almost no effort at 9 comparisons on > the worst case as it would allow you to do the simple change in the original > code (use i+1 for j instead of 0) > > > "MSDN" <sql_agent***@hotmail.com> wrote in message > news:%23EwKSEaaGHA.4564@TK2MSFTNGP03.phx.gbl... > > This is Sorted > > array 1,2,3,4 sum = 5 > > > > This is not Sorted > > array 1,4,2,3 sum = 5 > > > > Which one is faster?? > > > > SA > > > > "Greg Young [MVP]" <DruckDruckGo***@hotmail.com> wrote in message > > news:OMlt4xZaGHA.440@TK2MSFTNGP05.phx.gbl... > >> If the data were sorted you could do much better. If they are not sorted > >> you > >> would have n^2 as your worst case as you have to check every index of the > >> array for each value. > >> > >> even so you could still do slightly better by only issuing a single > >> add/sub > >> instead of a operation on every iteration ... see example. > >> > >> bool MyPairSum(int [] array, int sum) > >> { > >> for (int i = 0; i < array.Length; i++) > >> { > >> int need = sum - array[j]; > >> for (int j = 0; j < array.Length; j++) > >> { > >> if (array[j] == sum) > >> return true; > >> } > >> } > >> return false; > >> } > >> > >> Also your code has failure modes because int j = i + 1 ... what about the > >> following data? > >> > >> array 0,1,2 sum = 3 by using i+1 you say it doesn't exist. > >> > >> Another quick question ... what should the behavior be for the following? > >> > >> array 1,2,3,4 sum = 5 > >> > >> Cheers, > >> > >> Greg > >> > >> <karan.sha***@gmail.com> wrote in message > >> news:1146101141.203814.21600@i39g2000cwa.googlegroups.com... > >> Hey all, > >> > >> > >> I was asked this question in an interview recently: > >> > >> Suppose you have the method signature > >> > >> bool MyPairSum(int [] array, int sum) > >> > >> the array has all unique values (no repeats), your task is to find two > >> indices in the array whose sum equals the input parameter sum. If there > >> exists two entries in the array that sum together to equal the input > >> parameter of sum, then return true, otherwise return false. what's the > >> most efficient implementation? > >> > >> My question is can we have a better worse case runtime of O(n²) ?? > >> I'm thinking that in the worse case, you'd have to compare each index > >> against all the other indices and test each sum until you find one that > >> matches the input sum. In the worse case, there will be no pair of > >> indices that equal the input sum parameter. Am I overlooking a very > >> basic trick? I figured with all the sharp people in here, somebody can > >> discern whether I'm off base or not :) > >> > >> Here's the sample implementation I was thinking of: > >> > >> > >> bool MyPairSum(int [] array, int sum) > >> { > >> for (int i = 0; i < array.Length; i++) > >> { > >> for (int j = i + 1; j < array.Length; j++) > >> { > >> if ( array[i] + array[j] == sum) > >> return true; > >> } > >> } > >> return false; > >> } > >> > >> > >> Tks, Karan S. > >> > >> > > > > It does seem like there's no way around checking all possibilties
unless some other data structure was involved. I was trying to cut down on comparisons/summations by eliminating the first element, then the second, so the over run time would be on the order of n ( n - 1 ) ---------------- 2 in the worse case, which basically is O(n²). like from your example comparisons: 1 with 2, 1 with 3, 1 with 4, 2 with 3, 2 with 4, 3 with 4 (done, all combos tested). You wouldn't compare 1 with 1, 2 with 2, and the like since they're not different indexes. worse case runtime = 1/2 n² which amounts to O(n²) unfortunately. Thanks for your reply Greg Young [MVP] wrote: Show quoteHide quote > Also O(n^2) is talking about the worst case ... you have provided the best > case as a comparison ... > > to compare the worst case in this problem you would actually be looking at > iterations on a miss .. > > array 1,2,3,4 sum 12 > array 3,2,1,4 sum 12 > > in the onsorted case you have O^2 (loop through all twice) .. 16 > > in the sorted case you would be with almost no effort at 9 comparisons on > the worst case as it would allow you to do the simple change in the original > code (use i+1 for j instead of 0) > > > "MSDN" <sql_agent***@hotmail.com> wrote in message > news:%23EwKSEaaGHA.4564@TK2MSFTNGP03.phx.gbl... > > This is Sorted > > array 1,2,3,4 sum = 5 > > > > This is not Sorted > > array 1,4,2,3 sum = 5 > > > > Which one is faster?? > > > > SA > > > > "Greg Young [MVP]" <DruckDruckGo***@hotmail.com> wrote in message > > news:OMlt4xZaGHA.440@TK2MSFTNGP05.phx.gbl... > >> If the data were sorted you could do much better. If they are not sorted > >> you > >> would have n^2 as your worst case as you have to check every index of the > >> array for each value. > >> > >> even so you could still do slightly better by only issuing a single > >> add/sub > >> instead of a operation on every iteration ... see example. > >> > >> bool MyPairSum(int [] array, int sum) > >> { > >> for (int i = 0; i < array.Length; i++) > >> { > >> int need = sum - array[j]; > >> for (int j = 0; j < array.Length; j++) > >> { > >> if (array[j] == sum) > >> return true; > >> } > >> } > >> return false; > >> } > >> > >> Also your code has failure modes because int j = i + 1 ... what about the > >> following data? > >> > >> array 0,1,2 sum = 3 by using i+1 you say it doesn't exist. > >> > >> Another quick question ... what should the behavior be for the following? > >> > >> array 1,2,3,4 sum = 5 > >> > >> Cheers, > >> > >> Greg > >> > >> <karan.sha***@gmail.com> wrote in message > >> news:1146101141.203814.21600@i39g2000cwa.googlegroups.com... > >> Hey all, > >> > >> > >> I was asked this question in an interview recently: > >> > >> Suppose you have the method signature > >> > >> bool MyPairSum(int [] array, int sum) > >> > >> the array has all unique values (no repeats), your task is to find two > >> indices in the array whose sum equals the input parameter sum. If there > >> exists two entries in the array that sum together to equal the input > >> parameter of sum, then return true, otherwise return false. what's the > >> most efficient implementation? > >> > >> My question is can we have a better worse case runtime of O(n²) ?? > >> I'm thinking that in the worse case, you'd have to compare each index > >> against all the other indices and test each sum until you find one that > >> matches the input sum. In the worse case, there will be no pair of > >> indices that equal the input sum parameter. Am I overlooking a very > >> basic trick? I figured with all the sharp people in here, somebody can > >> discern whether I'm off base or not :) > >> > >> Here's the sample implementation I was thinking of: > >> > >> > >> bool MyPairSum(int [] array, int sum) > >> { > >> for (int i = 0; i < array.Length; i++) > >> { > >> for (int j = i + 1; j < array.Length; j++) > >> { > >> if ( array[i] + array[j] == sum) > >> return true; > >> } > >> } > >> return false; > >> } > >> > >> > >> Tks, Karan S. > >> > >> > > > > I guess in my code, the unSorted one would be faster in this specific
test case :). I'm trying to think of way to implement some pre-made data structure in .NET where you'd add each value to it as you pass through the array, then query against the structure somehow. Although, this would a best case run time of one pass and adding to the data structure (cn) and the cost of querying the data structure (c). This should result in a run time of c²n. Then again, the time cost of the data structure may be quite big too. I was thinking of something like a SortedList and then going from there. This interview question may have more of a way to see how I approach problems than what sort of solutions I come up with. Thanks for your reply! MSDN wrote: Show quoteHide quote > This is Sorted > array 1,2,3,4 sum = 5 > > This is not Sorted > array 1,4,2,3 sum = 5 > > Which one is faster?? > > SA > > "Greg Young [MVP]" <DruckDruckGo***@hotmail.com> wrote in message > news:OMlt4xZaGHA.440@TK2MSFTNGP05.phx.gbl... > > If the data were sorted you could do much better. If they are not sorted > > you > > would have n^2 as your worst case as you have to check every index of the > > array for each value. > > > > even so you could still do slightly better by only issuing a single > > add/sub > > instead of a operation on every iteration ... see example. > > > > bool MyPairSum(int [] array, int sum) > > { > > for (int i = 0; i < array.Length; i++) > > { > > int need = sum - array[j]; > > for (int j = 0; j < array.Length; j++) > > { > > if (array[j] == sum) > > return true; > > } > > } > > return false; > > } > > > > Also your code has failure modes because int j = i + 1 ... what about the > > following data? > > > > array 0,1,2 sum = 3 by using i+1 you say it doesn't exist. > > > > Another quick question ... what should the behavior be for the following? > > > > array 1,2,3,4 sum = 5 > > > > Cheers, > > > > Greg > > > > <karan.sha***@gmail.com> wrote in message > > news:1146101141.203814.21600@i39g2000cwa.googlegroups.com... > > Hey all, > > > > > > I was asked this question in an interview recently: > > > > Suppose you have the method signature > > > > bool MyPairSum(int [] array, int sum) > > > > the array has all unique values (no repeats), your task is to find two > > indices in the array whose sum equals the input parameter sum. If there > > exists two entries in the array that sum together to equal the input > > parameter of sum, then return true, otherwise return false. what's the > > most efficient implementation? > > > > My question is can we have a better worse case runtime of O(n²) ?? > > I'm thinking that in the worse case, you'd have to compare each index > > against all the other indices and test each sum until you find one that > > matches the input sum. In the worse case, there will be no pair of > > indices that equal the input sum parameter. Am I overlooking a very > > basic trick? I figured with all the sharp people in here, somebody can > > discern whether I'm off base or not :) > > > > Here's the sample implementation I was thinking of: > > > > > > bool MyPairSum(int [] array, int sum) > > { > > for (int i = 0; i < array.Length; i++) > > { > > for (int j = i + 1; j < array.Length; j++) > > { > > if ( array[i] + array[j] == sum) > > return true; > > } > > } > > return false; > > } > > > > > > Tks, Karan S. > > > > As you mention that this is an interview question ...
My guess is that they were looking to see how you approached the problem (and what questions you asked like "is the data sorted", "What's the general usage of the method i.e. 3 items vs 300") All of those items have alot to do with how you would want to implement the routine. <karan.sha***@gmail.com> wrote in message news:1146111861.197441.67190@y43g2000cwc.googlegroups.com... I guess in my code, the unSorted one would be faster in this specifictest case :). I'm trying to think of way to implement some pre-made data structure in .NET where you'd add each value to it as you pass through the array, then query against the structure somehow. Although, this would a best case run time of one pass and adding to the data structure (cn) and the cost of querying the data structure (c). This should result in a run time of c²n. Then again, the time cost of the data structure may be quite big too. I was thinking of something like a SortedList and then going from there. This interview question may have more of a way to see how I approach problems than what sort of solutions I come up with. Thanks for your reply! MSDN wrote: Show quoteHide quote > This is Sorted > array 1,2,3,4 sum = 5 > > This is not Sorted > array 1,4,2,3 sum = 5 > > Which one is faster?? > > SA > > "Greg Young [MVP]" <DruckDruckGo***@hotmail.com> wrote in message > news:OMlt4xZaGHA.440@TK2MSFTNGP05.phx.gbl... > > If the data were sorted you could do much better. If they are not sorted > > you > > would have n^2 as your worst case as you have to check every index of > > the > > array for each value. > > > > even so you could still do slightly better by only issuing a single > > add/sub > > instead of a operation on every iteration ... see example. > > > > bool MyPairSum(int [] array, int sum) > > { > > for (int i = 0; i < array.Length; i++) > > { > > int need = sum - array[j]; > > for (int j = 0; j < array.Length; j++) > > { > > if (array[j] == sum) > > return true; > > } > > } > > return false; > > } > > > > Also your code has failure modes because int j = i + 1 ... what about > > the > > following data? > > > > array 0,1,2 sum = 3 by using i+1 you say it doesn't exist. > > > > Another quick question ... what should the behavior be for the > > following? > > > > array 1,2,3,4 sum = 5 > > > > Cheers, > > > > Greg > > > > <karan.sha***@gmail.com> wrote in message > > news:1146101141.203814.21600@i39g2000cwa.googlegroups.com... > > Hey all, > > > > > > I was asked this question in an interview recently: > > > > Suppose you have the method signature > > > > bool MyPairSum(int [] array, int sum) > > > > the array has all unique values (no repeats), your task is to find two > > indices in the array whose sum equals the input parameter sum. If there > > exists two entries in the array that sum together to equal the input > > parameter of sum, then return true, otherwise return false. what's the > > most efficient implementation? > > > > My question is can we have a better worse case runtime of O(n²) ?? > > I'm thinking that in the worse case, you'd have to compare each index > > against all the other indices and test each sum until you find one that > > matches the input sum. In the worse case, there will be no pair of > > indices that equal the input sum parameter. Am I overlooking a very > > basic trick? I figured with all the sharp people in here, somebody can > > discern whether I'm off base or not :) > > > > Here's the sample implementation I was thinking of: > > > > > > bool MyPairSum(int [] array, int sum) > > { > > for (int i = 0; i < array.Length; i++) > > { > > for (int j = i + 1; j < array.Length; j++) > > { > > if ( array[i] + array[j] == sum) > > return true; > > } > > } > > return false; > > } > > > > > > Tks, Karan S. > > > > "Greg Young [MVP]" <DruckDruckGo***@hotmail.com> wrote in message I would *hope* that this was the interviewer's intent.news:esj3CsbaGHA.4144@TK2MSFTNGP04.phx.gbl... > As you mention that this is an interview question ... > > My guess is that they were looking to see how you approached the problem (and what questions you > asked like "is the data sorted", "What's the general usage of the method i.e. 3 items vs 300") > > All of those items have alot to do with how you would want to implement the routine. Asking "what's the most efficient implementation?" is a loaded question. Is the data sorted? Is it OK to sort the data, or do we need to copy the Array and sort that? Is the array so large that copying it causes memory issues? Is the data set small enough that O(N), O(NlogN) etc not come into play? What does the actual data normally look like? (let me Splain) If the data has very few gaps in it a brute force approach might be fastest. Example: Data = all integers from 1-100 Sum = 101 One pass through the data will suffice to find a valid result. OK, this is an extreme example, but if the data has few gaps, you will tend to get multiple valid solutions to the problem. In the example above there are 100 pairs that add up to 101 (assuming (x,y) is different from (y,x)) Thus a brute force search can succeed, possibly faster that the sort Anyway....food for thought Bill I guess in my code, the unSorted one would be faster in this specific
test case :). I'm trying to think of way to implement some pre-made data structure in .NET where you'd add each value to it as you pass through the array, then query against the structure somehow. Although, this would a best case run time of one pass and adding to the data structure (cn) and the cost of querying the data structure (c). This should result in a run time of c²n. Then again, the time cost of the data structure may be quite big too. I was thinking of something like a SortedList and then going from there. This interview question may have more of a way to see how I approach problems than what sort of solutions I come up with. Thanks for your reply! MSDN wrote: Show quoteHide quote > This is Sorted > array 1,2,3,4 sum = 5 > > This is not Sorted > array 1,4,2,3 sum = 5 > > Which one is faster?? > > SA > > "Greg Young [MVP]" <DruckDruckGo***@hotmail.com> wrote in message > news:OMlt4xZaGHA.440@TK2MSFTNGP05.phx.gbl... > > If the data were sorted you could do much better. If they are not sorted > > you > > would have n^2 as your worst case as you have to check every index of the > > array for each value. > > > > even so you could still do slightly better by only issuing a single > > add/sub > > instead of a operation on every iteration ... see example. > > > > bool MyPairSum(int [] array, int sum) > > { > > for (int i = 0; i < array.Length; i++) > > { > > int need = sum - array[j]; > > for (int j = 0; j < array.Length; j++) > > { > > if (array[j] == sum) > > return true; > > } > > } > > return false; > > } > > > > Also your code has failure modes because int j = i + 1 ... what about the > > following data? > > > > array 0,1,2 sum = 3 by using i+1 you say it doesn't exist. > > > > Another quick question ... what should the behavior be for the following? > > > > array 1,2,3,4 sum = 5 > > > > Cheers, > > > > Greg > > > > <karan.sha***@gmail.com> wrote in message > > news:1146101141.203814.21600@i39g2000cwa.googlegroups.com... > > Hey all, > > > > > > I was asked this question in an interview recently: > > > > Suppose you have the method signature > > > > bool MyPairSum(int [] array, int sum) > > > > the array has all unique values (no repeats), your task is to find two > > indices in the array whose sum equals the input parameter sum. If there > > exists two entries in the array that sum together to equal the input > > parameter of sum, then return true, otherwise return false. what's the > > most efficient implementation? > > > > My question is can we have a better worse case runtime of O(n²) ?? > > I'm thinking that in the worse case, you'd have to compare each index > > against all the other indices and test each sum until you find one that > > matches the input sum. In the worse case, there will be no pair of > > indices that equal the input sum parameter. Am I overlooking a very > > basic trick? I figured with all the sharp people in here, somebody can > > discern whether I'm off base or not :) > > > > Here's the sample implementation I was thinking of: > > > > > > bool MyPairSum(int [] array, int sum) > > { > > for (int i = 0; i < array.Length; i++) > > { > > for (int j = i + 1; j < array.Length; j++) > > { > > if ( array[i] + array[j] == sum) > > return true; > > } > > } > > return false; > > } > > > > > > Tks, Karan S. > > > > if (array[j] == sum) < == need
return true; Show quoteHide quote "Greg Young [MVP]" <DruckDruckGo***@hotmail.com> wrote in message news:OMlt4xZaGHA.440@TK2MSFTNGP05.phx.gbl... > If the data were sorted you could do much better. If they are not sorted > you > would have n^2 as your worst case as you have to check every index of the > array for each value. > > even so you could still do slightly better by only issuing a single > add/sub > instead of a operation on every iteration ... see example. > > bool MyPairSum(int [] array, int sum) > { > for (int i = 0; i < array.Length; i++) > { > int need = sum - array[j]; > for (int j = 0; j < array.Length; j++) > { > if (array[j] == sum) > return true; > } > } > return false; > } > > Also your code has failure modes because int j = i + 1 ... what about the > following data? > > array 0,1,2 sum = 3 by using i+1 you say it doesn't exist. > > Another quick question ... what should the behavior be for the following? > > array 1,2,3,4 sum = 5 > > Cheers, > > Greg > > <karan.sha***@gmail.com> wrote in message > news:1146101141.203814.21600@i39g2000cwa.googlegroups.com... > Hey all, > > > I was asked this question in an interview recently: > > Suppose you have the method signature > > bool MyPairSum(int [] array, int sum) > > the array has all unique values (no repeats), your task is to find two > indices in the array whose sum equals the input parameter sum. If there > exists two entries in the array that sum together to equal the input > parameter of sum, then return true, otherwise return false. what's the > most efficient implementation? > > My question is can we have a better worse case runtime of O(n²) ?? > I'm thinking that in the worse case, you'd have to compare each index > against all the other indices and test each sum until you find one that > matches the input sum. In the worse case, there will be no pair of > indices that equal the input sum parameter. Am I overlooking a very > basic trick? I figured with all the sharp people in here, somebody can > discern whether I'm off base or not :) > > Here's the sample implementation I was thinking of: > > > bool MyPairSum(int [] array, int sum) > { > for (int i = 0; i < array.Length; i++) > { > for (int j = i + 1; j < array.Length; j++) > { > if ( array[i] + array[j] == sum) > return true; > } > } > return false; > } > > > Tks, Karan S. > > n/m on i+1 must need coffee :)
Show quoteHide quote "Greg Young [MVP]" <DruckDruckGo***@hotmail.com> wrote in message news:OMlt4xZaGHA.440@TK2MSFTNGP05.phx.gbl... > If the data were sorted you could do much better. If they are not sorted > you > would have n^2 as your worst case as you have to check every index of the > array for each value. > > even so you could still do slightly better by only issuing a single > add/sub > instead of a operation on every iteration ... see example. > > bool MyPairSum(int [] array, int sum) > { > for (int i = 0; i < array.Length; i++) > { > int need = sum - array[j]; > for (int j = 0; j < array.Length; j++) > { > if (array[j] == sum) > return true; > } > } > return false; > } > > Also your code has failure modes because int j = i + 1 ... what about the > following data? > > array 0,1,2 sum = 3 by using i+1 you say it doesn't exist. > > Another quick question ... what should the behavior be for the following? > > array 1,2,3,4 sum = 5 > > Cheers, > > Greg > > <karan.sha***@gmail.com> wrote in message > news:1146101141.203814.21600@i39g2000cwa.googlegroups.com... > Hey all, > > > I was asked this question in an interview recently: > > Suppose you have the method signature > > bool MyPairSum(int [] array, int sum) > > the array has all unique values (no repeats), your task is to find two > indices in the array whose sum equals the input parameter sum. If there > exists two entries in the array that sum together to equal the input > parameter of sum, then return true, otherwise return false. what's the > most efficient implementation? > > My question is can we have a better worse case runtime of O(n²) ?? > I'm thinking that in the worse case, you'd have to compare each index > against all the other indices and test each sum until you find one that > matches the input sum. In the worse case, there will be no pair of > indices that equal the input sum parameter. Am I overlooking a very > basic trick? I figured with all the sharp people in here, somebody can > discern whether I'm off base or not :) > > Here's the sample implementation I was thinking of: > > > bool MyPairSum(int [] array, int sum) > { > for (int i = 0; i < array.Length; i++) > { > for (int j = i + 1; j < array.Length; j++) > { > if ( array[i] + array[j] == sum) > return true; > } > } > return false; > } > > > Tks, Karan S. > > The array isn't sorted I believe, just no dupes.Also, it just checks if
two indexes summed equals sum like array[3] + array[33] = sum !! Thanks for your input though :) Greg Young [MVP] wrote: Show quoteHide quote > If the data were sorted you could do much better. If they are not sorted you > would have n^2 as your worst case as you have to check every index of the > array for each value. > > even so you could still do slightly better by only issuing a single add/sub > instead of a operation on every iteration ... see example. > > bool MyPairSum(int [] array, int sum) > { > for (int i = 0; i < array.Length; i++) > { > int need = sum - array[j]; > for (int j = 0; j < array.Length; j++) > { > if (array[j] == sum) > return true; > } > } > return false; > } > > Also your code has failure modes because int j = i + 1 ... what about the > following data? > > array 0,1,2 sum = 3 by using i+1 you say it doesn't exist. > > Another quick question ... what should the behavior be for the following? > > array 1,2,3,4 sum = 5 > > Cheers, > > Greg > > <karan.sha***@gmail.com> wrote in message > news:1146101141.203814.21600@i39g2000cwa.googlegroups.com... > Hey all, > > > I was asked this question in an interview recently: > > Suppose you have the method signature > > bool MyPairSum(int [] array, int sum) > > the array has all unique values (no repeats), your task is to find two > indices in the array whose sum equals the input parameter sum. If there > exists two entries in the array that sum together to equal the input > parameter of sum, then return true, otherwise return false. what's the > most efficient implementation? > > My question is can we have a better worse case runtime of O(n²) ?? > I'm thinking that in the worse case, you'd have to compare each index > against all the other indices and test each sum until you find one that > matches the input sum. In the worse case, there will be no pair of > indices that equal the input sum parameter. Am I overlooking a very > basic trick? I figured with all the sharp people in here, somebody can > discern whether I'm off base or not :) > > Here's the sample implementation I was thinking of: > > > bool MyPairSum(int [] array, int sum) > { > for (int i = 0; i < array.Length; i++) > { > for (int j = i + 1; j < array.Length; j++) > { > if ( array[i] + array[j] == sum) > return true; > } > } > return false; > } > > > Tks, Karan S. karan.sha***@gmail.com wrote:
>The array isn't sorted I believe, just no dupes.Also, it just checks if Well then, sort the list first O(n.log n) and then run an O(n) search>two indexes summed equals sum like array[3] + array[33] = sum !! for pairs on the sorted list! After all, O(n)+O(n.log n) = O(n.log n). -- Lucian >> After all, O(n)+O(n.log n) = O(n.log n). Um... Not really. Or, should I say, "Only in th emost theortic case".Remember the "O(X)" translates to "time = X*C + K". Hence you are arguing that "n*Clinearsearch + Klinearsearch + (n.log.n)*Csort +Ksort) < (n*n) *Csearch + Ksearch)" The problem is the Csort is *so much* greater than Csearch, n would have to be turly massive before it becomes the domain factor in the formula. e.g., let's assume all the Ks are 0, and Clinearseach == Csearch, then we get n*Csearch + (n.log.n)*CSort < (n*n)*Csearch However, the simple search really isn't n*n, it's (n*(n+1))/2, which regrouped equas n*Csearch + (n*CSort) * (log.n) < (n * (n+1)*Csearch) /2 Multply by 2 2*n*Csearch + 2*(n*CSort) * (log.n)< (n * (n-1)*Csearch) Subtract 2*n*Csearch 2 * n * CSort * log.n < n * (n-3)*Csearch divide by n: 2 * log.n *CSort < (n-3) * Csearch Putting that all together, if CSort == CSearch, sort first is faster when n >=7 if CSort == CSearch*10, sort first is faster when n >=94 if CSort == CSearch*100, sort first is faster when n >=1461 if CSort == CSearch*1000, sort first is faster when n >=19789 Now, considering the Csearch here is simply one comparison, and Csort involves spliting, joining, comparing & copying array elements, 1:1000 ratio is not out of the question. I think you are missing the point about the subtraction part ..
You lower your constant by using the code as I wrote it .. by doing the subtraction up front you avoid doing the additions. on a given iteration yours ... is j comparisons + j additions .. mine is j comparisons + 1 subtraction. bool MyPairSum(int [] array, int sum) { for (int i = 0; i < array.Length; i++) { int need = sum - array[j]; for (int j = i+1; j < array.Length; j++) { if (array[j] == need) return true; } } return false; } Another interesting question is how much data is being passed into this and how often to you expect to be in your worst case? Since the data if sorted can be done in linear time, if you expected to be in your worst case (miss) most of the time with rather large datasets being passed in it might be worth while to take a look at sorting the data first as it could end up lowerring your average case. Greg <karan.sha***@gmail.com> wrote in message news:1146111134.247647.141220@g10g2000cwb.googlegroups.com... The array isn't sorted I believe, just no dupes.Also, it just checks iftwo indexes summed equals sum like array[3] + array[33] = sum !! Thanks for your input though :) Greg Young [MVP] wrote: Show quoteHide quote > If the data were sorted you could do much better. If they are not sorted > you > would have n^2 as your worst case as you have to check every index of the > array for each value. > > even so you could still do slightly better by only issuing a single > add/sub > instead of a operation on every iteration ... see example. > > bool MyPairSum(int [] array, int sum) > { > for (int i = 0; i < array.Length; i++) > { > int need = sum - array[j]; > for (int j = 0; j < array.Length; j++) > { > if (array[j] == sum) > return true; > } > } > return false; > } > > Also your code has failure modes because int j = i + 1 ... what about the > following data? > > array 0,1,2 sum = 3 by using i+1 you say it doesn't exist. > > Another quick question ... what should the behavior be for the following? > > array 1,2,3,4 sum = 5 > > Cheers, > > Greg > > <karan.sha***@gmail.com> wrote in message > news:1146101141.203814.21600@i39g2000cwa.googlegroups.com... > Hey all, > > > I was asked this question in an interview recently: > > Suppose you have the method signature > > bool MyPairSum(int [] array, int sum) > > the array has all unique values (no repeats), your task is to find two > indices in the array whose sum equals the input parameter sum. If there > exists two entries in the array that sum together to equal the input > parameter of sum, then return true, otherwise return false. what's the > most efficient implementation? > > My question is can we have a better worse case runtime of O(n²) ?? > I'm thinking that in the worse case, you'd have to compare each index > against all the other indices and test each sum until you find one that > matches the input sum. In the worse case, there will be no pair of > indices that equal the input sum parameter. Am I overlooking a very > basic trick? I figured with all the sharp people in here, somebody can > discern whether I'm off base or not :) > > Here's the sample implementation I was thinking of: > > > bool MyPairSum(int [] array, int sum) > { > for (int i = 0; i < array.Length; i++) > { > for (int j = i + 1; j < array.Length; j++) > { > if ( array[i] + array[j] == sum) > return true; > } > } > return false; > } > > > Tks, Karan S. Did you mean to type
int need = sum - array[ i ]; ?? On Thu, 27 Apr 2006 00:47:56 -0400, "Greg Young [MVP]" <DruckDruckGo***@hotmail.com> wrote: Show quoteHide quote >I think you are missing the point about the subtraction part .. > >You lower your constant by using the code as I wrote it .. by doing the >subtraction up front you avoid doing the additions. > >on a given iteration yours ... is j comparisons + j additions .. mine is j >comparisons + 1 subtraction. > > bool MyPairSum(int [] array, int sum) > { > for (int i = 0; i < array.Length; i++) > { > int need = sum - array[j]; > for (int j = i+1; j < array.Length; j++) > { > if (array[j] == need) > return true; > } > } > return false; > } > >Another interesting question is how much data is being passed into this and >how often to you expect to be in your worst case? Since the data if sorted >can be done in linear time, if you expected to be in your worst case (miss) >most of the time with rather large datasets being passed in it might be >worth while to take a look at sorting the data first as it could end up >lowerring your average case. > >Greg ><karan.sha***@gmail.com> wrote in message >news:1146111134.247647.141220@g10g2000cwb.googlegroups.com... >The array isn't sorted I believe, just no dupes.Also, it just checks if >two indexes summed equals sum like array[3] + array[33] = sum !! > >Thanks for your input though :) > > >Greg Young [MVP] wrote: >> If the data were sorted you could do much better. If they are not sorted >> you >> would have n^2 as your worst case as you have to check every index of the >> array for each value. >> >> even so you could still do slightly better by only issuing a single >> add/sub >> instead of a operation on every iteration ... see example. >> >> bool MyPairSum(int [] array, int sum) >> { >> for (int i = 0; i < array.Length; i++) >> { >> int need = sum - array[j]; >> for (int j = 0; j < array.Length; j++) >> { >> if (array[j] == sum) >> return true; >> } >> } >> return false; >> } >> >> Also your code has failure modes because int j = i + 1 ... what about the >> following data? >> >> array 0,1,2 sum = 3 by using i+1 you say it doesn't exist. >> >> Another quick question ... what should the behavior be for the following? >> >> array 1,2,3,4 sum = 5 >> >> Cheers, >> >> Greg >> >> <karan.sha***@gmail.com> wrote in message >> news:1146101141.203814.21600@i39g2000cwa.googlegroups.com... >> Hey all, >> >> >> I was asked this question in an interview recently: >> >> Suppose you have the method signature >> >> bool MyPairSum(int [] array, int sum) >> >> the array has all unique values (no repeats), your task is to find two >> indices in the array whose sum equals the input parameter sum. If there >> exists two entries in the array that sum together to equal the input >> parameter of sum, then return true, otherwise return false. what's the >> most efficient implementation? >> >> My question is can we have a better worse case runtime of O(n²) ?? >> I'm thinking that in the worse case, you'd have to compare each index >> against all the other indices and test each sum until you find one that >> matches the input sum. In the worse case, there will be no pair of >> indices that equal the input sum parameter. Am I overlooking a very >> basic trick? I figured with all the sharp people in here, somebody can >> discern whether I'm off base or not :) >> >> Here's the sample implementation I was thinking of: >> >> >> bool MyPairSum(int [] array, int sum) >> { >> for (int i = 0; i < array.Length; i++) >> { >> for (int j = i + 1; j < array.Length; j++) >> { >> if ( array[i] + array[j] == sum) >> return true; >> } >> } >> return false; >> } >> >> >> Tks, Karan S. > Yeah its getting late, I just cant type that example in correctly.
Show quoteHide quote "Michael H." <m@m.m> wrote in message news:hck0529ubohnopr1oso3gkiaibn58uj2vs@4ax.com... > Did you mean to type > > int need = sum - array[ i ]; > > ?? > > > On Thu, 27 Apr 2006 00:47:56 -0400, "Greg Young [MVP]" > <DruckDruckGo***@hotmail.com> wrote: > >>I think you are missing the point about the subtraction part .. >> >>You lower your constant by using the code as I wrote it .. by doing the >>subtraction up front you avoid doing the additions. >> >>on a given iteration yours ... is j comparisons + j additions .. mine is j >>comparisons + 1 subtraction. >> >> bool MyPairSum(int [] array, int sum) >> { >> for (int i = 0; i < array.Length; i++) >> { >> int need = sum - array[j]; >> for (int j = i+1; j < array.Length; j++) >> { >> if (array[j] == need) >> return true; >> } >> } >> return false; >> } >> >>Another interesting question is how much data is being passed into this >>and >>how often to you expect to be in your worst case? Since the data if sorted >>can be done in linear time, if you expected to be in your worst case >>(miss) >>most of the time with rather large datasets being passed in it might be >>worth while to take a look at sorting the data first as it could end up >>lowerring your average case. >> >>Greg >><karan.sha***@gmail.com> wrote in message >>news:1146111134.247647.141220@g10g2000cwb.googlegroups.com... >>The array isn't sorted I believe, just no dupes.Also, it just checks if >>two indexes summed equals sum like array[3] + array[33] = sum !! >> >>Thanks for your input though :) >> >> >>Greg Young [MVP] wrote: >>> If the data were sorted you could do much better. If they are not sorted >>> you >>> would have n^2 as your worst case as you have to check every index of >>> the >>> array for each value. >>> >>> even so you could still do slightly better by only issuing a single >>> add/sub >>> instead of a operation on every iteration ... see example. >>> >>> bool MyPairSum(int [] array, int sum) >>> { >>> for (int i = 0; i < array.Length; i++) >>> { >>> int need = sum - array[j]; >>> for (int j = 0; j < array.Length; j++) >>> { >>> if (array[j] == sum) >>> return true; >>> } >>> } >>> return false; >>> } >>> >>> Also your code has failure modes because int j = i + 1 ... what about >>> the >>> following data? >>> >>> array 0,1,2 sum = 3 by using i+1 you say it doesn't exist. >>> >>> Another quick question ... what should the behavior be for the >>> following? >>> >>> array 1,2,3,4 sum = 5 >>> >>> Cheers, >>> >>> Greg >>> >>> <karan.sha***@gmail.com> wrote in message >>> news:1146101141.203814.21600@i39g2000cwa.googlegroups.com... >>> Hey all, >>> >>> >>> I was asked this question in an interview recently: >>> >>> Suppose you have the method signature >>> >>> bool MyPairSum(int [] array, int sum) >>> >>> the array has all unique values (no repeats), your task is to find two >>> indices in the array whose sum equals the input parameter sum. If there >>> exists two entries in the array that sum together to equal the input >>> parameter of sum, then return true, otherwise return false. what's the >>> most efficient implementation? >>> >>> My question is can we have a better worse case runtime of O(n²) ?? >>> I'm thinking that in the worse case, you'd have to compare each index >>> against all the other indices and test each sum until you find one that >>> matches the input sum. In the worse case, there will be no pair of >>> indices that equal the input sum parameter. Am I overlooking a very >>> basic trick? I figured with all the sharp people in here, somebody can >>> discern whether I'm off base or not :) >>> >>> Here's the sample implementation I was thinking of: >>> >>> >>> bool MyPairSum(int [] array, int sum) >>> { >>> for (int i = 0; i < array.Length; i++) >>> { >>> for (int j = i + 1; j < array.Length; j++) >>> { >>> if ( array[i] + array[j] == sum) >>> return true; >>> } >>> } >>> return false; >>> } >>> >>> >>> Tks, Karan S. >> One change to this (actually the problem was in every one)
bool MyPairSum(int [] array, int sum) { for (int i = 0; i < array.Length -1; i++) { int need = sum - array[j]; for (int j = i+1; j < array.Length; j++) { if (array[j] == need) return true; } } return false; } Without the "array.Length -1" in the "for (i=" line, j would equal Length+1, and "array[j]" would blow up (except we would actually enter the second for()), but we would go through the outer loop one more time than necessary --- and our goal *is* to be the most efficient. "Greg Young [MVP]" <DruckDruckGo***@hotmail.com> wrote in message How would sorted data change things?news:OMlt4xZaGHA.440@TK2MSFTNGP05.phx.gbl... > If the data were sorted you could do much better. If they are not sorted > you > would have n^2 as your worst case as you have to check every index of the > array for each value. Show quoteHide quote > int j = i + 1 does not cause a failure. It avoids comparing a number against > even so you could still do slightly better by only issuing a single > add/sub > instead of a operation on every iteration ... see example. > > bool MyPairSum(int [] array, int sum) > { > for (int i = 0; i < array.Length; i++) > { > int need = sum - array[j]; > for (int j = 0; j < array.Length; j++) > { > if (array[j] == sum) > return true; > } > } > return false; > } > > Also your code has failure modes because int j = i + 1 ... what about the > following data? itself which you do in your example. In your example you would return True incorrectly with 0,2,3 sum = 4 > Original return True correctly> array 0,1,2 sum = 3 by using i+1 you say it doesn't exist. > Same here> Another quick question ... what should the behavior be for the following? > > array 1,2,3,4 sum = 5 Show quoteHide quote > > Cheers, > > Greg > > <karan.sha***@gmail.com> wrote in message > news:1146101141.203814.21600@i39g2000cwa.googlegroups.com... > Hey all, > > > I was asked this question in an interview recently: > > Suppose you have the method signature > > bool MyPairSum(int [] array, int sum) > > the array has all unique values (no repeats), your task is to find two > indices in the array whose sum equals the input parameter sum. If there > exists two entries in the array that sum together to equal the input > parameter of sum, then return true, otherwise return false. what's the > most efficient implementation? > > My question is can we have a better worse case runtime of O(n²) ?? > I'm thinking that in the worse case, you'd have to compare each index > against all the other indices and test each sum until you find one that > matches the input sum. In the worse case, there will be no pair of > indices that equal the input sum parameter. Am I overlooking a very > basic trick? I figured with all the sharp people in here, somebody can > discern whether I'm off base or not :) > > Here's the sample implementation I was thinking of: > > > bool MyPairSum(int [] array, int sum) > { > for (int i = 0; i < array.Length; i++) > { > for (int j = i + 1; j < array.Length; j++) > { > if ( array[i] + array[j] == sum) > return true; > } > } > return false; > } > > > Tks, Karan S. > > Why sorted data? - Well sorted data would allow it to be done in O(n) to
start with ... I already retracted the i+1 above. This question - array 1,2,3,4 sum = 5 is because there are 2 answers. Show quoteHide quote "SP" <ecneserpeg***@hotmail.com> wrote in message news:eC9SqhfaGHA.1348@TK2MSFTNGP05.phx.gbl... > "Greg Young [MVP]" <DruckDruckGo***@hotmail.com> wrote in message > news:OMlt4xZaGHA.440@TK2MSFTNGP05.phx.gbl... >> If the data were sorted you could do much better. If they are not sorted >> you >> would have n^2 as your worst case as you have to check every index of the >> array for each value. > > How would sorted data change things? > >> >> even so you could still do slightly better by only issuing a single >> add/sub >> instead of a operation on every iteration ... see example. >> >> bool MyPairSum(int [] array, int sum) >> { >> for (int i = 0; i < array.Length; i++) >> { >> int need = sum - array[j]; >> for (int j = 0; j < array.Length; j++) >> { >> if (array[j] == sum) >> return true; >> } >> } >> return false; >> } >> >> Also your code has failure modes because int j = i + 1 ... what about the >> following data? > > int j = i + 1 does not cause a failure. It avoids comparing a number > against itself which you do in your example. In your example you would > return True incorrectly with 0,2,3 sum = 4 > >> >> array 0,1,2 sum = 3 by using i+1 you say it doesn't exist. > > Original return True correctly > >> >> Another quick question ... what should the behavior be for the following? >> >> array 1,2,3,4 sum = 5 > > Same here > >> >> Cheers, >> >> Greg >> >> <karan.sha***@gmail.com> wrote in message >> news:1146101141.203814.21600@i39g2000cwa.googlegroups.com... >> Hey all, >> >> >> I was asked this question in an interview recently: >> >> Suppose you have the method signature >> >> bool MyPairSum(int [] array, int sum) >> >> the array has all unique values (no repeats), your task is to find two >> indices in the array whose sum equals the input parameter sum. If there >> exists two entries in the array that sum together to equal the input >> parameter of sum, then return true, otherwise return false. what's the >> most efficient implementation? >> >> My question is can we have a better worse case runtime of O(n²) ?? >> I'm thinking that in the worse case, you'd have to compare each index >> against all the other indices and test each sum until you find one that >> matches the input sum. In the worse case, there will be no pair of >> indices that equal the input sum parameter. Am I overlooking a very >> basic trick? I figured with all the sharp people in here, somebody can >> discern whether I'm off base or not :) >> >> Here's the sample implementation I was thinking of: >> >> >> bool MyPairSum(int [] array, int sum) >> { >> for (int i = 0; i < array.Length; i++) >> { >> for (int j = i + 1; j < array.Length; j++) >> { >> if ( array[i] + array[j] == sum) >> return true; >> } >> } >> return false; >> } >> >> >> Tks, Karan S. >> >> > > Here is a minor adaptation that may save some iterations depending upon
the sum you're asking for and what data is in the array. Starting with James Curran's code: bool MyPairSum(int [] array, int sum) { if (array.Length == 0) { return false; } int minValue = array[0]; int maxValue = array[0]; int need; // Do the first pass through the array need = sum - array[0]; for (int j = 1; j < array.Length; j++) { if (array[j] == need) { return true; } if (array[j] < minValue) minValue = array[j]; if (array[j] > maxValue) maxValue = array[k]; } // Now do the rest for (int i = 1; i < array.Length -1; i++) { need = sum - array[j]; if (minValue <= need && need <= maxValue) { for (int j = i+1; j < array.Length; j++) { if (array[j] == need) return true; } } } return false; } This eliminates cases in which the value at array[i] is such that no value in the array could possibly combine with it to sum to "sum". If the array contents were sufficiently disparate this could save time. Of course, if the array contents and the sum are such that almost any pair of values could potentially sum to "sum" then the additional test adds two comparisons and an && operation to the cost. In addition possibly you can add some "History-Efficiency-Metrics" of
previous executions and predict or guestimate an algorithm to use. at times it could be the wrong algorithm efficiency wise. This is done in Microprocessors today when doing look ahead calculations. Basically you are processing op-code ahead of time predicting that the processing logic might need the look-ahead calculation. SA Show quoteHide quote "Bruce Wood" <brucew***@canada.com> wrote in message news:1146158134.339358.50100@e56g2000cwe.googlegroups.com... > Here is a minor adaptation that may save some iterations depending upon > the sum you're asking for and what data is in the array. Starting with > James Curran's code: > > bool MyPairSum(int [] array, int sum) > { > if (array.Length == 0) { return false; } > > int minValue = array[0]; > int maxValue = array[0]; > int need; > > // Do the first pass through the array > need = sum - array[0]; > for (int j = 1; j < array.Length; j++) > { > if (array[j] == need) { return true; } > if (array[j] < minValue) minValue = array[j]; > if (array[j] > maxValue) maxValue = array[k]; > } > > // Now do the rest > for (int i = 1; i < array.Length -1; i++) > { > need = sum - array[j]; > if (minValue <= need && need <= maxValue) > { > for (int j = i+1; j < array.Length; j++) > { > if (array[j] == need) > return true; > } > } > } > return false; > } > > This eliminates cases in which the value at array[i] is such that no > value in the array could possibly combine with it to sum to "sum". If > the array contents were sufficiently disparate this could save time. > > Of course, if the array contents and the sum are such that almost any > pair of values could potentially sum to "sum" then the additional test > adds two comparisons and an && operation to the cost. > As Michael H pointed out above, that should be:
need = sum - array[i]; not need = sum - array[j]; As was pointed out by some of the other posters, the best algorithm
depends on the number of items in the array. Unless it is specifically mentioned in the question it is usually best that the algorithm should work with any indata size and therefore, the O() is the easiest thing to look at. An O(n*log n) solution has been posted in this thread. It consists of cloning the array, sorting it and finally traverse at it from both ends. Here is some sample code for it: public static bool MyPairSumSorted(int[] array2, int sum) { int[] array = (int[])array2.Clone(); Array.Sort(array); int i1 = 0; int i2 = array.Length - 1; while (i1 != i2) { int compare = array[i1] + array[i2] - sum; if (compare < 0) { i1++; } else if (compare > 0) { i2--; } else return true; } return false; } If the indata array is small, it will however be more efficent to use your method and avoid sorting. It will perform significantly when the indata is small. public static bool MyPairSum(int[] array, int sum) { for (int i = 0; i < array.Length; i++) { int need = sum - array[i]; for (int j = i+1; j < array.Length; j++) { if (array[j] == need) return true; } } return false; } The point where both method perform equally well seems to be when the array contains a little more than 100 items. Finally there is a meta method that is often used when an algorithm performs well with large data and less well with small data. You basically use the best of both worlds. It basically looks like this. const int cutoffPoint = 110; public static bool MyPairSumBoth(int[] array, int sum) { if(array.Length > cutoffPoint) MyPairSumSorted(array,sum); else MyPairSum(array,sum); } This will use the method that is best for the specific array. The disadvantage off this method is that it uses more code since both solutions has to be provided, but it can work efficently with any data size. -- Marcus Andrén  
Other interesting topics
ContextSwitchDeadlock
Type.GetType(String) not working Using CollectionBase Return month from dropdown as integer Some construction that I don't understand why it works as it does. Data binding an array to a listbox REGEX vs Stack Tokenizer? Salamander Online Decompiler v2 available WindowsIdentity and Non-AD directory services Calling .NET Framework v2.0 assembly from a v1.x Application |
|||||||||||||||||||||||
