Re: Simple but confusing algorith question
- From: "Greg Young [MVP]" <DruckDruckGoose@xxxxxxxxxxx>
- Date: Thu, 27 Apr 2006 01:25:23 -0400
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.
.
- Follow-Ups:
- Re: Simple but confusing algorith question
- From: Bill Butler
- Re: Simple but confusing algorith question
- References:
- Simple but confusing algorith question
- From: karan . shashi
- Re: Simple but confusing algorith question
- From: Greg Young [MVP]
- Re: Simple but confusing algorith question
- From: MSDN
- Re: Simple but confusing algorith question
- From: karan . shashi
- Simple but confusing algorith question
- Prev by Date: Re: Simple but confusing algorith question
- Next by Date: Re: Performance question
- Previous by thread: Re: Simple but confusing algorith question
- Next by thread: Re: Simple but confusing algorith question
- Index(es):
Relevant Pages
|
