Blog

Strings : Toeknize a string separated by delimiter

Continuing the previous post, let’s look at the second problem.

Problem statement

Find all tokens in a string which are separated by given delimiter.

Analysis

We have to traverse the string and for each character, check if that character is present in delimiter string. If it is, then it is end of the token started after previous encounter of the delimiter. Here forward we should scan all characters till the time we first encounter a character which is not a part of given delimiter string, that would be start of the next token.

Let’s look at it step by step.

Step 1 : Assume we have string as s and delimiter string as delim.
Search in s the first character which is not present in delim.
If there is no such byte, we are done, return NULL.
If there is such byte, then that would be start of our first token.

Step 2: Scan through the found token.
From the character found in step 1, scan through s till we again encounter a character present in delim.
If there is no such character, we are done, we have only one token and return the start position of that token.

If we have such character, that would be end of the token.

Great we have found one token, How about next one? 

For next token to be generated, we need to keep track where to start looking from in the string as we would have scanned a part of it in the previous tokens. So we keep track of the pointer where to start looking from.

Step 3 : Once we have found the end of token in step 2, again scan out all subsequent characters which are part of delim. Take the index of first non-delimiter character. This would be the starting point of our next token search.

Implementation note : To distinguish between whether it is first call to the function or subsequent call, we pass NULL pointer to the source string parameter indicating that it is subsequent call and not initial call.

Similar approach can be used to remove all characters which are present in a string from another string.

Code

Test cases

1. String and delimiter with one characters
S = “aaab_dddcc”
delim = “_”

2. String and delimiter with multiple characters
S = “aaab_dd?dcc”
delim = “_?”

3. Empty string
S = “”
delim = “_”

4. Empty delimiter
S = “aaab_dddcc”
delim = “”

5. String starting with delimiters
S = ___aaaaabbb
s = “_”

6. String ending with delimiters
S =”aaaa___”
s = “_”

7. String with no delimiter character
S = “aaaaaaaa”
s = “_”

8. String with all character as delimiter characters
S =”________”
s =”_”

Complexity analysis

Complexity of above code is O(N * M), where N is length of string and M is length of delimiter string.

Strings : Search functions

Introduction : String search functions

Many a times we need to find something or the other in a given string like find all words punctuated by given delimiter or find the location of a given sub string in bigger string etc. Under this topic we will discuss two problems 

1. Finding position of sub string in a given string.  (In this post)
2. Finding all sub strings in a given string which are separated by delimiter. (Next post)

Problem 1 : Find substring in a given string

Given a searched string S, and a substring s, check if s is present in S and if yes return the position in searched string.

Analysis

This is classic problem of traversing two string simultaneously and keeping track of characters in each.

One of the well known algorithm for this is needle and haystack algorithm. Steps of the algorithm are as follows.

1. Take begin of substring to be search.
2. Starting from begin of larger string S, do following
    2.a For each position pos in S, check if substring s can start from that position.
    2.b If the substring s can start, keep traversing both strings till either we find mismatch          or the substring is traversed completely.
    2.c. If substring is traversed completely, return the position where we started  i.e pos.
    2.d  If mismatch occurs, try matching from the next position.
    2.e  Repeat step 2.a to 2.d till we have traversed whole bigger string S.

Code

char * substr(char * haystack, char *needle){


  char * substring  = needle;
  if(needle == NULL)
      return NULL;
  
  if(*needle ==”) return haystack;
  
  if(haystack == NULL) return NULL;

  while(*haystack != ” ){
      char * pos = haystack;
 /* While substring is not terminated and characters in search string and substring are equal traverse both strings. */
     while(*needle !=” && *needle++ == *pos++);
                
 /* If we have reached end of the substring,return the pointer in search string where we started the search*/
     if(*needle == ” ) return haystack;

 /* else reset the substring pointer to start and increase the searched string by one position  */
     needle =  substring;
     haystack++;
  }
 /* If we reach end of the searched string, return NULL */
  if(*haystack == ”) return NULL;
}

There is one optimization where we can stopping matching substring once we know that the number of characters left in search string to match are less than the characters in substring.

Test cases

1. When substring is present

S = “aaabcbcd”
s = “bcbcd”

2. When substring is not present
S = “aaacbcd” 
s = “bcbcd”

3. Substring provided is empty
S = “aaacbcd” 
s =””

4. Substring pointer is NULL
S = “aaacbcd” 
s = NULL

5. Searched string pointer is NULL
S = NULL
s = “aaa”

6. Performance test, where we have a huge searched string and a small substring and it matches at the end.

Complexity analysis

Complexity of above code is O(N^2).


There are other algorithms like KMP pattern matching algorithms which do this is linear time, we would discuss that too in separate post.

String manipulation

Introduction : String manipulation

String is see is collection of character which is terminated with special character ”.

