forward and backward search algorithm on an array

Question

I'm working on a simple algorithm problem for practice and i'm trying to figure out why on about 20 percent of test cases it fails. The problem is thus, given an array of ints find the average of all valid ints in the array.

An int is valid if

It is greater than or equal to -273
at least one of the previous two or next two ints are two points away from the current one

if the int is invalid it should not be included in calculating the average. Also, I don't believe the problem wants the solution to be cyclic (not sure though just thought about it while writing this so will try) i.e. if you are at the first int array[0], then there are no previous two ints as opposed to the last two being the previous two in a cyclic array.

my strategy is summed up in the code below:

public double averageTemperature(int[] measuredValues)
{
    Queue<int> qLeft = new Queue<int>(2);
    Queue<int> qRight = new Queue<int>(2);

    double sum = 0d;
    int cnt = 0;

    for (int i = 0; i < measuredValues.Length; i++)
    {
        if (measuredValues[i] < -273)
            continue;
        if (qLeft.Count == 3)
            qLeft.Dequeue();
        for (int j = i + 1; j < measuredValues.Length; j++)
        {
            if (qRight.Count == 2)
            {
                break;
            }
            qRight.Enqueue(measuredValues[j]);
        }

        if (b(qLeft, qRight, measuredValues[i]) == true)
        {
            sum += measuredValues[i];
            cnt++;
            qLeft.Enqueue(measuredValues[i]);
        }


        qRight.Clear();
    }

    if (cnt > 0)
        return sum / cnt;
    return -300.0;
}
bool b(Queue<int> a, Queue<int> b, int c)
{
    foreach (int q in a)
    {
        if (Math.Abs(q - c) <= 2)
            return true;
    }
    foreach (int w in b)
    {
        if (Math.Abs(w - c) <= 2)
            return true;
    }
    return false;
}

However, my strategy fails for this test case

{-13, 12, -14, 11, -15, 10, -16, 9, -17, 8, -18, 7, 6, -19, 5, -400, -400, 4, -390, -300, -270, 3, -12, 3, 2}

I don't understand why. I'm i missing something obvious? i know they're might be another more efficient way of solving this but i don't want to try them until i know why my "naive" way does not work.

Well I finally figured out why thanks to you guys. Here is my revised code for those who may find it helpful:

public double averageTemperature(int[] measuredValues)
    {
        Queue<int> qLeft = new Queue<int>(2);
        Queue<int> qRight = new Queue<int>(2);

        double sum = 0d;
        int cnt = 0;


        for (int i = 0; i < measuredValues.Length; i++)
        {
            if (qLeft.Count == 3)
                qLeft.Dequeue();
            for (int j = i + 1; j < measuredValues.Length; j++)
              {
                if (qRight.Count == 2)
                {
                    break;
                }
                qRight.Enqueue(measuredValues[j]);
            }

            if (isValid(qLeft, qRight, measuredValues[i]) == true)
            {
                sum += measuredValues[i];
                cnt++;

            }
            qLeft.Enqueue(measuredValues[i]);
            qRight.Clear();
        }

        if (cnt > 0)
            return sum / cnt;
        return -300.0;
    }
    bool isValid(Queue<int> a, Queue<int> b, int c)
    {

        foreach (int q in a)
        {
            if (c >=-273 && Math.Abs(q - c) <= 2)
                return true;
        }
        foreach (int w in b)
        {
            if (c >=-273 && Math.Abs(w - c) <= 2)
                return true;
        }
        return false;
    }

is it "273" or "-273"? from your test case, i m guessing it will be "-273". — Wasif Hossain
– Wasif Hossain, Commented Feb 13, 2014 at 6:38
I'm not sure what you mean by "two points", but the data set you've given contains no elements in which the element two behind or ahead == the value of the current element +/- 2. — ormaaj
– ormaaj, Commented Feb 13, 2014 at 7:55
@ormaaj let me explain. -13 is valid because at least one element that is at most 2 elements away is at most 2 points greater than or smaller than -13. So 12 is obviously not 2 points away from -13 but -14 is only 1 point away from -13. So -13 is valid. If both 2 elements ahead of -13 were > +/- 2 points than -13 would be invalid. — TheJackal
– TheJackal, Commented Feb 13, 2014 at 11:23

Ronnie · Accepted Answer · 2014-02-13 06:22:02Z

1

try starting at the same point in the nested for() loop when comparing. like this: what do you get when you run it?

public double averageTemperature(int[] measuredValues)
{
Queue<int> qLeft = new Queue<int>(2);
Queue<int> qRight = new Queue<int>(2);

double sum = 0d;
int cnt = 0;

for (int i = 0; i < measuredValues.Length; i++)
{
    if (measuredValues[i] < -273)
        continue;
    if (qLeft.Count == 3)
        qLeft.Dequeue();
    for (int j = 0; j < measuredValues.Length; j++)
    {
        if (qRight.Count == 2)
        {
            break;
        }
        qRight.Enqueue(measuredValues[j]);
    }

    if (b(qLeft, qRight, measuredValues[i]) == true)
    {
        sum += measuredValues[i];
        cnt++;
        qLeft.Enqueue(measuredValues[i]);
    }


    qRight.Clear();
}

if (cnt > 0)
    return sum / cnt;
return -300.0;
}
bool b(Queue<int> a, Queue<int> b, int c)
{
foreach (int q in a)
{
    if (Math.Abs(q - c) <= 2)
        return true;
}
foreach (int w in b)
{
    if (Math.Abs(w - c) <= 2)
        return true;
}
return false;
}

is it adding one each direction to put you two away like you were before?

answered Feb 13, 2014 at 6:22

Ronnie

2392 silver badges9 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

TheJackal Over a year ago

Queue right should have at most two ints to the right of the current int. So starting at 0 will not work for sure

Ronnie Over a year ago

then start at i + 2 instead of i + 1 and see how that does.

Wasif Hossain · Accepted Answer · 2014-02-13 07:08:36Z

0

You are enqueuing into qLeft only when the current value in the array is valid, but this is not right. You need to enqueue into qLeft at each iteration of the outer for-loop that is being controlled by i.

See the following code:

for (int i = 0; i < measuredValues.Length; i++)
{
    if (measuredValues[i] < -273)
        continue;
    if (qLeft.Count == 3)
        qLeft.Dequeue();
    for (int j = i + 1; j < measuredValues.Length; j++)
    {
        if (qRight.Count == 2)
        {
            break;
        }
        qRight.Enqueue(measuredValues[j]);
    }

    if (b(qLeft, qRight, measuredValues[i]) == true)
    {
        sum += measuredValues[i];
        cnt++;
    }

    qLeft.Enqueue(measuredValues[i]); // YOU NEED TO ENQUEUE INTO qLeft EACH TIME REGARDLESS OF IT IS VALID OR INVALID
    qRight.Clear();
}

answered Feb 13, 2014 at 7:08

Wasif Hossain

3,9501 gold badge20 silver badges20 bronze badges

2 Comments

TheJackal Over a year ago

Tried that as well, all invalid ints are supposed to be discarded before computing the average. Adding an invalid int into queue left will distort the results

Wasif Hossain Over a year ago

Invalid ints are always discarded in the b() method. Invalid ints that fails in condition 1( < -273) are discarded immediately after the 1st if() inside outer loop. And those that fail in condition 2 are discarded in b() method. So why do you need to restrict the qLeft to insert only valid ints into?

Collectives™ on Stack Overflow

forward and backward search algorithm on an array

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related