Interview Question: Find the Missing Numbers Between 0 and Infinity

October 13, 2012 nateb Interviewing, Technology, 0

You are given a grab bag full of numbers. These numbers will be integers between zero and Max Integer. The numbers are not sorted in any way. Write a method that will return all every value not in this range.

Answer:

Given that it will not be possible to actually give this as a List of Integers; the values need to be returned as a collection of Ranges. A range is defined as a Start to End point.

public class Range
{
  public int Start;
  public int End;
  public override string ToString()
  {
    return string.Format("{0} to {1}",
      Start, End);
  }
}

Then its just a matter of walking the grab bag and fixing up the range segments as values are known to exist.

public static List MissingValues(IEnumerable<int> grabBag)
{
    if (grabBag == null)
        throw new ArgumentNullException("grabBag");

    //  Declare initial range (everything missing)
    var segments = new List();
    segments.Add(new Range { Start =0, End = int.MaxValue });

    foreach (var number in grabBag)
    {
        //  Enumerate the segments
        for (var i = 0; i < segments.Count; i++)
        {
            //
            //  Fix segment if range overlaps
            var actedOnSegment = false;
            if(segments[i].Start == number)
            {
                segments[i].Start = number+1;
                actedOnSegment = true;
            }
            else if(segments[i].End == number)
            {
                segments[i].End = number-1;
                actedOnSegment = true;
            }
            else if (segments[i].Start < number                 
                 && segments[i].End > number)
            {
                var oldEnd = segments[i].End;
                segments[i].End = number - 1;

                segments.Insert(i + 1, new Range { 
                  Start = number + 1, 
                  End = oldEnd });
            }

            //  If did something we can stop searching
            if (actedOnSegment)
            {
                break;
            }
        }
    }

    return segments;
}

Interview Question: Validate Parantheses Align A Simple BITS Client Written In PowerShell and C#