So whenever we want to allocate or reserve space for a string, we need to allocate one space extra for last NULL character.

char string[10] declares and defines a string which has 0 characters including NULL character.

Lets see some of the problems which involve traversal of string.

Problem 1 : Reverse a given string

Input : “abcd”

Output : “dcba”

It’s a very simple problem which explains the traversal of a string.
Idea is to have two pointers, one at the start of the string and other at the end. As we move for start pointer forward and end pointer backward, we swap characters at those position. As these two pointers cross each other, we stop.

void reverse(char s[]){
        int i=0, j;
        int end =  strlen(s);

     /Take care that we go only till end-1 as array is indexed from 0 */   
        for(i=0, j=end-1; i<j; i++, j–){
                char temp = s[i];
                s[i] = s[j];
                s[j] = temp;
        }

}

Problem 2 : Check if string is palindrome or not

Again just a traversal of string, one from the start and other from the end. As we move forward and backward, we need to check if characters at these positions are equal. As soon as we find one mismatch we return false. Continue till both indexes cross each other.

int palindrome(char s[]){
        int i=0, j;
        int end =  strlen(s);

        for(i=0, j=end-1; i<j; i++, j–){
                if(s[i] != s[j])
                        return 0;
        }
        return 1;

}

In palindrome problem always have two test cases :
One having string with odd length and other having string with even length.

Problem 3 : Copy on string to another

No big deal, traverse both strings together and copy ith character in source to ith index in destination.

There are couple of catches here.
First what if destination is smaller than source?
What if destination starts overlaps with source string?

Following code takes care of the first catch. Second can be taken care of by checking if dest base address is between source start and source end.
Usually we make source string as constant, so that second problem does not arise.

void copy(const char s[], char d[], int dest_size){
        int i=0, j;

        int len  = strlen(s);
        if(len > dest_size){
                printf(“String cannot be copied”);
        }
        for(i=0; s[i] != ”; i++){
                d[i] = s[i];
        }

        d[i] = ”;
}

Again take care of two things:
1. Always remember to terminate destination string with NULL character.
2. Always calculate the size of destination in calling function as if array is passed as parameter in a function, it will be treated as a pointer only and size will be always size of the pointer and not actual size of array.

In next post we would some other problems involving strings.

Fun with bits Part -3

Bitwise operation

Continuing from last two posts, today we will discuss problems which require slightly tricky bitwise operations to arrive at solutions.

Problem 1 :  Find two missing numbers in an array

We have seen solution of one missing element in this post. Can we somehow use that approach to arrive on solution?


Let’s take an example.

A = {1,4,5,6} Range is 1 to 6 and missing numbers here are 2 and 3.

Let’s follow steps we did for one missing number.


Step 1 : XOR all numbers 1 to 6
X =0001 XOR 0010 XOR 0011 XOR 0100 XOR 0101 XOR 0110 =  0111

Step 2 : XOR all numbers in set

Y = 0001 XOR 0100 XOR 0101 XOR 0110  =  0110

Step 3 XOR X and Y

Result  =  0111 XOR 0110 = 0001 = 1.

Find the LSB which is set in result. Using that information we know that one of the missing number should has that bit as set, in this case it should be bit at 0th position from right (0001).

So we can segregate numbers which have that particular bit set and those which don’t have that bit set.
Once we get that info, we can separately XOR them again with N numbers according to the condition of given bit being set.

Step 4 : Get the right most bit in result which is set.


Step 5 : Segregate number in two groups, one which have bit found in step 4 set and other which has numbers which don’t have that bit set.


In our given example C = {1,5} (with 0th bit is set) D = {4,6} (which don’t have 0th bit set)


Step 6 : XOR C and D separately.


X = 0001 XOR 0101  = 0100  Y = 0100 XOR 0110 = 0010


Step 7: Segregate all numbers ranging from 1 to n similar to step 5.


E = {1,3,5} F = {2,4,6}


Step 8 : XOR E and F separately.


W = 0001 XOR 0011 XOR 0101  = 0111 Z = 0010 XOR 0100 XOR 0110 = 0000


Step 9 XOR X and W will give us first number


Number 1  = X XOR W  = 0100 XOR 0111 = 0011 = 3


XOR Y and Z will give us second number

Number 2 = Y XOR Z = 0010 XOR 0000 = 0010 = 2

Finally we get our missing numbers.


Let’s test if it works for {1,2,4,6}


Result here will be 0001 XOR 0111 = 0110


Right most bit set is 1st bit from left.


C = {2,6} D = {1,4}

X = 0100  Y = 0101

E = {2,3,6} F ={1,4,5}

W = 0111 Z = 0000

First number =  X XOR W  = 0100 XOR 0111 = 0011 =3

Second number = Y XOR Z = 0101 XOR 0000 = 0101 = 5

Hence we can be sure that this works.

Code

Complexity analysis

