Nitriq Blog - Programming Job Interview Challenge #10 Answer

Programming Job Interview Challenge #10 Answer

If you select the text below, you can find the answer for this week's Job Interview Challenge #10 from dev102.com.

This is a fairly easy problem, you can find the missing number by taking the difference of the sum of the numbers you're given and what the total should be for 1 to n. If you actually do the sum of 1 to n via a for loop, the time complexity is O(2n), which is really just O(n), but if you want to get picky, you can make it actually O(1n) by only looping through the list you're handed and instead using the formula n(n+1)/2 to get the total of the numbers from 1 to n.

public static void FindMissingNumbers()
{
    //The O(n) that I discussed above is for
    //the FindMissingNumber method only

    int n = 100;
    List<int> numbers = CreateRandomList(n);
    Console.WriteLine("Found:     Left Out Number is: " + FindMissingNumber(numbers));

    n = 1000;
    numbers = CreateRandomList(n);
    Console.WriteLine("Found:     Left Out Number is: " + FindMissingNumber(numbers));

    n = 10000;
    numbers = CreateRandomList(n);
    Console.WriteLine("Found:     Left Out Number is: " + FindMissingNumber(numbers));

   //sample output
   //Generated: Left Out Number is: 31
   //Found:     Left Out Number is: 31
   //Generated: Left Out Number is: 840
   //Found:     Left Out Number is: 840
   //Generated: Left Out Number is: 6289
   //Found:     Left Out Number is: 6289

}

public static int FindMissingNumber(List<int> numbers)
{
    int numbersSum = numbers.Sum();
    int n = numbers.Count;
    int sum1ToNPlus1 = (n * (n + 1)) / 2; // this is much quicker than actually summing 1 through n+1

    return sum1ToNPlus1 - numbersSum;
}

public static List<int> CreateRandomList(int n)
{
    int nPlus1 = n + 1;
    List<int> allNumbersList = new List<int>();
    for (int i = 0; i < nPlus1; i++)
        allNumbersList.Add(i);

    Random rand = new Random();

    List<int> subsetNumbersList = new List<int>();
    while (allNumbersList.Count > 1)
    {
        int index = rand.Next(allNumbersList.Count);
        subsetNumbersList.Add(allNumbersList[index]);
        allNumbersList.RemoveAt(index);
    }

    Console.WriteLine("Generated: Left Out Number is: " + allNumbersList[0]);

    return subsetNumbersList;
}

Tuesday, July 1, 2008 - 11:00 AM CST - Permalink - Comments [0]
Tags:

Comments are closed.