Simple but confusing algorith question

[karan.shashi]

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 + array[j] == sum)
return true;
}
}
return false;
}


Tks, Karan S.

 

[Greg Young [MVP]]

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

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 + array[j] == sum)
return true;
}
}
return false;
}


Tks, Karan S.

 

[MSDN]

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

 

[MSDN]

if (array[j] == sum) < == need
return true;

 

[Greg Young [MVP]]

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 > sum {
//skip rest of list
}

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

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

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 + array[j] == sum)
return true;
}
}
return false;
}


Tks, Karan S.

 

[Greg Young [MVP]]

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)

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

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

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 + array[j] == sum)
return true;
}
}
return false;
}


Tks, Karan S.

 

[Greg Young [MVP]]

n/m on i+1 must need coffee

 

[Lucian Wischik]

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 think it's O(n) if the list is sorted...

(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.

 

[karan.shashi]

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

 

[karan.shashi]

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

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)

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

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

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 + array[j] == sum)
return true;
}
}
return false;
}


Tks, Karan S.

 

[Lucian Wischik]

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 !!

Well then, sort the list first O(n.log n) and then run an O(n) search
for pairs on the sorted list! After all, O(n)+O(n.log n) = O(n.log n).

 

[Greg Young [MVP]]

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
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

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

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 + array[j] == sum)
return true;
}
}
return false;
}


Tks, Karan S.

 

[karan.shashi]

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!

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

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 aboutthe
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

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 + array[j] == sum)
return true;
}
}
return false;
}


Tks, Karan S.

 

[karan.shashi]

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

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)

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

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

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 + array[j] == sum)
return true;
}
}
return false;
}


Tks, Karan S.

 

[karan.shashi]

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

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)

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

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

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 + array[j] == sum)
return true;
}
}
return false;
}


Tks, Karan S.

 

[Michael H.]

Did you mean to type

int need = sum - array[ i ];

??

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
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

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

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 + array[j] == sum)
return true;
}
}
return false;
}


Tks, Karan S.

 

[karan.shashi]

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!

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

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 aboutthe
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

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 + array[j] == sum)
return true;
}
}
return false;
}


Tks, Karan S.

 

[Greg Young [MVP]]

Yeah its getting late, I just cant type that example in correctly.

Did you mean to type

int need = sum - array[ i ];

??

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
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

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

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 + array[j] == sum)
return true;
}
}
return false;
}


Tks, Karan S.

 

[Greg Young [MVP]]

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.


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!

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

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

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 + array[j] == sum)
return true;
}
}
return false;
}


Tks, Karan S.

 

[SP]

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

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 + array[j] == sum)
return true;
}
}
return false;
}


Tks, Karan S.