Classic CS Programming Challenges

Does a LinkedList contain a loop...

2013-02-26T02:58:00Z

//the Console.Write(...); calls are debug and do not check for null...

#region

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;

#endregion

namespace CSChallenges
{
    internal class Node<T>
    {
        public T Value { get; set; }
        public Node<T> Next;

        public override string ToString()
        {
            return Value.ToString();
        }
    }

    internal class Program
    {
        private static void Main(string[] args)
        {
            Node<int> n1 = new Node<int> { Value = 1 };
            Node<int> n2 = new Node<int> { Value = 2 };
            Node<int> n3 = new Node<int> { Value = 3 };
            Node<int> n4 = new Node<int> { Value = 4 };
            Node<int> n5 = new Node<int> { Value = 5 };
            Node<int> n6 = new Node<int> { Value = 6 };

            n1.Next = n2;
            n2.Next = n3;
            n3.Next = n4;
            n4.Next = n6;
            n5.Next = n6;
            n6.Next = null;

            Node<int> iterator = n1;

            do
            {
                //proper check for null...
                if (iterator != null)
                {
                    Console.Write(iterator.Value + " | ");

                    iterator = iterator.Next;
                }
            } while (iterator != null); //is there an end...

            /**/
            Console.WriteLine();

            n6.Next = n1;
            iterator = n1;

            do
            {
                //proper check for null...
                if (iterator != null)
                {
                    Console.Write(iterator.Value + " | ");

                    iterator = iterator.Next;
                }
            } while (iterator != null && iterator != n1); //is there an end and assumes we know the 'head node'...

            /**/
            Console.WriteLine();

            n6.Next = n3; //set to something other than the head node...
            iterator = n2;

            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();

            //but what if we start in the 'middle' and there is a loop?
            do
            {
                //proper check for null...
                if (iterator != null)
                {
                    Console.Write(iterator.Value + " | ");

                    iterator = iterator.Next;
                }
            } while (iterator != null && iterator != n1 && stopwatch.Elapsed.TotalMilliseconds < 100); //timed loop terminator...

            //well, we'd loop forever if our Stopwatch didn't blow the whistle...
            //it isn't feasible to keep track of every value - there could be duplicates, by value.

            /**/
            Console.WriteLine();

            iterator = n2;
            Node<int> iteratorFast = n2;

            //the answer is to keep two Node<T> references, send them off at n and n+1 Next's and should n+1 detect n at n or n+1 Nodes ahead there is a loop...
            do
            {
                //proper check for null(s)...
                if (iterator != null && iteratorFast != null)
                {
                    Console.Write(iterator.Value + " " + iteratorFast.Value + " -> ");

                    //moves by 1...
                    iterator = iterator.Next;

                    //moves by 2...
                    iteratorFast = iteratorFast.Next;
                    if (iteratorFast != null)
                    {
                        iteratorFast = iteratorFast.Next;
                    }
                    else
                    {
                        //return value (true) if this were a function...
                        break;
                    }

                    Console.Write(iterator.Value + " " + iteratorFast.Value + " -> ");

                    if (iteratorFast == iterator || iteratorFast.Next == iterator)
                    {
                        //return value (true) if this were a function...
                        break;
                    }
                }
            } while (iterator != null && iteratorFast != null && iterator != n1 && iteratorFast != n1); //is there an end and assumes we know the 'head node'...

            /**/
            Console.WriteLine();

            iterator = n2;
            iteratorFast = n2;

            //or, more succinctly...
            while(iteratorFast != null && iteratorFast.Next != null)
            {
                Console.Write(iterator.Value + " " + iteratorFast.Value + " -> ");

                iterator = iterator.Next;
                iteratorFast = iteratorFast.Next.Next;

                Console.Write(iterator.Value + " " + iteratorFast.Value + " -> ");

                if(iteratorFast == iterator)
                {
                    //return value (true) if this were a function...
                    break;
                }
            }

            /**/
            Console.WriteLine();

            iterator = n2;
            iteratorFast = n2;

            //and, with an optimization...
            while (iteratorFast != null && iteratorFast.Next != null)
            {
                Console.Write(iterator.Value + " " + iteratorFast.Value + " -> ");

                iterator = iterator.Next;
                iteratorFast = iteratorFast.Next.Next;

                Console.Write(iterator.Value + " " + iteratorFast.Value + " -> ");

                if (iteratorFast == iterator || (iteratorFast != null && iteratorFast.Next == iterator))
                {
                    //return value (true) if this were a function...
                    break;
                }
            }

            Console.WriteLine();

            Console.WriteLine("Finished...");
            Console.ReadLine();
        }
    }
}

