Archive for July, 2012

Given a number n, print all primes smaller than or equal to n

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example, 5 is prime, as only 1 and 5 divide it.

For computing prime numbers we will use Sieve of Eratosthenes algorithm. The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes (below 10 million or so).

Algorithm

To find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:

  1. Create a list of consecutive integers from 2 to n: (2, 3, 4, …, n).
  2. Initially, let p equal 2, the first prime number.
  3. Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked.
  4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

When the algorithm terminates, all the numbers in the list that are not marked are prime

 public static void PrimeNumber(int n)
    {
      int[] numbers = new int[n + 1];
      if (n < 0)
      {
        Console.WriteLine("invalid value");
        return;
      }
      if (n < 3)
      {
        Console.WriteLine("Prime number is : 2");
        return;

      }


      int p = 0;
      for (int i = 2; i <= n; i++)
      {
        if (numbers[i] == 0)
        {
          p = i;
          for (int j = 2; p * j <= n; j++)
          {
            numbers[p * j] = 1;
          }
        }
      }

      for (int i = 2; i <= n; i++)
      {
        if (numbers[i] == 0) Console.Write(i + " , ");
      }


    }

Reverse the word in a string

For reversing the word in a string I used following algorithm

  1. Traverse the string and push the characters in stack, until we get space
  2. When space is encountered, pop the element from stack and enqueue in queue
  3. enqueue the spaces in queue
  4. once the traverse is complete add the last word in queue

Stack is used to reverse the characters and queue is used to maintain the order of characters

 

   public static void ReverseWordOfString(string s)
    {
      if (string.IsNullOrEmpty(s))
      {
        Console.WriteLine("String is empty");
        return;
      }

      Stack<char> charStack = new Stack<char>();
      var charArray = s.ToCharArray();
      int length = charArray.Length;
      Queue<char> result = new Queue<char>();
      Console.WriteLine("input string : {0}", s);
      for (int i = 0; i < length; i++)
      {
        if (charArray[i] != ' ')
        {
          charStack.Push(charArray[i]);
        }
        else
        {
          while (charStack.Count > 0)
          {
            result.Enqueue(charStack.Pop());
          }
          result.Enqueue(' ');
        }
      }
      while (charStack.Count > 0)
      {
        result.Enqueue(charStack.Pop());

      }

      Console.Write("String After reversing the words : ");
      Console.Write(result.ToArray());
      Console.WriteLine();

    }

RIL : Given AAABBGFF should get an output 3{A} 2{B}1{G}2{F}

Run-length encoding (RLE) is a very simple form of data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run. This is most useful on data that contains many such runs: for example, simple graphic images such as icons, line drawings, and animations. It is not useful with files that don’t have many runs as it could greatly increase the file size.

  /// <summary>
        /// Given AAABBGFF should get an output 3{A} 2{B}1{G}2{F}
        /// http://en.wikipedia.org/wiki/Run-length_encoding
        /// </summary>
        /// <param name="input"></param>
        public static void RIL(string input)
        {
            Console.Write(input + " : " );
            StringBuilder output = new StringBuilder();
            int charCount = 0;
            var inputChars = input.ToCharArray();
            char currentChar, nextChar;
            currentChar = nextChar = inputChars[0];

            for (int i = 0; i < inputChars.Length; i++)
            {
                currentChar = inputChars[i];
                if (i + 1 < inputChars.Length)
                {
                   
                    nextChar = inputChars[i + 1];
                }
                if (currentChar  != nextChar )
                {

                    output.Append(charCount + 1);
                    output.Append("{");
                    output.Append(currentChar);
                    output.Append("}");
                    charCount = 0;
                
                }
                else {
                    charCount++;
                }
            }
            output.Append(charCount );
            output.Append("{");
            output.Append(currentChar);
            output.Append("}");
            
            Console.Write(output.ToString());
            Console.WriteLine();

        }

