Archive for June, 2013

Today we have to write a program for finding the balance index in a given array. This problem can be solved on O( n ) time.

Approach 1

  1. Loop Through the array and calculate the sum ,let’s assume sum is equal to arraySum.
  2. Now again again iterate over array elements
    1. Calculate the sum of element say it is leftsum
    2. calculate the difference between arraySum and current Element in arraySum
    3. if arraySum is equal to leftSum, then current array index is the balance index.
  3. Otherwise return –1, means balance index is not present in the array.

Code:

        public static int BalanceIndex(int[] input)
        {
            int arraySum = 0;
            int leftSum = 0;
            int balnaceIndex = -1;
            //Calculate the sum of all elements
            for (int i = 0; i < input.Length; i++)
            {
                arraySum = arraySum + input[i];
            }

            Console.WriteLine("Sum of Array Elements : " + arraySum);

            for (int i = 0; i < input.Length; i++)
            {
                leftSum = leftSum + input[i];
                arraySum = arraySum - input[i];
                if (arraySum == leftSum)
                {
                    balnaceIndex = i;
                    return balnaceIndex;
                }
            }

            if (leftSum != arraySum)
            {
                return -1;
            }
            return balnaceIndex;
        }

Test Case

private static void BalanceIndexTest()

{

    int[] arr = new int[] { -7, 1, 5, 2, -4, 3, 0,8 };

    Console.WriteLine("Balance index for " + string.Join(",", arr) + " is : " + ArrayProblems.BalanceIndex(arr));

    int[] arr1 = new int[] { 1, 3, 4, 6, 7, 2, 5, 9, 1, 11, 9, 6, 5, 8, 9, 1 };

    Console.WriteLine("Balance index for " + string.Join(",", arr1) + " is : " + ArrayProblems.BalanceIndex(arr1));

    int[] arr2 = new int[] { -7, 1, 5, 2, -4, 3, 0};

    Console.WriteLine("Balance index for " + string.Join(",", arr2) + " is : " + ArrayProblems.BalanceIndex(arr2));


    int[] arr3 = new int[] { -7 };

    Console.WriteLine("Balance index for " + string.Join(",", arr3) + " is : " + ArrayProblems.BalanceIndex(arr));


}

Output

Sum of Array Elements : 8

Balance index for -7,1,5,2,-4,3,0,8 is : –1

Sum of Array Elements : 87

Balance index for 1,3,4,6,7,2,5,9,1,11,9,6,5,8,9,1 is : –1

Sum of Array Elements : 0

Balance index for -7,1,5,2,-4,3,0 is : 5

Sum of Array Elements : -7

Balance index for -7 is : -1

Write A Program to Detect Loop in Singly LinkedList

Given a single linked list, we have to detect loop. For this we will use two pointers called slow and fast. We will increment slow by one and fast by two. once both these pointers meet, this is the node from were loop is present

        public void DetectLoop(Node<T> node)
        {
            Node<T> slow = node;
            Node<T> fast = node;

            while (slow != fast && fast.Next != null)
            {
                slow = slow.Next;
                fast = fast.Next.Next;
                if (slow == fast)
                {
                    Console.WriteLine("Loop is detected");
                    return;
                }
            }
            Console.WriteLine("There is no loop");

        }

Write a Program to Print Following Number Pattern

Input  : Number of Rows

Output:

1
121
12321
1234321
123454321

Code

 

        public static void PrintNumberPattern2(int rows)
        {
            int i, j, k;
            //Loop for number of Rows
            for (i = 1; i <= rows; i++)
            {
                // Loop for printing numbers in increasing order
                for (j = 1; j < 2 * i + 1; j++)
                {
                    Console.Write(j);
                    if (j >= i)
                    {
                        break;
                    }
                }
                // Loop for printing numbers in decreasing order
                for (k = j - 1; k > 0; k--)
                {
                    Console.Write(k);
                }
                Console.WriteLine("");
            }
        }

Write a Program for Rotate a Sqaure Matrix by 90 Degree

Today we have to write a program for rotating a given matrix by 90 degree. This code only works with square matrix.

Code

        public static void MatrixRotation<T>(T[,] matrix)
        {
            Console.WriteLine("\n Input Matrix");
            Print2DMatrix(matrix);
            int row = matrix.GetLength(0);
            int column = matrix.GetLength(1);

            T temp;
            for (int i = 0; i < row; i++)
            {
                for (int j = i + 1; j < column; j++)
                {
                    temp = matrix[j, i];
                    matrix[j, i] = matrix[i, j];
                    matrix[i, j] = temp;
                }
            }


            for (int i = 0; i < row / 2; i++)
            {
                for (int j = 0; j < column; j++)
                {
                    temp = matrix[j, i];
                    matrix[j, i] = matrix[j, row - i - 1];
                    matrix[j, row - i - 1] = temp;
                }
            }
            Console.WriteLine("\n Rotation matrix");
            Print2DMatrix(matrix);

        }

        private static void Print2DMatrix<T>(T[,] matrix)
        {
            Console.WriteLine("--------------\n");
            int row = matrix.GetLength(0);
            int column = matrix.GetLength(1);

            for (int i = 0; i < row; i++)
            {
                for (int j = 0; j < column; j++)
                {
                    Console.Write(matrix[i, j] + " ");
                }
                Console.WriteLine(" ");
            }

        }

Result


Input Matrix

————–

11 12 13 14 15

21 22 23 24 25

31 32 33 34 35

41 42 43 44 45

51 52 53 54 55

Rotation matrix

————–

51 41 31 21 11

52 42 32 22 12

53 43 33 23 13

54 44 34 24 14

55 45 35 25 15

Input Matrix

————–

A B C D

E F G H

I J K L

M N O P

Rotation matrix

————–

M I E A

N J F B

O K G C

P L H D