Recursively traverse a directory...

2013-02-20T01:02:00Z

#region

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;

#endregion

namespace CSChallenges
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            List<string> enumeratedFiles = new List<string>(Directory.EnumerateFiles("C:\\Applications", "*.*", SearchOption.AllDirectories));

            List<string> enumeratedFiles2 = EnumerateFiles("C:\\Applications");

            Debug.Assert(enumeratedFiles.Count == enumeratedFiles2.Count);

            for (int i = 0; i < enumeratedFiles.Count; i++)
            {
                Debug.Assert(enumeratedFiles[ i ] == enumeratedFiles2[ i ]);
            }

            Console.WriteLine("Finished...");
            Console.ReadLine();
        }

        /// <summary>
        /// This leaves out a LOT of conditions, like error handling... (Access Denied, etc.)
        /// </summary>
        /// <param name="path"></param>
        /// <returns></returns>
        public static List<string> EnumerateFiles(string path)
        {
            List<string> enumeratedFiles = new List<string>();

            EnumerateFiles(path, enumeratedFiles);

            return enumeratedFiles;
        }

        private static List<string> EnumerateFiles(string path, List<string> enumeratedFiles)
        {
            enumeratedFiles.AddRange(Directory.GetFiles(path));

            foreach (string directory in Directory.GetDirectories(path))
            {
                EnumerateFiles(directory, enumeratedFiles);
            }

            return enumeratedFiles;
        }
    }
}

FizzBuzz

2013-02-19T01:40:00Z

Write a program that prints the numbers from 1 to 100. But for multiples of three print "Fizz" instead of the number and for the multiples of five print "Buzz". For numbers which are multiples of both three and five print "FizzBuzz".

Taken from: http://www.codinghorror.com/blog/2007/02/why-cant-programmers-program.html

#region

using System;

#endregion

namespace Challenges
{
    internal class Program
    {
        public static void Main(string[] args)
        {
            //yes, I added debug...

            for (int i = 1; i <= 100; i++)
            {
                bool multipleOfThree = false;
                bool multipleOfFive = false;
                
                if(i % 3 == 0)
                {
                    multipleOfThree = true;
                }
                if (i % 5 == 0)
                {
                    multipleOfFive = true;
                }

                if(!multipleOfThree && !multipleOfFive)
                {
                    Console.WriteLine(i);
                    continue;
                }
                if (multipleOfThree && multipleOfFive)
                {
                    Console.WriteLine("FizzBuzz (" + i + ")");
                    continue;
                }
                if(multipleOfThree)
                {
                    Console.WriteLine("Fizz (" + i + ")");
                    continue;
                }
                if (multipleOfFive)
                {
                    Console.WriteLine("Buzz (" + i + ")");
                    continue;
                }
            }

            /**/

            Console.ReadLine();

            //better yet...

            for (int i = 1; i <= 100; i++)
            {
                bool printInt = true;

                if (i % 3 == 0)
                {
                    printInt = false;
                    Console.Write("Fizz");
                }
                if (i % 5 == 0)
                {
                    printInt = false;
                    Console.Write("Buzz");
                }
                if (printInt)
                {
                    Console.WriteLine(i);
                }
                else
                {
                    Console.WriteLine(" (" + i + ")");
                }
            }

            /**/

            Console.ReadLine();
        }
    }
}

