Monthly Archives: September 2015

Maximum Sum of All Sub-arrays

Keep scanning through the array and calculating the maximum sub-array that ends at every position. The sub-array will either contain a range of numbers if the array has intermixed positive and negative values, or it will contain the least negative value if the array has only negative values.

Use Kadane’s algorithm which runs in O(n) time.

 

    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = new int[] { 5, -2, 3, 18, -4, 29, 2, -5 };
            FindMaximumSumofAllSubArrays(arr);
            Console.ReadLine();
        }

        private static void FindMaximumSumofAllSubArrays(int[] arr)
        {
            List<int> arrList = new List<int>();
            int maxSumSoFar = -2147483648;
            int curSum = 0;
            //loop for for chcking if all numbers in an array are negative.
            foreach (int item in arr)
            {
                if (maxSumSoFar < item)
                {
                    maxSumSoFar = item;
                }
            }

            if (maxSumSoFar < 0)
            {
                Console.WriteLine("All Array Numbers are Negative and Maximum sum is " + maxSumSoFar);
                return;
            }
            maxSumSoFar = 0;
            foreach (int item in arr)
            {
                curSum += item;
                if (curSum > maxSumSoFar)
                {
                    maxSumSoFar = curSum;
                }
                if (curSum < 0)
                {
                    curSum = 0;
                }
            }
            Console.WriteLine(maxSumSoFar);
        }
    }

First Character Appearing Only Once

Implement a function to find the first character in a string which only appears once. For example: It returns ‘D’ when the input is “AamolDGoteAamolGote”. Typical solution for this problem may be scanning the input string from its beginning to end. We compare the current scanned character with every one behind it. If there is no duplication after it, it is a character appearing once. Since it compares each character with O(n) ones behind it, the overall time complexity is O(n2) if there are n characters in a string. Instead of doing this we can follow the approach using Hash tables, we can implement a hash table, in which keys are characters and values are their occurrence times in a string. It is necessary to scan strings twice: When a character is visited, we increase the corresponding occurrence time in the hash table during the first scanning. In second round of scanning, whenever a character is visited we also check its occurrence time in the hash table. The first character with occurrence time 1 is the required output.

        private static void FirstCharacterAppearingOnlyOnce(string input)
        {
            char[] inputCharacters = input.ToCharArray();
            IDictionary<char, int> characterCount = new Dictionary<char, int>();
            foreach (char c in inputCharacters)
            {
                if (characterCount.ContainsKey(c))
                {
                    characterCount[c] = ++characterCount[c];
                }
                else
                {
                    characterCount.Add(c, 1);
                }
            }

            foreach (char c in characterCount.Keys)
            {
                if (characterCount[c] == 1)
                {
                    Console.WriteLine("First Character Appearing Only Once is: " + c.ToString());
                    return;
                }
            }
        }

Left Rotation of String

Left rotation of a string is to move some leading characters to its tail. For e.g. if the input string is “AamolDGote” and a number 2, the rotated result is “molDGoteAa”.

 private static void LeftRotateString(string input, int numberOfCharacters)
{
#region Approach 1
string strFirst = input.Substring(0, numberOfCharacters);
string strSecond = input.Substring(numberOfCharacters, input.Length - numberOfCharacters);
string result = string.Concat(strSecond, strFirst);
Console.WriteLine(result);
#endregion

#region Approach2
string str = input;
str = str + input; //Append same string 
result = str.Substring(numberOfCharacters, input.Length - 1);
Console.WriteLine(result);
#endregion
}

Reverse Words in a String

Below code snippet shows 3 ways to reverse words in the string

  1. Approach 1 describes traditional ways of reversing entire string, then using space delimiter reverse each word.
  2. Approach 2 – Split string using space and reverse the array using .NET built method of Array.reverse
  3. Approach 3 – Similar to 2 but using only one line of code
    class Program
    {
        static void Main(string[] args)
        {
            string input = "Aamol Gote's blog is my tech net know hows";
            Approach1UsingCharArray(input);
            Approach2UsingArrayReverse(input);
            Approach3UsingSingleLOC(input);
            Console.ReadLine();
        }


        private static void Approach1UsingCharArray(string input)
        {
            string reversedStr = ReverseString(input);
            StringBuilder sb = new StringBuilder(reversedStr.Length);
            foreach (string str in reversedStr.Split(' '))
            {
                sb.Append(string.Concat(ReverseString(str), ' '));
            }
            Console.WriteLine(sb.ToString().Trim());
        }

        private static string ReverseString(string str)
        {
            char[] stringContent = str.ToCharArray();
            for (int start = 0, end = stringContent.Length - 1; start < end; start++, end--)
            {
                char temp = stringContent[start];
                stringContent[start] = stringContent[end];
                stringContent[end] = temp;
            }
            return new string(stringContent);
        }

        private static void Approach2UsingArrayReverse(string input)
        {
            string[] strArr = input.Split(' ');
            IEnumerable<string> strReverArr = strArr.Reverse<string>();
            StringBuilder sb = new StringBuilder(input.Length);
            foreach (string str in strReverArr)
            {
                sb.Append(string.Concat(str, ' '));
            }
            Console.WriteLine(sb.ToString().Trim());
        }

        private static void Approach3UsingSingleLOC(string input)
        {
            string reversed = string.Join(" ", input.Split(' ').ToArray<string>().Reverse<string>());
            Console.WriteLine(reversed);
        }
    }