Blog

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.

Backtracking : Eight Queens problem

Backtracking : Eight Queens problem

Given N x N chessboard, find a way to place N queens such that none of the queen can attack other. A queen can move along the column, row and diagonal of the chess board.

This is typical example of backtracking algorithm. What we need to do is that start with the first queen at the bottom left position and check all other queens can be place satisfying the constraints of the game. If at nay point we can not go forward, we try to replace the previous queen on next safe location and try again. If we are stuck at dead end, then we might need to replace more than one queen from their position so that we can move forward.
Let’s take this example, you have a 4 x 4 chessboard and you need to place four queens on it.
We place the queen at the left most bottom corner. Once we place queen there, our available options are for placing queen 2 are shown.

Looking at the figure below we can infer that there is no way possible to place Q3 and Q4 both with current configuration. Hence we back track and select another available position for Q2

Again we can’t place Q3 and Q4, and we try all other available positions for Q2, but none of those work .(exercise). Hence we change the position of the Q1.
After changing the position of Q1, we can reach the solution as shown in figure below, with couple of more backtracks of course.

Next step to figure out that if the queens is safe at a particular position. We need to check the column, row and diagonal, to make sure no other queen is placed in those places.

8 queens (1)

8 queens (2)

8 Queen solution implementation

#include &lt;stdio.h&gt;
#define N 8

int isColumnSafe(int chessBoard[N][N], int col){
	
	for(int i=0; i&lt;N; i++){
		if(chessBoard[i][col]) return 0;
	}
	return 1;
}

int isRowSafe(int chessBoard[N][N], int row){
	
	for(int i=0; i&lt;N; i++){
		if(chessBoard[row][i]) return 0;
	}
	return 1;
}

int isDiagonalSafe(int chessBoard[N][N], int row, int col){

	int j;

	/* Check the left upper diagonal */

	for(int i=row, j = col; i&gt;=0 &amp;&amp; j&gt;=0; i--, j--){
		if(chessBoard[i][j]) return 0;
	}

	/*check left lower diagonal */
	for(int i=row, j = col; i&lt;N &amp;&amp; j&gt;=0; i++, j--){
		if(chessBoard[i][j]) return 0;
	}
	
	return 1;
}

int isSafe(int chessBoard[N][N], int row, int col){

	int columnSafe = isColumnSafe(chessBoard, col);
	int rowSafe = isRowSafe(chessBoard, row);
	int diagonalSafe  = isDiagonalSafe(chessBoard, row, col);

	return columnSafe &amp;&amp; rowSafe &amp;&amp; diagonalSafe;
}

void placeQueen(int chessBoard[N][N], int i, int j){
	chessBoard[i][j] =1;
}
void removeQueen(int chessBoard[N][N], int i, int j){
	chessBoard[i][j] =0;
}

int solveQueens(int chessBoard[N][N], int col){
	
	if(col &gt;= N) return 1;

	for(int i=0; i&lt;N; i++){
		if(isSafe(chessBoard, i, col)){
			placeQueen(chessBoard, i, col);
			if(solveQueens(chessBoard,col+1)) return 1;
			removeQueen(chessBoard,i,col);
		}
	}
	
	return 0;
}  

int main(void) {
	int chessBoard[8][8];
	solveQueens(chessBoard, 0);
	
	return 0;
}

Complexity of backtracking algorithm for 8 queens problem will be O(N*N).>  : http://www-isl.ece.arizona.edu/ece175/assignments275/assignment4a/Solving%208%20queen%20problem.pdf

Reverse a linked list,find nth node from end, reverse k nodes

Let’s take a break from binary search tree for a while. There are couple of more problems which we can discuss later. Next some posts will be on singly linked list. 
Linked list is list of nodes where every node contains data and a pointer to the next node. 

Last node of the list points to the NULL. First node of the list is called as head of the list.
Each node of linked list can be defined as follows

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

In this post we are going to see three problems as listed below
1. Reversing a linked list
2. Finding the Kth element from the end of list.
3. Reverse every K nodes of a list.

Problem 1 : Reverse a linked list

Let’s take an example

Output should be


The catch in this problem is to change the head pointer. So we need to take of the first node and last node, for first node, next node will be NULL and the last node will become head node.


We can start with three pointers, one pointing to previous node, initialized to NULL,  second pointing to the current node and the third node is next of the current , which will be used to traverse ahead from current once next pointer of the next is modified.

Before modification

 After modification                             


Code

Recursive implementation of the same is

Problem 2 : Find Kth element from the end

This problem involves a trick. If we move one pointer K nodes ahead of the second pointer, when first node reaches at the end, second pointer is at the Kth node from the end. As simple as that 🙂