Complexity of above code is O(N).


Fun with bits : Find rightmost bit set in given number

Bitwise operations

In previous post we discussed basics on bitwise operations.
In this post we would take some classic interview questions which can be easily solved if we apply some bit manipulations.

Problem 1 : Find the missing number 

Given a set of N numbers ranging from 1 to N, one number is missing, find the missing number.
Numbers are non-sorted order.

Analysis

We can easily find the element by having a hash key being numbers in set and increasing the count of the index whenever we encounter number in given set.
This approach required O(N) extra space. We want to avoid that extra space usage. 
Let’s look at XOR operation first.

 0 XOR 0 = 0
 0 XOR 1  = 1
 1 XOR 0  = 1
 1 XOR 1  = 0
Given above rules, we can derive that A XOR A = 0 because this will always make number of ones as even. For example,
9 XOR 9 = 1001 XOR 1001 = 0000.

Do we get some hint? 
We know that range of numbers is 1 to N, if XOR all numbers from 1 to N let’s call result as X. and then XOR all numbers which are actually present in set, call it Y and then if we XOR both X and Y, we get the missing number as all the numbers from 1 to N which are present in set will cancel each other.
Example,
Range is 1 to 5
Set as  {1,3,4,5} = {0001, 0011, 0100, 0101}

Step 1 : XOR all numbers 1 to 5
X =0001 XOR 0010 XOR 0011 XOR 0100 XOR 0101 =  0001

Step 2 : XOR all numbers in set
Y = 0001 XOR 0011 XOR 0100 XOR 0101 =  0011

Step 3 XOR X and Y
Result  =  0001 XOR 0011 = 0010 = 2 which is over missing element.

Code

@a as input set of numbers
@n as range of elements in input

int missing_elem(int a[], int n){
        int X =0, Y=0;
        int i, N;
/* XOR all elements in range 1 to n */
        for(i=1; i<=n; i++){
                X = X ^ i;
        }
/* XOR all elements in input set */
        for(i=0; i<n-1; i++){
                Y = Y ^ a[i];
        }
/* XOR X and Y will give us missing number.*/
        return X ^ Y;
}

Problem 2  : Find duplicate element

Given a set of numbers range from 1 to N, one number is missing and one number is duplicate. 
Find the missing and duplicate number.

Let’s work on an example
A  = {1,2,3,3,4,5} Range as 5

Step 1 : XOR all numbers 1 to 5
X =0001 XOR 0010 XOR 0011 XOR 0100 XOR 0101 =  0001

Step 2 : XOR all numbers in set

Y = 0001 XOR 0010 XOR 0011 XOR 0011 XOR 0100 XOR 0101 =  0010

Step 3 XOR X and Y as Z

Result  =  0001 XOR 0010 = 0011
Same logic mentioned above goes for this problem too.

One more problem which uses similar logic is “Find a number which occurs odd number of times in given input set”

Problem 3 : Find the position of right most set bit

Example : Let be the number be 18 = 00010010
Now if reset all bits except the LSB bit which is set and then take log (base 2), we can get the position of LSB which is set.
We can do that by 
x & !(x-1)

x-1 = 00010001
!(x-1) = 11101110

x & ! (x-1)  = 00010010 & 11101110 = 0000010 =2

Log2(2)  = 1, that is the position of LSB set.

Hence our return value becomes
log2(x &!(x-1))

In next post we would discuss couple of more problems on bitwise operations like finding two duplicate elements in a given input set etc. 

Fun with bits Part -1

Bitwise operations

Everything in computer is eventually represented as bits. A byte has eight bits, word has two bytes or 16 bits, and a long as two words or 32 bits. (True for 32 bit system).
There are only two states possible for each bit. So range of values represented by any collection of bits is 0 to 2^N -1 where N is number of bits in collection. If we take into account the sign bit, the range changes to -2^N to 2^N-1.

For example range of
Char  is 0 to 255 (2^8-1)
Integer is 0 to  4294969275 (2^32-1)

There are many operations which are bit specific and many other which can be efficient performed using bit manipulation. In this post we are going to see some problems which can be solved using bit operations.

Some basic operations on bits

1. OR
Rule : If any one bit is set, result is true or set

2. AND
Rule : If all bits are set, then only result is set.

3. NOT
Rule: Switch the bit, i.e. if unset, result is true and vice-a-versa

4. XOR
Rule If odd number of bits are set, then only result is true.

We will see Left rotation and right rotation operation on bits as we work on problems.

Problem 1 : Find sign of a number

How do we identify sign of an integer, yes, it’s the first bit in the number. So solution of this problem is to just check the first bit of the given number and we can easily do that by ANDing Most significant bit with 1. Catch here is we need to we don’t need to use mask.

Hence solution is

sign = (value >> (sizeof(int) * CHAR_BIT – 1));

