Showing posts with label C#. Show all posts
Showing posts with label C#. Show all posts

Friday, April 3, 2015

How to implement Stack using linked list

Stacks are easier to implement using linked lists. There is no need to set a limit on the size of the stack

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LinkedlistUsingStack
{
    public class Node
    {
        public int Data { get; set; }
        public Node Next { get; set; }
        public Node(int data)
        {
            this.Data = data;
        }
    }
    public class Stack
    {
        private Node _stackTop;

        public void Push(int newValue)
        {
            Node newNode = new Node(newValue);

            newNode.Next = _stackTop;
            _stackTop = newNode;

        }
        public bool IsEmpty()
        {
            return _stackTop == null;
        }
        public int Pop()
        {
            Node temp = _stackTop;
            var data = temp.Data;
            _stackTop = temp.Next;
            return data;
        }
        public void Print()
        {
            Node current = _stackTop;
            while (current != null)
            {
                Console.WriteLine(current.Data);
                current = current.Next;
            }
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            Stack st = new Stack();
            st.Push(1);
            st.Push(2);
            st.Push(3);
            Console.WriteLine("Before Pop");
            st.Print();
            st.Pop();
            st.Pop();
            Console.WriteLine(st.IsEmpty());
            Console.WriteLine("After Pop");
            st.Print();
        }
    }
}

Sunday, March 29, 2015

How to Find if Linked List contains Loops or Cycles in C#

In this post I will show you how to detect loop in linked list.

We can find the loop in the linked list via Floyd’s Cycle-Finding Algorithm, explained here.

The algorithm is pretty straightforward:

  1. We start at the beginning of the linked list with two pointers.
  2. The first pointer is incremented through each node of the list. The second pointer moves twice as fast, and skips every other node.
  3. If the linked list contains a loop, these two pointers will eventually meet at the same node, thus indicating that the linked list contains a loop.

.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algo
{
    public class Node
    {
        public Node Next { get; set; }
        public int Value { get; set; }
        public Node(int value)
        {
            this.Value = value;
        }

    }
    public class LinkedList
    {
        private Node _head;
        public LinkedList()
        {

        }
        public void AppendLast(Node newNode)
        {
            if (_head == null)
            {
                _head = newNode;
            }
            else
            {
                Node current = _head;
                while (current.Next != null)
                {
                    current = current.Next;
                }
                current.Next = newNode;
            }
        }
        public override string ToString()
        {
            Node current = _head;
            StringBuilder builder = new StringBuilder();
            while (current != null)
            {
                builder.Append(current.Value + "->");
                current = current.Next;
            }
            return builder.ToString();
        }
        public bool IsCycle()
        {
            Node slow = _head;
            Node fast = _head;
            while (fast != null && fast.Next != null)
            {
                fast = fast.Next.Next;
                slow = slow.Next;
                if (slow == fast)
                    return true;
            }
            return false;

        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            LinkedList list = new LinkedList();
            list.AppendLast(new Node(10));
            list.AppendLast(new Node(20));
            list.AppendLast(new Node(30));
            Node cycle = new Node(40);
            list.AppendLast(cycle);
            list.AppendLast(new Node(60));
            list.AppendLast(cycle);

            if (list.IsCycle())
            {
                Console.WriteLine("Linked List is cyclic as it contains cycle or loop");
            }
            else
            {
                Console.WriteLine("LinkedList is not cyclic, no loop or cycle found");
            }



        }
    }
}

Reverse a given linked list in c#

 

In this post I will show you how to reverse a  given linked list in c#.For example a given linked list as show below

10->20->30-NULL

then output should be

30->20->10-NULL

 

image

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algo
{
    public class List
    {
        public List Next { get; set; }
        public int Value { get; set; }
        public List(int value)
        {
            Value = value;
        }
        public override string ToString()
        {
            List current = this;
            StringBuilder builder = new StringBuilder();
            while (current!=null)
            {
                builder.Append(current.Value + "->");
                current = current.Next;
            }
            return builder.ToString();
        }
        public List ReverseList()
        {
            List prev = null;
            List next = null;
            List current = this;
            while (current!=null)
            {
                next = current.Next;
                current.Next = prev;
                prev = current;
                current = next;
            }
            return prev;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            List list = new List(10);
            list.Next = new List(20);
            list.Next.Next = new List(30);
            Console.WriteLine(list);
            var rev = list.ReverseList();
            Console.WriteLine(rev);
        }
    }
}

How to check a tree is a binary tree of not