Binary Search Tree Challenge

2013-02-19T01:34:00Z

#region

using System;
using System.Collections.Generic;

#endregion

namespace BinaryTreeSearch
{
    public class TreeNode<T>
    {
        public TreeNode<T> Parent { get; set; }
        public TreeNode<T> Left { get; set; }
        public TreeNode<T> Right { get; set; }
        public T Value { get; set; }

        public override string ToString()
        {
            return "Parent: " + (Parent == null ? default(T) : Parent.Value) + " Number: " + Value + " Left: " + (Left == null ? default(T) : Left.Value) + " Right: " + (Right == null ? default(T) : Right.Value);
        }
    }

    internal class Program
    {
        public static void Main(string[] args)
        {
            TreeNode<int?> treeNode = new TreeNode<int?> {Value = 100};

            AddTreeNode(treeNode, new TreeNode<int?> {Value = 95});
            AddTreeNode(treeNode, new TreeNode<int?> {Value = 105});

            /**/

            AddTreeNode(treeNode, new TreeNode<int?> {Value = 93});
            AddTreeNode(treeNode, new TreeNode<int?> {Value = 97});

            AddTreeNode(treeNode, new TreeNode<int?> {Value = 103});
            AddTreeNode(treeNode, new TreeNode<int?> {Value = 107});

            /**/

            AddTreeNode(treeNode, new TreeNode<int?> { Value = 92 });
            AddTreeNode(treeNode, new TreeNode<int?> { Value = 94 });
            AddTreeNode(treeNode, new TreeNode<int?> { Value = 96 });
            AddTreeNode(treeNode, new TreeNode<int?> { Value = 98 });

            AddTreeNode(treeNode, new TreeNode<int?> { Value = 102 });
            AddTreeNode(treeNode, new TreeNode<int?> { Value = 104 });
            AddTreeNode(treeNode, new TreeNode<int?> { Value = 106 });
            AddTreeNode(treeNode, new TreeNode<int?> { Value = 108 });

            /**/

            Console.WriteLine("DepthWiseIterationFromTheLeft");
            DepthWiseIterationFromTheLeft(treeNode);

            /**/

            Console.WriteLine("\n\nDepthWiseIterationFromTheRight");
            DepthWiseIterationFromTheRight(treeNode);

            /**/

            Console.WriteLine("\n\nBreadthWiseIterationFromTheLeft");
            BreadthWiseIterationFromTheLeft(treeNode);

            /**/

            Console.WriteLine("\n\nBreadthWiseIterationFromTheRight");
            BreadthWiseIterationFromTheRight(treeNode);

            /**/

            Console.ReadLine();
        }

        public static void AddTreeNode(TreeNode<int?> treeNode, TreeNode<int?> treeNodeToAdd)
        {
            if (treeNode == null || treeNodeToAdd == null)
            {
                return;
            }

            if (treeNodeToAdd.Value <= treeNode.Value)
            {
                if (treeNode.Left == null)
                {
                    treeNodeToAdd.Parent = treeNode;
                    treeNode.Left = treeNodeToAdd;
                }
                else
                {
                    AddTreeNode(treeNode.Left, treeNodeToAdd);
                }
            }

            if (treeNodeToAdd.Value > treeNode.Value)
            {
                if (treeNode.Right == null)
                {
                    treeNodeToAdd.Parent = treeNode;
                    treeNode.Right = treeNodeToAdd;
                }
                else
                {
                    AddTreeNode(treeNode.Right, treeNodeToAdd);
                }
            }
        }

        public static void DepthWiseIterationFromTheLeft(TreeNode<int?> treeNode)
        {
            if (treeNode == null)
            {
                return;
            }

            Console.Write(treeNode.Value + " ");

            DepthWiseIterationFromTheLeft(treeNode.Left);
            DepthWiseIterationFromTheLeft(treeNode.Right);
        }

