29 Nov 2013

DP: Longest Common Sub-Sequence

Problem Statement:
    Find the LCS or Longest Common Sub-sequence (not necessarily contiguous) of the two given Sequences.

Seq 1: P R A T E E K
Seq 2: R A T H O R E

LCS is : R A T E

  Solution :

LCS applications:
1. Molecular Biology : 
          To compare DNA sequences

2. File Comparison: 
3. Screen Redisplay:
           As in Mobile display only the changed pixel are updated, instead of updating the whole screen.
 This is problem is combinatorial in nature and therefore can be solved by Brute force,
Possible Subset of the given sequences of length m and n will be 2^m and 2^n respectively, which will be matched by one with each other. Thus , the Complexity of the algorithm will be exponential.

Now,
    Question is "Can we do Better" as Professor Tim Roughgarden says.


 We can see this problem fulfilling the properties of Dynamic Programming.

 Principle behind Dynamic Programming says , start with recursive algorithm , which may be inefficient because of repeated computation of sub-problems. Simply remember the solution of sub-problems, which reduce the recomputing and will be simply looked up when required.
Thus computation time reduces to proportional to the number of sub-problems.

Dynamic Programming Properties:
1. Optimal sub-structure :
           We can decompose our problem in to smaller sub-sequence and calculate solution for them.

Fig: Optimal Sub-Structure
2. Overlapping Sub-Problem:
          Our Problem involves kind of recursion.



Given

Seq 1: P R A T E E K
Seq 2: R A T H O R E


Fig: LCS for given strings
Here ,all those characters are picked which come from diagonal cell, i.e. which are marked in orange, cell in green indicates the Longest Common Sub-sequence


Full Source Code: LINK
  
 /**
  * Longest Common Sequnece Subroutine
  */
 public static int lcs(String s1, String s2){

  char[] X = s1.toCharArray();
  char[] Y = s2.toCharArray();
  int[][] LCS = new int[Y.length +1 ][X.length +1 ];

  for(int i=1;i<=Y.length;i++)
  {
   for(int j=1;j<=X.length;j++)
   {
    if(Y[i -1 ]== X[j-1])
     LCS[i][j] = 1 + LCS[i-1][j-1];
    else
     LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1]);
   }
  }

  // Start Trace Back
  StringBuilder sb= new StringBuilder();
  int i=Y.length ;
  int j=X.length ;

  while(i > 0 && j>0)
  {
   //System.out.println(i + " " + j);
   if(Y[i-1] == X[j-1])
   {
    sb = sb.append(X[j-1]);
    i--;
    j--;
   }
   else
   {
    if(LCS[i][j-1]> LCS[i-1][j])  
     j--;
    else
     i--;
   }
  }

  System.out.println(sb.reverse());
  return LCS[Y.length][X.length];
 }

References:1. http://www.ics.uci.edu/~eppstein/161/960229.html
                    2. Refer NPTEL videos of design and algoritms (IIT Mumbai)
                    3. http://www.youtube.com/watch?v=wJ-rP9hJXO0


Please comment  and post suggestions

Happy Coding!! :)


Continuous Subsequence divisible by a number

Problem Statement: 
      What is the number of sub-sequences divisible by the given divisor  ?  

Given sequence:

                        {1 , 1 , 3 , 2 , 4, 1 ,4 , 5}
Divisor is 5

Answer is 11

Reference : Problem number 3 of
http://www.mii.lt/olympiads_in_informatics/pdf/INFOL062.pdf

Solution: 

Our goal is find the number of continuous sub-sequences divisible by the divisor
We will group the pre-fixes of the given sequence by the remainders (here modulo 5) of the sums of their elements.
If there are 'k'  prefixes for some remainder, then number of continuous sub sequences, with the sums of elements divisible by divisor (here 5) will be given by



nC2    = k(k-1)/2

 


Full Source Code: LINK