This is continuation of my post How to create binary tree in c#.In this post I will show you how to check a given tree is a binary tree or not.

  public bool isBST()
        {
            return (IsBST(_root));
        }
private bool IsBST(Node node)
        {
            if (node == null) return (true);

            // do the subtrees contain values that do not 
            // agree with the node? 
            if (node.Left != null && FindMaxValue(node.Left) > node.Data) return (false);
            if (node.Right != null && FindMinValue(node.Right) <= node.Data) return (false);

            // check that the subtrees themselves are ok 
            return (IsBST(node.Left) && IsBST(node.Right));
 } 

Mirror of a binary tree

 

This is continuation of my post How to create binary tree in c#.In this post I will show you how convert a given binary tree into it’s mirror image.

/**
Changes the tree into its mirror image.

So the tree...
       4
      / \
     2   5
    / \
   1   3

is changed to...
       4
      / \
     5   2
        / \
       3   1

Strategy:Uses a recursive helper that recurs over the tree, swapping the left/right pointers.

 public void MirrorTree()
        {
            MirrorTree(_root);
        }

private void MirrorTree(Node node)
        {
            if (node != null)
            {
                // do the sub-trees 
                MirrorTree(node.Left);
                MirrorTree(node.Right);

                // swap the left/right pointers 
                Node temp = node.Left;
                node.Left = node.Right;
                node.Right = temp;
            }
 } 

How to print out all path from root to leaf of a given binary tree

This is continuation of my post How to create binary tree in c#.In this post I will show you how to print all path from root to leaf of a given binary tree in c#.Let’s consider following binary tree.

             *       4
             *    2     5
             *  1    3    

For above tree there are three path from root to leaf

Path 1 : 4 2 1

Path 2: 4 2 3

Path 3: 4 5

  public void PrintPath()
        {
            int[] path = new int[100];
            printPaths(_root, path, 0);
        }
        private void printPaths(Node node, int[] path, int pathLen)
        {
            if (node == null) return;

            // append this node to the path array 
            path[pathLen] = node.Data;
            pathLen++;

            // it's a leaf, so print the path that led to here 
            if (node.Left == null && node.Right == null)
            {
                PrintArray(path, pathLen);
            }
            else
            {
                // otherwise try both subtrees 
                printPaths(node.Left, path, pathLen);
                printPaths(node.Right, path, pathLen);
            }
        }

        private void PrintArray(int[] path, int pathLen)
        {
            for (int i = 0; i < pathLen; i++)
            {
                Console.Write(path[i] + " ");
            }
            Console.WriteLine();
        }

Given a binary tree, find path sum

Given a tree and a sum, returns true if there is a path from the root  down to a leaf, such that adding up all the values along the path  equals the given sum.let’s consider the following binary tree as an example and path sum value is 9.

       4
      / \
     2   5
    / \
   1   3

Root-to-leaf paths:
   path 1: 4 2 1
   path 2: 4 2 3
   path 3: 4 5

You can see that there are two path that gives sum 9 (Path2 and Path 3).Traverse the tree from root to leaves in top down fashion and subtract the node value from the sum  and check to see if the sum is 0 when you run out of tree.

 public bool HasPathSum(int sum)
        {
            return HasPathSum(_root, sum);
        }
        private bool HasPathSum(Node root, int sum)
        { 
            // return true if we run out of tree and sum==0 
            if (root == null)
                return sum == 0;
            else
            {
                int subSum = sum - root.Data;
                return (
                    HasPathSum(root.Left, subSum)
                    || HasPathSum(root.Right, subSum)
                    );
            }

        }


 

How to find min or max value in a given binary tree

This is continuation of my post How to create binary tree in c#.In this post I will show you how to find max or min value in a given binary tree.

Min Value: Loop down to find the leftmost leaf

Max Value: Loop down to find the rightmost leaf

     public int FindMinValue()
        {
            return FindMinValue(_root);
        }

        private int FindMinValue(Node root)
        {
            if (root == null)
                return -1;
            else
            {
                Node current = root;
                while (current.Left!=null)
                {
                    current = current.Left;
                }
                return current.Data;

            }
        }
        public int FindMaxValue()
        {
            return FindMaxValue(_root);

        }

        private int FindMaxValue(Node root)
        {
            if (_root == null)
                return -1;
            else
            {
                Node current = root;
                while (current.Right!=null)
                {
                    current = current.Right;
                }
                return current.Data;
            }
        }

How to calculate max depth of given binary tree in c#

This is continuation of my post How to create binary tree in c#.In this post I will show you how to calculate max depth of a given binary tree in c#.

MaxDepth of a tree -- the number of nodes along the longest path from the root node down to the farthest leaf node.

  public int MaxDepth()
        {
            return MaxDepth(_root);
        }
        private int MaxDepth(Node root)
        {
            if (root == null)
                return -1;
            // compute the depth of each subtree 
            else
            {
                int leftDepth = MaxDepth(root.Left);
                int rightDepth = MaxDepth(root.Right);
                //Return max of left or right tree.
                return 1 + Math.Max(leftDepth, rightDepth);
            }
        }

How to calculate size of binary tree

This is continuation of my post How to create binary tree in c# .In this post I will show you how to find size of binary tree.Size of binary tree is number of nodes in a given tree.

Following is the recursive implementation of size function

  //Compute the number of nodes in a tree. 
        public int Size()
        {
            return Size(_root);
        }
        private int Size(Node root)
        {
            if (root == null)
                return 0;
            return 1 + Size(root.Left) + Size(root.Right);
        }

How to create binary tree in c#

A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees" on either side. A null pointer represents a binary tree with no elements -- the empty tree. The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree.

download

Implementation

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BTree
{
    public class Node
    {
        public int Data { get; set; }
        public Node Left { get; set; }
        public Node Right { get; set; }
        public Node()
        {

        }
        public Node(int data)
        {
            this.Data = data;

        }
    }
    public class BinaryTree
    {
        private Node _root;
        public BinaryTree()
        {
            _root = null;
        }
        public void Insert(int data)
        {
            // 1. If the tree is empty, return a new, single node 
            if (_root == null)
            {
                _root = new Node(data);
                return;
            }
            // 2. Otherwise, recur down the tree 
            InsertRec(_root, new Node(data));
        }
        private void InsertRec(Node root, Node newNode)
        {
            if (root == null)
                root = newNode;

            if (newNode.Data < root.Data)
            {
                if (root.Left == null)
                    root.Left = newNode;
                else
                    InsertRec(root.Left, newNode);

            }
            else
            {
                if (root.Right == null)
                    root.Right = newNode;
                else
                    InsertRec(root.Right, newNode);
            }
        }
        private void DisplayTree(Node root)
        {
            if (root == null) return;

            DisplayTree(root.Left);
            System.Console.Write(root.Data + " ");
            DisplayTree(root.Right);
        }
        public void DisplayTree()
        {
            DisplayTree(_root);
        }

    }

    class Program
    {
        static void Main(string[] args)
        {
            BinaryTree tree = new BinaryTree();
            Node root = new Node();

            tree.Insert(4);
            tree.Insert(2);
            tree.Insert(5);
            tree.Insert(1);
            tree.Insert(3);
            tree.DisplayTree();
        }
    }
}

Saturday, February 28, 2015

How to create instance of generic class using reflection

In this post I am going to show how to create instance of generic class using c# reflection.The trick is to use the MakeGenericType to make the argument(s) and then call create Instance. Here is a code snippet:

Type d1 = typeof(List<>);
 
Type[] typeArgs = { typeof(string) };
 
Type makeme = d1.MakeGenericType(typeArgs);
 
object o = Activator.CreateInstance(makeme);
 
List<string> itsMe = o as List<string>;

Sunday, February 22, 2015

How to convert DataSet to List

In this post I am going to show you a very useful c# code snippet that convert DataSet to List<T>.

 

   public static List<T> ToCollection<T>(this DataTable dt)
        {
            List<T> lst = new List<T>();
            Type tClass = typeof(T);
            PropertyInfo[] pClass = tClass.GetProperties();
            List<DataColumn> dc = dt.Columns.Cast<DataColumn>().ToList();
            T cn;
            foreach (DataRow item in dt.Rows)
            {
                cn = (T)Activator.CreateInstance(tClass);
                foreach (PropertyInfo pc in pClass)
                {
                  
                   DataColumn d = dc.Find(c => c.ColumnName == pc.Name);
                   if (d != null)
                   {
                       if (item[pc.Name] != DBNull.Value)
                       {
                           pc.SetValue(cn, (item[pc.Name]), null);
                       }
                   }   
                }
                lst.Add(cn);
            }
            return lst;
        }

Tuesday, February 17, 2015

Self host web API

In this post I will show you how to create web api that run outside IIS application.
Open visual studio and create a console application
image

Add the Web API and OWIN Packages

From the Tools menu, click Library Package Manager, then click Package Manager Console. In the Package Manager Console window, enter the following command:
Install-Package Microsoft.AspNet.WebApi.OwinSelfHost
image
Right click  the project and add new class named Startup.cs and add following code snippet in it
public class Startup 
    { 
        // This code configures Web API. The Startup class is specified as a type
        // parameter in the WebApp.Start method.
        public void Configuration(IAppBuilder appBuilder) 
        { 
            // Configure Web API for self-host. 
            HttpConfiguration config = new HttpConfiguration(); 
            config.Routes.MapHttpRoute( 
                name: "DefaultApi", 
                routeTemplate: "api/{controller}/{id}", 
                defaults: new { id = RouteParameter.Optional } 
            ); 

            appBuilder.UseWebApi(config); 
        } 
    } 

Next, add a Web API controller class. In Solution Explorer, right click the project and select Add / Class to add a new class named HelloController and add following code snippet
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Web.Http;

namespace SelfHostWebApi
{
    public class HelloController : ApiController
    {
        // GET api/values/5 
        public string Get(int id)
        {
            return "Hello API";
        }
    }
}
Open Program.cs and add following code inside main method
using Microsoft.Owin.Hosting;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Net.Http;
using System.Text;
using System.Threading.Tasks;

namespace SelfHostWebApi
{
    class Program
    {
        static void Main(string[] args)
        {
            string baseAddress = "http://localhost:9000/";

            // Start OWIN host 
            using (WebApp.Start<Startup>(url: baseAddress))
            {
                // Create HttpCient and make a request to api/values 
                HttpClient client = new HttpClient();

                var response = client.GetAsync(baseAddress + "api/hello").Result;

                Console.WriteLine(response);
                Console.WriteLine(response.Content.ReadAsStringAsync().Result);
            }

            Console.ReadLine();
        }
    }
}

Your self hosted web api is ready.When you run the application you will see following output if everything works fine
image


How to create Fibonacci series using Linq

In this post I am going to show you how to generate fiboancci number series using Linq.

What is Fibonacci series : The Fibonacci Sequence is the series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... The next number is found by adding up the two numbers before it.

 public static IEnumerable<int> Fib(int n)
        {
            List<int> fibs = new List<int>();
            Enumerable.Range(0, n)
                .ToList()
                .ForEach(f => fibs.Add((f <= 1 ? 1 : fibs[f - 2] + fibs[f - 1])));
            return fibs;


        }

Saturday, February 7, 2015

How to post data using HttpClient

In this post I will show you how to post data to web api using HttpClient.

  private static async Task PostJSON()
        {
            HttpClient httpClient = new HttpClient();
            HttpContent content = new StringContent(@"{ ""Username"": """ + "etc." + @"""}");
            content.Headers.ContentType = new MediaTypeHeaderValue("application/json");
            HttpResponseMessage response =
                await httpClient.PostAsync("http://myapi.com/authentication", content);
            string statusCode = response.StatusCode.ToString();
        }

        /// <summary>
        /// Post Key/Value
        /// </summary>
        /// <returns></returns>
        private static async Task Post()
        {
            HttpClient client = new HttpClient();

            var values = new Dictionary<string, string>();
            values.Add("author", "santosh");
            values.Add("text", "singh");
            var content = new FormUrlEncodedContent(values);
            var response = await client.PostAsync("http://localhost:4500/quote", content);
        }

Saturday, November 1, 2014

How to check stream has Image or not

Let's suppose you have a page on which user upload there image and you want to validate that user is uploading image file only not other file format.The one easy solution is use regex and validate the extension of the file but if user rename the extension of the file and upload some executable code.Following is the simple c# code snippet that check the file type by the header value.

private bool IsImage()
    {
        bool isImage = false;
        FileStream stream = new FileStream(Server.MapPath(@"Images\a.txt"), FileMode.Open, FileAccess.Read);
        StreamReader reader = new StreamReader(stream);
        // Read the first 25 characters, we will be checking for a GIF or JPG signature.
        char[] strBuffer = new char[25];
        reader.ReadBlock(strBuffer, 0, 25);
        string stringBuffer = new string(strBuffer);
        // Is this an image?
        if (stringBuffer.IndexOf("GIF8") &gt; -1 || stringBuffer.IndexOf("JFIF") &gt; -1)
        {
            isImage = true;
            Response.Write("It's an image");

        }
        else
        {
            Response.Write("It's HTML or other junk.");
        }
        return isImage;
    }

How To Convert HTML to Text, Easily


Whether you want to convert an HTML page into pure text so you can parse out that special piece of information, or you simply want to load a page from the Net into your own word processing package, this mini function could come in handy.
It’s called StripTags and accepts an HTML string. Using a regular expression, it identifies all <tags>, removes them, and returns the modified string. Here’s the code:

<%@ Page Language="C#" ValidateRequest="False" AutoEventWireup="true" CodeFile="StripTag.aspx.cs"
 Inherits="StripTag" %>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head runat="server">
 <title>Untitled Page</title>
</head>
<body>
 <form id="form1" runat="server">
     <div>
         <asp:TextBox ID="TextBox1" runat="server" Height="172px" Width="363px" TextMode="MultiLine"></asp:TextBox></div>
     <asp:Button ID="Button1" runat="server" Text="Button" OnClick="Button1_Click" />
     <asp:Label ID="Label1" runat="server" Text="Label"></asp:Label>
 </form>
</body>
</html>


using System;
using System.Data;
using System.Configuration;
using System.Collections;
using System.Web;
using System.Web.Security;
using System.Web.UI;
using System.Web.UI.WebControls;
using System.Web.UI.WebControls.WebParts;
using System.Web.UI.HtmlControls;

public partial class StripTag : System.Web.UI.Page
{
   protected void Page_Load(object sender, EventArgs e)
   {


   }
   public string StripTags(string HTML)
   {
       // Removes tags from passed HTML 
       return System.Text.RegularExpressions.Regex.Replace(HTML, "<[^>]*>", "");
   }


   protected void Button1_Click(object sender, EventArgs e)
   {
       Label1.Text = StripTags(TextBox1.Text);

   }
}

Sunday, September 28, 2014

Decorator Design Pattern

Intent:
Attach additional responsibilities to an object dynamically. Decorators provide a flexible alternative to sub classing for extending functionality (also known as Wrapper)





using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DecoratorPattern
{

    public class UpperStream : Stream
    {
        private Stream _stream;
        public UpperStream(Stream stream)
        {
            this._stream = stream;

        }
        public override long Length
        {
            get { return _stream.Length; }
        }
        public override int Read(byte[] buffer, int offset, int count)
        {

            var numberOfBytesRead = _stream.Read(buffer, offset, count);
            for (int i = 0; i < numberOfBytesRead; i++)
            {
                buffer[i] = (byte)char.ToUpper((char)((int)buffer[i]));
            }


            return numberOfBytesRead;
        }
        public override bool CanRead
        {
            get { return true; }
        }
        public override bool CanSeek
        {
            get { throw new NotImplementedException(); }
        }
        public override bool CanWrite
        {
            get { throw new NotImplementedException(); }
        }
        public override void Flush()
        {
            throw new NotImplementedException();
        }
        public override long Position
        {
            get
            {
                throw new NotImplementedException();
            }
            set
            {
                throw new NotImplementedException();
            }
        }
        public override long Seek(long offset, SeekOrigin origin)
        {
            throw new NotImplementedException();
        }
        public override void SetLength(long value)
        {
            throw new NotImplementedException();
        }
        public override void Write(byte[] buffer, int offset, int count)
        {
            throw new NotImplementedException();
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            string message = "Hello Decorator";
            MemoryStream ms=new MemoryStream(Encoding.UTF8.GetBytes(message));
            UpperStream stream = new UpperStream(ms);
            StreamReader reader = new StreamReader(stream);
            Console.WriteLine(reader.ReadToEnd());
        }
    }
}

Strategy Design Pattern

Strategy Design Pattern
Define a family of algorithms, encapsulate each one, and make them interchangeable. Strategy lets the algorithm vary independently from clients that use it.


Problem:
Client wants to decide at run-time what serialization it should use to serialize a type. Many different serialization algorithms are already available.
Solution:
Encapsulate the different serialization algorithms using the Strategy pattern!
C# Code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace StrategyPattern
{

    public interface ISerializer
    {
        void Serialize();
    }
    public class XmlSerializer : ISerializer
    {
        public void Serialize()
        {
            Console.WriteLine("Xml serilizer Invoked");
        }
    }
    public class JsonSerializer : ISerializer
    {
        public void Serialize()
        {
            Console.WriteLine("Json serializer Invoked");
        }
    }
    public class Context
    {
        private ISerializer _serializer;
        public Context(ISerializer serializer)
        {
            this._serializer = serializer;
        }
        public void Serialize()
        {
            _serializer.Serialize();
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            Context ctx = new Context(new XmlSerializer());
            ctx.Serialize();
        }
    }
}