I was doing a coding test (for practice) that went something like this:

Input is a string with |'s and *'s.
E.g. **|*|*|**|***

Implement the function:
List<int> countItems(string line, List<int> startLocations, List<int> endLocations)

Count the number of * characters that are between an opening and closing pair of | characters.

Where the 2 locations are arrays with the start and end locations (indices) to consider withing the string line.

For example if line = *|*|* and startLocations = [1] and endLocations = [3] it means I need to check the substring *|*.
And since there is only 1 pipe, the result is zero.
The location values seemed to be 1-based and not 0-based for some reason.

If the range was 1 and 5, for example, the result would be 1 because there is only 1 * between pipes.

The code I came up with that did manage to solve about half the test cases is as follows:

List<int> countItems(string line, List<int> startLocations, List<int> endLocations)
{
    var results = new List<int>();
    
    if (String.IsNullOrWhiteSpace(line) || startLocations.Count == 0)
    {
        return results;
    }

    for (var i = 0; i < startLocations.Count; i  )
    {
        var startIndex = startLocations[i] - 1;
        var endIndex = endLocations[i] - 1;

        var start = false;
        var total = 0;
        var tempTotal = 0;

        for (var j = startIndex; j < endIndex; j  )
        {
            if (!start && line[j] == '|')
            {
                start = true;
                tempTotal = 0;
            }
            else if (start && line[j] == '*')
            {
                tempTotal  ;
            }
            else if (line[j] == '|')
            {
                total  = tempTotal;
                tempTotal = 0;
            }
        }

        if (line[endIndex] == '|')
        {
            total  = tempTotal;
        }

        results.Add(total);
    }

    return results;
}

All the test cases either passed or failed because it ran out of time.

The error said it exceeded a time of 3 seconds.

Now I couldn't see the actual data being passed into the tests, so I'm not able to test it more.

But I suspect the solution was some kind of temporary list or dictionary so as to only iterate over the string 1 time instead of many times as in my code.

I want to learn what kind of solution to use in cases like this, but not really sure if this is a common type of question where the solution has some kind of name or common concept.

I would appreciate any obvious pointers to solving this type of question or even links to similar programming challenges where I can practice more.

CodePudding user response：

In this case I think the best option would be to use stack theory. It is a variation of the parenthesis balancing problem. You can find more about it here Article parenthesis balancing problem

CodePudding user response：

I managed to redo the test and I found the answer and problem type.

This is a "plates between candles" type of problem.

I was trying to solve it myself but almost ran out of time and eventually just copy/pasted an answer I found.
This was a practice run, not an actual test or application.

This was the solution that worked... I'll be studying it to better understand it...

List<int> numberOfItems(string s, List<int> startIndices, List<int> endIndices)
{
    int q = startIndices.Count;
    int l = s.Length;

    for (var i = 0; i < startIndices.Count; i  )
    {
        startIndices[i]--;
        endIndices[i]--;
    }

    var ans = new List<int>();
    var prev = new int[l];
    var next = new int[l];
    var preSum = new int[l];

    int p = -1, nxt = -1;

    // calculating prev candle up to this index.
    for (int i = 0; i < l; i  )
    {

        if (s[i] == '|')
        {
            p = i;
        }
        prev[i] = p;
    }
    //Calculating next candle from this index.

    for (int i = l - 1; i >= 0; i--)
    {

        if (s[i] == '|')
        {
            nxt = i;
        }
        next[i] = nxt;
    }

    int c = 0;

    // calculating the number of stars between these indices.
    for (int i = 0; i < l; i  )
    {

        if (s[i] == '*')
        {
            c  ;
        }
        preSum[i] = c;
    }

    // calculating ans.
    for (int k = 0; k < q; k  )
    {

        int i = startIndices[k];
        int j = endIndices[k];

        int right = prev[j];// position of left candle.
        int left = next[i];// position of right candle.
                           //cout<<right<<left;

        if (left == -1 || right == -1 || left > right)
        {
            ans.Add(0);
        }
        else
        {
            ans.Add(preSum[right] - preSum[left]);
        }
    }
    return ans;
}