Code

Problem 3 : Reverse every K nodes in linked list

Example,

We start the reversing of the K nodes from the end. So we reverse the last K nodes first and then  change pointer of the existing lists last node to point to the head of reverse K nodes.


This can be easily implementation with recursion.

Code

Driver program from above functions, change the function calls 🙂


Complexity analysis

All of the above problems have complexity of O(N).

Binary tree to doubly linked list conversion

Binary tree to doubly linked list conversion

This is very commonly asked problem in Amazon and Google interview question. It checks your understanding of binary tree and doubly link list data structures, their traversals and creation. In a binary tree, a node has two pointers, one point to the left child of the node and other points to the right child of the node. Similarly, in a doubly linked list, a node contains two pointers, one point to the next node and other points to the previous node of the current node. Given a binary tree, how can we convert the binary tree to a doubly linked list? To make the problem clear, let’s take an example.

convert binary tree to dll
Binary tree to doubly linked list conversion

Output should be

convert binary tree to doubly linked list
Doubly linked list from binary tree

Binary tree to a doubly linked list: Line of thought

The first question you should be asking is which node should be the head of the doubly linked list? If the leftmost node in the binary tree is to be head, you need to traverse a tree in inorder. However, if the root node has to be the head node, then you should do preorder traversal.

This question could be great started as it shows your understanding of tree traversals.

Let’s say our problem is to have inorder traversal. If a binary tree is binary search tree, the interviewer can just tell you to provide the output as a sorted list, which is another way of saying inorder traversal.

To convert a binary tree to a doubly linked list, at each node, the previous pointer will point to the inorder predecessor of the node whereas next pointer points to inorder successor of the node. We have left and right pointers already in the node, use them as previous and next pointer respectively.
Now, problem is to keep track of inorder successor and predecessor of the node. To keep track of inorder predecessor, store the previous node of the current node visited throughout traversal. We would link the left child to the inorder predecessor.
How to keep find the inorder successor of a node, if the node is left child of some node, the inorder successor would be parent node. At the parent node, it would be the leftmost child of the right child if it exists. This is not scary as it sound, inorder successor part is automatically implemented if we do the recursive inorder traversal of the tree.

There is one special case to handle, which is the leftmost node. This node will be head of the doubly linked list and there is no previous node to link it’s left to. 

This whole problem is a complex version of inorder traversal of a binary tree, but at the end, it is inorder traversal. We can first write the generic inorder traversal and then modify the process step to suit our needs.

    private void inorder(Node root){
        if(root == null) return;

        if(root.left != null) inorder(root.left);
        process(root);
        if(root.right != null) inorder(root.right);
    }

We have to modify this to send previous node, where root connects it’s left child in process step and head, which is set only once, to store the head of result doubly linked list.

private void inorder(Node root, Node prev, Node head){
        if(root == null) return;

        if(root.left != null) inorder(root.left);
        process(root, prev,head);
        if(root.right != null) inorder(root.right);
    }

What we have to do in process step? If the current node is the leftmost node, we will set that head of the doubly linked list. If the previous node is null yet, that means, we have it the leftmost node.
What if the previous node is not null, in that case, we have already created or assigned head of the doubly linked list, and the previous node points to the last node of the doubly linked list. It means we have to link right pointer of the previous node to the current node.
Set left pointer of the current node to the previous node irrespective of the previous node. The last step would update the previous with the current node.

private void process(TreeNode root, TreeNode prev, TreeNode head){
	if(prev == null){
		head = root;
	}
	else{
		prev.setRight(root);
	}
	root.setLeft(prev);
	prev = root;
}

The only problem is that if we are implementing the process function Java, we cannot change the value of pointer because Java passes arguments as pass-by-value rather than pass-by-reference. In short, even though head and previous pointers are updated in process function, the change would not be reflected in the calling function. To handle this, we will create a mutable static class with two members called head and previous and pass it to process function. Why this method works, please refer  :  pass-by-value and pass-by-reference in java

    private void process(TreeNode root, Context context){
        if(context.prev == null){
            context.head = root;
        }
        else{
            context.prev.setRight(root);
        }

        root.setLeft(context.prev);
        context.prev = root;
    }

An algorithm to convert a binary tree to a doubly linked list

  1. Start from root node, currentNode.
  2. If currentNode->left != NULL, currentNode = currentNode->left. (Moving down the tree on the left side)
  3. At this point we are at the left most node, check if previous == NULL.
    1. If previous is NULL, then this node has to be the head node.
    2. Mark currentNode as head and currentNode->left = previous = NULL.
  4. previous = currentNode.
  5. Traverse up the tree in inorder traversal.
    1. previous->right = currentNode.
    2. currentNode->left = previous
    3. previous = currentNode
  6. If currentNode->right != NULL, currentNode = currentNode->right and go to step 2.