Test Cases

  1. AAABBGFF : 3{A}2{B}1{G}2{F}
  2. WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWW WWWWWWBWWWWWWWWWWWWWW : 12{W}1{B}12{W}3{B}24{W}1{B}14{W}
  3. AAABBGGGGGGGGFFXXXXXXTTTTTyyyyyyvvvvv : 3{A}2{B}8{G}2{F}6{X}5{T}6{y}5{v}
  4. AAAABBCCCCCCCBBCCCCDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD :

    4{A}2{B}7{C}2{B}4{C}38{D}

In a clock, calculate the angle between hour and minute handle

A method to solve such problems is to consider the rate of change of the angle in degrees per minute. The hour hand of a normal 12-hour analogue clock turns 360° in 12 hours (720 minutes) or 0.5° per minute. The minute hand rotates through 360° in 60 minutes or 6° per minute.

Equation for the angle of the hour hand

ΘH = (60H+M)/2

 

Equation for the degrees on the minute hand

ΘM= 6M

M= Minute and H = Hour

Angle between Hour and minute handle

ΘH - ΘM

Co-ordinate of triangle: A(x1, y1), B(x2, y2), C(x3, y3) and Point P (x, y).

Approach:

  1. Calculate the area triangle that is are of triangle ABC. Area A
  2. Calculate the area of PAB. Area A1
  3. Calculate the area of PBC. Area A2
  4. Calculate the area PCA. Area A3
  5. If Point P lies outside the triangle than A1+A2+A3 >A.

Area of Triangle: [x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2)]/2

In above approach, we will have precision problem because we are dividing the result by 2. So to handle this issue, by taking off 2 times of triangle are.

sub list of a sorted (ascending order)link list is reversed. correct it

sub list of a sorted (ascending order)link list is reversed. correct it.

Input
1->2->3->4->8->7->6->5->9->10->11
Output
1->2->3->4->5->6->7->8->9->10->11

To solve this problem :

  1. Find the pointer, from dis order starts say first
  2. Find the pointer where dis order ends say last node
  3. Setting next of last node to null
  4. Reverse the linked list from first to last
  5. join the linked list with reversed linked list
  6. join the linked list with remaining list

Node Class : Used for Creating Link List

public class Node<T>
  {
    private T nodeValue;
    private Node<T> nextNode;

    public Node()
    {
      this.nodeValue = default(T);
      this.nextNode = null;
    }

    public Node(T nodeValue)
    {
      this.nodeValue = nodeValue;
      this.nextNode = null;
    }

    /// <summary>
    /// Value of node
    /// </summary>
    public T NodeValue
    {
      get { return nodeValue; }
      set { this.nodeValue = value; }
    }

    /// <summary>
    /// The node this node links to
    /// </summary>
    public Node<T> NextNode
    {
      get { return this.nextNode; }
      set { this.nextNode = value; }
    }
  }
    /// <summary>
    /// 1--->2--->3--->4--->9--->8-->7--->6--->5--->10--->11--->NULL
    /// </summary>
    /// <param name="head"></param>
    public static void correctList(Node<int> head)
    {

      if (head == null)
      {
        Console.WriteLine("Empty List");
        return;
      }

      Node<int> current = head;
      Node<int> first = null;
      Node<int> last = null;
      Node<int> mark1 = null;

      while (current != null && current.NodeValue < current.NextNode.NodeValue)
      {
        mark1 = current;
        current = current.NextNode;
      }

      first = current; //Pointer to node, LL Disorder starts

      while (current != null && current.NodeValue > current.NextNode.NodeValue)
        current = current.NextNode;


      last = current.NextNode; //Pointer to node, LL Disorder Ends

      current.NextNode = null; // Setting next of last node to null

      Reverse(ref first);//reverse the sub list that dis order starts to disorder ends

      mark1.NextNode = first; // join the initial linklist with reversed linkedlist 

      while (first.NextNode != null)
      {
        first = first.NextNode;
      }

      first.NextNode = last; // join the merged link list with sorted linklist
      Console.WriteLine();
      Console.WriteLine("Output");
      
      PrintList(head);
      Console.WriteLine();

    }

    public static void Reverse(ref Node<int> head)
    {

      Node<int> first;
      Node<int> rest;
      if (head == null) return;
      first = head;
      rest = first.NextNode;
      if (rest == null) return;
      Reverse(ref rest);
      first.NextNode.NextNode = first;
      first.NextNode = null;
      head = rest;

    }
    public static void PrintList(Node<int> head)
    {
      while (head != null)
      {
        Console.Write(head.NodeValue);
        head = head.NextNode;
        if (head != null) Console.Write("->");
      }

    }

