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();

        }

Difference between TRUNCATE, DELETE and DROP TABLE in SQL (Transact-Sql)

1. Both Truncate and Delete are used to delete rows from a table.

2. Truncate is like a delete command without a WHERE clause. 

3. Truncate deletes all rows of a table without logging for each row deletion. Truncate is a DDL command whereas Delete is a DML command.

4. Delete allows you to choose the rows to be deleted based on some condition but Truncate clears everything. Delete logs for each row it deletes, also will raise trigger if there is one and also it acquires lock before deleting that row.

5. Truncate removes all the rows in the table but retains its table structure, indexes, columns, constraints etc. Even Delete retains the constraints, structure, columns,etc.

6. Drop table completely removes a table from the data base including its structure, constraints etc. 

7. We cannot use Truncate on table that has Foreign Key referenced and even on a table that has participated in indexed view.

8. Truncate cannot activate Trigger whereas Delete can.

Advantage of Truncate over Delete as explained in MSDN:

Compared to the DELETE statement, TRUNCATE TABLE has the following advantages:

·         Less transaction log space is used.

The DELETE statement removes rows one at a time and records an entry in the transaction log for each deleted row. TRUNCATE TABLE removes the data by deallocating the data pages used to store the table data and records only the page deallocations in the transaction log.

·         Fewer locks are typically used.

When the DELETE statement is executed using a row lock, each row in the table is locked for deletion. TRUNCATE TABLE always locks the table and page but not each row.

·         Without exception, zero pages are left in the table.

After a DELETE statement is executed, the table can still contain empty pages. For example, empty pages in a heap cannot be deallocated without at least an exclusive (LCK_M_X) table lock. If the delete operation does not use a table lock, the table (heap) will contain many empty pages. For indexes, the delete operation can leave empty pages behind, although these pages will be deallocated quickly by a background cleanup process.

Examples:

TRUNCATE TABLE Employee;

DELETE FROM Employee Where Salary> 10000;

DROP TABLE Employee;

Performing Inner Join and Left Outer Join in LINQ Queries

Linq supports joining just like any other querying language. Syntax is bit different from standard SQL query though. Also We need to add some logic to achieve Left Outer Join as there is no standard keyword for this.

In our example, we have list of people with their name and their address. We also have list of houses in city with their house name and owner name. 

a. Lets understand performing inner join. Inner join joins two tables based on some condition. Results will include only those entries from joined tables which match the condition. To illustrate inner join we need to find out all the people who own a house with their address. We use "join" keyword with "on" clause to achieve this inner join.  Example I have provided is self explanatory.

b. If we have to output all the people along with their house names if they own otherwise print empty string, then we can go for left outer join. In this join lets make People as left item. We use  DefaultIfEmpty() method to ensure for every People entry will appear in output result. DefaultIfEmpty() provides empty\default for each non matching sequence i.e for any People object if matching sequence in Houses is empty then DefaultIfEmpty returns single default item. In next select we can check if result is default or contains some value. If result sequence contains some value other than default, then we can output that value otherwise we can output empty string or default value.

