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

Tip for Making Ajax Calls in window.beforeunload / window.unload especially if you are using Angular JS

If you are making Ajax calls in angular application in $window.beforeunload event, then there is high possibility that you will see the issue that the server side API which needs to be invoked as part of Ajax calls is not getting invoked.

Reason for this is, for making Ajax calls you will be using $http and all $http calls are async in nature, so browser will kill the thread before sending the request. $http internally uses below API

xhr.open(method, url, true);

The third parameter in an xhr.open() can be set to false or true, where false is synchronous and true is asynchronous. In the Angular case, it is hard coded to true, so that all outgoing calls will be asynchronous. So using $http is not a good choice in this scenario.

Instead of $http you can use $ajax from jQuery to make these Ajax calls, as $ajax provides an option to dictate if the request should be asynchronous or synchronous. It can be dictated with help of parameter async: false

$window.unload(function () {
    $.ajax({
        type: 'PUT',
        async: false,
        url: 'api/unlockcustomer?id=123'
    });
});

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

Algorithm to check if one string is combination of other (Anagram)

Two strings are anagrams if they are written using the same exact letters, ignoring space, punctuation and capitalization. Each letter should have the same count in both strings. For example, ‘Eleven plus two’ and ‘Twelve plus one’ are meaningful anagrams of each other. Below is the code sample

        /// <summary>
        /// Determines whether first string is permutations of second one.
        /// We simply iterate through this code, counting how many times each character appears.
        /// Then, afterwards, we compare the two arrays.
        /// </summary>
        /// <param name="first">The first.</param>
        /// <param name="second">The second.</param>
        /// <returns></returns>
        public static bool IsStringPermutationOfOther(string first, string second)
        {
            if (first.Length != second.Length)
                return false;

            //There are only 256 unique ASCII characters
            int[] characterCounts = new int[256];

            foreach (char c in first)
            {
                characterCounts[(int)c]++;
            }

            foreach (char c in second)
            {
                if (--characterCounts[(int)c] < 0)
                    return false;
            }
            return true;
        }

For following test strings

            Console.WriteLine(IsStringPermutationOfOther("Amol", "lomA"));
            Console.WriteLine(IsStringPermutationOfOther("Amol", "Amol"));
            Console.WriteLine(IsStringPermutationOfOther("Amol", "Amol   "));
            Console.WriteLine(IsStringPermutationOfOther("eleven plus two", "twelve plus one"));

It Returns

• True
• True
• False
• True

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

    }