Algorithm to move all ones(1's) in an array to end of the array - O(n) Solution

Problem:
Given an array which contains only 0's and 1's. Write an algorithm to move all the 1's in the array to end of the array in one traversal only. Avoid unnecessary swapping and using extra space.

Different version of this problem would be Dutch National Flag Problem, which is very common question in many interviews in initial stages. Above given problem is simplified version of 0, 1, 2 or Dutch Flag problem, where we are concerned only about moving 0's to initial parts of the given array. We keep track of index of zeroes(i.e. nothing but number of zeroes that we have encountered till now), whenever we find zero in the array we swap with this zero index that we have been tracking.

Solution:
Below code in C#, I think code itself is self explanatory. If not drop a comment please.

========================================================================

           int[] arr = { 1, 0, 1, 0, 1, 0, 1, 0, 1};


            int zeroIndex = 0;
            for (int i = 0; i < arr.Length; i++)
            {
                if (arr[i] == 0)
                {
                    if (i!= zeroIndex && arr[i] != arr[zeroIndex])
                    {
                        int temp = arr[i];
                        arr[i] = arr[zeroIndex];
                        arr[zeroIndex] = temp;
                    }
                        zeroIndex++;
                    
                }
            }


            for (int i = 0; i < arr.Length; i++)
            {
                Console.Write(arr[i]);
            }
========================================================================

Hooking Mouse and Keyboard, Marshaling and few user32 library methods call in C#

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Runtime.InteropServices;
using System.Threading;

namespace WindowsFormsApplication1
{

    [Flags]
    public enum SendMessageTimeoutFlags : uint
    {
        SMTO_NORMAL = 0x0,
        SMTO_BLOCK = 0x1,
        SMTO_ABORTIFHUNG = 0x2,
        SMTO_NOTIMEOUTIFNOTHUNG = 0x8
    }
    public partial class Form1 : Form
    {

        public delegate int HookProc(int code, IntPtr wparam, IntPtr lparam);
        static int hHook = 0;
        static int mHook = 0;
        IntPtr windowHandle;
        uint processHandle;

        int WH_MOUSE = 7;
        int WH_KEYBOARD = 2;
        static int HC_ACTION = 0;
        static int VK_CONTROL = 11;

        //This is the Import for the SetWindowsHookEx function.
        //Use this function to install a thread-specific hook.
        [DllImport("user32.dll", CharSet = CharSet.Auto, CallingConvention = CallingConvention.StdCall)]
        public static extern int SetWindowsHookEx(int idHook, HookProc lpfn, IntPtr hInstance, int threadId);

        //This is the Import for the UnhookWindowsHookEx function.
        //Call this function to uninstall the hook.
        [DllImport("user32.dll", CharSet = CharSet.Auto, CallingConvention = CallingConvention.StdCall)]
        public static extern bool UnhookWindowsHookEx(int idHook);

        [DllImport("user32.dll", CharSet = CharSet.Auto, CallingConvention = CallingConvention.StdCall)]
        public static extern IntPtr GetForegroundWindow();


        [DllImport("user32.dll")]
        static extern int GetWindowText(IntPtr hWnd, StringBuilder text, int count);

        //This is the Import for the CallNextHookEx function.
        //Use this function to pass the hook information to the next hook procedure in chain.
        [DllImport("user32.dll", CharSet = CharSet.Auto,CallingConvention = CallingConvention.StdCall)]
        public static extern int CallNextHookEx(int idHook, int nCode, IntPtr wParam, IntPtr lParam);

        [DllImport("user32.dll", CharSet = CharSet.Auto, CallingConvention = CallingConvention.StdCall)]
        public static extern short GetAsyncKeyState(int vkey);

        [DllImport("kernel32.dll", CharSet = CharSet.Auto, CallingConvention = CallingConvention.StdCall)]
        public static extern int GetLastError();


        [DllImport("user32.dll", CharSet = CharSet.Auto, CallingConvention = CallingConvention.StdCall)]
        public static extern IntPtr FindWindow(string classname, string windowName);

        [DllImport("user32.dll", CharSet = CharSet.Auto, CallingConvention = CallingConvention.StdCall)]
        public static extern IntPtr SendMessage(IntPtr hWnd,uint Msg,IntPtr wParam,IntPtr lParam);

        [DllImport("user32.dll", SetLastError = true, CharSet = CharSet.Auto)]
        public static extern IntPtr SendMessageTimeout(
            IntPtr hWnd,
            uint Msg,
            UIntPtr wParam,
            IntPtr lParam,
            SendMessageTimeoutFlags fuFlags,
            uint uTimeout,
            out UIntPtr lpdwResult);

        HookProc MouseHookProcDel;
        HookProc KeyBoardHookProcDel;

        [StructLayout(LayoutKind.Sequential)]
        public class POINT
        {
            public int x;
            public int y;
        }

        //Declare the wrapper managed MouseHookStruct class.
        [StructLayout(LayoutKind.Sequential)]
        public class MouseHookStruct
        {
            public POINT pt;
            public int hwnd;
            public int wHitTestCode;
            public int dwExtraInfo;
        }

        //to marshal to lparam of keyboard hook into a manage type
        [StructLayout(LayoutKind.Sequential)]
        public class KBDLLHOOKSTRUCT
        {
            public uint vkCode;
            public uint scanCode;
            public uint flags;
            public uint time;
            public uint dwExtraInfo;
        }

        public Form1()
        {
            InitializeComponent();
        }


        public static int MouseHookProcedure(int code, IntPtr wparam, IntPtr lparam)
        {
            MouseHookStruct mouse = (MouseHookStruct)Marshal.PtrToStructure(lparam, typeof(MouseHookStruct));
       
            if(code == 0)
            {
                //Create a string variable that shows the current mouse coordinates.
                String strCaption = "x = " +
                        mouse.pt.x.ToString("d") +
                            "  y = " +
                mouse.pt.y.ToString("d");
                //You must get the active form because it is a static function.
                Form tempForm = Form.ActiveForm;

                //Set the caption of the form.
                tempForm.Text = strCaption;
                return CallNextHookEx(hHook, code, wparam, lparam);
            }
            else
                //calls the next hook with same message and parameters
                return CallNextHookEx(hHook, code, wparam, lparam);
        }

        public static int KeyBoardProcedure(int code, IntPtr wparam, IntPtr lparam)
        {
           //KBDLLHOOKSTRUCT's structure is copied as it is from msdn to support marshaling
            KBDLLHOOKSTRUCT pkbhs = (KBDLLHOOKSTRUCT)Marshal.PtrToStructure(lparam, typeof(KBDLLHOOKSTRUCT));
            int bControlKeyDown = 0 ;
            switch (code)
            {
                //0 refers to HC_ACTION
                case 0:
                    {
                        // Check to see if the CTRL key is pressed
                        bControlKeyDown = GetAsyncKeyState(VK_CONTROL) >> ((sizeof(short) * 8) - 1);

                       //write to logic to handle ctrl+esc or alt+tab or any other key here
                       //then return 1               
                        break;
                    }

                default:
                    return CallNextHookEx(mHook, code, wparam, lparam);
                   
            }
            return CallNextHookEx(mHook, code, wparam, lparam);
        }

        private void button1_Click(object sender, EventArgs e)
        {
            if (hHook == 0 && mHook==0)
            {
                // Create an instance of HookProc.
                MouseHookProcDel = new HookProc(Form1.MouseHookProcedure);
                KeyBoardHookProcDel = new HookProc(Form1.KeyBoardProcedure);

                hHook = SetWindowsHookEx(WH_MOUSE,
                            MouseHookProcDel,
                            (IntPtr)0,
                            AppDomain.GetCurrentThreadId());

                mHook = SetWindowsHookEx(WH_KEYBOARD,
                            KeyBoardHookProcDel,
                            (IntPtr)0,
                            AppDomain.GetCurrentThreadId());
                //If the SetWindowsHookEx function fails.
                if (hHook == 0)
                {

                    MessageBox.Show("SetWindowsHookEx Failed" + ":" + GetLastError().ToString());
                    return;
                }
                button1.Text = "UnHook Windows Hook";
            }
            else
            {
                bool ret = UnhookWindowsHookEx(hHook);
                ret = UnhookWindowsHookEx(mHook);
                //If the UnhookWindowsHookEx function fails.
                if (ret == false)
                {
                    MessageBox.Show("UnhookWindowsHookEx Failed");
                    return;
                }
                hHook = 0;
                mHook = 0;
                button1.Text = "Hook Mouse and Keyboard";
                this.Text = "Mouse Hook";
            }
        }

        private void GetActiveWindowTitle()
        {          
            const int nChars = 256;
            IntPtr handle = IntPtr.Zero;
            StringBuilder Buff = new StringBuilder(nChars);
            handle = GetForegroundWindow();

            if (GetWindowText(handle, Buff, nChars) > 0)
            {
                MessageBox.Show(Buff.ToString());

            }
            return;
        }

        private void timer1_Tick(object sender, EventArgs e)
        {
            //on timer elapsed, we get the active window's title
            // uncomment to use it
            //GetActiveWindowTitle();
        }

        private void CheckWhetherProcessIsHung()
        {
           //easy way of doing this would be to check process.Responding attribute
           //C# makes it totally easy with Process class

            //edit is the class name here for Notepad
            IntPtr hwnd = FindWindow("Edit", null);
            UIntPtr let;

            //Aborts if the process to which we are sending message fails
            IntPtr result =  SendMessageTimeout(hwnd, 0, (UIntPtr)0, (IntPtr)0, SendMessageTimeoutFlags.SMTO_ABORTIFHUNG, 15000, out let);
           
            //there will be error if result = 0, get last error and show it then
            if (result == (IntPtr)0)
                MessageBox.Show(GetLastError().ToString());
        }

        private void button2_Click(object sender, EventArgs e)
        {
            CheckWhetherProcessIsHung();
        }
    }
}

References:

Pinvoke.net , msdn dev center -desktop and microsoft support pages

Non-Recursive (Morris) In-Order Traversal and Recursive In-Order Traversal in C#

Morris In-Order traversal traverses the given tree in in-order without using Recursion or Stack. Morris In-Order traversal uses concept of threading the nodes, which are either leaves or which do not have right node to their in-order successors. This allows traversing back in in-order hierarchy simple. Traversal also removes the links that are created for this purpose and keep the tree unchanged.

Steps involved in Morris traversal are:

1. Get the in-order predecessor of current node: In-order successor of any given node in BST is a node's left node's right most element.

2. When you reach such in-order predecessor for current node, since that node will be either be a leaf node or a node that does not have right child. Make current as right child of that in-order predecessor and move current node pointer to its left item.

3. A temporary pointer "pre" is used to find out the in-order predecessor of given node "current". "pre.Right = current; " is used to thread in-order predecessor node to its successor.

4. When current moves to the left most element in the tree, print the data of the node and move current to current's right. This is important. It uses previously created link to move to in-order successor of current.

5. Then to remove this link, we follow finding in-order predecessor procedure until pre-Right points to current node itself. That means there is a link between current and the node "pre" is pointing to. Since we have already visited that node, we shall break this link, by setting pre.Right = null. We also shall print this "current" node data and then move to its in-order successor using the links that we created in earlier steps.

6. When pre.Right == Current means  there is a link that we created between pre and current. We shall break link and proceed to next in-order successor using Current = current.Right;

7. Also Current = current.Right when (pre.Right== current) assures that after left tree is processed, we move right part of the given binary search tree.

8. When Current moves to left most node of the tree, i.e. if Current.Left == null then Current= current.Right assures we traverse back to its in-order successor using the link that we already created.


Below code also includes a method which does recursive in-order traversal in order to compare with Morris traversal.

Complete Code:
=======================================================================

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


namespace ConsoleApplication4
{
    class Program
    {
        static void Main(string[] args)
        {
            Node root = new Node();
            root.Data = 6;
            root.Left = new Node(4);
            root.Left.Right = new Node(5);
            root.Right = new Node(10);
            root.Left.Left = new Node(2);
            root.Left.Left.Left = new Node(1);
            root.Right.Left = new Node(8);
            root.Right.Left.Right = new Node(9);
            root.Right.Left.Left = new Node(7);
            root.Right.Right = new Node(14);
            root.Right.Right.Left = new Node(13);
            root.Right.Right.Left.Left = new Node(12);
            root.Right.Right.Right = new Node(17);


            PrintInorderTraversal(root);
            Console.WriteLine("");
            Add(root, 3);
            Add(root, 11);


            PrintInorderTraversal(root);
            Console.WriteLine("");
            Console.WriteLine("morris inorder travesal using threading");
            Console.WriteLine("");
            MorrisInorderTraversal(root);
            Console.ReadLine();




        }


        static void MorrisInorderTraversal(Node root)
        {
            Node current = root;
            Node pre = null;
            while (current != null)
            {
                //it is looping back to parent
                //using already threaded leaf and node in hierarchy
                if (current.Left == null)
                {
                    Console.Write(current.Data + " ");
                    current = current.Right;
                }
                else
                {
                    //now find the inorder predeccsor or current node
                    pre = current.Left;
                    while (pre.Right != null && pre.Right != current)
                    {
                        pre = pre.Right;
                    }
                    if (pre.Right == null)
                    {
                        //inorder predeccesor found
                        //move current to left again
                        pre.Right = current;
                        current = current.Left;
                    }
                    else
                    {
                        //after every thread is been created from a node which does not have a right node
                        //to its inorder successor
                        //now lets visit that inorder successor using right pointer


                        //lets print the data and move to right i.e go up to inorder successor                        
                        pre.Right = null;
                        Console.Write(current.Data+" ");
                        current = current.Right;
                    }


                }
            }
        }
        static void PrintInorderTraversal(Node current)
        {
            if (current != null)
            {
                PrintInorderTraversal(current.Left);
                Console.Write(current.Data+" ");
                PrintInorderTraversal(current.Right);
            }
        }


        static void Add(Node root, int data)
        {
            Node current = root; Node Parent = null;
            Node temp = new Node(data);
            while (current != null)
            {
                if (current.Data > data)
                {
                    Parent = current;
                    current = current.Left;
                }
                else if(current.Data < data)


                {
                    Parent = current;
                    current = current.Right;
                }
                else
                {
                    //duplicte value
                    return;
                }               
            }
            //empty tree
            if (Parent == null)
            {
                root = temp;
            }
            else
            {


                if (Parent.Data > data)
                {
                    Parent.Left = temp;
                }
                else
                {
                    Parent.Right = temp;
                }
            }
        }
    }


    public class Node
    {
        int data;


        public Node()
        {
        }


        public int Data
        {
            get { return data; }
            set { data = value; }
        }
        Node left = null;


        public Node Left
        {
            get { return left; }
            set { left = value; }
        }


        Node right =null;


        public Node Right
        {
            get { return right; }
            set { right = value; }
        }


        public Node(int v)
        {
            data = v;
        }        
    }
}

=======================================================================

Reference & Thanks: GeeksForGeeks.org

Basic Threading

A thread is an independent execution path

C# supports parallel execution of code through multithreading.

How Threading Works

Multithreading is managed internally by a thread scheduler, a function the CLR typically delegates to the operating system. A thread scheduler ensures all active threads are allocated appropriate execution time, and that threads that are waiting or blocked do not consume CPU time.

On a single-processor computer : Thread scheduler performs time-slicing — rapidly switching execution between each of the active threads.

On a multi-processor computer: Multithreading is implemented with a mixture of time-slicing and genuine concurrency, where different threads run code simultaneously on different CPUs. It’s almost certain there will still be some time-slicing, because of the operating system’s need to service its own threads — as well as those of other applications.

A thread is said to be preempted when its execution is interrupted due to an external factor such as time-slicing.

When to Use

·         Maintaining a responsive user interface

·         Making efficient use of an otherwise blocked CPU

·         Parallel programming

·         Speculative execution

·         Allowing requests to be processed simultaneously

Thread Pooling

Whenever you start a thread, a few hundred microseconds are spent organizing such things as a fresh private local variable stack. The thread pool cuts these overheads by sharing and recycling threads, allowing multithreading to be applied at a very granular level without a performance penalty.

The thread pool also keeps a lid on the total number of worker threads it will run simultaneously. Too many active threads throttle the operating system with administrative burden and render CPU caches ineffective. Once a limit is reached, jobs queue up and start only when another finishes.

The thread pool starts out with one thread in its pool. As tasks are assigned, the pool manager “injects” new threads to cope with the extra concurrent workload, up to a maximum limit. After a sufficient period of inactivity, the pool manager may “retire” threads if it suspects that doing so will lead to better throughput.

You can set the upper limit of threads that the pool will create by calling ThreadPool.SetMaxThreads; the defaults are:

• 1023 in Framework 4.0 in a 32-bit environment
• 32768 in Framework 4.0 in a 64-bit environment
• 250 per core in Framework 3.5
• 25 per core in Framework 2.0

Synchronization

Synchronization constructs can be divided into four categories: (Blocking/Locking/Signaling/NonBlocking)

Blocking:

Wait for another thread to finish or for a period of time to elapse.

Sleep, Join, and Task.Wait are simple blocking methods.

Locking:

Limit the number of threads that can perform some activity or execute a section of code at a time.

Monitor, Mutex, SpinLock (Exclusive locking)

Semaphore, SemaphoreSlim, Reader/Writer locks (Nonexclusive locking)

Signaling:

These allow a thread to pause until receiving a notification from another.

Event wait handles and Monitor’s Wait/Pulse methods. Framework 4.0 introduces the CountdownEvent and Barrier.

NonBlocking:

These protect access to a common field by calling upon processor primitives.

Thread.MemoryBarrier, Thread.VolatileRead, Thread.VolatileWrite, the volatile keyword, and the Interlocked class.

Events - Adding event keyword to a delegate C#

By now I expect we know how to create a delegate and creating an event using the delegate. Let us get into details how adding event keyword changes the way delegate is treated.

An 'event' keyword in front of a delegate does more than exposing the delegate type to Subscribers. Here subscribers refers to classes that add methods to the delegate by  exposed  Broadcaster. Broadcaster is the class that exposes the delegate type with keyword event. 

When compiler discovers event declaration, it does three things that makes event different than a normal delegate. 

void delegate DateTimeHandler(object sender, TimeEventArgs args);

public event DateTimeHandler DataTimeChanged;

1. Compiler creates an event accessor for the just like Property accessor. 

 DateTimeHandler _timeHandler;

public DateTimeHandler DateTimeChanged

{

      add { _timeHandler += value;}

      remove { _timeHandler -= value;}

}

2. Compiler checks for any references to DateTimeChanged inside the Broadcaster class which are other than += and -= operations and redirects them to underlying private _timeHandler delegate field.

3. Compiler translates all the += and -= operations to the event accessor which compiler resolved in step 1. This make behavior + and - different when applied to events.

Differences between a normal delegate and an event in terms of their behaviors are listed below:

      

       1. An event can only be invoked by the broadcaster, in case of delegate it can be invoked by any class that has access to it. In case of delegate a subscriber class can call\broadcast to other subscribers by invoking the delegate.

      2. A normal delegate can be cleared off\ reset by the class that is using it. Any class that has access to delegate can set the delegate to its own method and thereby clear off methods that were assigned by all delegates.

     3. An event can only subscribed to or unsubscribed but the subscribers list or methods associated with event can not be modified or cleared as that can happen with normal delegate.

Consider the case when DateTimeHandler delegate in above example is exposed instead of event DataTimeChaneged. Lets assume class A and Class B use this delegate by giving their own method like below.

Controller.Instance. DateTimeHandler += a.MethodA;

Controller.Instance. DateTimeHandler += b.MethodB;

Some other class C which also can access to event can set DateTimeHandler to  different definition altogether and there by make it loose all other subscribers(i.e. A and B) information and initialization.

Controller.Instance. DateTimeHandler = c.MethodC; //Now controller's delegate loses track of all other subscribers and methods.

Class C can also invoke DateTimeHandler delegate there by calling MethodA and MethodB of  class A and Class B respectively, like below:

if(isBadIntention)

{

      Controller.Instance.DateTimeHandler(this, dummyEventArgs);

}

Reference:

All thanks to "C# 4.0 in Nutshell" by Joe Albahari. I have written here what I have understood from Albahari's book and also from my learning.

Fault Contracts in WCF

* Fault Contracts are used to send exception information from a service to client.

* Every information that passes between service and clients must be serialized. Hence this exception information that is required to be passed to client must be of serializable type or it must be a defined data contract which can hold information about exception.

* Fault contracts are used in release environment. This is to make sure clients do not get to see internal implementation of service through exception details.

* When we need all exception details to be passed on to client for debugging or development purposes then we can set includeExceptionDetailsInFaults="true" instead of using fault contract. All we need is to set this attribute in service behavior defined for service endpoint to get all the details of exception at client side. Client has to handle these non-generic exceptions in its code.

<behaviors>
  <serviceBehaviors>
    <behavior name="MyServiceBehavior">
      <serviceMetadata httpGetEnabled="True"/>
      <serviceDebug includeExceptionDetailInFaults="True" />
    </behavior>
  </serviceBehaviors>
</behaviors>

*Every OperationContract that might raise the Fault exception must define the type of the exception in its attribute. 

[OperationContract]
[FaultContract(typeof(UploadFault))]
void UploadData(byte [] data);

Exception Type Defined:

[DataContract]
public class UploadFault
{    
    private string message
    private string errorType;

    [DataMember]
    public string ErrorMessage
    {
        get { return messasge; }
        set { message = value; }
    }

    [DataMember]        
    public string ErrorType
    {
        get { return errorType; }
        set { errorType = value; }
    }
}

Callbacks in WCF with an Example

WCF allows service to call back its clients. This way service acts like client and client acts like a service. Client must support\facilitate call back by hosting call back object. Clients are required to support the call back and provide the end point info of call back in their every call to the service. Steps involved in creating a call  back are,

a. Service defines call back type(interface that client's call back handler class must implement). Call back contract need not be marked as Service contract but it is implied.

b. Service contract mentions name of call back type in the service contract attribute.

//call back type

interface IExampleCallBack

{

   [OperationContract] 

   void ClientAction();

}

[ServiceContract(CallbackContract = typeof(IExampleCallback))] 

interface IExampleContract

{

   [OperationContract] 

   void ServiceMethod1();

}

c. Client creates call back host by providing bindings that support call backs, endpoint for the call back and the call back class that implements the call back type. Though this class need not have the attribute ServiceBehavi

d. Client instantiates InstanceContext class by providing call back handler object as parameter to the constructor. 

e. Since Client is supposed to pass call back end point info to the service. Client shall pass this InstanceContext object while creating the proxy.

class ExampleCallBack: IExampleCallBack

{

   public void ClientAction() {//do something based on service call}

}

IExampleCallBack callback = new ExampleCallBack();

InstanceContext context = new InstanceContext(callback);

ExampleContractClient proxy = new ExampleContractClient(context);

proxy.ServiceMethod1();

Service can use OperationContext to get the call back instance and then call methods on call back instance i.e. methods on client side.

IExampleCallBack callback = OperationContext.Current.GetCallbackChannel<IExampleCallBack>();

callback.ClientAction();  

Important Notes and Points about Call backs:

1. HTTP does not support call back because of its connection less nature.  Hence we cannot use BasicHttpBinding or WSHttpBinding for call back mechanism. NetTcpBinding, NamedNetPipeBinding can support call backs due to their underlying bidirectional transport. WSDualHttpBinding also supports call back mechanism by setting two http channels underneath.

2. By default service class is single threaded. Service instance is associated with a lock and only one thread can own this lock at a time, to access the service instance. Invoking the clients code requires service thread to be blocked while call backs are invoked. A deadlock would occur since when clients reply, processing that reply would need ownership of service instance's lock. There are three ways to avoid this deadlock:

    a. Making the service behavior Multithreaded, which means more resources and complex synchronization.

  b. Making the service behavior class as Re-Entrant. A service can be configured as re-entrant by setting the concurrency mode as ConcurrencyMode.Reentrant. When service is configured to be reentrant, service instance still is locked and owned by single thread. But WCF will release the lock quietly before invoking a call back method.

    c. Making the call back methods as OneWay. This can be done  by setting IsOneWay tag on call back operation contract to true. This assures there will be no reply from the client and hence eventhough service is single threaded there would be no deadlock.

    

[ServiceBehavior(ConcurrencyMode = ConcurrencyMode.Reentrant)]

class ExampleService : IExampleContract

{

   public void ServiceMethod1()

   {

      IMyContractCa llback callback = OperationContext.Current.GetCallbackChannel<IExampleCallback>();

      callback.ClientAction();

   }

}

IsOneWay Attribute:

interface IExampleCallBack

{

   [OperationContract(IsOneWay = true)] 

   void ClientAction();

}