Convert Tree to DLL : implementation in Java

package com.company.BST;

/**
 * Created by sangar on 21.10.18.
 */
public class TreeToDLL {

    public static class Context {
        public TreeNode head;
        public TreeNode prev;
    }
    
    private void process(TreeNode root, Context context){
        if(context.prev == null){
            context.head = root;
        }
        else{
            context.prev.setRight(root);
        }

        root.setLeft(context.prev);
        context.prev = root;
    }

    public void treeToDllRecursion(TreeNode root, Context context){

        if(root == null) return;

        if(root.getLeft() != null) {
            treeToDllRecursion(root.getLeft(),context);
        }

        process(root,context);

        if(root.getRight() != null)
			treeToDllRecursion(root.getRight(), context);
    }
}

Definition of TreeNode and BinarySearchTree is given below.

package com.company.BST;

/**
 * Created by sangar on 21.10.18.
 */
public class TreeNode<T> {
    private T value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(T value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public T getValue(){
        return this.value;
    }
    public TreeNode getRight(){
        return this.right;
    }
    public TreeNode getLeft(){
        return this.left;
    }

    public void setValue(T value){
        this.value = value;
    }

    public void setRight(TreeNode node){
        this.right = node;
    }

    public void setLeft(TreeNode node){
        this.left = node;
    }
}
package com.company.BST;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree<T> {

    private TreeNode<T> root;

    public void BinarySearchTree(){
        root = null;
    }

    public void insert(int value){
        this.root =  insertNode(this.root, value);
    }

    private TreeNode insertNode(TreeNode root, int value){
        if(root == null){
            //if this node is root of tree
            root = new TreeNode(value);
        }
        else{
            if((int)root.getValue() > value){
                /*If root is greater than value,
				node should be added to left subtree */
                root.setLeft(insertNode(root.getLeft(), value));
            }
            else{
                /*If root is less than value,
				node should be added to right subtree */
                root.setRight(insertNode(root.getRight(), value));
            }
        }
        return root;
    }
    
    public TreeNode getRoot(){
        return this.root;
    }

    public void setRoot(TreeNode node){
        this.root = node;
    }
  }

Binary search tree to DLL conversion : C implementation

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

struct node{
        int value;
        struct node *left;
        struct node *right;
};
typedef struct node Node;

void treetoListRec(Node * node, Node ** prev, Node **ptrToHead){
        if(node == NULL)
                return;
        /* Go to left most child */
        if(node->left)
                treetoListRec(node->left, prev, ptrToHead);

        /* If this wasn't the first node being added to list*/  
        if(*prev!= NULL){
                (*prev)->right = node;
        }
        else{
                 *ptrToHead = node; 
         }
        /*make left pointer point to last node, and update the 
          last node to current*/

        node->left = *prev;
        *prev= node;

        /* If there is right child, process right child */
        if(node->right)
                treetoListRec(node->right, prev, ptrToHead);

}
Node * createNode(int value){
        Node * newNode=  (Node *)malloc(sizeof(Node));
        newNode->value = value;
        newNode->right = NULL;
        newNode->left = NULL;
        return newNode;
}
Node * addNode(Node *node, int value){
    if(!node)
        return create_node(value);
    else{
        if (node->value > value)
            node->left = addNode(node->left, value);
        else
            node->right = addNode(node->right, value);
    }
    return node;
}
 
/* Driver program for the function written above */
int main(){
        Node *root = NULL;
        Node * prev = NULL;
        Node *ptrToHead = NULL;
        //Creating a binary tree
        root = addNode(root,30);
        root = addNode(root,20);
        root = addNode(root,15);
        root = addNode(root,25);
        root = addNode(root,40);
        root = addNode(root,37);
        root = addNode(root,45);
        
        treetoListRec(root,&prev, &ptrToHead);
        
        return 0;
}

This requires traversal of each node at least once, hence complexity analysis is O(N).

Note

There is one method , which takes into consideration that the whole problem can be divided into sub-problems involving left sub tree and right sub tree, once these sub problems are solved, we can combine solutions of these to come up with the solution of the bigger problem.

Basic idea is to convert left sub binary tree to doubly linked list, then convert right sub binary tree to doubly linked list and join both the lists with root in between. Idea is very well explained here

Please share if there is something missing or wrong. If you want to contribute to website, please reach out to us on communications@algorithmsandme.com