Re: Simple but confusing algorith question

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.shashi@xxxxxxxxx> wrote in message
news:1146111861.197441.67190@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
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:
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]" <DruckDruckGoose@xxxxxxxxxxx> wrote in message
news:OMlt4xZaGHA.440@xxxxxxxxxxxxxxxxxxxxxxx
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.shashi@xxxxxxxxx> wrote in message
news:1146101141.203814.21600@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
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.




.

Relevant Pages

  • Re: Subset Sum problem (w/ limited scope)
    ... The "Subset Sum" problem (stated various ways depending on what you ... a subset of those integers that sums up to zero. ... Are there going to be duplicate values in your original array? ...
    (comp.lang.fortran)
  • Re: How can I find the greatest possible sum within 12 months? A newbie...
    ... It may be because you have headers, and when I tied it first I omitted ... You may have omitted to enter it as an array formula (see notes on ... the starting sum is in A2 and the end sum is in A123. ... Excel will insert them for you. ...
    (microsoft.public.excel.worksheet.functions)
  • Re: Explanation of SUMPRODUCT
    ... I don't even think you need to enter it as an array ... Yes, we know this, but in this case SUM is an array formula SUMPRODUCT ... > each element is the number of times the corresponding cell value appears ...
    (microsoft.public.excel.programming)
  • Re: Simple but confusing algorith question
    ... bool MyPairSum(int array, int sum) ... indices that equal the input sum parameter. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Simple but confusing algorith question
    ... through the array, then query against the structure somehow. ... structure and the cost of querying the data structure. ... array 1,2,3,4 sum = 5 ... indices that equal the input sum parameter. ...
    (microsoft.public.dotnet.languages.csharp)
Loading