Category Archives: data structures

Implement Queue with 2 Stacks

In this approach, newStack has the newest elements on top and oldStack has the oldest elements on top. When we dequeue an element, we want to remove the oldest element first, and so we dequeue from oldStack. If oldStack is empty, then we want to transfer all elements from newStack into this old stack in reverse order.To insert an element, we push onto stackNewest, since it has the newest
elements on top.

Below is the code, this implements generic interface

    /// <summary>
    /// My Queue Interface
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public interface IMyQueue<T>
    {
        /// <summary>
        /// Adds the specified element.
        /// </summary>
        /// <param name="element">The element.</param>
        void Add(T element);
        /// <summary>
        /// Peeks this instance.
        /// </summary>
        /// <returns></returns>
        T Peek();
        /// <summary>
        /// Removes this instance.
        /// </summary>
        /// <returns></returns>
        T Remove();
    }

    /// <summary>
    /// 
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <seealso cref="TwoStacksAndQueues.IMyQueue{T}" />
    public class MyQueue<T> : IMyQueue<T>
    {
        private Stack<T> oldStack;
        private Stack<T> newStack;
        public MyQueue()
        {
            oldStack = new Stack<T>();
            newStack = new Stack<T>();
        }

        /// <summary>
        /// Adds the specified element.
        /// </summary>
        /// <param name="element">The element.</param>
        public void Add(T element)
        {
            newStack.Push(element);
        }

        /// <summary>
        /// Peeks this instance.
        /// </summary>
        /// <returns></returns>
        public T Peek()
        {
            T element;
            while (newStack.Count > 0)
            {
                oldStack.Push(newStack.Pop());
            }
            element = oldStack.Peek();
            return element;
        }

        /// <summary>
        /// Removes this instance.
        /// </summary>
        /// <returns></returns>
        /// <exception cref="System.InvalidOperationException">No Element Exists to remove</exception>
        public T Remove()
        {
            T element;
            if (oldStack.Count == 0)
            {
                while (newStack.Count > 0)
                {
                    oldStack.Push(newStack.Pop());
                }
            }

            if (oldStack.Count > 0)
            {
                element = oldStack.Pop();
            }
            else
            {
                throw new InvalidOperationException("No Element Exists to remove");
            }
            return element;
        }
    }
Advertisements

String Contains Unique Set of Characters – Write an static method and extension method as well

Below code explains to determine if a string has all unique characters.

Assumption : String is ASCII character set and not Unicode. We’ll assume for simplicity that the character set is ASCII. If not, we would need to increase the storage size, but the rest of the logic would be the same.

Approach:
There are only 256 unique ASCII characters so any string length greater than 256 bound to have duplicate set of ASCII characters. Create an array of boolean values, where the flag at index i indicates, whether character i in the alphabet is contained in the string. If you run across this character a second time, you can immediately return false.

Below is the code snippet, code snippet also has string extension method as well.

    class Program
    {
        /// <summary>
        /// Strings the contains unique characters.
        /// Assmuption : String is ASCII character set and not unicode. 
        /// The time complexity for this code is 0(n), where n is the length of the string.The space
        /// complexity is 0(1).
        /// 
        /// </summary>
        /// <param name="input">The input.</param>
        /// <returns></returns>
        public static bool StringContainsUniqueCharacters(string input)
        {
            //There are only 256 unique ASCII characters so any string length greater than 256 
            //bound to have duplicate set of characters.
            if (input.Length > 256) return false;

            // Create an array of boolean values, where the flag at index i indicates
            // whether character i in the alphabet is contained in the string. If you run across this
            // character a second time, you can immediately return false.
            bool[] charArr = new bool[256];

            //Iterate through all characters.
            foreach (char c in input)
            {
                if (charArr[(int)c])
                {
                    return false;
                }
                else
                {
                    charArr[(int)c] = true;
                }
            }
            return true;
        }

        static void Main(string[] args)
        {
            string str = "aamol";
            Console.WriteLine("String "+ str + " contains unique characters "  + StringContainsUniqueCharacters(str));
            str = "amol";
            Console.WriteLine("String " + str + " contains unique characters " + StringContainsUniqueCharacters(str));
            Console.ReadLine();
            str = "aamol";
            Console.WriteLine("String " + str + " contains unique characters " + str.ContainsUniqueCharacters());
            str = "amol";
            Console.WriteLine("String " + str + " contains unique characters " + str.ContainsUniqueCharacters());
            Console.ReadLine();
        }
    }
    public static class StringUtlity
    {
        /// <summary>
        /// Strings the contains unique characters Extension Method.
        /// Assmuption : String is ASCII character set and not unicode. 
        /// The time complexity for this code is 0(n), where n is the length of the string.The space
        /// complexity is 0(1).
        /// 
        /// </summary>
        /// <param name="input">The input.</param>
        /// <returns></returns>
        public static bool ContainsUniqueCharacters(this string input)
        {
            //There are only 256 unique ASCII characters so any string length greater than 256 
            //bound to have duplicate set of characters.
            if (input.Length > 256) return false;

            // Create an array of boolean values, where the flag at index i indicates
            // whether character i in the alphabet is contained in the string. If you run across this
            // character a second time, you can immediately return false.
            bool[] charArr = new bool[256];

            //Iterate through all characters.
            foreach (char c in input)
            {
                if (charArr[(int)c])
                {
                    return false;
                }
                else
                {
                    charArr[(int)c] = true;
                }
            }

            return true;
        }

    }