Snippets

                    // input array is assumed to be sorted
        public int BinarySearch(int[] arr, int x)
        {
            if (arr.Length == 0)
                return -1;

            int mid = arr.Length / 2;

            if (arr[mid] == x)
                return mid;

            if (x < arr[mid])
                return BinarySearch(GetSubArray(arr, 0, mid - 1), x);
            else
            {
                int _indexFound = BinarySearch(GetSubArray(arr, mid + 1, arr.Length - 1), x);
                if (_indexFound == -1)
                    return -1;
                else
                    return mid + 1 + BinarySearch(GetSubArray(arr, mid + 1, arr.Length - 1), x);
            }
        }


        public int[] GetSubArray(int[] arr, int start, int end)
        {
            List<int> _result = new List<int>();
            for (int i = start; i <= end; i++)
            {
                _result.Add(arr[i]);
            }
            return _result.ToArray();
        }                

                        public class BinaryTreeNode
    {
        public BinaryTreeNode Left { get; set; }

        public BinaryTreeNode Right { get; set; }

        public int Data { get; set; }

        public BinaryTreeNode(int data)
        {
            this.Data = data;
        }
    }

     public void InsertIntoBST(BinaryTreeNode root, int data)
        {
            BinaryTreeNode _newNode = new BinaryTreeNode(data);

            BinaryTreeNode _current = root;
            BinaryTreeNode _previous = _current;

            while (_current != null)
            {
                if (data < _current.Data)
                {
                    _previous = _current;
                    _current = _current.Left;
                }
                else if (data > _current.Data)
                {
                    _previous = _current;
                    _current = _current.Right;
                }
            }

            if (data < _previous.Data)
                _previous.Left = _newNode;
            else
                _previous.Right = _newNode;
        }                

                        public class ParkingLot
    {
        List<ParkingSpot> _parkingSpots;

        public ParkingLot()
        {
            _parkingSpots = new List<ParkingSpot>();
            // 10 parking spots; 2 free; 6 Regular Paid; 2 Handicapped Free

            //2 free
            for (int i = 0; i < 2; i++)
            {
                _parkingSpots.Add(new ParkingSpot(true));
            }

            //6 Regular Paid
            for (int i = 0; i < 6; i++)
            {
                _parkingSpots.Add(new ParkingSpot(false));
            }

            //2 Handicapped Free
            for (int i = 0; i < 2; i++)
            {
                _parkingSpots.Add(new HandicappedParkingSpot());
            }
        }


        public ParkingSpot FindFreeSpot()
        {
            return this._parkingSpots.Find(p => p.IsFree == true && p.IsAvailable);
        }

        public ParkingSpot FindPaidSpot()
        {
            return this._parkingSpots.Find(p => p.IsFree == false && p.IsAvailable);
        }

        public int GetAvailableSpotsCount()
        {
            return this._parkingSpots.Count(p => p.IsAvailable);
        }

        public int GetTotalSpots()
        {
            return this._parkingSpots.Count;
        }
    }

    public class ParkingSpot
    {
        public bool IsAvailable { get; set; }
        public bool IsFree { get; set; }
        public IVehicle ParkedVehicle { get; set; }
        public ParkingMeter Meter { get; set; }

        public void Park(IVehicle vehicle)
        {
            if (this.ParkedVehicle == null)
            {
                this.ParkedVehicle = vehicle;
                this.IsAvailable = false;
            }
            else
            {
                throw new Exception("Parking Spot is Taken. Cannot Park here!");
            }
        }

        public ParkingSpot()
        {
            this.IsAvailable = true;
            this.IsFree = true;
        }

        public ParkingSpot(bool isFree)
        {
            this.IsAvailable = true;
            this.IsFree = isFree;
            if (!this.IsFree)
            {
                this.Meter = new ParkingMeter();
            }
        }
    }

    public class HandicappedParkingSpot : ParkingSpot
    {

    }

    public class ParkingMeter
    {
        public DateTime EndTime { get; set; }
        public int MinutesRemaining
        {
            get
            {
                if (DateTime.Now >= EndTime)
                    return 0;
                else
                    return (EndTime - DateTime.Now).Minutes;
            }
        }

        public int ParkingIntervalMins
        {
            get
            {
                return 1;
            }
        }

        public void Pay(int quarters)
        {
            EndTime = DateTime.Now.AddMinutes(quarters * ParkingIntervalMins);
        }

    }


    public interface IVehicle
    {
        string Make { get; set; }
        string Model { get; set; }
        void Drive();
    }

    public class Car : IVehicle
    {
        public string Make
        {
            get;
            set;
        }

        public string Model
        {
            get;
            set;
        }

        public void Drive()
        {
        }

        public void Park()
        {
        }

    }

    public class Truck : IVehicle
    {
        public string Make
        {
            get;
            set;
        }

        public string Model
        {
            get;
            set;
        }

        public void Drive()
        {
        }

        public void Park()
        {
        }
    }                

                        public class BinaryTreeNode
    {
        public BinaryTreeNode Left { get; set; }

        public BinaryTreeNode Right { get; set; }

        public int Data { get; set; }

        public BinaryTreeNode(int data)
        {
            this.Data = data;
        }
    }

        public enum TreeTraversal
        {
            PREORDER,
            INORDER,
            POSTORDER
        }

        public void PrintTree(BinaryTreeNode root, TreeTraversal treeTraversal)
        {
            Action<int> printValue = delegate(int v)
            {
                Console.Write(v + " ");
            };
        
            switch (treeTraversal)
            {
                case TreeTraversal.PREORDER:
                    PreOrderTraversal(printValue, root);
                    break;
                case TreeTraversal.INORDER:
                    InOrderTraversal(printValue, root);
                    break;
                case TreeTraversal.POSTORDER:
                    PostOrderTraversal(printValue, root);
                    break;
                default: break;
            }
        }

        public void PreOrderTraversal(Action<int> action, BinaryTreeNode root)
        {
            if (root == null)
                return;

            action(root.Data);
            PreOrderTraversal(action, root.Left);
            PreOrderTraversal(action, root.Right);
        }

        public void InOrderTraversal(Action<int> action, BinaryTreeNode root)
        {
            if (root == null)
                return;

            InOrderTraversal(action, root.Left);
            action(root.Data);
            InOrderTraversal(action, root.Right);
        }

        public void PostOrderTraversal(Action<int> action, BinaryTreeNode root)
        {
            if (root == null)
                return;

            PostOrderTraversal(action, root.Left);
            PostOrderTraversal(action, root.Right);
            action(root.Data);
        }                

                    public static BinaryTreeNode BuildBinarySearchTree(int[] sortedArray)
        {
            if (sortedArray.Length == 0)
                return null;

            int _mid = sortedArray.Length / 2;
            BinaryTreeNode _root = new BinaryTreeNode(sortedArray[_mid]);
            int[] _left = GetSubArray(sortedArray, 0, _mid - 1);
            int[] _right = GetSubArray(sortedArray, _mid + 1, sortedArray.Length - 1);
            _root.Left = BuildBinarySearchTree(_left);
            _root.Right = BuildBinarySearchTree(_right);

            return _root;
        }


        public int[] GetSubArray(int[] array, int start, int end)
        {
            List<int> _result = new List<int>();
            for (int i = start; i <= end; i++)
            {
                _result.Add(array[i]);
            }
            return _result.ToArray();
        }                

                    /// <summary>
        /// This method sorts elements in linked list and returns a new sorted linked list
        /// </summary>
        /// <param name="head">head node of unsorted linked list</param>
        /// <param name="count">number of elements in unsorted linked list</param>
        /// <returns>head node of new sorted linked list</returns>
        public static Node SortLinkedList(Node head, int count)
        {
            // Basic Algorithm Steps
            //1. Find Min Node
            //2. Remove Min Node and attach it to new Sorted linked list
            //3. Repeat "count" number of times

            Node _current = head;
            Node _previous = _current;

            Node _min = _current;
            Node _minPrevious = _min;

            Node _sortedListHead = null;
            Node _sortedListTail = _sortedListHead;

            for (int i = 0; i < count; i++)
            {
                _current = head;
                _min = _current;
                _minPrevious = _min;

                //Find min Node
                while (_current != null)
                {
                    if (_current.Data < _min.Data)
                    {
                        _min = _current;
                        _minPrevious = _previous;
                    }
                    _previous = _current;
                    _current = _current.Next;
                }

                // Remove min Node 
                if (_min == head)
                {
                    head = head.Next;
                }
                else if (_min.Next == null) //if tail is min node
                {
                    _minPrevious.Next = null;
                }
                else
                {
                    _minPrevious.Next = _minPrevious.Next.Next;
                }


                //Attach min Node to the new sorted linked list
                if (_sortedListHead != null)
                {
                    _sortedListTail.Next = _min;
                    _sortedListTail = _sortedListTail.Next;
                }
                else
                {
                    _sortedListHead = _min;
                    _sortedListTail = _sortedListHead;
                }
            }

            return _sortedListHead;
        }                

                    public int[] SelectionSort(int[] arr)
        {
            //1. Find min
            //2. Swap it with first element
            //3. Repeat starting from secong position onwards.
            int _min = 0;
            for (int i = 0; i < arr.Length; i++)
            {
                _min = i;
                for (int j = i; j < arr.Length; j++)
                {
                    if (arr[j] < arr[_min])
                        _min = j;
                }
                int _temp = arr[i];
                arr[i] = arr[_min];
                arr[_min] = _temp;
            }
            return arr;
        }                

                    public int[] BubbleSort(int[] _arr)
        {
            for (int i = _arr.Length - 1; i > 0; i--)
            {
                for (int j = 0; j < i; j++)
                {
                    if (_arr[j] > _arr[j + 1])
                    {
                        int temp = _arr[j];
                        _arr[j] = _arr[j + 1];
                        _arr[j + 1] = temp;
                    }
                }
            }
            return _arr;
        }                

                    // 1. remove first char 
