Graphs : Euler circuit and Euler path in graphs

To understand basics of graph, please follow  link:  Graphs : Basics and representation
Today we will be discussing a typical problem on graph that is to find if there exists an Euler path or Euler circuit in graph and if yes, trace that path or circuit.

Problem statement

Find if a connected graph has Euler path or circuit.
Euler path is trail in graph which visits each edge only once from source to destination. For example in following graph, Euler path will be :

Euler Path of a graph

Similarly, Euler circuit is Euler path only where source and destination nodes is same node.

Analysis

There are two types of graphs : Directed and undirected graphs, for each of them condition for having Euler path and circuit vary a bit. So consider undirected graph first.
For undirected graphs:
For an undirected graph to have Euler path, each and every node of the graph should have even degree except from start and end node of path which may odd degree. To understand what is degree,please follow the link at the top which explains basics about graphs,

To have Euler circuit all nodes should have even degree with no exception.
For directed graphs:
For a directed graph to have Euler path, on each node, number of incoming edges should be equal to number of outgoing nodes except start node where out degree is one more than in degree and end node where incoming is one more than outgoing.
To have Euler circuit, all nodes should have in degree equal to out degree.
We have to keep in mind that for both directed and undirected graphs, above conditions hold when all nodes with non zero degree are part of strongly connected component of graph. To read more on strongly connected component, please follow this link : Graphs : Connected components

Now, since we know condition to have Euler path and circuits, we write code for it. All we need to do is to count in degree and out degree of each node and check for conditions above. If they meet, we are all good to say yes else no there does not exist any Euler path. 

Code

Complexity of above code is O(V+E)

Once we have figured out that there is a Euler path, we need to find that path. There are two algorithms for it.

  1. Hierholzer’s algorithm
  2. Fleury’s algorithm
In next posts we will discuss about these two algorithms and their implementations.

Operating systems : Thread models using user and kernel space threads

Threads are very important concept in operating systems. We covered the basics and difference between a process and thread in Process Vs Threads post.
Let’s understand it in more detail.

Thread models

We briefly touched upon various thread models which are usually used for implementation of threads. These models are :
1. 1: 1 model
2. M:1 model
3. M:N model
So before understanding what these models are, we should understand what is difference between user space threads and kernel space threads.
User space threads are those threads which are completely implemented in user space using some library which is implemented above kernel. These threads are easy to manage and schedule as whole logic is in application itself. Also, for obvious reasons, application using user level threads is portable to any kernel. No kernel mode privileges are required for switching between threads.
Problem with these threads is that kernel is totally unaware of multithreading at application and any blocking system call will block the whole process.So, these kind of threads are useful in application when thread are in runnable for most of their lifetime. Also, thread needs to give up control voluntarily, else no other thread in process will be able to run.
Use space threads
When thread is implemented in user space, application has to maintain its thread table to keep track of thread status.

Kernel space threads are threads which are implemented in kernel and there is no logic required at application level. Thread creating, management and scheduling is done in kernel space. Advantage is that kernel is aware of threading model and scheduling can be done accordingly.
Drawback of this mode is kernel has to keep track of threads, synchronizations and scheduling, which will be overhead.
To get best of both worlds, we have something called as hybrid models and that’s where above mentioned threading models come into picture, Let’s see them one by one.
1 : 1 model
In this model, for each thread in user space, there is corresponding thread in kernel space, so in true sense kernel can leverage the multiprocessor by scheduling different threads on different processors.
Window server usually follow this model.
1:1 Model
M:1 model
In this model, for M user space threads there is only on thread in kernel space, It is as good as implementing user space thread because once there is system call to kernel, process will be blocked as only once thread is there in kernel. This can be overcome by replacing blocking system calls to kernel with non blocking equivalents, however many systems cannot be implemented as non blocking version.
M:1 Model
M:N model
This model in true sense leverage the threading model, where for M threads in user space, kernel has N threads, there is no predefined one to one mapping between user space threads and kernel space thread and it is done dynamically.
M:N Thread model
Problem is that scheduling needs to be implemented at both user space as well as kernel space.