Main Program

      Node<int> a = new Node<int>(1);
      Node<int> a1 = new Node<int>(2);
      Node<int> a2 = new Node<int>(3);
      Node<int> a3 = new Node<int>(4);
      Node<int> a4 = new Node<int>(8);
      Node<int> a5 = new Node<int>(7);
      Node<int> a6 = new Node<int>(6);
      Node<int> a7 = new Node<int>(5);
      Node<int> a8 = new Node<int>(9);
      Node<int> a9 = new Node<int>(10);
      Node<int> a10 = new Node<int>(11);

      a.NextNode = a1;
      a1.NextNode = a2;
      
      a2.NextNode = a3;
      
      a3.NextNode = a4;
      
      a4.NextNode = a5;
      
      a5.NextNode = a6;
      
      a6.NextNode = a7;
      
      a7.NextNode = a8;
      
      a8.NextNode = a9;

      a9.NextNode = a10;
      
      a10.NextNode = null;
      Console.WriteLine("Input");
      Microsoft.PrintList(a);
      Microsoft.correctList(a);

In computational complexity theory, 3SUM is the following computational problem conjectured to require roughly quadratic time:

Given a set S of n integers, are there elements a, b, c in S such that a + b + c = 0?

It is possible to solve the algorithm in O(n2) time using simple algorithms, and matching lower bounds are known for some specialized models of computation.

The program mentioned below works only with sorted List

 public static void SortedList3SumProblem(int[] inputArray)
    {
      int a, b, c;
      int length = inputArray.Length;
      for (int i = 0; i < length - 3; i++)
      {

        a = inputArray[i];
        int k = i + 1;
        int l = length  - 1;

        while (k < l)
        {
          b = inputArray[k];
          c = inputArray[l];
          if (a + b + c == 0)
          {
            Console.WriteLine(a + "," + b + "," + c); ;
            break;
          }
          else if (a + b + c > 0)
            l = l - 1;
          else
            k = k + 1;
        }

      }
    }

Input

0, -25, -10, -7, -3, 2, 4, 8, 10

Output

Input Array

0;-25;-10;-7;-3;2;4;8;10

——————————–

0,-10,10

-10,2,8

-7,-3,10

 public static void RepeatedEvenTimes(int[] inputArray)
    {
      Dictionary<int, int> numbers = new Dictionary<int, int>();
      int length = inputArray.Length;
      int num = -1;
      for (int i = 0; i < length; i++)
      {
        if (numbers.Keys.Contains(inputArray[i]))
        {
          numbers[inputArray[i]] = numbers[inputArray[i]] + 1;
        }
        else
        {

          numbers.Add(inputArray[i], 1);
        }
      }

      Console.Write("input Array ");
      Console.WriteLine(string.Join(",", inputArray));

      foreach (var item in numbers)
      {
        if (item.Value % 2 == 0)
        {
          num = item.Key;
          Console.WriteLine("{0} Repeated {1} times ", item.Key, item.Value);
          break;
        }

      }

      if (num == -1)
      {
        Console.WriteLine("No number Repeated even number of times");
      }

      Console.WriteLine("-----------------------------------------------");
    }
 