        public static void DepthWiseIterationFromTheRight(TreeNode<int?> treeNode)
        {
            if (treeNode == null)
            {
                return;
            }

            Console.Write(treeNode.Value + " ");

            DepthWiseIterationFromTheRight(treeNode.Right);
            DepthWiseIterationFromTheRight(treeNode.Left);
        }

        public static void BreadthWiseIterationFromTheLeft(TreeNode<int?> treeNode)
        {
            if (treeNode == null)
            {
                return;
            }

            var queue = new Queue<TreeNode<int?>>();

            queue.Enqueue(treeNode);

            while(queue.Count != 0)
            {
                var treeNode2 = queue.Dequeue();

                Console.Write(treeNode2.Value + " ");

                if (treeNode2.Left != null)
                {
                    queue.Enqueue(treeNode2.Left);
                }
                if (treeNode2.Right != null)
                {
                    queue.Enqueue(treeNode2.Right);
                }
            }
        }

        public static void BreadthWiseIterationFromTheRight(TreeNode<int?> treeNode)
        {
            if (treeNode == null)
            {
                return;
            }

            var queue = new Queue<TreeNode<int?>>();

            queue.Enqueue(treeNode);

            while (queue.Count != 0)
            {
                var treeNode2 = queue.Dequeue();

                Console.Write(treeNode2.Value + " ");

                if (treeNode2.Right != null)
                {
                    queue.Enqueue(treeNode2.Right);
                }
                if (treeNode2.Left != null)
                {
                    queue.Enqueue(treeNode2.Left);
                }
            }
        }
    }
}

Reversing last names...

2013-02-12T01:40:00Z

If I have a list of first and last names in a HashSet<string>, how would I go about reversing the names?

#region

using System;
using System.Collections.Generic;

#endregion

namespace Interview
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            HashSet<string> firstAndLastNames = new HashSet<string>();

            firstAndLastNames.Add("Mike Anderson");
            firstAndLastNames.Add("Jeff Basquat");
            firstAndLastNames.Add("Paul Thompson");
            firstAndLastNames.Add("Brent Smith");
            firstAndLastNames.Add("Chris Price");

            List<string> firstNames = new List<string>();
            List<string> lastNames = new List<string>();

            foreach (string fullName in firstAndLastNames)
            {
                //assumes first and last and only one space in the name...
                string[] fullNameSplit = fullName.Split(' ');

                firstNames.Add(fullNameSplit[0]);
                lastNames.Add(fullNameSplit[1]);
            }

            HashSet<string> newFirstAndLastNames = new HashSet<string>();

            for (int i = 0, j = firstAndLastNames.Count - 1; i < firstAndLastNames.Count && j >= 0; i++, j--)
            {
                newFirstAndLastNames.Add(firstNames[ i ] + " " + lastNames[ j ]);
            }

            Console.WriteLine("Done.");

            /**/

            Console.ReadLine();
        }

        //what I wrote during the interview...
        private static void ReverseLastNames()
        {
            Dictionary<string, string> original = new Dictionary<string, string>();

            original.Add("Mike", "Anderson");
            original.Add("Jeff", "Basquat");
            original.Add("Paul", "Thompson");
            original.Add("Brent", "Smith");
            original.Add("Chris", "Price");

            string[] lastNames = new string[original.Count];

            int i = 0;
            foreach (string lastName in original.Values)
            {
                lastNames[i++] = lastName;
            }

            Dictionary<string, string> reversed = new Dictionary<string, string>(original.Count);

            i = lastNames.Length - 1;
            foreach (string firstName in original.Keys)
            {
                reversed.Add(firstName, lastNames[i--]);
            }
        }
    }
}

Intersecting lists of strings...

2013-02-12T01:06:00Z

Find the intersection between two lists of strings.

#region

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

#endregion

