3
\$\begingroup\$

I had to develop an algorithm that will find gap between sequential Ids within a List<long>.

For example as input we had the following List<long> = {1,2,3,6,7,8,11,12,15,16}. This means that algorithm should find the numbers 4,5,9,10,13,14 .

For this task I developed the following method, but not sure about effectiveness of this method in case of large data input, also about clean code readability.

        private const int AllowedGap = 1;

        public static List<long> FindMissingSequentialIDs(List<long> ids)
        {
            List<long> response = new List<long>();

            for (int i = 0; i < ids.Count() - 1; i++)
            {
                if (ids[i + 1] - ids[i] > AllowedGap)
                {
                    long currentGapCount = ids[i + 1] - ids[i] - 1;

                    long missedSeqId = 0;
                    while (currentGapCount != 0)
                    {
                        if (missedSeqId == 0)
                        {
                            missedSeqId = ids[i + 1] - 1;
                            response.Add(missedSeqId);

                            currentGapCount--;

                            if (currentGapCount == 0)
                            {
                                break;
                            }
                        }

                        else
                        {
                            missedSeqId = missedSeqId - 1;

                            response.Add(missedSeqId);

                            currentGapCount--;
                        }
                    }
                }
            }

            return response;
        }

Seems like this worked , but what would you improve here ?

\$\endgroup\$
9
  • \$\begingroup\$ Can we assume that input is ordered and not containing duplicates? \$\endgroup\$ Mar 23, 2023 at 14:56
  • \$\begingroup\$ I would go with a state machine, where the input is the list, the 'initial id', the gap betwen ids and a non-gap state, a gap state. The transition to the gap state (whether from a non-gap or from the gap) 'emits' the current id. This would assume ordered input and a constant gap. That way you only need to have the current state and input to determine the output. \$\endgroup\$
    – Kristian H
    Mar 23, 2023 at 15:49
  • \$\begingroup\$ Peter Csala yes we can this is actually Kafka consumed events sequential Id's which is assumed to be original and sequential(ordered) \$\endgroup\$
    – So_oP
    Mar 23, 2023 at 19:04
  • \$\begingroup\$ Are you aware of the fact that ordering guarantee is on topic's partition level, not on topic level? \$\endgroup\$ Mar 24, 2023 at 9:58
  • \$\begingroup\$ Peter Csala can you please explain bit better ? Did not understand what you tried to say \$\endgroup\$
    – So_oP
    Mar 24, 2023 at 10:06

3 Answers 3

2
\$\begingroup\$

If you're allowed to use LINQ, you can simplify. Essentially create a lazily-evaluated Range of numbers from the min to the max, then exclude those in your list, return that final lazily-evaluated list and iterate over it.

private static IEnumerable<long> GetGaps(IEnumerable<long> list)
{
    return Range(list.Min(), list.Max()).Except(list);
}

private static IEnumerable<long> Range(long start, long count)
{
    long max = start + count - 1L;
    
    if (count < 0 || max > long.MaxValue)
    {
        throw new ArgumentOutOfRangeException(nameof(count));
    }
    
    return RangeIterator(start, count);
}

private static IEnumerable<long> RangeIterator(long start, long count)
{
    for (long i = 0L; i < count; i++)
    {
        yield return start + i;
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ There is IEnumerable<int> Range(int start, int count). \$\endgroup\$
    – greybeard
    Mar 24, 2023 at 8:46
  • \$\begingroup\$ @greybeard correct- OP is specifically using longs, which is why I had to invent one for that. \$\endgroup\$ Mar 24, 2023 at 16:07
1
\$\begingroup\$

using Count() extension would count the elements of the collection on each iteration, which would impact the performance, and since you're using List<long> you can use Count property instead. ids.Count.

Current code can be simplified to something like this :

// assuming all elements are positive integers
public static IEnumerable<long> FindMissingSequentialIDs(List<long> ids)
{
    if(ids == null) throw new ArgumentNullException(nameof(ids));

    if (ids.Count == 0) yield break;
    
    ids.Sort(); // sort the elements first

    for (var i = 0; i < ids.Count - 1; i++)
    {
        var current = ids[i];

        var next = ids[i + 1];

        var gap = next - current;

        if (gap == AllowedGap) continue;

        for (var x = current + 1; x < next; x++)
            yield return x;
    }
}

This code will only read and return the missing, which means less memory allocation. You can then hook it up with another iterator or just use ToList to store the results into a new list.

Example :

var missing = FindMissingSequentialIDs(ids).ToList();
\$\endgroup\$
0
\$\begingroup\$

Your code seems to be very low level and optimzed for performance (excepting the call of Count() that was already mentioned by iSR5). However, most cases do not require that micro performance optimization so if there is no performance problem, I would go with a readable and maintainable version of the algorith.

That is usualy the usage of LINQ methods:

private static IEnumerable<int> FindGaps(List<int> list)
{
    var min = list[0];
    var max = list[list.Count - 1];
    var set = new HashSet<int>(list);
    
    return Enumerable.Range(min, max-min).Where(i => !set.Contains(i));
}

The parameter 'AllowedGap' should be passed to the method instead of defined as static field. That "extra rule" makes the algorithm a bit more complex, but I would still prefer working with lists instead of counting indices.

private static IEnumerable<int> FindGaps(List<int> list, int allowedCapCount = 1)
{
    if (list.Count == 0)
    {
        return new int[0];
    }
    
    var min = list[0];
    var max = list[list.Count - 1];
    var existing = new HashSet<int>(list);
    var stack = new List<int>();
    var gaps = new List<int>();

    foreach (var item in Enumerable.Range(min, max - min))
    {
        if (existing.Contains(item))
        {
            if (stack.Count >= allowedCapCount)
            {
                gaps.AddRange(stack);
            }
            stack.Clear();
        }
        else
        {
            stack.Add(item);
        }
    }
    
    gaps.AddRange(stack);
    
    return gaps;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.