input Array 3,3,3,5,5,5,2,2,2
No number Repeated even number of times
———————————————–
input Array 100,1,1,3,5,3,3
1 Repeated 2 times
———————————————–
input Array 2,2,2,2,2
No number Repeated even number of times
———————————————–

Reverse LinkList using Recursion

Node Class : For creating LinkList

public class Node<T>
    {
        private T nodeValue;
        private Node<T> nextNode;

        public Node()
        {
            this.nodeValue = default(T);
            this.nextNode = null;
        }

        public Node(T nodeValue)
        {
            this.nodeValue = nodeValue;
            this.nextNode = null;
        }

        /// <summary>
        /// Value of node
        /// </summary>
        public T NodeValue
        {
            get { return nodeValue; }
            set { this.nodeValue = value; }
        }

        /// <summary>
        /// The node this node links to
        /// </summary>
        public Node<T> NextNode
        {
            get { return this.nextNode; }
            set { this.nextNode = value; }
        }
    }

LinkList

class LinkList
    {
        public static void Test()
        {
            // Create a link list
            Node<int> a1 = new Node<int>();
            a1.NodeValue = 10;

            Node<int> a2 = new Node<int>();
            a2.NodeValue = 11;

            Node<int> a5 = new Node<int>();
            a5.NodeValue = 12;

            Node<int> a3 = new Node<int>();
            a3.NodeValue = 13;

            Node<int> a4 = new Node<int>();
            a4.NodeValue = 14;
            a1.NextNode = a2;
            a2.NextNode = a3;
            a3.NextNode = a4;
            a4.NextNode = a5;
            a5.NextNode = null;

            //reverse the link list
            
            Console.WriteLine("----------------------------------------------------");
            Console.WriteLine("Reverse  List");           
            Reverse(ref a1);           
            PrintLinkList(a1);
            Console.WriteLine("----------------------------------------------------");

        }
        public static void Reverse(ref Node<int> head)
        {

            Node<int> first;
            Node<int> rest;
            if (head == null) return;
            first = head;
            rest = first.NextNode;
            if (rest == null) return;
            Reverse(ref rest);
            first.NextNode.NextNode = first;
            first.NextNode = null;
            head = rest;

        }
        public static void PrintLinkList(Node<int> head)
        {
            var temp = head;
            while (temp != null)
            {
                Console.Write(temp.NodeValue + "-->"
                  );
                temp = temp.NextNode;

            }
            Console.WriteLine();

        }




    }

Write a Program to Return Excel Sheet Column Header Name if Input is a Number

input

           -11
              1
            26
            52
            28
           702
           703

output

input number -11 is invalid
input number 1 , output alphabet A
input number 26 , output alphabet Z
input number 52 , output alphabet AZ
input number 28 , output alphabet AB
input number 702 , output alphabet ZZ
input number 703 , output alphabet AAA

 public static string ConvertToAlphabet(int number)
        {
            int temp = number;
            char[] alphabets = new char[] { 'A', 'B', 'C', 'D', 'E', 
                                            'F', 'G', 'H', 'I', 'J', 
                                            'K', 'L', 'M', 'N', 'O', 
                                            'P', 'Q', 'R', 'S', 'T', 
                                            'U', 'V', 'W', 'X', 'Y', 
                                            'Z' };
            string Alphabet = string.Empty;
            int Index = 0;

            if (number <= 0)
            {

                Console.WriteLine("input number {0} is invalid", temp);

                return string.Empty;
            }

            if (number < 27)
            {

                Console.WriteLine("input number {0} , output alphabet {1}"
                    , temp, alphabets[number - 1]);

                return alphabets[number - 1].ToString();
            }
            while (number > 0)
            {
                Index = number % 26;
                number = number / 26; ;

                if (Index == 0)
                {
                    Index = 26;
                    number = number - 1;
                }
                Alphabet = alphabets[Index - 1] + Alphabet;

            }

            Console.WriteLine("input number {0} , output alphabet {1}"
                , temp, Alphabet);
            return Alphabet;
        }