namespace Interview
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            List<string> one = new List<string>();
            List<string> two = new List<string>();

            one.AddRange(new[] {"1", "1", "4", "6", "7", "9", "3", "6", "9"});
            one.AddRange(one);
            one.AddRange(one);
            one.AddRange(one);
            one.AddRange(one);
            one.AddRange(one);
            one.AddRange(one);
            two.AddRange(new[] {"1", "8", "3", "1", "6", "2", "4", "6"});
            two.AddRange(two);
            two.AddRange(two);
            two.AddRange(two);
            two.AddRange(two);
            two.AddRange(two);
            two.AddRange(two);

            Stopwatch stopwatch = new Stopwatch();
            int numberOfIterations = 25000;

            /**/

            stopwatch.Reset();
            stopwatch.Start();
            for (int i = 0; i < numberOfIterations; i++)
            {
                List<string> result = Linq(one, two);
            }

            Console.WriteLine(stopwatch.Elapsed);
            Console.WriteLine("Linq\n");

            /**/

            stopwatch.Reset();
            stopwatch.Start();
            for (int i = 0; i < numberOfIterations; i++)
            {
                List<string> result = Slow(one, two);
            }

            Console.WriteLine(stopwatch.Elapsed);
            Console.WriteLine("Slow\n");

            /**/

            stopwatch.Reset();
            stopwatch.Start();
            for (int i = 0; i < numberOfIterations; i++)
            {
                List<string> result = SlowWithOptimization(one, two);
            }

            Console.WriteLine(stopwatch.Elapsed);
            Console.WriteLine("SlowWithOptimization\n");

            /**/

            stopwatch.Reset();
            stopwatch.Start();
            for (int i = 0; i < numberOfIterations; i++)
            {
                List<string> result = Faster(one, two);
            }

            Console.WriteLine(stopwatch.Elapsed);
            Console.WriteLine("Faster\n");

            /**/

            stopwatch.Reset();
            stopwatch.Start();
            for (int i = 0; i < numberOfIterations; i++)
            {
                List<string> result = MuchFaster(one, two);
            }

            Console.WriteLine(stopwatch.Elapsed);
            Console.WriteLine("MuchFaster\n");

            /**/

            stopwatch.Reset();
            stopwatch.Start();
            for (int i = 0; i < numberOfIterations; i++)
            {
                List<string> result = FasterThanLinq(one, two);
            }

            Console.WriteLine(stopwatch.Elapsed);
            Console.WriteLine("FasterThanLinq\n");

            Console.WriteLine("Done.");

            /**/

            Console.ReadLine();
        }

        private static List<string> Linq(List<string> one, List<string> two)
        {
            List<string> intersection = new List<string>();

            intersection.AddRange(one.Intersect(two).ToList());

            return intersection;
        }

        private static List<string> Slow(List<string> one, List<string> two)
        {
            List<string> intersection = new List<string>();

            foreach (string stringOne in one)
            {
                if (two.Contains(stringOne))
                {
                    if (!intersection.Contains(stringOne))
                    {
                        intersection.Add(stringOne);
                    }
                }
            }

            return intersection;
        }

        private static List<string> SlowWithOptimization(List<string> one, List<string> two)
        {
            List<string> intersection = new List<string>();

            foreach (string stringOne in one)
            {
                //kinda, until 'intersection' fills...
                if (!intersection.Contains(stringOne))
                {
                    if (two.Contains(stringOne))
                    {
                        if (!intersection.Contains(stringOne))
                        {
                            intersection.Add(stringOne);
                        }
                    }
                }
            }

            return intersection;
        }

        private static List<string> Faster(List<string> one, List<string> two)
        {
            List<string> intersection = new List<string>();

            one.Sort();
            two.Sort();

            int i = 0;
            int j = 0;

            while (i < one.Count && j < two.Count)
            {
                string stringOne = one[ i ];
                string stringTwo = two[ j ];

                if (stringOne == stringTwo)
                {
                    if (!intersection.Contains(stringOne))
                    {
                        intersection.Add(stringOne);
                    }

                    do
                    {
                        ++i;
                    } while (i < one.Count && one[ i ] == stringOne);

                    do
                    {
                        ++j;
                    } while (j < two.Count && two[ j ] == stringTwo);

                    continue;
                }

                j++;
            }

            return intersection;
        }

        private static List<string> MuchFaster(List<string> one, List<string> two)
        {
            Dictionary<string, int> intersection = new Dictionary<string, int>();

            foreach (string stringOne in one)
            {
                if (!intersection.ContainsKey(stringOne))
                {
                    intersection.Add(stringOne, -1);
                }
            }

            foreach (string stringTwo in two)
            {
                if (!intersection.ContainsKey(stringTwo))
                {
                    intersection.Add(stringTwo, 1);
                }
                else
                {
                    if (intersection[stringTwo] == -1)
                    {
                        intersection[stringTwo] = 0;
                    }
                }
            }

            return intersection.Where(kvp => kvp.Value == 0).Select(kvp => kvp.Key).ToList();
        }

        private static List<string> FasterThanLinq(List<string> one, List<string> two)
        {
            HashSet<string> existsInOne = new HashSet<string>();
            HashSet<string> existsInTwo = new HashSet<string>();

            foreach (string stringOne in one)
            {
                if (!existsInOne.Contains(stringOne))
                {
                    existsInOne.Add(stringOne);
                }
            }

            foreach (string stringTwo in two)
            {
                if (existsInOne.Contains(stringTwo))
                {
                    if (!existsInTwo.Contains(stringTwo))
                    {
                        existsInTwo.Add(stringTwo);
                    }
                }
            }

            return existsInTwo.ToList();
        }
    }
}