Given a sequence of words, print all anagrams together

Print all anagrams together

Many a times we need to sort some things which are not integers, foremost being strings. How do we go about using quick sort. I did not know that C library has a function for it. This function is very powerful and easily sort anything given the compare function. So in today’s post we will be using that function and learn how it can be used to solve our problem statement.
Given a list of words, group all words together which are anagrams. For example, if input is like :

cat
tac
act
dog
god
gdo

Analysis

First of all, we want to understand how to strings can be identified as anagrams. There are more efficient ways to do it, but the most simple one is sort two string based on characters and if two resultant strings match, two strings are anagrams.

Now the problem boils down to sorting each individual string and then sort the entire array of strings. The anagram strings will automatically will grouped together.
If we look closely, we have another problem, that is when we sort the original strings individually, original strings are lost. So, idea is to have a duplicate array of strings and then sorting operation. Also to after sorting the duplicate array, we will loose the original index of string once we sort the entire array. Hence we need to store that information too.

Let’s figure what we need to store and how?
We have array of strings, let’s say there can be maximum 100 such strings.
So we create and array of character pointers to store these strings.
Also, we need a duplicate array where we will sort strings and also we need to store the position of the string in original array so, duplicate array would look like:
Next step is to sort individual string in duplicate array, where we will use the library function qsort().
This function is very easy to use, there are four parameters you have to pass:
1. The buffer or the array you want to have sorting performed on.
2. The size of buffer
3. Size of individual element of buffer.
4. And last and most important is the compare function, which has to be written in code and passed as function pointer to this function.
For further details of qsort() function usage follow : qsort

Once all the strings are individually sorted, sort the entire array of strings using the same qsort(), only difference will be the compare function which will now run on entire string instead of character.

We are almost done! Now we have all anagrams placed next to each other, however, we need to print original words. That’s where the index we stored in duplicate array will help and we will print words from original array using the order given in duplicate array.

Code for printing anagrams together

Complexity Analysis

This code will perform sorting on M strings, each of size N characters, so complexity of algorithm to print all anagrams together will be O(MlogM + MNlogN) MNlogN because NlogN for sorting each string of size N and there are M strings,MlogM to sort M strings in array.

Reading input from standard input

Reading input from standard input

Now a days,big companies usually have their first round of interview online where they outsource test to either HakerRank or some other such website. One thing which is of at most importance in those tests is that we need to pass test cases which are run when you submit the code. These test cases are taken from file or standard input and need to be read from standard input. For example, question based on array and array elements will be given on one line on STDIN, without mentioning the size of the array first. So input will be like  34 45 56 78 89 100. We need to read this input, process it and then produce the output.
Many a times, we flounder when we need to take inputs from stdin as we are not used to such things in our day to day coding. In this post I am covering methods in which you can read inputs for STDIN.

Solution

Whenever we are reading from STDIN, use fgets() to read the entire line from it. fgets() takes three arguments, first the buffer where it will read the input to, second size of input to be read in bytes and third the source of input which in our case will be STDIN. For details refer : fgets()
Now, once we have read the entire line of integers from STDIN in buffer, we need to segregate each integer from it. There comes the sscanf ()function.
sscanf() takes three arguments, first the buffer which is read by the fgets(), second the format string of input like “%d” for integers, and last the place where it need to put the scanned input. For more details on sscanf please refer : sscanf()
Now, let’s put this all together and see if it works. In following code, I am scanning a list of numbers from STDIN and storing them in an array and then printing that array. If you have notice, in code we have something called as n which is also read with sscanf, it helps us in finding the pointer in the buffer from which we need to read next integer from, else we will always be reading the first integer only.
Now look at when there are multiple lines are given as input from the STDIN like below are the edges of a particular graph, from which we need to store graph representation:
2 3
4 5
6 8
Reading of this kind of input is very similar to what we saw above. Only thing is now we need to put fgets() in while loop till we have input to read from line.
Notice one thing that now, we are checking return value of sscanf() against two because now we are explicitly reading two integers from the line, whereas in previous case we were reading one integer at a time.
This is how one can read from standard input and please let me know if you could not follow something or want to add to it.