Implementation:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
        /**
  * Sub-Routine to count numnber of sub-sequnces
  * @param d: the given divisor
  */
 public static int solve(int[] arr, int d)
 {
  Object o;
  int Answer = 0;
  int[] hash = new int[d];

  int sum = 0;
  int val;
  int num;

  for (int i = 0; i < arr.length; i++) {
   num = arr[i];

   if(num % d == 0) // count numbers which are divisible by divisor
    Answer ++ ;

   sum +=  num; 
   val = sum % d;

   if(val<0) //handle negative numbers
    val = val * (-1);

   hash[val] = hash[val] + 1;
  }

  int size=hash.length ;
  for (int i = 0; i < size; i++)  {
   int count = hash[i];

   if(count > 1)
    Answer = Answer + count * (count -1)/2 ;
  }
  System.out.println(Answer+hash[0]);
  return Answer+hash[0];
 } 

Users are requested to refer the reference.
If u liked my article please comment and like the page on facebook.
Happy Coding!! :)

Stack: Minimum Element Lookup with O(1)

Problem Statement: 
    Implement a Stack with Minimum Element look-up in Constant time.


Solution:
Full Source Code : LINK

For this problem we would require extra stack which will maintain the Minimum element on the top. This stack will always have minimum element on the top.

We will be customizing the "Push" and "Pop" operations slightly of the Custom Stack in order for constant look-up of minimum element in the Stack.
We will be using two stacks viz.

1. Original Stack: Stack holding the elements
2. Min Stack : Stack holding min element on top


Fig: Original Stack and Min Stack for the given Sequence
1. Push Operation: 
           a) If element being pushed is smaller than the top element of Min Stack,
                           push to Original Stack and also Min Stack.
           b) If element being pushed is greater than the top element of Min Stack,
                           push to Original Stack.

Push Sub-routine implementation


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
       /**
  * Push Subroutine
  */
 @Override
 public void push(int data) {
  if(original.isEmpty())
   minStack.push(data);

  else{
   if(data < minStack.peek())
    minStack.push(data);
  }
  original.push(data);
 }

2. Pop Operation:
          a) If top element of Original Stack is equal to top element of Min Stack
                         pop Original Stack and also pop Min Stack
          b) If top of Original Stack is not equal to top of Min Stack                    
                         pop Original Stack only.

Pop Sub-routine implementation


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
        /**
  *Pops element from the custom stack 
  */
 @Override
 public int pop() {
  if(original.peek() == minStack.peek())
   minStack.pop();

  return original.pop();
 }

 
3. Get Minimum Operation:
          Return the top element of Min Stack

4. Peek
        Return top element of Original Stack


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
/**
  * Peek Minimum Element
  */
 @Override
 public int getMin(){
  return minStack.peek();
 }

 /**
  * Peek for the element
  */
 @Override
 public int peek() {
  return original.peek();
 }

 @Override
 public boolean isEmpty() {
  return original.isEmpty();
 }

Please comment and post your suggestion. Please "Like" page on facebook if u liked the article.
Happy Coding!! :)

Linked List: Deleted Node with given pointer

Problem Statement:
         Given a pointer of a Singly Linked List, delete the node pointed by the given Pointer.

Given Linked List with given Pointer pointing to "2"

Fig: Linked List with given pointer at 2

Solution: 

 Here the trick is copy the content of the next node that is "3" here to the given node ("2" here)
and delete the next node.



1
2
3
4
5
public void deleteNode(Node current){
  Node nextNode = current.next;
  current.data=nextNode.data ;
  current.next = nextNode.next;
 }

The Node structure of Linked List



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
/**
 * Linked List Node
 * @author Prateek
 */
class Node {

 public int data;
 public Node next;
 
 public Node(int data){
  this.data=data;
 }
 
 public String toString(){
  return ""+data;
 }
}

Note: This logic is not applicable for the last node in the Linked List.

Please post your comment and suggestions.
Happy Coding!! :)

Insertion Sort

Problem Statement:
    Implement and Discuss Insertion Sort

Solution:

Insertion Sort is one of the basic sorting techniques , which is simple but inefficient in sorting large amount of data as compared to Quick Sort, Merge Sort , Heap Sort etc ..

However Insertion sort has a number of advantages:

1. Adaptive: i.e. efficient for data sets that are already substantially sorted.
           Time Complexity : O(n+d) , where d is the number of inversions.
