Find duplicate characters in string

Our task is simple, find all the duplicate characters in a string.

Input: I am test program

Output: a m t r

Algorithm: Logic is quite simple, see below steps:

  1. Check for input string validity.
    1. If string is not valid prompt user.
  2. Create a dictionary that has character as KEY and, their count as VALUE.
  3. Loop over the input string,
    1. If current character is already exists in dictionary then increment its count by 1.
    2. If current character doesn’t exist in dictionary than add it to the dictionary and set 1 as it’s count because we have found it once.
  4. Loop over the dictionary and check for value, if you find any item whose value is higher than 1 then print it.
  5. If there is no item whose value is not higher than 1 then prompt user.

Code in C#:

void PrintDuplicateCharacters(string strInput)
{
    if (string.IsNullOrWhiteSpace(strInput))
    {
        Console.WriteLine("Input is not valid");
    }
    else
    {
        var dict = new Dictionary<charint>();
        foreach (var item in strInput)
        {
            if (Equals(item, ' '))
            {
                continue;
            }
 
            if (dict.ContainsKey(item))
            {
                dict[item]++;
            }
            else
            {
                dict.Add(item, 1);
            }
        }
 
        bool isAnyCharacterFound = false;
        foreach (var item in dict)
        {
            if (item.Value > 1)
            {
                Console.WriteLine(item.Key);
                isAnyCharacterFound = true;
            }
        }
 
        if (!isAnyCharacterFound)
        {
            Console.WriteLine("No duplicate character found");
        }
    }
    Console.ReadKey();
}

Count integers from a string in JavaScript

Today’s problem is quite simple, we need to find total numbers from a user input.

Example 1:

Input string: I’m Sunil and 25 years old. I’ve 5.6 years of experience and will be 6 years of experienced in year 2017.

Output: 5

Explanation: 25 will be out first number. Then we have 5.6, in this case we’ll consider it two numbers (this is requirement), but if it is like 56 then this will be 1 number. So by now we have 3 numbers. Fourth one will be 6, and fifth will be 2017.

Example 2:

Input string: +45.6 – 89

Output: 3 (45, 6, 89)

Logic:

Step 1: First of all check for boundary conditions like invalid input; In my code I might not handled all.

Step 2: If input string is good, then add a special character at the end of the string. In my case I have added period (.).

Step 3: Loop and read all the characters of the string one by one.

Step 4: If character is an integer then add it in a variable. If character is not an integer and previously defined variable is not empty that means we have found an integer and current character is a non integer, we need to skip this. So reset the variable that is holding integers and increase the variable that is counting the number of integers.

Code:

<!DOCTYPE html>
<html>
<head>
    <meta charset="UTF-8">
    <title>Find integer count from a string</title>
    <script type="text/javascript">
        function FindNumbers()
        {
            var someString = document.getElementById('txtInput').value;
            var totalNumbersInString = 0, finalString = '';
            someString += '.';
            for (var i = 0; i < someString.length; ++i)
            {
                if (isNaN(someString[i]) && finalString.length > 0) {
                    totalNumbersInString++;
                    finalString = '';
                }
                else if(!isNaN(someString[i])) {
                    finalString += someString[i];
                }
            }

          document.getElementById('lblOutput').innerHTML = totalNumbersInString;
        }
    </script>
</head>
<body>
    Input string: <input id="txtInput" type="text"> <br>
    <input value="Process" onclick="FindNumbers()" type="submit"><br>
    Output: <div><label id="lblOutput"></label></div>
</body>
</html> 

 

 

 

Fill count of distinct pairs of integers form an array whose sum if a given number in C#

Input: a = [ 2, 4, 3, 5, 6, -2, 4, 7, 8, 9]

Number k = 7

Pair Count = (2, 5), (4, 3), (-2, 9) = 3

Constraints: In a pair numbers should be different and all the pairs should be unique.

Lets say, a = [6, 6, 3, 9, 3, 5, 1]

k = 12

Possible pairs: (6 , 6), (3, 9), (9, 3)

But as per given constraints,  (6, 6) is invalid. And, (3,9) and (9, 3) both are same so we’ll consider only one of them.

Algorithm:

Step1: Prepare a dictionary and add all the items of the array into this dictionary. Array items as KEY and their frequency as VALUE. As we don’t care about the value of this dictionary, we just need a better data structure, to get our item fast, and dictionary is best for such kind of tasks.

