Category Archives: Algorithms

Compute number of ways to make amount of money with coins of the available denominations.

Below code snippet is easiest way to compute number of ways to make amount of money with coins of the available denominations.

Example: for amount=20 and denominations 20, 10, 5, 1, program should output 10 ways.

    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(MaxPossibleCombinations(4, new int[] { 1,2,3}));
            Console.WriteLine(MaxPossibleCombinations(20, new int[] { 20, 10, 5, 1 }));
            Console.ReadLine();
        }

        public static int MaxPossibleCombinations(int amount, int[] denominations)
        {
            int[] wayofDoingNAmount = new int[amount + 1];
            wayofDoingNAmount[0] = 1;
            foreach (int coin in denominations)
            {
                for (int higherAmount = coin; higherAmount < amount + 1; higherAmount++)
                {
                    int remainderAmount = higherAmount - coin;
                    wayofDoingNAmount[higherAmount] += wayofDoingNAmount[remainderAmount];
                }
            }
            return wayofDoingNAmount[amount];
        }
    }

This can also be achieved using the memoize technique. Memoization ensures that a function doesn’t run for the same inputs more than once by keeping a record of the results for given inputs (usually in a hash map).

Stack extended with Min Value – Generic Stack

Stack which, in addition to push and pop, also has a
function min which returns the minimum element. Push, pop and min
operate in 0(1) time

To solve this we use 2 stack

  • superStack
  • stackWithMin

superStack behaves like a normal stack and stackWithMin keeps track of minimum values.

Below is code snippet for the class with generic implementation.

    public class StackWithMin<T> where T : IComparable
    {
        private Stack<T> superStack;
        private Stack<T> stackWithMin;

        public StackWithMin()
        {
            this.superStack = new Stack<T>();
            this.stackWithMin = new Stack<T>();
        }
        public T Pop()
        {
            if (this.superStack.Count <= 0)
                throw new InvalidOperationException("Stack Empty.");

            T lastPopedElement = this.superStack.Pop();
            T element = this.stackWithMin.Peek();
            if (element.CompareTo(lastPopedElement) == 0)
            {
                this.stackWithMin.Pop();
            }
            return lastPopedElement;
        }

        public void Push(T element)
        {
            if (this.superStack.Count == 0)
            {
                this.stackWithMin.Push(element);
                this.superStack.Push(element);
                return;
            }

            if (element.CompareTo(this.Min()) <= 0)
            {
                this.stackWithMin.Push(element);
            }
            this.superStack.Push(element);
        }

        public T Min()
        {
            if (this.superStack.Count <= 0)
                throw new InvalidOperationException("Stack Empty.");

            return this.stackWithMin.Peek();
        }
    }

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;
        }
    }

Interger /Number Array Sorting in Javascript.

Javascript arrays have the sort() method which sorts the items of an array. By default, the sort() method sorts the values as strings in alphabetical and ascending order.

var names = ["John", "Mary", "Amol", "Robert"];
names.sort();

It is an inplace sort for an array and sorted array would be some thing like this

["Amol", "John", "Mary", "Robert"]

However, if numbers are sorted as strings, “25” is bigger than “100”, because “2” is bigger than “1”. Because of this, the sort() method will produce an incorrect result when sorting numbers. You can fix this by providing a “compare function”

array.sort(compareFunction)

Compare function will look some thing like this

function compareFunction(a, b){
	return a-b
};

When the sort() method compares two values, it sends the values to the compare function, and sorts the values according to the returned (negative, zero, positive) value.

So final number array example looks something like this.

var numberArr = [100, 1, 200, 150, 10, 20];
numberArr.sort(compareFunction);
function compareFunction(a, b) {
    return a - b
};

Removing Duplicates from Linked List

To remove duplicates from a linked list, we need to be able to track duplicates. Dictionary/hash table will work well here. We will iterate through the linked list, adding each element to a dictionary/hash table. When we discover a duplicate element, we remove the element and continue iterating. We can do this all in one pass. This solution takes 0(N) time, where N is the number of elements in the linked list.

        public static void RemoveDuplicateNodes(Node node)
        {
            Dictionary<string, string> nodeDictionary = new Dictionary<string, string>();
            Node previousNode = null;
            while (node != null)
            {
                if (nodeDictionary.ContainsKey(node.Data))
                {
                    previousNode.NextNode = node.NextNode;
                }
                else
                {
                    nodeDictionary.Add(node.Data, node.Data);
                    previousNode = node;
                }
                node = node.NextNode;
            }
        }

If we do not have an option to use dictionary, we can iterate with two pointers: current which iterates through the linked list, and runner which checks all subsequent nodes for duplicates. It runs in 0(1) space, but 0(N2 – N Square) time.

        /// <summary>
        /// Removes the duplicate nodes without dictionary.
        /// </summary>
        /// <param name="node">The node.</param>
        public static void RemoveDuplicateNodesWithoutDictionary(Node node)
        {
            while (node != null)
            {
                Node runnerNode = node;
                while (runnerNode.NextNode != null)
                {
                    if (runnerNode.NextNode.Data == node.Data)
                    {
                        runnerNode.NextNode = runnerNode.NextNode.NextNode;
                    }
                    else
                    {
                        runnerNode = runnerNode.NextNode;
                    }
                }
                node = node.NextNode;
            }
        }

String – Is one string Rotation of other?

Assume you have a method isSubstring which checks if one word is a substring
of another. In C# you can use string.contains. Given two strings, str1 and str2, write code to check if str2 is a rotation of str1, using only one call to isSubstring / string.contains (e.g. “olAam” is a rotation of “Aamol”).

If we imagine that str2 is a rotation of str1, then we can ask what the rotation point is. For example, if you rotate Aamol after “Aam”, you get “olAam”. In a rotation, we
cut str1 into two parts x and y, and rearrange them to get str2.
str1 = xy = Aamol
x= Aam
y= ol
str2 = yx = olAam

So, we need to check if there’s a way to split str1 into x and y such that xy = str1 and yx = str2. Regardless of where the division between x and y is, we can see that yx will always be a substring of xyxy. That is str2 will always be a substring of str1str1. That’s how we solve the problem: simply do isSubstring(str1str1, str2).

        /// <summary>
        /// Determines whether the specified STR1 is rotation.
        /// </summary>
        /// <param name="str1">The STR1 - Original String </param>
        /// <param name="str2">The STR2 - Rotated String</param>
        /// <returns></returns>
        public static bool IsRotation(string str1, string str2)
        {
            //Check if str1 and str2 are equal length and not empty
            if (!string.IsNullOrEmpty(str1) &&
                !string.IsNullOrEmpty(str2) &&
                str1.Length == str2.Length)
            {
                /* Concatenate str1 and str2 in a new string */
                string str1str1 = str1 + str1;
                return str1str1.Contains(str2);
            }
            return false;
        }

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;
        }

    }