2. Stable: does not change the relative order of elements with equal keys
3. In-Place : no additional space required.
4. Online : can sort as it receives the data.
5. More efficient than other quadratic algorithms O(n^2) like , Selection Sort and Bubble Sort,
     best case is O(n) for insertion sort and worst case is O(n^2)
     
Humans usually sort the deck of cards using insertion sort.

Concept Involved:
   For every iteration the element picked is inserted into its correct position in the already sorted array, for N element each element is picked and placed to its correct position. 




Full Source Code: LINK


Code Implementation:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
       /**
  * Insertion Sort Subroutine
  */
 public int[] insertionSort(int[] arr)
 {
  int size = arr.length;
  for(int i=1;i<size;i++){
   int j=i;
   int num=arr[i];
   while(j>0 && arr[j-1] > num){
    arr[j]=arr[j-1];
    j--;
   }
   arr[j]=num;
  }
  return arr;
 }

Steps involved in sorting the given sequence:
   Sequence : {3, 7, 4, 9, 5, 2, 6, 1}
 
Fig: Sorting of 30 element array

3 7 4 9 5 2 6 1
3 7 4 9 5 2 6 1
7 4 9 5 2 6 1
4 7 9 5 2 6 1
3 4 7 9 5 2 6 1
3 4 5 7 9 2 6 1
2 3 4 5 7 9 6 1
2 3 4 5 6 7 9 1
1 2 3 4 5 6 7 9

Below is another graphical representation of intermediate step
of insertion sort.
Fig: Steps involved in Insertion Sort
References: Wikipedia
Try writing code for insertion sort by yourself
Please comment and post your suggestions.

Happy Coding!! :)

Queue

Problem Statement:
        Implement Queue

Solution: 

Given below is the kind of scenario in case of Queue Data structure ,
where items are pushed(en-queue-d) from rear and removed (de-queue-d) from front.


Fig: Example of Queue
Operations supported by Queue data structure are:
1. En-queue:
            It means insertion of elements from rear pointer
2. De-queue:
         It means deletion of items from front pointer.

A Queue supports FIFO operations i.e. First In First Out (FIFO)

Implementation:
-
/**
 * Queue Implementation
 * @author Prateek
 */
public class Queue {
 
 private static int DEFAULT_CAPACITY = 5;
 
 int front;
 int rear;
 int arr[];

 public Queue() {
  arr = new int[DEFAULT_CAPACITY];
  Arrays.fill(arr, -1);
  front = 0;
  rear = 0;
 }

 public Queue(int size) {
  DEFAULT_CAPACITY=size;
  arr = new int[DEFAULT_CAPACITY];
  Arrays.fill(arr, -1);
  front = 0;
  rear = 0;
 }
 
 public void push(int data) {
  rear = (rear) % (DEFAULT_CAPACITY);
  if (arr[rear] == -1) {
   arr[++rear] = data;
   System.out.println("Pushed: " + arr[rear - 1]);
  } else 
   System.out.println("Queue is Full");
 }

 public void pop() {
  int val = arr[front];
  arr[front] = -1;
  front++;
  System.err.println("Poped: " + val);
 }

 public void display() {
  System.out.print("Queue is : \t");
  int i = front;
  while (i <= DEFAULT_CAPACITY) {
   System.out.print(arr[i]+"\t");
   i = (i + 1) % DEFAULT_CAPACITY;
   if (i == rear)
    break;
  }
 }
}
-

References:
http://basicstodatastructures.blogspot.in/2013/10/queue.html from a good friend of mine.

Please post your comments and suggestions

Happy Coding!! :)

Stack

Problem Statement: 
        Implement Stack

Solution:

Stack supports three main operations:
1. Push:
         Insertion of element
2. Pop:
       Removal of the last element inserted
3. Peek:
 
A stack supports LIFO operations i.e. Last In First Out (LIFO)
These all operations are assisted by the "top" pointer which tracks the top most element element in the stack. 

Fig: Stack of books and Stack of Boxes
-
 /**
 * Stack Implementation
 * @author Prateek Rathore
 *
 */