Recursive tree traversal orders...

2009-09-25T16:05:00Z

using System;
using System.Collections.Generic;

namespace VMTree
{
    internal class Program
    {
        private static readonly Queue<Node> Queue = new Queue<Node>();

        private static void Main()
        {
            var node1 = new Node();
            var node2 = new Node();
            var node3 = new Node();
            var node4 = new Node();
            var node5 = new Node();
            var node6 = new Node();
            var node7 = new Node();

            node1.Value = 1;
            node2.Value = 2;
            node3.Value = 3;
            node4.Value = 4;
            node5.Value = 5;
            node6.Value = 6;
            node7.Value = 7;

            node1.Left = node2;
            node1.Right = node3;

            node2.Left = node4;
            node2.Right = node5;

            node3.Left = node6;
            node3.Right = node7;

            Console.WriteLine("PreorderTraversal");

            PreorderTraversal(node1);

            Console.WriteLine("InorderTraversal");

            InorderTraversal(node1);

            Console.WriteLine("PostorderTraversal");

            PostorderTraversal(node1);

            Console.WriteLine("BreathFirstTraversal");

            BreadthFirstTraversal(node1);

            Console.ReadLine();
        }

        private static void PreorderTraversal(Node node)
        {
            if (node == null)
            {
                return;
            }

            Console.WriteLine(node.Value.ToString());

            PreorderTraversal(node.Left);
            PreorderTraversal(node.Right);
        }

        private static void InorderTraversal(Node node)
        {
            if (node == null)
            {
                return;
            }

            InorderTraversal(node.Left);

            Console.WriteLine(node.Value);

            InorderTraversal(node.Right);
        }

        private static void PostorderTraversal(Node node)
        {
            if (node == null)
            {
                return;
            }

            PostorderTraversal(node.Left);

            PostorderTraversal(node.Right);

            Console.WriteLine(node.Value);
        }

        private static void BreadthFirstTraversal(Node node)
        {
            if (node == null)
            {
                return;
            }

            Queue.Enqueue(node.Left);

            Queue.Enqueue(node.Right);

            Console.WriteLine(node.Value);

            if (Queue.Count != 0)
            {
                BreadthFirstTraversal(Queue.Dequeue());
            }
        }
    }

    internal class Node
    {
        public int Value { get; set; }
        public Node Left { get; set; }
        public Node Right { get; set; }
        public override string ToString()
        {
            return Value.ToString();
        }
    }
}

Reversing a string...

2009-09-25T16:01:00Z

#region

using System;
using System.Text;

#endregion

