Longest Common Substring and Longest Common Subsequence (LCS) - Code using C# (Part 1)

Before starting with algorithms, let us understand difference between a substring of a string and a susbsequence of a string. Substring and subsequence are confusing terms. 

Sub-string is the part of the input string itself. It has characters in the same order they appear in the main string. Whereas subsequence is the string which has sequence of characters of main string, which can be formed by deleting one or many characters randomly from the input string.

Example:

Input string    : "HELLO WELCOME EVERYONE"

Sub-string     : "EVERY" or "COME"

Subsequence : "LWCME"

Longest Common substring

Longest Common substring of two given strings is the string which is common substring of both given strings and longest of all such common substrings.

Example:
String 1   : "HELLO WELCOME EVERYONE"
String 2   : "NO TWEET NO NO WELEVERYONEWELHELL"
LCString : "EVERYONE"

One approach of solving this would be using Dynamic Programming.

a. Allocate a 2D array of size [str1.Length, str2.Length]
b. Each value of this matrix saves the information about length of longest substring that's ending at that position. e.g. L[3,4] gives length of longest common substring of first three characters of first input string and first four characters of second input string.
c. If we start with 1st character of string 1 and 1st character of string 2, if they match we can say L[0, 0] = 1
d. We then can build this array by seeing if LCS value at any postion is greater than cached LCS value.
e. We will also save the ending index of the longest common substring till every point when character do not match. This can be used to backtrack and get the actual LCS from given input string.
f. L[str1.Length, str2.Length] will have the final LCS length saved in it.
g. Each step uses LCS value calculated in previous steps and adds one to it if characters match at new indexes in both given strings.

In below C# code I'm assuming array of characters are passed as input instead of string.