public class Stack {
 int arr[];
 private static final int DEFAULT_CAPACITY = 10;
 public static int top = -1;
 
 public Stack() {
  arr = new int[DEFAULT_CAPACITY];
 }
 
 public Stack(int size) {
  arr = new int[size];
 }

 public void push(int data) {
  arr[++top] = data;
 }
 public int pop() {
  return arr[top--];
 }

 public int peek() {
           return arr[top];
 }
 
 public boolean isEmpty() {
  if(top==-1)
   return true;
  return false;
 }
}
-

References:
   Refer to one of my friend's post on stacks: LINK
               
Please post your comments and suggestions.

Happy Coding !! :)

Is Binary Tree Symmetric

Problem Statement:
       Check if the Given Binary Tree is Symmetric about the plane passing through root.

Fig: Symmetric Binary Tree about the place passing through root

Solution:
Full Source Code :  LINK
Below is the recursive implementation to check if Binary Tree is Symmetric


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
       /**
  * Sub-routine to check if Binary Tree is Symmetric
  */
 public boolean isSymmetric(Node left, Node right){
  if ( (left==null && right!=null) || (left!=null && right==null) )
   return false;

  if(left==null && right==null)
   return true;

  return isSymmetric(left.left,right.right) && isSymmetric(left.right,right.left);
 }

Please comment and post your suggestions.
Happy Coding!! :)

25 Nov 2013

DP: Longest Increasing Sub-Sequence

Problem Statement:
        Given a sequence , find the Longest sub-sequence which is increasing.
        Given Sequence: 

                      2 , 7 , 3 , 4 , 9 , 8 , 12

Resultant Longest sub-sequence is 2 , 3 , 4 , 9 , 12

Solution:

Full Source Code: LINK

  What are the number of possbile subsets ?
 = 2^n

We will solve this problem using Dynamic Programming(DP)
For a DP , it has the properties
1. Optimal Sub-Structure
          It means if i have solution of sub- problems , and optimal solution of those sub-problems can be combined to get the solution of bigger problem..

We will define a term ,
L(i) = Length of the  Longest Increasing Sub-Sequence which includes element arr[i] as its last element.

Equation for the optimal sub-structure
      L(i) = 1 + MAX ( L(j) )    , where 0<= j < i  and A[i]  > A[j]
  
2. Overlapping Sub-Problem:
              We can observe that there are values which needs to be recomputed again and again, therefore its and overlapping.

Consider and example
           
      
As i have discussed in previous posts of DP(Dynamic Programming) can be solved by memomisation or tabulation method,
I have used tabulation method here to find the solution

Intermediate Steps involved for the given sample


 L(0) = 1   
 L(1) = 1 + Max(L(0))  
     = 1 + Max(1)  
     = 1 + 1  
     = 2  
 L(2) = 1 + Max(L(0))  
     = 1 + Max(1)  
     = 2  
 L(3) = 1 + Max(L(0),L(2))  
     = 1 + Max(1 ,2)  
     = 1 + 2   
     = 3  
 L(4) = 1 + Max(L(0),L(1),L(2),L(3))       
     = 1 + Max(1 , 2 , 2 , 3)  
     = 1 + 3  
     = 4  
 L(5) = 1 + Max(L(0),L(1),L(2),L(3))  
     = 1 + Max(1 , 2 , 2 , 3 )  
     = 4  
 L(6) = 1 + Max(L(0),L(1),L(2),L(3),L(4),L(5))  
     = 1 + Max(1 , 2 , 2 , 3 , 4 , 4)  
     = 5  