If number is negative, then it MSB of the number will be copied on all bits as we shift right. All 1s will give us -1. If the number is positive, MSB is 0 and hence the overall number after shifting will be zero.
Hence this implementation return 0 if number is  positive and -1 if number is negative.
This is architecture specific code.

Problem 2 : Check if number is power of 2

Let’s check some of numbers which are power of 2
2  = 0010
4 =  0100
8 =  1000
16 = 0001000

So is there any pattern? Yes there is. If a number is power of two, it has only one bit set.
How do we find that only one bit is set?

Let check numbers which are one less than power of 2
2-1 =1 = 0001
4-1 =3 = 0011
8-1 =7 = 0111
16-1 =15 =01111

Do we see something here? yes that is all the bits after the bit which is set in number which is power of 2 are set.
So, v & v-1 will give us 0 is number is power of two.
2 & 1 =  0010 & 0001 = 0000
4 & 3 =  0100 & 0011 = 0000
8 & 7 = 1000 & 0111 = 0000
9 & 8 = 1001 & 1000 = 1000

Hence we have to just return value & value-1.
If returned value is zero, then number is power of 2. If non-zero, then number is not power of zero.

However if input is zero, then we incorrectly return it as power of 2. Hence the final code should be

value && ! (value & value-1).

Let’s see what happens when value is zero.

Expression becomes 0 && ! (0 & -1) = 0 && 1 =0. In this implementation, we return non-zero if number is power of 2 else 0.

Problem 3 : Find number of bits set.

First solution is to scan through all bits of number and count which are set. This requires N operations where N is number of bits in number.

We can do better than that.

10 = 1010 9 = 1001 = 10 & 9 = 1000
11 = 1011 10 = 1010 = 1010
12 = 1100 11 = 1011 = 1000
14 = 1110 13 = 1101 = 1100

We can see from above table that, when we AND a number with number -1, it clears the least significant set bit.

So every time we and N and N-1, we clear LSB, one bit at a time. We can continue to do so till our number turns to zero.

for(i=0; v!=0; i++)
     v & = v-1;

This code will require only M operations where M is number of bits set in number.

These are three basic problems involving bit wise operation. We would discuss couple of problems which use XOR operations on finding duplicate element or missing element in a given input array.

Loop in linked list

Loop in linked list

Detect loop in linked list is very common linked list question which is asked in telephonic interview rounds. Problem statement is :

Given singly linked list, check if there is loop in linked list and if yes, find start node or point of the loop.

For example, if for linked list shown below, there is a loop in linked list and it start at node 8.

loop in linked list
Loop in linked list, starting node is 8

Loop in linked list : thoughts

What is difference between a normal singly linked list and a linked list with loop? If we traverse normal linked list, we are destined to encounter a node which is null, which in effect is the last node of normal linked list. However, in a linked list with a loop, we will never reach null and circle around in the loop.

Can we use this property to find if there is a loop or not in a linked list? If we move two pointers with different speeds,, the fast pointer, which moves two nodes at a time will reach to end of linked list before slow pointer, which moves one node at a time, in a normal list (without a loop). However, in list with loop, fast pointer will go around in circles and eventually, slow pointer will catch up with it. So, if ever, before fast pointer reaches null, slow pointer catches up with it, there is definitely a loop in linked list. This method of using fast and slow pointers to traverse linked list at different speeds is commonly known as hare and tortoise method and used in solving many problems on linked list like find middle of linked list, palindrome linked list etc.

Let’s take an example and see what we are thinking is correct. Below is a linked list with a loop, let’s see if slow and faster pointer ever meet.

We initialize slow as head(4) and fast as next of head(3).  fast moves two steps and hence reaches node 8, where as slow reaches at 3.

Since, fast is not null yet, we jump again, this time fast points to 7 and slow points to 5.

Again, fast is still not null, so we move again, fast now is at 8 and so is slow.

This is where we can safely say that there is a loop linked list.

    public boolean isLoop(){
        /* 
            Base condition if there is no nodes,
            return false
         */
        if(this.head == null){
            return false;
        }
        
        Node slow = this.head;
        Node fast = slow.getNext(); // slow cannot be null here
        
        while(fast != null && fast != slow){
            /*
            Move faster ponter two nodes at a time.
             */
            fast = fast.getNext();
            if(fast == null) return false;
            
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) { slow = slow.getNext(); }
        }
        
        return fast == slow;
    }

There is common mistake which happens is to check content of fast and slow pointers to see if there are at the same node. This will fail when there are duplicate values in different nodes. To avoid wrongly predicting nodes being equal when actually content is equal, compare node addresses and not content.

Start of loop in linked list

This problem is interesting and require a bit of thinking. Can we find number of nodes in loop?
Starting from node fast and slow met at, move fast two nodes at a time and slow one node at a time, they will again meet at the same node. Keep count of how many nodes slow pointer moved, it will give length of loop. You can try with different length loops and see that it is actually true.