public static void PrintLongestCommonSubstring(char[] str1, char[] str2)         {             int[,] l = new int[str1.Length, str2.Length];             int lcs = -1;             string substr = string.Empty;             int end = -1;                         for (int i = 0; i < str1.Length; i++)             {                 for (int j = 0; j < str2.Length; j++)                 {                     //if character at 'i' in string 1 and character at 'j' in string 2                     matches then increment the length of lcs value for that position                     if (str1[i] == str2[j])                     {                         //taking care of array indexes                         if (i == 0 || j == 0)                         {                             l[i, j] = 1;                         }                         else                         {                             //characters match , lets update new lcs value                             l[i, j] = l[i - 1, j - 1] + 1;                         }                         //This is to get the longest common substring                         // use end index in the first string for longest common substring                         if (l[i, j] > lcs)                         {                             lcs = l[i, j];                             end = i;                         }                     }                     else                     {                         //characters do not match use set length of LCS at that position                         as 0                         l[i, j] = 0;                     }                 }             }             for (int i = end - lcs + 1; i <= end; i++)             {                 substr += str1[i];             }                         Console.WriteLine("Longest Common SubString Length = {0}, Longest Common                  Substring = {1}", lcs, substr);         }

NOTE: I hope comments in the above code helps in understanding the code block. 

I will continue this article and explain about finding Longest Common Subsequence in next article.

Algorithm and References: wikipedia (link provided above)

C# - throw or throw ex? Differences between "throw" and "throw ex" in exception handling

When we use throw ex, it throws a new exception with empty call stack or call stack starting from there to the higher\caller. It's always a good habit to use 'throw' instead on 'throw ex' inside catch block since it retains the complete call stack for the exception. 'Throw ex' can be replaced with 'throw new exception' to add mode details to the exception caught or add custom information to the exception. Throwing new exception is preferred in cases where code block raises an exception for cases like invalid input or format etc and add explanatory message about that case to that exception.

Choosing between throw and throw new exception("message") or throw ex mainly depends on ,

a. What 'call stack' you like to retain or send to the caller.

b. What information you like the caller to see on catching this exception like custom message for that exception or application specific information\exception types.

Safe Way To Abort A Thread in C# - Brief about ThreadAbortException, ThreadInterruptedException and volatile variables

Yeah, one of the favorite questions of any interviewer when it comes to multithreading. 

Are you thinking of Thread.Abort()? Let us see why we shouldn't we consider Abort() on a thread. If below information looks like content of MSDN, bear with me because most of the concepts in this article are from MSDN pages only.

    è When thread abort method is called, ThreadAbortException is raised in the method that is being                 executed. Even if the exception is handled in the thread method, it is re-thrown at the end of catch                   block. Yes, ThreadAbortException is a special kind of exception which is thrown even when it is assumed              to be "handled".

         è Unexecuted finally blocks are executed before the thread is aborted. The thread is not guaranteed                   to abort immediately, or at all. This situation can occur if a thread does an unbounded amount of                      computation in the finally blocks that are called as part of the abort procedure, thereby indefinitely                delaying the abort. To wait until a thread has aborted, you can call the Join method on the thread                   after calling the Abort method, but there is no guarantee the wait will end.

è  If Abort is called on a thread that has been suspended, a ThreadStateException is thrown in the thread that called Abort, and AbortRequested is added to the ThreadStateproperty of the thread being aborted. A ThreadAbortException is not thrown in the suspended thread until Resume is called.

è  If Abort is called on a managed thread while it is executing unmanaged code, a ThreadAbortException is not thrown until the thread returns to managed code.

è  If two calls to Abort come at the same time, it is possible for one call to set the state information and the other call to execute the Abort. However, an application cannot detect this situation.

Now that we saw why terminating a thread by calling Thread.Abort is not a good idea. Let us discuss few approaches of terminating a thread in safer way.

Method 1 – using volatile variable:

Variables that are marked as “volatile” can be accessed across multiple threads in thread-safe manner. We can use this property of volatile variable to control the execution of thread method. Yes, we can terminate the thread based on the value of this volatile variable, the caller can simply set this variable from its code.

Little about volatile keyword:

“The volatile keyword indicates that a field might be modified by multiple threads that are executing at the same time. Fields that are declared volatile are not subject to compiler optimizations that assume access by a single thread. This ensures that the most up-to-date value is present in the field at all times.

The volatile modifier is usually used for a field that is accessed by multiple threads without using the lock statement to serialize access.”

A simple but not so accurate example (copy pasted from StackOverflow as-it-is):

volatile bool shutdown = false;

void RunThread()

{

   while (!shutdown)

   {

      ...

   }

}

void StopThread()

{

   shutdown = true;

}

This allows your thread to cleanly finish what it was doing, leaving your app in a known good state.

Method 2 using Thread.Interrupt(), volatile and exception handling for cleaned up termination:

ThreadInterruptedException is an exception which can be handled in the thread method. Thread.Interrupt can be called only on a thread that is in WaitSleepJoin state. Calling Interrupt when a thread is in the WaitSleepJoin state will cause a ThreadInterruptedException to be thrown in the target thread. If the thread is not in the WaitSleepJoin state, the exception is not thrown until the thread enters that state. If the thread never blocks, it could complete without ever being interrupted.

Approach is to handle this exception in the target thread method and exit gracefully. Combining this with a volatile variable like in method 1 will provide much safer way to terminate the thread. It also assures that thread will be “aborted”, sorry let us say terminated even when thread may block in a “sleep” or “wait” state.

Again an example from StackOverflow(as-it-is copied):

try

{

    while (keepGoing)

    {

        /* Do work. */

    }

}

catch (ThreadInterruptedException exception)

{

    /* Clean up. */

}

I have compiled this article from the answers I read on StackOverflow and MSDN articles. If you find useful please thank me by liking this post.

Lambda Expression, Statement Lambda, Action Delegate, Func Delegate, Differences Between Action and Func and Instantiating Delegates with Lambda

Continuing from last page:
Lambda expressions or statement lamda can be passed where a delegate is expected.

Lamda expressions may or may not expect input parameters and have an expression to right of lambda that may evaluate to a return value.

      Func<int, int, int, int, int> hello = (a, b, c, d) => a + b + c + d;

   here a,b,c,d are input parameters and return type is int which is result of expression (a+b+c+d). 

In above lambda expression is assigned to Func delegate which accepts 4 input parameters of type 'int' and return type is 'int' again.

We have to make sure, lambda expressions input is convertible to delegate's input type & return of lambda is convertible to delegate's return type.


In above case (a+b+c+d) will be of type of int which is same of Func<int,int,int,int,int TResult> delegate's return type i.e. int.


Lambda expression can also contain statements to right of lamda that might not return any value.


           Action<int> mm = (a) => Console.WriteLine("EEE");
      mm(5);

In above example right side of expression does not evaluate to anything though it accepts a parameter 'a'. This is assigned to default Action<int> delegate which does not expect any return type, but has an input parameter of type 'int'.

Now let us see what is a statement lambda. Statement lambda is similar to lambda expression but statement(s)/expression to the right of lambda is enclosed in {} braces.
They can contain multiple statement since they are enclosed in braces. Braces also indicate scope /block of lambda statement. 


                Action<int> actw = (a) => 
            {
                string s = "square = " + a * a;
                s = s + " - new";
                Console.WriteLine(s); 
            }

Here we are assigning statement lambda to a delegate that has single input parameter of type int. We are not returning anything from lambda but redirecting the square of number to console.

We use lambda and anonymous methods only in simple scenarios where a set of simple statements can be passed in method, instead of having dedicated method of handling or instantiating delegate.
In below example, I'm invoking a delegate and assigning a statement lambda for callback. Here having a callback method that would just print completion status would not make much sense and hence I replaced it with a lambda expression which outputs the delegate's method execution status in the callback.
Here AsyncCallback expects a method that accepts IAsyncResult parameter and return type is void. Our statement lambda accepts this IAsyncResult  as input and returns nothing and hence can be passed in as method that is expected by AsyncCallback.


        public static void ExecuteDelegate(Func<int, int, int, int, int> hello)
        {
                hello.BeginInvoke(2, 3, 4, 5,                
                   new AsyncCallback((asyncresult) => {  
                          Console.WriteLine("Completed = " +  
                                    asyncresult.IsCompleted); }),                
                                  null);
        }


Till now I have only use Func<> and Action<> delegates but lambda can be used for any delegate of matching return and input types. Func and Action are the delegates provided by default by the framework to avoid overhead of writing our own delegates for general cases. These delegates are generic they are extended to accept 0, 1, 2, 3 or more parameters. Number of input parameters that are accepted by both delegates was 0 to 4 in .NET 3.5.

Main difference between Action delegate and Func delegate is,

Action - delegate that does not have return value and accepts up-to four input parameters. (.NET 3.5)
Action also can encapsulate a method that take no input and no return value. 

Types:
Action
Action<in T1> - in represents input parameter.
Action<in T1,in T2>
Action<in T1,in T2,in T3>
Action<in T1,in T2,in T3,in T4>

Func<TResult> - Func delegate is used when we have a return value but input parameter list is optional. Func delegate can encapsulate method that returns a value and accepts no input. Func can encapsulate methods that have 0 - 4 in put parameters and return a value. Last value in parameter list represents the return type.

Func<TResult> - TResult represrents return type.
Func<in T1, out TResult> 
...............


delegate void PrintCharsDelegate(string s);


PrintCharsDelegate del = (s) =>
                   {
                       Console.WriteLine("Encryted String for {0} = ", s);
                              foreach (char ch in s)
                              {                                                   
                                                   Console.Write((char)((int)ch+1));
                              }
                   };
del("Hello");



Here statement lambda which encrypts the given string, is assigned to delegate which accepts string and returns nothing.

Anonymous methods are very similar to statement lambdas. They can be used to instantiate delegates just like statement lambda. We will see them in another article

Anonymous Methods, Lambda Expressions, lamda vs anonymous and their advantages

Anonymous methods:

Anonymous methods are introduced in .NET 2.0. Anonymous methods are inline methods with no name that can be directly assigned to a delegate. These methods are set of statements without any special syntax as in lambda expressions.

Advantages of anonymous methods over lambda are:

 They can be assigned/converted to delegate of any signature. They do no need parameter list to be mentioned like in lambda expressions.

Examples:

 Example 1.a

button1.Click += delegate(System.Object o, System.EventArgs e)
                   { System.Windows.Forms.MessageBox.Show("Click!"); };

Example 1.b

delegate int Square(int k);

Square d = new delegate(int k){return k*k;};

Common for Both Lambda and Anonymous methods:

1. We avoid overhead of writing methods for handlers or delegate by using anonymous methods whenever possible. 
2. They can't be explicitly called in code. 
3. They can't contain goto or break or continue statements where the target is out of expression or method block.
4.  Scope of variables in anonymous methods is method block only.
5.  They can't accept parameters using ref or out keyword.
6.  They can use variable declared outside their scope and such variable are called outer variables.

Lambda Expressions:

Lambda expressions are introduced in C# 3.0. They are used to instantiate a delegate by an inline method. This inline method will contain lambda (=>) after the input parameter list and statement to the right of lambda symbol. 

(input parameters) => expression

By using lambda expressions we can write local methods that can be passed as arguments that expect delegate as an argument.

    

     (x) => x? 5:0;

  () => SomeMethod() //zero parameters

Here, x is the input parameter. 

Statement lambda is similar to lambda expressions where in set of statements to the right of lambda are enclosed in {} and parameter list is to the left of lambda operator. 

      (input parameters) => {statement;}

Lambda expression can only be used to instantiate delegate of particular signature.

The general rules for lambdas are as follows:

• The lambda must contain the same number of parameters as the delegate type.
• Each input parameter in the lambda must be implicitly convertible to its corresponding delegate parameter.
• The return value of the lambda (if any) must be implicitly convertible to the delegate's return type.

Abstract Class vs Interfaces (C#) - Differences, Recommendations about when to use what?

This is a favorite question of any interviewer. Probabilities are less where interviewer expects syntactic differences rather one might be looking at design level differences. Next question which follows is "When do you prefer interface over abstract classes" or other way round. I have collected answers over the internet to compile one simple page to answer this question.

Below is from John Noah's interview questions comiplation:

An abstract class can provide complete, default code and/or just the details that have to be overridden.	An interface cannot provide any code at all,just the signature.
In case of abstract class, a class may extend only one abstract class.	A Class may implement several interfaces.
An abstract class can have non-abstract methods.	All methods of an Interface are abstract.
An abstract class can have instance variables.	An Interface cannot have instance variables.
An abstract class can have any visibility: public, private, protected.	An Interface visibility must be public (or) none.
If we add a new method to an abstract class then we have the option of providing default implementation and therefore all the existing code might work properly.	If we add a new method to an Interface then we have to track down all the implementations of the interface and define implementation for the new method.
An abstract class can contain constructors .	An Interface cannot contain constructors .
Abstract classes are fast.	Interfaces are slow as it requires extra indirection to find corresponding method in the actual class.

Below answers are from MSDN.

When shall we prefer Abstract classes or Interface over other? 

• If you anticipate creating multiple versions of your component, create an abstract class. Abstract classes provide a simple and easy way to version your components. By updating the base class, all inheriting classes are automatically updated with the change. Interfaces, on the other hand, cannot be changed once created. If a new version of an interface is required, you must create a whole new interface.

• If the functionality you are creating will be useful across a wide range of disparate objects, use an interface. Abstract classes should be used primarily for objects that are closely related, whereas interfaces are best suited for providing common functionality to unrelated classes.

• If you are designing small, concise bits of functionality, use interfaces. If you are designing large functional units, use an abstract class.

• If you want to provide common, implemented functionality among all implementations of your component, use an abstract class. Abstract classes allow you to partially implement your class, whereas interfaces contain no implementation for any members.

WPF - CheckAccess, Invoke and BeginInvoke On Dispatcher(Similar to InvokeRequired) C#

Assuming we are aware of thread safe model of updating control's text from a different thread(not the main thread), I will explain how do we do the same in WPF.

Every control has a DispatcherObject. Just like in Windows Forms only the thread that created Dispatcher can access that object. We will use either BeginInvoke or Invoke on this dispatcher object to update the text  of the control. Invoke is synchronous and hence will block the call until main thread completes this request. Be cautious while using Invoke in multithreading applications, you might get blocked on this call and you might lose the whole point of being on different thread.

BeginInvoke is asynchronous call on the method that you specify in the delegate. Both Invoke and BeginInvoke accept delegate to the method to be invoked as argument and also parameters to this method as object array. 

For identifying whether we are trying to update control's property on main thread or some other thread we used InvokeRequired in Windows Forms, in WPF we use CheckAccess() method on the dispatcher object of control. Note intellisense might not work for this method, you can go ahead and type it.

I have copied a simple example which combines concept of AutoResetEvent and also BeginInvoke and check access which avoid any "InvalidThreadException: Calling thread can not access this object because a different thread owns it"! exception.

I have used a simple delegate:

        delegate void  textupdater(string text);

private void AutoResetEvent_Click(object sender, RoutedEventArgs e)

        {

            textBox1.Text = string.Empty;

            

            Thread t = new Thread(new ParameterizedThreadStart(HelloWordlInLoop));            

            t.Start(10);

            handle.WaitOne();

            updateText("In the main thread after event handle has been reset");

        }

        void updateText(string text)

        {

            try

            {

                if (textBox1.Dispatcher.CheckAccess())

                {

                    textBox1.Text += text;

                    textBox1.Text += "\n New Update via BeginInvoke";

                }

                else

                {

                    textBox1.Dispatcher.BeginInvoke(new textupdater(updateText), DispatcherPriority.Normal,     

                                                     new object[] { text });

                }

            }

            catch(Exception ex)

            {

                MessageBox.Show(ex.ToString());

            }

        }

        void HelloWordlInLoop(object obj)

        {

            int i = (int)obj;

            while (i-- > 0)

            {

                Thread.Sleep(1000);

                updateText("\n Updating from Second Thread without setting EventHandle. i = " + i.ToString());

            }

            handle.Set();

        }