Below example shows how Left Outer Join and Inner Joins are performed in our example:

        public static void Main(string[] args)

        {

            People p1 = new People { Name = "Manu", Address = "Marathalli" };

            People p2 = new People { Name = "Dada", Address = "BTM" };

            People p3 = new People { Name = "Saavu", Address = "Kunadanahalli" };

            People p4 = new People { Name = "Vasanth", Address = "Munnekolala" };

            People p5 = new People { Name = "Andy", Address = "Jayanagar" };

            People p6 = new People { Name = "Putta", Address = "JP Nagar" };

            Houses h1 = new Houses { HouseName = "Jaipur Palace", HouseOwnerName = "Putta" };

            Houses h2 = new Houses { HouseName = "Mysore Palace", HouseOwnerName = "Manu" };

            Houses h3 = new Houses { HouseName = "Pune Vihar", HouseOwnerName = "Vasanth" };

            List<People> people= new List<People> { p1, p2, p3, p4, p5, p6 };

            List<Houses> houses = new List<Houses> { h1, h2, h3 };

            Console.WriteLine("Inner Join Results:");

           //Inner join to print all the Person with house with house name

            var houseOwners = from p in people

                              join h in houses on p.Name equals h.HouseOwnerName

                              select new { p.Name, PersonHouseName = h.HouseName, p.Address };

            foreach (var h in houseOwners)

            {

                Console.WriteLine(h.Name+" : "+h.PersonHouseName+" : "+h.Address);

            }

            Console.WriteLine("************************************************************************");

           //Left outer join to print all the people and also their house names if they have one otherwise empty string

            Console.WriteLine("Left Outer Join Results:");

            var allppl = from p in people

                   join h in houses on p.Name equals h.HouseOwnerName into tempOwners

                   from nonOwners in tempOwners.DefaultIfEmpty()

                   select new { p.Name, PersonHouseName = (nonOwners==null)? string.Empty:nonOwners.HouseName, p.Address };

            foreach (var h in allppl)

            {

                Console.WriteLine(h.Name + " : " + h.PersonHouseName + " : " + h.Address);

            }

        }

    public class People

    {

        public string Name {set;get;}

        public string Address { set; get; }

    }

    public class Houses

    {

        public string HouseName { set; get; }

        public string HouseOwnerName { set; get; }

    }

Console Output Window:

Threads, Threads Overhead ,Kernel Internals, Kernel Architecture and Asynchronous Methods in C# - Part 2

Thread Context Switching:

A single CPU can only do one thing at a time. Windows keeps switching between processes to give user robust & responsive system and also better overall experience. Windows Scheduler give slices of CPU time to each thread. It is called Quantum(Time period varies from architecture to architecture). After each time-slice elapses windows scheduler switches to another thread. This is called thread context switching. This switching enables multiple threads to share same CPU & hardware resources to provide "multitasking" support. 

The next thread that gets CPU might be from different process itself. In such case windows has to change to that process virtual address space as seen by the CPU before executing any code of that process or processing any data  of that process. 

Each Context switch  has to go through below steps:

1. Save the context of the thread that just finished executing.
2. Place the thread that just finished executing at the end of the queue for its priority.
3. Find the highest priority queue that contains ready threads.
4. Remove the thread at the head of the queue, load its context, and execute it.

Saving the context requires thread context must be stored somehow so that when next switch happens to that thread we can restore this information. This step of storing and restoring from thread's context structure includes,

• Saving the values of CPU registers that were assigned to the current thread into thread's context structure inside thread's kernel object data structure.  
• Changing virtual address space if required as explained before.
• Loading from next thread's context into CPU registers.

This is performance overhead at the cost of giving user a responsive system. This switching would allow,

• Avoiding CPU starvation by preempting ready threads over threads that are waiting for input or resource.
• Execution Ready threads to be taken up according to their Priority.
• CPU time to all the processes allowing each one to run.
• Keep system responsive even when few threads\processes go into deadlock or infinite loop.

Hence multiple thread approach will add to number of context switches which in turn affects performance.  

Now lets see how new thread creation adds to Windows performance overhead:

When windows context switches CPU from one thread to another, previously executing thread's data and code reside in CPU cache, so that CPU does not have access RAM. This is to avoid latency in accessing information from memory. When a new thread is created, it might have to access different data and execute different code altogether. Since this will not be on CPU cache, it has to populate this data from RAM into cache, to speed up the processing speed. This might happen every time a new thread is added, thus causing performance overhead.[CLR Via C#].

Now that we understand why thread creation, destruction and maintenance causes affects performance and memory efficiency , we will see how number of threads affect GC performance.

Number of threads also affect the performance of Garbage Collector. Before collection or GC cycle, GC must suspend all the threads. GC walks through stack of each thread to mark the root of each heap object, walk their stack again to update the stack to updating the roots of objects that have moved during compaction. GC resumes all the threads only after this collection cycle. This causes GC to perform slow.

Multiple threads keep the application responsive but they also have above explained overheads. When designing an application with multiple threads we need to understand real intent of each thread and its necessity before creating one.

I will end thread overhead concepts here. In my next articles, I will go briefly into Kernel and its architecture.

Threads, Threads Overhead ,Kernel Internals, Kernel Architecture and Asynchronous Methods in C# - Part 1