private int getNumNodesInLoop(Node slow){

        Node fast = slow;
        int count = 0;

        do{
            /*
            Move faster pointer two nodes at a time.
            As we are sure that there is loop in LL at this
            point, fast cannot be null. That's why it is
            removed from the while loop condition too.
             */
            fast = fast.getNext();
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) {
                slow = slow.getNext();
                count++;
            }
        }while(fast != slow);

        return count;
    }

Now, we have number of nodes in loop, let’s say k. How can we find starting node of loop. We take two pointers again, fast and slow, fast is k nodes ahead of slow which is at head of list. Why? Hypothesis is that if we move them with same speed, when slow reaches start of loop, fast would have finished traversing k loop nodes and will also be at the start of loop. So, with fast ahead of slow by k nodes, when both meet, that node should be start of loop in linked list.

Start of loop in linked list implementation

package com.company;

/**
 * Created by sangar on 14.10.18.
 */
public class LinkedList<T> {
    private Node<T> head;

    public LinkedList(){
        head = null;
    }

    public void insert(T data){
        //If this is the first node to insert
        if(this.head == null){
            this.head = new Node<>(data);
        }
        else{
            Node current = this.head;
            /* Defensive programming, just in case current is null
            * As we check null condition for head earlier,
			it should not be null in this while loop ever though
            * */
            while(current != null && current.getNext() != null){
                current = current.getNext();
            }
            //We are at the last node.
            current.setNext(new Node(data));
        }
    }

    public Node getLastNode(){

        if(this.head == null){
            return null;
        }
        else{
            Node current = this.head;

            while(current != null && current.getNext() != null){
                current = current.getNext();
            }
            return current;
        }
    }

    public Node<T> get(T data){
        /*
            Base condition if there is no nodes,
            return null
         */
        if(this.head == null){
            return null;
        }
        else{
            Node current = this.head;
            /* Defensive programming, just in case current is null
            * As we check null condition for head earlier, it
			should not be null in this while loop ever though
            * */
            while(current != null && current.getData() != data){
                current = current.getNext();
            }

            return current;
        }
    }

    /* As we need slow pointer to get number
    of nodes again, we will return slow pointer
    rather than boolean
     */
    private Node isLoop(){
        /*
            Base condition if there is no nodes,
            return false
         */
        if(this.head == null){
            return null;
        }

        Node slow = this.head;
        Node fast = slow.getNext(); // slow cannot be null here

        while(fast != null && fast != slow){
            /*
            Move faster pointer two nodes at a time.
             */
            fast = fast.getNext();
            if(fast == null) return null;

            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) { slow = slow.getNext(); }
        }

        return fast == slow ? slow : null;
    }

    private int getNumNodesInLoop(Node slow){

        Node fast = slow;
        int count = 0;

        do{
            /*
            Move faster pointer two nodes at a time.
            As we are sure that there is loop in LL at this
            point, fast cannot be null. That's why it is
            removed from the while loop condition too.
             */
            fast = fast.getNext();
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) {
                slow = slow.getNext();
                count++;
            }
        }while(fast != slow);

        return count;
    }

    public Node getStartNodeLoop(){

        Node slow = isLoop();

        /* If slow is not null, it means there is a loop */
        if(slow != null){
            int k = getNumNodesInLoop(slow);

            slow = this.head;

            //Give fast head start of k nodes.
            Node fast = slow;
            while(k-- > 0 && fast != null){
                fast = fast.getNext();
            }

            while(fast != slow){
                slow = slow.getNext();
                fast = fast.getNext();
            }
        }
        return slow;
    }
}

Test cases for finding loop in linked list implementation

package test;

import com.company.LinkedList;
import com.company.Node;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class LoopInLinkedListTest {

    LinkedList<Integer> tester = new LinkedList<>();
    @Test
    public void loopPresentTest() {

        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(7);
        tester.insert(10);

        //Created a loop
        Node loopNode = tester.get(8);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }

    @Test
    public void loopAbsentTest() {

        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(7);
        tester.insert(10);

        assertEquals(null, tester.getStartNodeLoop());
    }

    @Test
    public void EmptyLinkedListTest() {
        assertEquals(null, tester.getStartNodeLoop());
    }

    @Test
    public void OneNodeLoopTest() {
        tester.insert(4);

        //Created a loop
        Node loopNode = tester.get(4);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }

    @Test
    public void loopBackToHeadTest() {
        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(5);
        tester.insert(7);


        //Created a loop
        Node loopNode = tester.get(4);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }
}

Complexity to find a loop in linked list is O(n) as we have to scan all node of linked list at least once.

Please share if there is something wrong or missing.

Reference : cslibrary.stanford.edu/103/LinkedListBasics.pdf

Programming Interview Question : Build binary search tree given inorder and preorder traversal