namespace StringReversal
{
    internal class Program
    {
        private static void Main()
        {
            //this is the easy way...
            const string sentence = "Reverse me.";

            var stringBuilder = new StringBuilder(sentence.Length);

            for (int i = sentence.Length - 1; i >= 0; i--)
            {
                stringBuilder.Append(sentence[ i ]);
            }

            //slightly harder, but not by much.
            Console.WriteLine(stringBuilder.ToString());

            var reversed = new char[sentence.Length];

            for (int i = sentence.Length - 1, j = 0; i >= 0; i--, j++)
            {
                reversed[j] = sentence[ i ];
            }

            Console.WriteLine(new String(reversed));

            //OK, finally now, without using a second array.
            char[] reversed2 = sentence.ToCharArray();

            for (int i = 0; i < reversed2.Length/2; i++)
            {
                char temp = reversed2[ i ];

                reversed2[ i ] = reversed2[reversed2.Length - i - 1];

                reversed2[reversed2.Length - i - 1] = temp;
            }

            Console.WriteLine(new String(reversed));

            //end
            Console.ReadLine();
        }
    }
}

Does an array contain the sum...

2009-09-25T15:59:00Z

A few days ago someone asked me to detect if an integer could be produced by the sum of two integers in an array of integers.

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace LittleProblem
{
    internal class Program
    {
        private static void Main()
        {
            long algorithmTimeForContainsSum1 = 0;
            long algorithmTimeForContainsSum2 = 0;

            var algorithmTimesForContainsSum1 = new List<long>();
            var algorithmTimesForContainsSum2 = new List<long>();

            var random = new Random();

            var stopwatch = new Stopwatch();

            int containedSum = 0;
            int didNotContainSum = 0;

            //main iteration loop...
            for (int i = 0; i < 10000; i++)
            {
                var list = new List<int>();

                //create arrays of varying length, from 1 to the main iteration loop length...
                for (int j = 0; j < i + 1; j++)
                {
                    list.Add(random.Next(1, 100));

                    //Console.WriteLine(i + " : " + j);
                }

                int numberToFind = random.Next(1, 100)*2;

                stopwatch.Start();
                bool containsSum1ContainsSum = ContainsSum1(list, numberToFind);
                stopwatch.Stop();
                algorithmTimeForContainsSum1 += stopwatch.ElapsedMilliseconds;
                algorithmTimesForContainsSum1.Add(stopwatch.ElapsedMilliseconds);

                stopwatch.Reset();

                stopwatch.Start();
                bool containsSum2ContainsSum = ContainsSum2(list, numberToFind);
                stopwatch.Stop();
                algorithmTimeForContainsSum2 += stopwatch.ElapsedMilliseconds;
                algorithmTimesForContainsSum2.Add(stopwatch.ElapsedMilliseconds);

                Debug.Assert(containsSum1ContainsSum == containsSum2ContainsSum);

                if (containsSum1ContainsSum)
                {
                    containedSum++;
                }
                else
                {
                    didNotContainSum++;
                }
            }

            Console.WriteLine(containedSum + " : " + didNotContainSum);
            Console.WriteLine(algorithmTimeForContainsSum1);
            Console.WriteLine(algorithmTimeForContainsSum2);

            Console.ReadLine();
        }

        //O(n^2)
        private static bool ContainsSum1(IList<int> list, int sum)
        {
            for (int i = 0; i < list.Count; i++)
            {
                for (int j = 0; j < list.Count; j++)
                {
                    if (i != j)
                    {
                        if (list + list[j] == sum)
                        {
                            return true;
                        }
                    }
                }
            }

            return false;
        }

        //O(n log n)
        private static bool ContainsSum2(List<int> list, int sum)
        {
            list.Sort();

            int i = 0;
            int j = list.Count - 1;

            while (i != j)
            {
                int sum2 = list + list[j];

                if (list + list[j] == sum)
                {
                    return true;
                }

                if (sum2 < sum)
                {
                    i++;
                }
                else
                {
                    j--;
                }
            }

            return false;
        }
    }
}