// 2. find permutations of the rest of chars
// 3. Attach the first char to each of those permutations.
//     3.1  for each permutation, move firstChar in all indexes to produce even more permutations.
// 4. Return list of possible permutations.

public string[] FindPermutations(string word)
        {
            if (word.Length == 2)
            {
                char[] _c = word.ToCharArray();
                string s = new string(new char[] { _c[1], _c[0] });
                return new string[]
                {
                    word,
                    s
                };
            }

            List<string> _result = new List<string>();

            string[] _subsetPermutations = FindPermutations(word.Substring(1));
            char _firstChar = word[0];
            foreach (string s in _subsetPermutations)
            {
                string _temp = _firstChar.ToString() + s;
                _result.Add(_temp);
                char[] _chars = _temp.ToCharArray();
                for (int i = 0; i < _temp.Length - 1; i++)
                {
                    char t = _chars[i];
                    _chars[i] = _chars[i + 1];
                    _chars[i + 1] = t;
                    string s2 = new string(_chars);
                    _result.Add(s2);
                }
            }
            return _result.ToArray();
        }                

                    public bool IsPrime(int num)
        {
            bool _isPrime = true;

            if (num % 2 == 0) return false;

            for (int i = 3; i <= Convert.ToInt32(Math.Sqrt(num)); i = i + 2)
            {
                if (num % i == 0)
                {
                    _isPrime = false;
                    break;
                }
            }
            return _isPrime;
        }