Remove duplicates from a linked List in C#

Problem source: HackerRank -More Linked Lists

You have a linked list that has n Nodes and their data is in ascending order. A Node object has an integer data field, data, and a Node instance pointer, , pointing to another node (i.e.: the next node in a list). our task is to write a method to remove duplicates from this list and print remaining nodes.

Sample Input

6
1
2
2
3
3
4

Sample Output

1 2 3 4 

Explanation

N is total number of Nodes in linked list. The data, 2 and 3 occurs more than one so we need to delete duplicate nodes from the linked list. Once all the duplicate nodes are deleted then print this linked list , which is 1, 2, 3, 4.

class MoreLinkedLists
    {
        public class Node
        {
            public int data;
            public Node next;
            public Node(int d)
            {
                data = d;
                next = null;
            }
        }
        static void Main(string[] args)
        {
            Node head = null;
            int T = Int32.Parse(Console.ReadLine());
            while (T-- > 0)
            {
                int data = Int32.Parse(Console.ReadLine());
                head = Insert(head, data);
            }

            head = removeDuplicates(head);
            display(head);
            Console.ReadKey();
        }

        public static Node removeDuplicates(Node head)
        {
            if (head != null)
            {
                Node start = head;
                while (start != null)
                {
                    if (start.next != null && start.data == start.next.data)
                    {
                        start.next = start.next.next;
                    }
                    else
                    {
                        start = start.next;
                    }
                }
            }
            return head;
        }

        public static Node Insert(Node head, int data)
        {
            Node p = new Node(data);
            if (head == null)
            {
                head = p;
            }
            else if (head.next == null)
            {
                head.next = p;
            }
            else
            {
                Node start = head;
                while (start.next != null)
                {
                    start = start.next;
                }
                start.next = p;
            }
            return head;
        }

        public static void display(Node head)
        {
            Node start = head;
            while (start != null)
            {
                Console.Write(start.data + " ");
                start = start.next;
            }
        }
    }

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

Reverse an Integer Array without using extra space in C#

Our approach is to solve this problem without traversing whole array. So we keep two variables, one is set to start item of an array and another is set to end item of an array.and we move both of them simultaneously. So, in n/2 iterations we completely traverse the array.

Time complexity = O(n)

        static void Main(string[] args)
        {
            int[] arr = { 61, 19, 34, 83, 123, 97 };
            Reverse(arr);
            foreach (var item in arr)
            {
                Console.WriteLine(item);
            }
            Console.ReadKey();
        }

        static void Reverse(int[] arr)
        {
            if (arr.Length == 0 || arr.Length == 1)
            {
                return;
            }
            else
            {
                int start = 0, end = arr.Length - 1, temp = 0;
                while (start < end)
                {
                    temp = arr[end];
                    arr[end] = arr[start];
                    arr[start] = temp;
                    ++start;
                    --end;
                }
            }
        }

Our task is to find top two integers from an integer array. For example:

Array: []

Output: Invalid Input

Array: [-1]

output: Max1: -1, Max2: -1

Array: [2,18]

Output: Max1: 2, Max2: 18

Array:[15, 45, 34, 100, -456, 432, 2, 1000]

Output: Max1: 1000, Max2: 432

Code in C#:

 class FindTopTwoIetemsFromUnSortedArray
    {
        static void Main(string[] args)
        {
            int[] arr = { 12342,-162361,12342};
            FindTopTwoMaxIntegers(arr);
            Console.ReadKey();
        }

        static void FindTopTwoMaxIntegers(int[] arr)
        {
            if (arr == null || arr.Length == 0)
            {
                Console.WriteLine("Invalid input");
            }
            else
            {
                int max1 = int.MinValue, max2 = int.MinValue;
                foreach (int item in arr)
                {
                    if (item >= max1)
                    {
                        max2 = max1;
                        max1 = item;
                    }
                    else if (item <item > max2)
                    {
                        max2 = item;
                    }
                }

                if (max2 == int.MinValue)
                {
                    max2 = max1;
                }

                Console.WriteLine($"Max1:{max1}, Max2: {max2}");
            }
        }
    }

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