Clone linked list with arbit pointer

Problem statement

Given a linked list with next and arbitrary pointer, clone the given linked list.

Given linked list will be something like below figure.

Linked list with arbitrary pointer

Analysis

This problem can be solved using extra N spaces where we store the next and arbitrary pointer mapping of the given linked list. However, challenge is to do it in O(1) space complexity.

Idea here is to add a node between each two nodes of original list which will eventually become node in clone linked list. For example, in above list, a new node will be added between 1 and 2 with value 1, between 2 and 3 with value as 2 and so on.
After this step linked list looks like

After adding nodes in between

Code for  above step
Now we can access the clone node with
and arbitrary pointer of clone node can be set as

Code for above step
Last step will be to segregate two linked list.
Code for above step

Code

Complexity Analysis

Time complexity of above code is O(N) and space complexity is O(1).

Re-arrange array elements in-place.

Problem statement

Given an array in A = [a1,a2,a3,….an, b1, b2,b3,…bn,c1,c2,c3,…..cn] form
Rearrange above array in below manner: A = [a1,b1,a2,b3,a3,b3,……an,bn]
For example,
If input A =[1,2,3,4,5,6,7,8,9,10],
Output should A =[1,6,2,7,3,8,4,9,5,10]

Analysis

Above problem can be solved easily using extra space. However, let’s optimize the space requirement. Algorithm is based on rotation of  array.
We will process each group from right to left. Put last element of group at the start of the array and rotate the array till that point., repeat till all elements are not processed.
Algorithm
  1. Take each group one by one.
  2. Take the last element of the current group and save it.
  3. Rotate the given array from 0 to index of last element of current group.
  4. Put last element saved in step 2 at start of the array.
  5. Repeat above steps till all elements are processed.

Let’s take an example
A = [1,2,3,,x,y,z, 4,5,6]
There are three groups [1,2,3], [x,y,z] and [4,5,6]
Now we will take last element of group [4,5,6] i.e 6
And we will right rotate the entire array till position of 6. So A becomes
A = [6,1,2,3,x,y,z,4,5]
Now we take last element of group [x,y,z] i.e. z
Now right rotate array till position of z. So array becomes
A = [z,6,1,2,3,x,y,4,5]
Similarly for group [1,2,3] i.e 3
Array becomes.
A= [3,z,6,1,2,x,y,4,5]
Now last element of group [4,5,6] is 5 as we have considered 6 earlier. After doing processing which we did for 6, array will be
A = [5,3,z,6,1,2,x,y,4]
After processing y.
A = [y,5,3,z,6,1,2,x,4]
After processing 2
A = [2,y,5,3,z,6,1,x,4]
In similar fashion we will process remaining 4,x, and 1.
Output will be A = [1,x,4,2,y,5,3,z,6]

Code

Complexity Analysis

Complexity of code will be O(N^2) and space complexity is O(1)

Strings : Find if any anagram of string is palindrome.

Problem statement

Given a string, find out if any anagram of given string is palindrome.
For example, “AABBC” has an anagram “ABCBA” which is palindrome.

Analysis

Brute force solution will be to find all anagrams of string and then check each one if that is palindrome. For N character long string, we will have n! anagrams and checking each one of that for palindrome will be computation intensive task, so not a good solution.
What is required for a string to be palindrome string?
We need first half of the string to contain same characters as second half. In case of odd length string we can safely ignore the middle character.
In other terms, each character should occur even number of time except one which is middle character which may occur odd number of times.
Best way to check if character occurs even number of times is to increment to count when it is zero and decrement when it is 1.If at the end we have count corresponding to that character as zero, that means we have even number of occurrence of this character, if not then we have odd number of occurrence.
Extending the same idea from previous post: we will be using a hash table and increment- decrement corresponding count of character in hash.
At the end we will sum the array and if sum of array is greater than 1, then we cannot have any anagram which will be palindrome else at least anagram of string will be palindrome.

