Thursday, May 24, 2012

Cross thread operation exception - WinForms C#

InvalidOperationException: "Cross-thread operation not valid: Control 'label1' accessed from a thread other than the thread it was created on." This is an exception that is raised when we try to access control's(label1) methods from a different thread than the one that created that control.

In a simple scenario, If we try to set a value for a control from another thread using the control's direct property setter, we will receive this exception.

Let us take an example of status label to be updated from another thread, which performs some other operations and wants to update the same on label. This scenario is very common in GUI development using WinForms. We will use InvokeRequired property of the control to find out whether the control can be updated directly using the control's value property.

InvokeRequired is value that indicates whether caller has to "invoke" a method to make any calls on the control. This is because on a different thread. 

Solution: 
step 1:  Declare a delegate to accept a method that sets label's text
step 2:  Write a method that handles both InvokeRequired and direct text setter to update the text of label.
step 3:  When on different thread, that is when InvokeRequired, Invoke the same method by passing it through the delegate and also the text to be updated as parameter

C# code:


private delegate void UpdateText(string text);
private void SeLabelText( string  text)


 {
   if(label1.InvokeRequired)


 {
        label1.Invoke(new  UpdateText (  SeLabelText  ), text); //invoke using a delegate that accepts method and text as param
     } 
   else

 { 
     label1.Text= text;

   }
}


SetLabelText("New label text");

Now call SetLabelText whenever it is required to update the text of label1, no matter what thread you are on and we are ThreadSafe!

Wednesday, May 23, 2012

Linear Solution: Finding Kth smallest element in an array using Quickselect algorithm

Finding kth smallest element array is a common question across interviews. When this question is asked,  do not even bother to ask whether the input array is sorted. This question can be asked in different ways like:

  • Find the nth largest element in an unsorted array
  • Given two unsorted arrays find kth smallest element in both of the arrays and likewise.
Most widely known solution for this problem is to use QuickSelect algorithm, which is a modification of QuickSort itself. 

A brute force approach would be to sort the array and then to pick the kth largest or smallest element. How do we improve this solution without sorting the entire array?

Quicksort:

Before we get into QuickSelect , let us understand Quicksort in brief. Quicksort works faster in practical than explained. Quicksort can sort n items in O(nlogn) time in an average case. In worst case, Quicksort makes upto n^2 comparisons. With in-space partitioning we can achieve a space complexity of O(n). How a quick sort works?

Simple Quicksort Algorithm:

a. Find a pivot. Pivot is an index inside the bounds of input array chosen intelligently, uniformly and in a random way(Well that's way to make Quicksort efficient!). Let us call this step as "Pivot identification"
b. Group all the elements whose value is lesser than element at index 'pivot' into one array and all the elements that are greater than the value at index pivot into another array. Let us call this step as "partitioning".
c. Recursively call quicksort method on these smaller arrays and concatenate smaller array, pivot and greater array to make the sorted array. 

Simple enough, but this uses unnecessary space for arrays that are created while partitioning. Now lets do "partitioning" "In-place". We call an algorithm as in-space when algorithm works on the given data structure rather than using extra space.  

To make partitioning in-space:

a. We need to modify all the values in the given array such that all the values below pivot's index are less than value at pivot's index and all the values above pivot's index are greater than value at pivot's index.

b. Above step can be achieved by swapping all the elements that are less than value at pivot's index towards starting of array and keep this count say 'storeIndex'. Once we this is done all the values after pivot will be greater than value at pivot. To simplify the swapping lets move pivot element to last element of array using swapping and once we swap other values as required in step -a , we will move back pivot to end of the count 'storeIndex'. This storeIndex will have pivot's index at the end of partitioning. 

Pseudo code for this as in wiki:
 // left is the index of the leftmost element of the array
   // right is the index of the rightmost element of the array (inclusive)
   //   number of elements in subarray = right-left+1
   function partition(array, 'left', 'right', 'pivotIndex')
      'pivotValue' := array['pivotIndex']
      swap array['pivotIndex'] and array['right']  // Move pivot to end
      'storeIndex' := 'left'
      for 'i' from 'left' to 'right' - 1  // left ≤ i < right
          if array['i'] < 'pivotValue'
              swap array['i'] and array['storeIndex']
              'storeIndex' := 'storeIndex' + 1
      end for
      swap array['storeIndex'] and array['right']  // Move pivot to its final place
      return 'storeIndex'



Now lets write in-place Quicksort alogirthm:

Quicksort(array, start ,end)
{
    if array.length <= 1 return array; //recursive return condition
    choose  pivot such that start<=pivot<=end
    pivotindex = partition( array, start, end , pivot);
    return Quicksort(array, start, pivotindex -1) + pivot element + Quicksort(array, pivotindex+1, end); 
}


Let us end a about quicksort now and concentrate on given problem to find out the kth smallest element. To do this we will use quick sort, partitioning and finding pivot that we learnt above.


Quickselect

Quickselect is an alteration of quick sort, where we

  • Find the pivot 
  • Partition based on pivot
  • Check if the required 'k' belongs to which of these partitions and recursively use above steps to find out where is kth smallest element
Here only alteration is 3rd step, where we need to calculate which part of array we need to recursively select to find kth smallest element. Logic is ,
"When we partition an array based on pivot_index then there will be pivot_index -1 elements in first part of array and (actual length of array - pivot_index) in second part of array. If we have find "kth" smallest element, check if k falls in (0, pivot_index-1) or (pivot_index+1, end) sub array. Based on this decision recursively find out where it falls"

Below algorithm is from Yale university's wiki. Algorithm itself is self explanatory. 

*Finding the pivot in a randomized way will make it difficult to understand the complexity of algorithm. 
*In any average case, this algorithm will work in O(n) [tough calculations involved to prove this since we use randomized way to find out the pivot]. Even in worst case this algorithm does not grow beyond O(n^2).
Hence it is better than sorting out whole array and picking from the index, which in better case can be done in O(nlogn).
* Using in-place version of same algorithm will keep the space complexity in O(n).


QuickSelect(A, k)
  let r be chosen uniformly at random in the range 1 to length(A)
  let pivot = A[r]
  let A1, A2 be new arrays
  # split into a pile A1 of small elements and A2 of big elements
  for i = 1 to n
    if A[i] < pivot then
      append A[i] to A1
    else if A[i] > pivot then
      append A[i] to A2
    else
      # do nothing
  end for
  if k <= length(A1):
    # it's in the pile of small elements
    return QuickSelect(A1, k)
  else if k > length(A) - length(A2)
    # it's in the pile of big elements
    return QuickSelect(A2, k - (length(A) - length(A2))
  else
    # it's equal to the pivot
    return pivot

More Info and references:
1. http://en.wikipedia.org/wiki/Quicksort : Quicksort implementations and pseudo code snippets
2. http://pine.cs.yale.edu/pinewiki/QuickSelect :Quickselect algorithm and complexity calculation.

Tuesday, May 22, 2012

Finding a loop in a singly linked list - O(n) solution

We can go about this problem in many ways. We will look into few solutions which work in linear time and without adding to space complexity. 

By above problem definition,  list can either be a:

a. Completely reversed list : where last node of the list points to first node of the list.
a->b->c->d->a

b. Randomly looped list: Where some node in the list points to some other node in the list which has already appeared. i.e. list can be like  
a->b->c->d->c

If it is a completely reversed list then we can traverse to the end of list to find out whether last node is same as current node as below. 

public bool IsLooped(Node head){
  Node currentNode = head;
  while (currentNode = currentNode.next()){
    if (currentNode == head) return true;
  }
  return false;
}

Most of the times, interviewer will not expect you to find out full-loops. Instead he will be looking for a solution to find out Randomly looped list. 

We will discuss three solutions numbered based on how good the solution is.

1. "Floyd's Cycle-Finding Algorithm" as published in "Non-deterministic Algorithms" by Robert W. Floyd.

In this method we traverse the list using two pointers, one moves at double the speed than the other.
We will come across the loop when the fast moving pointer's node is same as the node slow pointer is pointing to. This algorithm works in O(n) time complexity.

This algorithm finds out the loop within one traversal of the entire list.

Algorithm:
a . Slow pointer goes through each node
b.  Fast pointer goes twice fast and checks if the node pointed by fast node and node next to it is same as node pointed slow pointer. If it is same then it means we found the loop. Easy as it reads.

Below code snippet is from link that is from reference mentioned at the end of this article:

// Best solution
public bool hasLoop(Node startNode){
  Node slowNode = startNode;  Node fastNode1 = startNode; Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

2. This solution is by Ostermiller. Here we will have to traverse the list thrice to find out the loop. Hence it works in linear time.

Algorithm :
a. Keep the check node to null and initialize two variables since to 0 and sinceScale to 2.

b. Keep moving the current node to next node till since is less than or equal to sinceScale.
This step assures current node is moved thrice and each time it is checked with checknode if there is a loop.
This step will check each node to which current node moved in those iterations with checknode.

c. Change the check node in next while iteration to node pointed to by current node and repeat step -2.

Reset 'since' to 0 once checknode is modified. This is to allow current node to be checked with new checknode in each iteration while since < sinceScale ,keeping the checknode constant during these iterations.

public bool hasLoop(Node startNode){
  Node currentNode = startNode;
  Node checkNode = null;
  int since = 0;
  int sinceScale = 2;
  do {
    if (checkNode == currentNode) return true;
    if (since >= sinceScale){
        checkNode = currentNode;
        since = 0;
        sinceScale = 2*sinceScale;
    }
    since++;
  } while (currentNode = currentNode.next());
  return false;
}

3. Reversing the list: This solution is valid when problem states list can be modified. This is a brute force approach where we remember the initial node and start reversing the list, if we get back to the initial node that means there is a loop. Note: Use it only when interviewer is good with modifying the list.

References:
This is a nice article which covers finding out a loop in detail. All code snippets are picked from this website. http://ostermiller.org/find_loop_singly_linked_list.html . Thanks!

Monday, May 21, 2012

Shallow Copy and Deep Copy in C#

When copying one instance to another there are several ways of doing it. If we try to assign an object to another object, only reference gets copied and hence both objects will point to same memory.

Obj a = new  Obj();
Obj b = a; //a and b will have same reference

Hence if you modify anything in one object will modify another. It is because in memory it is same memory, same reference assigned to two variables.

Shallow Copy: 


Shallow copy is the way copying an object's value type fields bit by bit into target object and object's reference types are copied as references into the target object but not the referenced object itself. This can be done in C# using MemberwiseClone() method on an object. As in MSDN, "The MemberwiseClone method creates a shallow copy by creating a new object, and then copying the nonstatic fields of the current object to the new object."

This cloned object will contain all the values of value types that are in source object and references are copied for reference types that are in source object. i.e. copying all fields that value type bit by bit copy and for all reference type fields only references are copied but not the referred object. Lets look into below example:


    class A:ICloneable
    {
        public string i = "";
        public B b;

        #region ICloneable Members

        public object Clone()
        {
            return this.MemberwiseClone();
           
        }

        #endregion
    }


 class B
    {
        public string j = "";
    }

With above two classes let's try to do a shallow copy(see inline comments to understand what's happening in each step)


            A a = new A(); //new instance creation of type A
            a.b = new B(); //instance for b which is part of object a. This is reference type that is in A
            a.b.j = "test"; //assign values for variables inside instance b which is contained in instance a
            a.i = "test"; //i is the value type here, assigning the value to the value type inside A

            A a1 = a.Clone() as A;        //Shallow copy using this.MemberwiseClone() in A's instance 

            a1.i = "asas"; //Change the value in cloned copy for value type
            a1.b.j = "changed"; //change value in cloned copy for a variable inside reference type of A's instance

Now what we observe in above steps:

a. When we clone a to a1, all the values of a are copied to a1 including variable 'j' which is reference type b
i.e. after cloning a1.i will have value 'test' and a.b.j will have value 'test'.

b. To prove references are copied for reference type not just value copy, we will change the value a1.b.j to some other string "changed". This changes the value of a.b.j as well. This is because when clone is created , all members are cloned and references are copied as it is. Hence a.b has reference as a1.b.


Deep Copy: 

Deep copy is the way of copying an object completely bit-by-bit i.e. Deep copy copies value of every field inside an object. For nested objects(objects that contain other objects), deep copy creates new instances for each object inside nested object and copies all the values for fields inside them. 

In short, after deep copy copied instance will have same values that were in source object but none of them refer to same memory or hold same reference.

Deep copy can be performed using MemberwiseClone() method also. For each object contained in current object do a memberwise clone and copy all the values of all fields to perform a deep copy.

class A:ICloneable
    {
        public string i = "";
        public B b;

        #region ICloneable Members
        
        //This method performs deep copy
        public object Clone()
        {
            A a = this.MemberwiseClone() as A; //creating a new instance of A to copy values to
            a.b = this.b.Clone() as B; //copy each value or clone for each instance inside instance b
            return a; //return the copied object
           
        }

        #endregion
    }

    class B
    {
        public string j = "";

         public object Clone()
        {
            return this.MemberwiseClone();
            
        }
    }

In above example Clone() method of class A performs deep copy by first calling this.MemberwiseClone() on this. This step assures all value types inside are copied into new instance i.e. a inside clone method. For reference type B inside class A, we need to create another instance which copies instance b that is contained  in object a. This can be done calling memberwise clone on instance b which is in a. This call assures all the value types inside b are copied into new instance and this new instance can be assigned to the instance which we will return as deep copied instance. 

Note: Since class B did not have any reference type MemberwiseClone call in B works well for deep copy.


Deep copy implementation without using nested MemberwiseClone()


However in real time scenarios, each instance is a composition of many instances in turn might hold many instances. Hence to do a deep copy using MemberwiseClone() requires nested cloning of each instance contained and in the same hierarchy as the source object. This grows in complexity with dynamic binding and run time instance creation. It also required that we implement Deep copy for each class inside the source type. 

This complexity can be overcome by using Serialization and Deserialization to create a deep copy instance. Only classes that are marked with [Serializable] attribute can only be copied using this technique. But remember this simple way of deep copy comes with the overhead of Serialization and Deserialization and hence might impact performance.




Below is the example from stackoverflow:


public static T DeepClone<T>(T obj)
{
 using (var ms = new MemoryStream())
 {
   var formatter = new BinaryFormatter();
   formatter.Serialize(ms, obj);
   ms.Position = 0;
   return (T) formatter.Deserialize(ms);
 }
}

Steps involved are:

  •  Serialize the source object into a memory stream
  •  Set the position to starting of the stream.
  •  Deserialize this memory stream , type cast it to source object type and return as deep copy 


Value Types in C#

There are two types of Data types in C#, Value types and Reference types.  Value types are those variables which can directly assigned a value with. Few examples are 

a. Structs
b. Enums
c. Primitive(Simple) data types like Int, Char

When a value type variable is assigned to another variable, value associated with that variable is assigned to other unlike reference types where reference is copied.

System.Object is base class for any type in .NET.

Quick Points about Value Types:
  1. Value types are allocated on Stack
  2.  All Value Types derive implicitly from System.ValueType class, which derives System.Object which is base for any type.  We cannot create a class that inherits from ValueType. 
  3. Value types can implement interfaces. e.g. structure can implement interfaces.
  4. Each default will have a default value. When struct is instantiated with default values for each of its member.
  5. ValueType class overrides few methods of System.Object class.
Even Value types can be defined with new operator, though it is very rare we use such a statement.

int i = new int();
It is same as creating a variable of type and assigning it to default value. 
int  i = 0; // creates and assigns value 0 to i