Build the binary search tree from inorder and preorder traversals.


For example,
Inorder traversal is {10, 12, 20, 30, 37, 40, 45}
Preorder traversal is {30, 20, 10, 12, 40, 37, 45}

The resultant binary search tree should be


Analysis

Basic definition and problems related to binary search tree can be read at this post.

As we know that inorder traversal of binary search tree list left child first, then root and right child last. Preorder traversal of BST traverses root first, left node and at last right node.
Can we use these properties?
First step, find the root of the tree. Going by the property of preorder traversal, first element will be the root of the tree.  So, we have root with us.
Search for the element in inorder traversal. According to inorder traversal, all elements on the left side of the root element will form left sub tree, and all on right side will form right sub tree.
Cool, we have now root node of BST, left sub tree and right sub tree.
Now we need to find the root of left sub tree and right sub tree and add them to the root.
Again, after root, next element will be root of either left sub tree or right sub tree. We can do this by looking into the two sub parts of inorder traversal.
From above discussion, we can see that at every step, we divide the inorder traversal in two parts and use preorder traversal to search for root of sub trees.

Algorithm to build Binary Search Tree

  1. Take first element in preorder traversal and make root.
  2. Search for the element in step 1 in inorder traversal.
  3. Take left part of inorder traversal and repeat step 1 and 2 with next element in preorder traversal as root.
  4. Take right part of inorder traversal and repeat step 1 and 2 with next element in preorder traversal as root.
* This algorithm will automatically take care when there is no element in left or right sub tree.

Code

Above code executes as follows
Root : 30
Left sub tree :10, 12, 20 
Right sub tree :37, 40, 45

Root : 20
Left sub tree :10, 12 
Right sub tree :

Root : 10
Left sub tree :
Right sub tree :12

Root : 40
Left sub tree : 37 
Right sub tree : 45 


Final output will be
10, 12, 20, 30, 37, 40, 45

Test cases

1. Normal tree
Inorder traversal  {10, 12, 20, 30, 37, 40, 45}
Preorder traversal {30, 20, 10, 12, 40, 37, 45}

2. Empty tree
Inorder traversal  :{}
Preorder traversal :{}

3. When inorder or preorder does not form BST
Fail

4. When tree has duplicate elements

Complexity Analysis

Complexity of above algorithm is O(N*N) as for every element in preorder, we might need to traverse the whole inorder array if binary search tree is completely skewed. 

References

Merge two sorted linked lists

Merge two sorted linked lists

Problem statement is simple : Merge two sorted linked lists, without using extra space. To refer to the basics of linked list, please follow the post : Linked list data structure. This problem is commonly asked in telephonic round of Amazon and Microsoft. Let’s take an example and understand what is required as solution. Given two linked lists as following,

merge two sorted linked lists
Two sorted linked lists

Result should be like this:

merge two sorted linked list
Resultant linked list.

Merge two sorted linked lists : Thoughts

Consider following two steps to merge sorted linked lists. First, figure out which node should be head of result list. Compare head nodes of two give lists, which ever is smaller, that should be the head of result list.

Second, compare two nodes, one from each list and decide which should go next in result linked list.  Advance the pointer to next node of the node which is added to result list.

As no new node is allocated during this merge, we have to make sure that all the references are maintained when nodes are added to merged linked list.

merge two sorted linked list
Two sorted list to be merged

We can start with one list as merge list and add nodes from second list at appropriate place in that list. Let’s say L1 is our merged list and we always compare node on L2 to see if it should be placed in L1 at current position. L1 grows as more nodes are sorted in merge list.

We compare first two nodes L1 and L2, and decide that node(2) has to go in merged list as head. If it was head of L2, we would have swapped L1 and L2 heads and still L1 will be head of merged list. Why? Because we want that L1 always points to last node in merged list and L1 to represent sorted merged list till this point and L2 switches between two input lists.

As L1 always points to the last node of merged linked list, next node to compare should be L1.next i.e node(4) and L2 i.e node(3).

As L1 follows the merged linked list, we will move L1.next to point node(3), however doing it directly will lead to lose of entire linked list following it. So we do it in four steps : store L1 next as temp; link L2 to L1.next; L2 points to temp and then move L1 to L1.next

Node temp = L1.next;
L1.next = L2;
L2 = temp;
L1 = L1.next
merge two sorted linked lists

Next nodes to be compared are node(5), which is L1.next and node(5) which is L2.

Comparing node 4 and 5 to add in sorted merge list

Of course node(4) has to be added to merged linked list, what should we do? First save L1.next in temp, temp now points to node(5). Second, point L1.next to L2, point L2 to temp, and at last, L1 moves to L1.next. State of two sorted linked lists looks as follows.

merge two sorted linked lists

By this time you must have noticed that L1 and L2 do not point to the one list all the time, L1 always points to the last node of merged list and L2 points to first node of separated list which needs to be merged.