Before we get into Asynchronous methods and using them, let us find answers for:

What are threads, What is a kernel object and thread kernel object,  How threads are created and destroyed, How windows handles Threads, What a thread consumes, What is Context switching, Why do we use multiple threads, What is asynchronous in terms of CLR, Why we need asynchronous programming, How is it different from traditional threaded programming, What is ThreadPool, How can we achieve asynchronous behavior using ThreadPool, How ThreadPool and CLR are related etc.

I assure you I will not get into MultiThreading concepts or Thread synchronization concepts when trying to explain threads and asynchronous programming.

Threads:

As we understand basics of thread, Thread is a basic unit of execution. Threads can be thought of as logical CPUs. We can say thread's job is to virtualize CPU. Different processes run on different threads hence each of them have an isolated environment of execution. Thread is responsible for execution of application code. Also, Threading allows us to deviate from current or main thread and execute some computation or some method on different thread. We mostly use multithreading in scenarios where we need to keep the UI responsive irrespective of things going on underneath, when we need to compute\parse\work with large information which might not be of immediate concern, backup and restore activities which need not keep user idle, waiting for keystrokes or waiting for other processes or waiting on events etc.

Aim of any application is to avoid keeping user idle while he waits for something to happen. Threading allows to create separate execution context for these event based or computing based methods or I/O wait methods while letting the user work on the application. 

Everything sounds good and concept of threading seems to meet all our parallel execution or background execution needs. Don't get into parallel execution right away! We need to understand many other things before we get into parallel execution.

Quick Notes here:

a. All threads of a process share its virtual address space and system resources.

Threads Overhead: 

Thread is an OS concept than language or framework feature. Threads do have overhead like performance and space overhead associated with them. Two majors types of overhead with Threads are:

1. Memory & Resources that are associated with Thread.

2. Context Switching between Threads

OS allocates memory for each thread creation. Memory is allocated for different purposes. We will see each of them in brief. Every thread contains each of the following:

1. Thread Kernel Object:

Kernel object is a block of memory allocated by the kernel. This memory block is a data structure that contains and maintains information about the object. Typical Kernel objects are File objects, pipe object, mutex object, file mappings etc. In general any kernel(OS) function called by your application, that returns an handle back to the application may create a kernel object, but not always. An Application has to keep track of all kernel objects that are created by its process. In turn application can keep track of kernel objects by their handles. These handles can be later used by the process to clear off all the resources\objects that process created. Consider example of process. Process object is also a kernel object. Whenever a process is created, a table is created in which indexes of all the objects used by process are stored. Any kernel objects created by your process gets an entry in this table. 

Handle is nothing but the index to this kernel object's entry in this process table. Kernel takes care clearing a kernel object whenever the usage count of that object becomes zero.

Quick points here:

a. Usage count is the common property across all these kernel object data structures. 

b. Closehandle will decrease the usage count of kernel object by 1. It will cleared off only when the usage count reaches 0. Hence a kernel object may remain in memory even after the process dies. 

Does not this point touch something about "Disposing" unmanaged resources in our managed code? Yes, you got it! 