Below is the logic of the sub-routine to find the increasing sub sequence:



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 private static int[] LIS;  
 private static int[] sol; //Array to retrive the sequence
 static int tail=0;   //final element of sequence

 /**
  * Procedure to find LIS
  * @param arr : input array
  * @return longest value on increasing sub sequence
  */
 public static int lis(int[] arr){
  int len = arr.length ;

  LIS = new int[len];
  sol = new int[len] ; 

  Arrays.fill(sol, -1);

  LIS[0] = 1; //base case
  int MAX_LIS=1;  // default value
  int max; // gets max value for each i
  for(int i=1;i < len ; i++)
  {
   max=0;
   for(int j=0 ; j<i ; j++)
   {
    if(arr[i] > arr[j] && LIS[j] > max )
    {
      sol[i] = j ; //used to save
      max = LIS[j]; //update max for value of i
    }
   }
   LIS[i] = 1 + max ;

   if(LIS[i] > MAX_LIS){
    MAX_LIS = LIS[i];
    tail=i;
   }
  }

  printSequence(sol, arr);
  System.out.println("Sequence length : " + MAX_LIS);
  return MAX_LIS ;
 }

Below is the sub-routine to print the increasing sub-sequence computed from the above sub routine.


1
2
3
4
5
     public static void printSequence(int[] sol , int[] arr){
  System.out.println("Sequence : ");
  for (int j = tail; j >= 0; j = sol[j])
   System.out.print(arr[j]+"\t");
 }


Please comment and post suggestions , for the above code.

Happy Coding !! :)

22 Nov 2013

LRU Cache

Problem Statement:
       Implement basic LRU (Least Recently Used) Cache

Solution:

LRU cache properties:
  1. Adds item to the start of list if not present in the list
  2. Updates the item if already present , and brings the item to the start of list
  3. If cache is full removes the last element and add the new item to the start of list.
Given below LRU cache is implemented using concept of Queue(implemented by Linked List) and Hash Table.

Full Source Code : LINK

Item Structure in the LRU Cache:

 /**
 * Item Node structure in the LRU Cache
 * @author Prateek
 */
class Item {
 public Item prev;
 public Item next;
 public String key;
 public String data;

 public Item(){}

 public Item(String key, String data){
  this.key = key;
  this.data = data;
 }
 
 @Override
 public String toString(){
  return this.key+" : "+this.data;
 }
}

Implementation of the LRU Cache

/**
 * LRU Cache implementation
 * @author Prateek
 */
public class LRUCache {

 public Item head; 
 public Item tail;
 public int maxsize;

 //to hold key for every item
 private HashMap hash;

 public LRUCache(int size) {
  this.maxsize = size ;
  hash = new HashMap();
  head = new Item("0","0");
  tail = new Item("0","0");
  head.next = tail;
  tail.prev = head;
 }

 /**
  * Add item to the beggining of Linked List
  * @param item
  */
 public void addItemAtFirst(Item item){
  item.next = head.next;
  item.prev = head;
  head.next.prev = item;
  head.next = item;
 }

 /**
  * Remove item from the Linked List
  * @param item
  */
 public void removeItem(Item item){
  item.prev.next = item.next;
  item.next.prev = item.prev ;
 }

 /**
  * @return the value , and remove the node from between and add to the 
  *                     the beggining
  */
 public String get(String key){

  Item item= hash.get(key);
  if(item!=null)
  {
   if(hash.size()==1)
    return item.data;
   
   removeItem(item);
   addItemAtFirst(item);
   return item.data;
  }
  else
   return null;
 }

 /**
  * Insert to hashmap and linkedlist, if size is exceeded remove the tail element
  */
 public void put(String key, String data){
  Item item = hash.get(key);
  if(item==null) //item not found 
  {
   item = new Item(key,data);
   hash.put(key,item);
   addItemAtFirst(item);
   if(hash.size() == maxsize)
   {
    hash.remove(tail.prev.key);
    removeItem(tail.prev);
   }
  }
  else //item found in the hashmap, update data
  {   item.data = data;
   removeItem(item);
   addItemAtFirst(item);
  }
 }
 
 /**
  * Display Cache Content
  */
 public void displayLRUCache(){
  System.out.println("Items in the Cache");
  Item temp=head.next;
  while(temp.next!=null)
  {
   System.out.print(temp.data + " ");
   temp=temp.next;
  }
 }
}

This post is just to provide basic knowledge of LRU cache. You can extract basic idea from this post for developing your production code to work in multi-threaded environment and insertion of generic items. The above post is similar to the API implementation of LinkedHashMap in Java.

Feel free to post your comments or suggestions , critiques are too most welcome.

Happy Coding !! :)