Now, L1.next which is node(7) and L2 which is node(5) will be compared.

node(5) is to be added in merged sorted list. Again same set of steps. L1.next stored as temp, L1.next points to L2 i.e. node(5) and then L2 points to temp i.e. node(7)

merge two sorted linked lists

Again, node(9) which is L1.next will be compared to L2 i.e node(7). L1.next should point to L2. Final state will be as follows

At this point, L1.next i.e node(8) is less than L2, this is simple case, where we just move L1 to L1.next and L2 remains as is.

merge two sorted linked lists

Next two nodes follow the same pattern and added to merged sorted linked list.

At this point, special condition occurs which is L1.next is null. In this case, point L1.next to L2 and two linked lists are merged.

Two sorted linked lists are merged into a sorted list

Merge two sorted linked lists : Implementation

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int data;
    struct node *next;
} Node;
 
Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}

void printList(Node * head){
    while(head){
        printf("%d->" , head->data );
        head = head->next;
    }

    printf("NULL");
    printf("\n");
}
Node * MergeLists(Node *list1, Node *list2) {
  if (!list1) return list2;
  if (!list2) return list1;

  Node *head;
	//Chosing head of merged list
  if (list1->data < list2->data) {
    head = list1;
  } else {
    head = list2;
    list2 = list1;
    list1 = head;
  }
	
  while(list1->next && list2) {
    if (list1->next->data > list2->data) {
	//Step 1. Save the next pointer
      Node *tmp = list1->next;
	//Step 2. Change next pointer to point L2
      list1->next = list2;
	//Step 3. Move L2 to temp
      list2 = tmp;
    }
	//Step 4. Move L1 ahead
    list1 = list1->next;
  } 
  if (!list1->next) list1->next = list2;
  return head;
}
int main(){
        Node * L1 = NULL;
        Node * L2 = NULL;
        Node * result = NULL;
        int carry = 0 ;
        /* creating list 1 */
        push(&L1,7);
        push(&L1,6);
        push(&L1,4);
        push(&L1,3);
	
        /* creating list 2 */
        push(&L2,10);
        push(&L2,8);
        push(&L2,1);
 
        L1 = MergeLists(L1,L2); 
        printList(L1);
 
        return 0;
}

Complexity of this method to merge two sorted lists into one is O(n+m) where n and m are number of nodes in two sorted linked lists.

Recursive implementation to merge two sorted linked lists

#include<stdlib.h>
#include<stdio.h>
 
typedef struct node{
    int data;
    struct node *next;
} Node;
 
Node * mergeSort(Node *a, Node *b){
    Node *result = NULL;
    if(a ==  NULL)
        return b;
    else if(b == NULL)
        return a;

    /* For the first node, we would set the result to either a or b */
      if(a->data <= b->data){
         result = a;
        /* Result's next will point to smaller one in lists 
           starting at a->next  and b */
         result->next = mergeSort(a->next,b);
      }
      else {
        result = b;
       /*Result's next will point to smaller one in lists 
         starting at a and b->next */
        result->next = mergeSort(a,b->next);
      }
      return result;
}

Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}

void printList(Node * head){
    while(head){
        printf("%d->" , head->data );
        head = head->next;
    }

    printf("NULL");
    printf("\n");
}

/* Driver program to run above code */
int main(){
        Node * L1 = NULL;
        Node * L2 = NULL;
        Node * result = NULL;
        int carry = 0 ;
        /* creating list 1 */
        push(&L1,7);
        push(&L1,6);
        push(&L1,4);
        push(&L1,3);
        /* creating list 2 */
        push(&L2,10);
        push(&L2,8);
        push(&L2,1);
      
        L1 = mergeSort(L1,L2); 
        printList(L1);
        
        return 0;
}

Please share if there is something wrong or missing. If you want to take personalized coaching from our expert teachers, please signup for free demo class.

Add two numbers represented by linked lists

Add two numbers represented by linked lists

Given two linked lists, where linked list represents a big number and each node of linked list contains one digit of the number. Problem is to add two numbers represented by linked lists. The result should be stored in a third linked list. It should be noted that the head node contains the most significant digit of the numbers.

For example. let’s say we have been given two numbers: 12563 and 56743 and we have to add them. Two linked lists which will represent these numbers are as shown below.

add two numbers represented by linked lists
add two numbers represented by linked lists

Result of adding these two linked list would be:

result of adding two numbers represented by linked lists

Adding two linked lists: thoughts