Now back to threads, OS creates and allocates a kernel object data structure for each thread created. This data structure contains information about thread. This data structure also contains information about "Thread context". This is a memory block that contains set of CPU registers. When Windows is running on a machine with an x86 CPU, the thread’s context uses about 700 bytes of memory. For x64 and IA64 CPUs, the context is about 1,240 and 2,500 bytes of memory, respectively.[CLR Via C#]. Each thread maintains exception handlers, a scheduling priority, thread local storage, a unique thread identifier, and a set of structures that system requires. These all information will be part of kernel object data structure.

Thread Context includes thread's set of CPU's registers, kernel stack, thread environment block and user stack in the address space of user's process. We will see each of this concept one by one.

2. Thread Environment Block(TEB or TIB): 

TEB is also called as Thread information Block (TIB). TEB is user-mode portion of Windows thread control structures. Structure of TEB can be seen here. TEB structure should not be directly accessed .  This contains head of thread's exceptional handling chain. 

This also contains storage for data that is local to the thread and also some data structures that can be used by user interface modules like OpenGL and GDI. This structure consumes 1 page of memory.

More information about TEB and viewing TEB information can be found here.

3. User Stack:

a. This stack is used to store all local variables and parameters passed to methods.

b. It also contains address indicating what thread should execute next after returning from current method.

1MB is allocated by default by windows for a thread's user stack.

4. Kernel Stack: 

In simple terms, this is the stack used by kernel. Any parameters that are passed from user-mode code to kernel are copied from thread's user stack to thread's kernel stack. OS does this copying. Kernel also stores local variables that are used by thread's kernel method on this stack. This stack is used by kernel to store all the arguments that are passed to other kernel methods, to store all local data of those functions and to store return addresses.

All arguments passed to kernel method is validated before OS starts operating on them. Once OS starts operating on these arguments , application will not be able to modify these arguments' values. The kernel-mode stack is 12 KB when running on a 32-bit Windows system and 24 KB when running on a

64-bit Windows system.

5. DLL Thread ATTACH and Thread DETACH notifications:

Whenever a thread is created in a process, windows calls DLLMain methods of all the dlls that are loaded in the process by passing DLL_THREAD_ATTACH flag. Also when a thread dies, windows calls DLLMain method with DLL_THREAD_DETACH flag on all the dlls that are loaded in the process. This may be required to initialize the thread with expected state as the executing library wants it.

Imagine the case where  there are numerous dlls loaded in our process and windows has to call DLLMain method on all dlls for each thread creation and destruction. That sure is a overhead, is not it?

All the above factors that a thread contains makes us understand, memory (space) and performance (time) overhead that is involved in thread creation, destroying and keeping it alive.

But this is not all, Context Switching between threads also adds to performance overhead. Let us see this in detail in my next article.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

I will continue with more information about context switching adding to thread overhead, more into kernel and OS architecture and need for asynchronous methods in next my article.

Note: This article is the information that I pooled from CLR Via C# book, MSDN articles, University websites, StackOverflow answers, Albahari's C# 4.0 Nutshell etc. If you have any problem with content please let me know.

Find Whether Each Element of One Array Occurs Same Number of Times In Second Array - O(n)

Problem:
Given two arrays find out if each element in array1 occurs same number of time in array2 :-
input = {2,3,4,2,3}
{3,2,3,2,4}
output = true

Solution 1:

Below solutions assumes that numbers are positive. If two arrays contains same numbers in any order then XOR of all elements of one array must be same as XOR of all elements of another array.


This does not work in case where XOR result of two arrays are same. As Anshu Pointed out in his comments e.g.  [36, 74] is same as [98, 12] See my other solutions in such case.

        static bool AreTheySameArrays(int[] arr1, int[] arr2)
        {
            if (arr1.Length != arr2.Length) return false;
            int xor1 = arr1[0]; int xor2 = arr2[0];
            for (int i = 1; i < arr1.Length; i++) { xor1 = xor1 ^ arr1[i]; xor2 = xor2 ^ arr2[i]; }
            return (xor1 == xor2);            
       

Solution 2:

This solution covers all the cases.  This approach uses brute force approach of keeping the count of each element in first array and reducing the same when we find the same element in second array. Finally, we iterate over this count list to find whether all the elements have count as zero. If not return false.



        static bool AreTheySameArraysUsingDictionary(int[] arr1, int[] arr2)
        {
            if (arr1.Length != arr2.Length) return false;
            Dictionary<int, int> countTable = new Dictionary<int,int>();
            for (int i = 0; i < arr1.Length; i++)
            {
                if (countTable.ContainsKey(arr1[i])) { countTable[arr1[i]]++; }
                else countTable.Add(arr1[i], 1);
            }

            for (int i = 0; i < arr2.Length; i++)
            {
                if (countTable.ContainsKey(arr2[i])) { countTable[arr2[i]]--; }
                else return false;
            }
            foreach(KeyValuePair<int,int> entry in countTable)
            {
                if (entry.Value != 0) return false;
            }
            return true;
        }


Note:
Solution is not tested regressive. If you find it not working let me know. 

Longest Common Substring Problem - Dynamic Programming (C#)

Given two strings, we need to find out the longest sub string of first string which is also present in second string. 

Let us understand what sub strings are, sub strings of a string "manu" are 'm', 'a','n','u','ma','man','an', 'anu', 'nu'. We are only concerned about sub strings but not all permutations of the given string . 

Let us take example of strings, "hello" and "yellow". The common sub strings for these two are many but we need to find out the longest one which is "ello" in this case. Yes, now we get the idea. This can easily be solved in a recursive way. This problem is where we need to use previously computed result and build solution over it. Common sub string will start with a character that is common in both string 1 and string 2. With compromise to time and space we can solve above problem in O(m*n) time and O(m*n) space using straight away approach. Since we use previously computed values, we can store them and avoid extra computations and thus make this solution belong to category of "Dynamic Programming". 

For each character str1[i] we loop with all the characters in str2. If str1[i] matches with any character in str2, we can say common sub string  exists here which is of length (length of longest common sub string of str1[1..i-1], str2[1..j-1] +1) or starts here which is of length 1. We will use a two dimensional array of dimensions [str1.len, str2.len] to store, longest common sub string at that point [i,j].

if str1[m] == str2[n] 

     LCS(Str1[1..m], str2[1..n]) = LCS(str1[1..m-1],str2[1..n-1]) +1

else

      LCS(Str1[1..m], str2[1..n]) = 0

For "hello" and "yellow" above mentioned LCS method can be explained with below table:

This wiki link explains this solution better using tables to store intermediate values and solving complete problem by solving smaller problems. We will code above explained solution using C#. We need to iterate over each character of string 2 inside each character looping of string 1 and make sure we update lcs_so_far whenever we come across lcs of common sub string of greater height. We can use the length and last index of common sub string to actually print the longest common sub string.

Below implementation does not handle boundary or any special checks. It is only to explain the longest common sub string algorithm. [Tested with multiple inputs]

Code:

        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 (str1[i] == str2[j])

                    {

                        if (i == 0 || j == 0)

                        {

                            l[i, j] = 1;

                        }

                        else

                            l[i, j] = l[i - 1, j - 1] + 1;

                        if (l[i, j] > lcs)

                        {

                            lcs = l[i, j];

                            end = i;

                        }

                    }

                    else

                        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);

        } 

Longest Common sub string problem can be solved efficiently using suffix trees. We can achieve almost linear time with suffix trees or even "Trie". I will cover "Trie" and\or suffix trees in some other article. "Trie" allows you easy text search like suffix trees. They both allow a text to be searched in quicker time but may need space and time to create the tree.

Note: Using trees will be ideal here. 

Find The Largest Palindrome Lesser Than The Given Number 'N' - O(Log(N)) base 10

Problem:
Given a number "N", find out a number "k" such that 'k' is the largest palindrome that is lesser than "N". [Even when given number is a palindrome]
e.g. if N if 64 print 55, if N=320 Print 313.

Analysis & Algorithm:
For our simplicity we will create an integer array from the given number. This array will save each digit as its element.Lets write IsPalindrome method such that it accepts this integer array and determines whether number is already a palindrome.

We need to understand that while we are doing any swap or interchange or modification, resultant number should not go greater than given number itself.

If second half of the array is mirror image of numbers in first half of the array around mid point, then we can say that is a palindrome. Do not even try decreasing the number in a loop and keep checking whether the reduced number is a palindrome. That certainly is a bad approach.

Lets try anther approach where we make second half of the array as the mirror image of first half of array. For this we can copy numbers in the 'i'th position of array into 'array.length -i'th position. This would assure we will get a palindrome number.

But, wait, this would not give what is asked for. We need to find a number which is strictly lesser than given number and the largest of all palindromes under it.

Lets iterate from i=0 to i<=len/2, where len is the number of digits in the given number.

If we handle few cases then we can improve above mentioned solution to work for us:

1. When a[i] > a[len-i], then we cannot simply copy a[len-i] = a[i], this will make the number greater than given number. This case can be handled like subtraction of a larger digit from a smaller digit, where we take the carry from next digit. Similarly when a[i]>a[len-i], we will try to take the carry from the next digit i.e. a[len-i-1]. If that digit is a zero, we will proceed till we get a non zero integer and then carry from it. i.e. reduce that non zero number in the array by 1 and then make all zeros on the way to 9. This is same like in subtraction again. Once this is done we can copy the value a[i] into a[len-i].

2. If a[i]<a[len-i], directly copy a[i] into a[len-i]

3. If the number itself is a palindrome, reduce the number by 1 and apply the same algorithm as above.


If you take care of indexes properly above algorithm should work you in all the cases. C# Code for above explained solution is below. Comment if you have a suggestion or if you find a problem in my approach.


Solution:



        public static void GetLargestPalindromeLesserThan(int[] num)
        {
            int len = num.Length - 1;
            //check if its already a palindrome, then we will alter the number as 1 as given input
            if(isPalindrome(num))
            {
                int k =0;
                while (num[len - k] == 0)
                {
                    num[len - k] = 9; ;
                    k++;
                }
                num[len - k]--;
            }
            for (int i = 0; i <= len / 2; i++)
            {


                if (i != (len - i))
                {
                    if (num[i] > num[len - i])
                    {

                        int k = 1;
                        while (num[len - i - k] == 0 && (len - i - k) != i)
                        {
                            //same as taking a carry and moving it to next digit
                            num[len - i - k] = 9;
                            k++;
                        }
                        num[len - i - k]--;
                        num[len - i] = num[i];
                    }


                    else
                    {
                        num[len - i] = num[i];
                    }
                }
                
            }
            for (int i = 0; i <= len; i++)
            {
                Console.Write(num[i]);
            }
        }


        private static bool isPalindrome(int[] num)
        {
            int len = num.Length - 1;
            for (int i = 0; i < len / 2; i++)
            {
                if (num[i] != num[len - i])
                {
                    return false;
                }
            }
            return true;
        }

Reverse words of a given string - In place C# function without using string operations

Problem:

Given a string like "No, I'm Not Manu M S" print the words of the string in reverse order. Output: "S M Manu Not I'm No,". Do not use another string or stack or extra storage for doing this.

Solution:

We will write plain C style code without using any C# string method. Lets assume, words are separated by a space. Lets ignore the case wherever other symbols can separate the words( for our simplicity). We are asked to reverse the words but not the string reversal itself.

Our method follows below steps,

1. Find the length of a string. Bear with me to use Length property of string, since it is straight forward , lets not even code how to find the length also.

2. Reverse the string in-place, for each character in string from 0 to length/2 swap character at [length - i] with character at [i]. Remember to exit this loop at length/2, otherwise string gets reversed again. i.e. after length/2 steps we will have the reversed string with us.

3. For each word in the reversed string, reverse the characters. This step is not O(n) since we loop for the letters of a word inside the loop which loops through each character of reversed string. Inner loop is to reverse letters of each word of the reversed string. Make sure indexes are incremented carefully, to consider index of space, last index of space etc.

4. Print the string now. We have the words reversed.

Code:

       public static void ReverseWords(char[] words)

        {

            //O(n)

            int lenght = words.Length - 1;

            char temp ='o'; 

            //O(n/2)

            for (int i = 0; i <= lenght/2; i++)

            {

                //swap char at n-i with i

                temp = words[i];

                words[i] = words[lenght - i];

                words[lenght - i] = temp;

            }

            int wordStartIndex = 0;

            int wordEndIndex = 0;

            for (int i = 0; i <= lenght; i++)

            {

                if (words[i] == ' '  || i== lenght)

                {

                    //special care for last word

                    if (i != lenght)

                        wordEndIndex = i - 1;

                    else

                        wordEndIndex = lenght;

                    for (int j = wordStartIndex; j <= (wordStartIndex + wordEndIndex) / 2; j++)

                    {

                        //swap char at n-i with i

                        

                        temp = words[j];

                        words[j] = words[wordEndIndex + wordStartIndex- j];

                        words[wordEndIndex + wordStartIndex - j] = temp;

                    }

                    wordStartIndex = i + 1;

                }

            }

            //print the reversed words in given string

            for (int i = 0; i <= lenght; i++)

            {

                Console.Write(words[i]);

            }

            Console.WriteLine();

        }