Step2: Now as all the unique items have  been inserted in dictionary, so loop over given array and check for (K – array item). If this exists as KEY in dictionary that means there is a pair and it would be (K – array item, array item). But, once we have found a pair we need to check it should not be the same item. If all the constraints are satisfied then increase the count of pairs.

Step3: Now after all these we have number of pairs. But is this our output? Nope.

In our dictionary we have all the unique items of the array, that means for a pair, it contains both the items into this dictionary. For example, items 3,4 both are in dictionary and in our count variable we included pair (3, 4) and (4, 3). But as per our constraints we need to include them only once. So in count of pairs would be our (count variable / 2).

C# Code:

        static void GetNumberOfPairs()
        {
            int[] a = { 2, 4, 3, 5, 6, -2, 4, 7, 8, 9 };
            int k = 7;
            int count = NumberOfPairs(a, k);
            Console.WriteLine(count);
        }
        static int NumberOfPairs(int[] a, long k)
        {
            var count = 0;
            var dict = new Dictionary<int, int>();
            foreach (int item in a)
            {
                if (dict.ContainsKey(item))
                {
                    dict[item]++;
                }
                else
                {
                    dict.Add(item, 1);
                }
            }

            for (int i = 0; i < a.Length; i++)
            {
                if (dict.ContainsKey((int)k - a[i]) && (k - a[i] != a[i]))
                {
                    count++;
                }
            }

            return count / 2;
        }

Determining triangle type based on sides length in C#

Our task is to determine what kind of triangle it is based on it’s side’s length. Before we start let’s understand definitions of triangles:

Equilateral: All the side are equal in size.

Isosceles: Any two sized are equal.

Algorithm: We’ll group our sides and if group count is 1 that means triangle is EQUILATERAL. If group count is 2 that means it’s ISOSCELES. If group count is greater than 2 that means NONE OF THESE.

Code in C#

        static void Main(string[] args)
        {
            int N = Convert.ToInt32(Console.ReadLine());
            for (int i = 0; i < N; ++i)
            {
                string[] input = Console.ReadLine().Split(' ');
                TrianleType(input);
            }
            Console.ReadKey();
        }

        private static void TrianleType(string[] input)
        {
            int count = input.GroupBy(x => x).Count();
            if (count == 1)
            {
                Console.WriteLine("Equilateral");
            }
            else if (count == 2)
            {
                Console.WriteLine("Isosceles");
            }
            else 
            {
                Console.WriteLine("None of these");
            }
        }

Find all pair of Array of Integers whose sum is equal to a given number in C#

Our task is to find all the possible pairs (no duplication) of integers whose sum is given. See below examples:

Array : [2, 4, 3, 5, 6, -2, 4, 7, 8, 9]
Given sum : 7
pairs whose sum is equal to value : 7
(2, 5) , (4, 3) , (3, 4) , (-2, 9)

Array : [0, 14, 0, 4, 7, 8, 3, 5, 7]
Sum : 11
pairs whose sum equals: 11
(7, 4) , (3, 8) , (7, 4)

Array : [10, 9, 5, 9, 0, 10, 2, 10, 1, 9]
Sum : 12
pairs whose sum equals 12
(2, 10)

There are two ways of doing this,

Method 1: Brute Force approach – use two nested loops and make a pair and compare sum of them with given number. Its time complexity would be O(n^2).

Method 2: In this method we loop over the array only once. For each item of array, subtract this item from given number and if array item doesn’t exist in our list then add it otherwise print this item and subtraction of array item and given number. Its time complexity would be O(n) as we loop over only once and comparison are also less.

        static void Main(string[] args)
        {
            int[] arr = { 2, 4, 3, 5, 6, -2, 4, 7, 8, 9 };
            int n = 7;
            PrintPairs(arr, n);
            Console.ReadKey();
        }
               
        private static void PrintPairs(int[] arr, int n)
        {
            List<int> arrayItemList = new List<int>();
            foreach (var item in arr)
            {
                int remainingvalue = n - item;
                if (arrayItemList.Contains(remainingvalue))
                {
                    Console.WriteLine($"({ item},{remainingvalue})");
                }
                else
                {
                    arrayItemList.Add(item);
                }
            }
        }

Find Two Missing Numbers in O(n)

Given an array of n unique integers where each element in the array is in range [1, n]. The array is not necessarily sorted and has all distinct elements. The task is to find missing numbers if there is any.