This problem is very easy to solve if the order of the digits stored in the linked list is reversed. Look at the code given at leetcode.

 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       int carry =0;
 
        ListNode newHead = new ListNode(0);
        ListNode p1 = l1, p2 = l2, p3=newHead;
 
        while(p1 != null || p2 != null){
            if(p1 != null){
                carry += p1.val;
                p1 = p1.next;
            }
 
            if(p2 != null){
                carry += p2.val;
                p2 = p2.next;
            }
 
            p3.next = new ListNode(carry%10);
            p3 = p3.next;
            carry /= 10;
        }
 
        if(carry==1) 
            p3.next=new ListNode(1);
 
        return newHead.next;
    }

However, linked lists are not stored in reversed order and basic mathematics tells us that addition starts from the least significant digit. To access least significant digit of the numbers, we will visit the last nodes of both the lists and add them up, create a new node to store the result, take care of the “carry” if any.

Next, we go to the second to last node and do the same. Link the result node to the result node which was created when we added the last nodes.

This will continue  backwards till we reach head of one the list. Once, we reach head of a linked list, we just add all the nodes of the remaining list to the result.

It is clear that we go to the end of the lists and move back one node at a time. Actually, this is a reverse traversal of a linked list, which can easily be done with recursion, function call stack will automatically store previous nodes. However, we need to take into account the difference in the number of digits in two number and hence the difference in length of the two lists.

So before starting recursion, calculate the size difference and move the longer list pointer to appropriate place so that we reach the last node of both lists at the same time.

Another thing is to take care of is carry. If two digits add more than 10, forward the carry to the next node and add it to it. If most significant digit addition results in a carry, create an extra node to store carry.

Add two numbers represented by linked lists: implementation

#include<stdlib.h>
#include<stdio.h>

typedef struct node{
	int data;
	struct node *next;
} Node;


int length( Node * head ){
	int len = 0;
	Node * current  = head;
	while(current){
		len++;
		current = current->next;
	}
	return len;
}

Node * createNode(int value){
	
	Node * newNode = (Node *)malloc(sizeof(Node));
	newNode->data = value;
	newNode->next = NULL;
	
	return newNode;

}
/* Addition of a node to linked list */
void push(Node **head, int value){
	
	Node *newNode = createNode (value);
	if(!(*head) ){
		*head = newNode;
	}
	else{
		newNode->next = (*head);
		*head = newNode;
	}
}
/* This function is actually helper function 
	which does all house keeping like calculating 
	lengths of lists,calling recursive implementation,
	creating extra node for carry in MSD,
	and adding any remaining nodes left in longer list. */

/* result is pointer to pointer to the head of resulting node */ 
void addTwoNumbers(Node *L1, Node *L2, int *carry, Node  **result)
{
	int len1 = length( L1 );
	int len2 = length( L2 );
	int diff = 0;
	
	if(len1 < len2){
		Node * current = L1;
		L1 = L2;
		L2 = current;
    }
    diff = abs(len1-len2);
    Node * current = L1;
    
    while(diff--)
    	current = current->next;
    	
    /* Call the recursive implementation */
    addListRecursively(current, L2, carry, result);
    
    diff = abs(len1-len2);
    
    /* Add remaining nodes in longer list */
    addRemainingDigits(L1, carry, result, diff);
    
    if(*carry){
    	push(result, *carry);
    }
    return;
}
void addListRecursively(Node *L1, Node *L2, 
						int *carry, Node **result){

        int sum;
        if(!L1)
            return;

        addListRecursively(L1->next, L2->next, carry, result);

        /*We have reached the last node of both lists, add them */
        sum = L1->data + L2->data + (*carry);
       
        int value = sum%10;
		*carry = sum/10;
        push(result, value);
       
        return;
}
void addRemainingDigits(Node *L1, int *carry,
						Node **result, int diff){
	int sum =0;
	
	if(!L1 || !diff)
		return;
	addRemainingDigits(L1->next, carry, result, diff-1);
	
	sum = L1->data + (*carry);
	int value = sum%10;
	*carry = sum/10;
    
    push(result, value);
    
    return;
}

void printList( Node * head ){
	Node * current = head;
	while(current){
		printf("%d ->", current->data);
		current = current->next;
	}
	printf("NULL");
}
/* Driver program to run above code */
int main(){
        Node * L1 = NULL;
        Node * L2 = NULL;
        Node * result = NULL;
        int carry = 0 ;
        /* creating list 1 */
        push(&L1,3);
        push(&L1,4);
        push(&L1,6);
        push(&L1,7);
        /* creating list 2 */
        push(&L2,8);
        push(&L2,9);
        push(&L2,7);
      
        printList(L1);
        printf("\n");
        printList(L2);
        
        addTwoNumbers(L1,L2, &carry, &result);
        printf("\n");
        printList(result);
        return 0;
}

Since we traverse the number of nodes in the long list, the complexity of the algorithm would be O(n), where n is the number of nodes in the long list. Also, we need n extra nodes to store the result. Hence space complexity to add two numbers represented by linked lists is O(n).

Please share if there something wrong or missing. If you are preparing for an interview, please signup for free interview preparation kit.