Code

Complexity Analysis

Complexity of above code is O(N) with constant amount of memory required.

Strings : Find if two strings are anagrams

Check if strings are anagram

Given two strings, find out if they are anagrams of each other. Strings are said to be anagrams if they have same characters but in different order.For example, abcd and dcba are anagrams.

Analysis

It’s actually a simple problem, we need to just check if both the strings contain same characters. 
First approach will be to sort both the string and compare if they are same. While sorting all the characters will come in lexicographical order and string with same characters will have same order of characters.
Best we can achieve using sort is O(N log N).
Can we do better? We have to keep track of character in one string in another. So if we find what all characters (count of each character) are there in first string, we can easily do that using hash table and compare with characters (count again) present in second string. If both the hash tables are equal, we can say that strings are anagrams.
Here we are using two hash tables. We can do away with on hash table. How?
While traversing the first string we will increment the count against character. While traversing the second string, we will decrement the count against character in the same hash table. If at any time if count of any character goes less than zero, it means, character is present in second string but not in first, so we can say strings are not anagrams.
If we finish complete scanning of second string, we return true.
To avoid check the hash table at the end for non zero count, we can first have a check on length of two strings, if lengths are not equal, straightforwardly say non anagrams. (Think how it avoids check of non zero count at the end :))

Code to find if strings are anagrams

Complexity Analysis

Complexity of algorithm to identify to strings as anagrams is O(N) where N is length of string.

Interrupts and bottom halves Part 2

In the last post in interrupts we discussed some of the design issued to be considered while writing an interrupt service routine. Two main things which came up were: Interrupt Service Routine should be as quick as possible and perform some reasonable amount of work. These two requirement are mutually contradicting. How do we achieve these two goals?

Bottom Halves

To do so, we divide the ISR into two parts called as halves. First one is top half which does the minimum required functions of for handling given interrupt and schedules the other half which is called as bottom half which does the bulk of the task later.

Bottom halves are required because as we know when ISR executes, it disables all other interrupts on running processor and same interrupt on all processors. To increase the response time and throughput of the system, we need to finish ISR as soon as possible.
Let’s take an example : A packet arrives at network card. Card has to generate an interrupt to kernel saying it has a packet. Now above dichotomy comes into picture. If kernel starts to process the whole packet in the ISR, network card will not be able to receive any packet till ISR if finish.
So in top of half of the ISR, kernel just acknowledges the reception of packet, copies it in main memory and network is again ready for the new packet.
Rest of the processing is done by the bottom half at later point of time.
There are some considerations we should keep in mind while delegating work to bottom half:
If work is time sensitive, hardware specific or needs all other interrupts to be disable while being done, do it in interrupts top half, rest all can be delegated to bottom half.
Bottom halves are implemented using: Tasklets, softirqs or works queues.
Now let us look into some of the very basic questions asked about interrupts.

Difference between exception, trap and interrupt

Traps

Trap is usually called as software interrupts also. It is specifically added by the programmer using instruction to transfer control to a given handler. Best example is INT instruction. As it is added explicitly by the programmer, we always know when trap will occur. Trap and simple function call are same except that trap stores registers on stack and we need to do IRET in order to return from it.

Exceptions

Exceptions occur when program as encounter a conditions which is not as per the expectation. Exceptions are usually called as automatically generated traps, however there is no specific instruction associated with exceptions. Common causes of exceptions are divide by zero, executing illegal op-code or illegal memory access, break point exceptions, overflow exception etc. As soon as any condition above is encountered, current execution is suspended and control passes to exception handler. Exception handler decides what to do like aborting the process or restarting it etc.

Interrupts

Interrupts do not have anything to do with currently executing instruction. These are external to the process currently being executed. These are generated by like receiving a packet on network card, pressing a key on keyboard, serial ports, parallel ports, timers etc. CPU after executing the current instruction, passed control to Interrupt handler and once interrupt handler finishes, control returns back to the next instruction of the program which was interrupted.