Input  : {10, 5, 8, 1}
Output : 2, 3, 4, 6, 7, 9

Input : {3, 2, 4}
Output : 1 

Input : arr[] = {1, 2}
Output :

Algorithm: As array is not sorted so we first add all the items into dictionary (because reading is index based and quite fast).

Step1: Loop over the array and add all the items to our dictionary. Dictionary will have array items as KEY and if item is present in array then Value would be TRUE else FALSE.

Step2: Find the greatest item of the array.

Step3: Loop from 1 to the max item of the array

Step4. For each iteration of the loop, check whether this number is present in our Dictionary. if not present then print this number, otherwise skip.

class FindTwoMissingNumbers
    {
        static void Main(string[] args)
        {
            /// Input array
            int[] arr = { 10, 2, 8, 6, 5 };
 
            /// Temporary container. Array item will be our KEY and Value
            /// would be if TRUE that means item is not missing, FALSE 
            /// means item is missing so print this item.
            /// 
            Dictionary<int, bool> dict = new Dictionary<int, bool>();
 
            /// Add all the array items to this container. Array item 
            /// will be our KEY and value would be TRUE for all the items.
            for (int i = 0; i < arr.Length; ++i)
            {
                dict.Add(arr[i], true);
            }
 
            /// Loop from 1 to n (nth item of the array, i.e. max item of the array)
            int maxItem = arr.Max(x => x);
            for (int i = 1; i <= maxItem; ++i)
            {
                /// If a number is not present that means this is missing item
                /// so print it
                if (!dict.ContainsKey(i))
                {
                    Console.WriteLine(i);
                }
            }
 
            Console.ReadKey();
        }
    }

 

Check if string follows order of characters defined by a pattern or not.

Given an input string and a pattern, check if characters in the input string follows the same order as determined by characters present in the pattern. Assume there won’t be any duplicate characters in the pattern.

Examples:

Input: string = "engineers rock", pattern = "er";
Output: true
All 'e' in the input string are before all 'r'.

Input: string = "engineers rock", pattern = "egr";
Output: false
There are two 'e' after 'g' in the input string.

Input: string = "engineers rock", pattern = "gsr";
Output: false
There are one 'r' before 's' in the input string.

Algorithm: The approach is quite simple. Please follow the below steps:

Step1: First get a new filtered string from input string that has same characters as pattern.

1.1. Loop over all the characters of the input string.
1.2. Check whether a input string’s character matches with any character of pattern.
1.3. If there are any consecutive characters then add only one character to our filtered list. To do so, use a char type variable and match it with current variable, if matches then skip otherwise add current character to our filtered list.

Step2: Filtered list has only same number of characters as our pattern, if not then return FASLE, if yes then match all the characters. If there is any character that doesn’t match in the same sequence as pattern then return false otherwise return TRUE.

We are done now. Lets see the actual implementation of the above algorithm.

class StringPatternMatching
{
  static void Main(string[] args)
  {
    Console.WriteLine(IsStringFollowThePattern("engineers rock", "er"));
    Console.WriteLine(IsStringFollowThePattern("engineers rock", "egr"));
    Console.WriteLine(IsStringFollowThePattern("engineers rock", "gsr"));
    Console.WriteLine(IsStringFollowThePattern("engineers rock", "eger"));
    Console.ReadKey();
  }
 
  static bool IsStringFollowThePattern(string input, string pattern)
  {
    var filteredInputCharacters = new List<char>();
    char previousChar = default(char);
    /// Loop over the input string to get only pattern matching 
    /// characters
    foreach (var item in input)
    {
      /// Check for the pattern characters, if match then go
      if (pattern.Contains(item))
      {
         /// If there are consecutive duplicate characters then add 
         /// only one, skip rest. If previous character is same as 
         /// current character then skip otherwise add it to our
         /// filtered list.
         if (previousChar != item)
         {
            filteredInputCharacters.Add(item);
            previousChar = item;
         }
       }
     }
 
     /// Filtered list has only same number of characters as our pattern, 
     /// if not then return FASLE, if yes then match all the characters.
     /// If there is any character that doesn't match in the same sequence 
     /// as pattern then return false otherwise return TRUE.
     for (int i = 0; i < filteredInputCharacters.Count; ++i)
     {
       if (filteredInputCharacters[i] != pattern[j])
       {
         return false;
       }
     }
 
     return true;
   }
}