Coding Recipies: January 2014

27 Jan 2014

Linked List : Pair Swapping(Iterative)

Problem Statement:
Iterative Pair swap the elements of the Linked List

Source Code
Solution:

We require minimum of three pointers. I have used 'temp' for moving forward. 'back' pointer points to the next of 'front' pointer.'front' is the leading pointer which then later connects to 'back'.

Below is the Iterative Implementation:

/**
  * Iterative Subroutine to swap pairs of nodes of linked list
  * @return new Head of the linked list
  */
 public Node pairSwap(Node head){
  Node temp=head;
  head=head.next; //new head
  
  Node front,back;
  while(temp!=null && temp.next!=null)
  {
   back=temp;
   front=temp.next;
   
   back.next=front.next;
   front.next=back;
   
   if(temp.next!=null)
    temp=temp.next;
   if(temp.next!=null)
    back.next=temp.next;
  }
  return head;
 }

Please comment and post if any better or efficient approach available may be with lesser pointers.
Happy Coding !! :)

Linked List: Pair Swapping (Recursive)

Problem Statement:
Perform pair-wise swapping on the given linked list using recursion.

Source Code Link
Solution:

Below is the subroutine implementation for achieving the resultant linked list

/**
  * Recursive Subroutine to swap pairs of nodes of linked list
  * @return new Head of the linked list
  */
 public Node pairSwap(Node head){
  Node curr=head;
  Node front=null;
 
  if(curr!=null && curr.next!=null){
   front=curr.next;
   curr.next = pairSwap(front.next);
   front.next=curr;
  }
  return (front!=null) ? front : curr;
 }

Please comment and post your suggestion or any modification to the above code.
Happy Coding !!:)

26 Jan 2014

Two Stacks

Problem Statement:
Implement two stacks in an array.

Fig: Two Stack implementation

Source Code
Solution:

For implementing two stacks in an array efficiently we will take two TOP pointers which grow from opposite sides of the array.

PUSH , POP , PEEK takes the "StackNumber" argument which decides on which stack operation is to be performed.

 
 /**
  * Push Operation
  * @param stackNum 0: 1st stack  , 1: 2nd stack
  * @param data : data to be pushed
  * @throws InterruptedException 
  */
 public void push(int stackNum, int data) throws InterruptedException{
  Thread.sleep(10);
  if(stackNum==1){
   pushToStack1(data);
  }
  else if(stackNum==2)
   pushToStack2(data);
  else
   System.out.println("Invalid Stack Number");
 }
 
 public int pop(int stackNum) throws InterruptedException{
  Thread.sleep(10);
  if(stackNum==1)
   return popFromStack1();
  else if (stackNum==2)
   return popFromStack2();
  else{
   System.err.println("Invalid Stack");
   return -1;
  }
 }
 
 public int peek(int stackNum) throws InterruptedException{
  Thread.sleep(10);
  if(stackNum==1)
   return peekFromStack1();
  else if (stackNum==2)
   return peekFromStack2();
  else{
   System.err.println("Invalid Stack");
   return -1;
  }
 }

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

Three Stacks

Problem Statement:
Implement three stacks in a single array.

Fig: Implement three stacks in a given array

Source Code
Solution:
The concept is to divide the given array into three parts and using auxiliary space to store status of "Top" pointer of each stack.

Push and Pop operation accepts an extra argument , which specifies on which stack the operation is to be performed.

Below is the implementation of PUSH, POP and PEEK subroutines.

 private int stackSize=5;
 private int[] tops={-1,-1,-1};
 private int[] arr=new int[stackSize * 3];

 /**
  * Push operation
  * @param stackNum : specifies the stack number
  * @return: insertion status
  * @throws InterruptedException 
  */
 public boolean push(int stackNum, int item) throws InterruptedException{
  int index= stackNum * stackSize + tops[stackNum] + 1;
  if(tops[stackNum] < stackSize -1 ){
   tops[stackNum]++;
   arr[index]=item;
   Thread.sleep(10);
 System.out.println(Arrays.toString(arr));
   return true;
  }
  else{
   System.err.println("Stack Full");
   return false;
  }
 } 

 /**
  * Pop operation
  * @param stackNum: specifies the stack number
  * @return the poped item
  * @throws InterruptedException 
  */
 public int pop(int stackNum) throws InterruptedException{

  if(tops[stackNum]==-1)  {
   System.err.println("Stack is Empty");
   return -1;
  }
  int index= stackNum * stackSize + tops[stackNum];
  tops[stackNum]--;
  int item= arr[index];
  arr[index]=0;
  Thread.sleep(10);
  System.out.println(Arrays.toString(arr));
  return item;
 }

 /**
  * Peek operation
  * @param stackNum: specifies the stack number
  * @return top element of the specified stack
  */
 public int peek(int stackNum){
  if(tops[stackNum]==-1)  {
   System.out.println("Stack is Empty");
   return -1;
  }

  int index= stackNum * stackSize + tops[stackNum];
  return arr[index];
 }

Happy Coding !! :)

Queue with two Stacks

Problem Statement:
Implement Queue using two stacks.

Fig: Queue using two stacks

Source Code Link
Solution:

I expect you are aware of operations that ADTs(Abstract Data Types) Queue and Stack supports. All we have to do is implement Enqueue and Dequeue opertions using operations of a Stack, i.e. push, pop , peek , isEmpty and size.

1st Approach(inefficient):
Suppose we have two stacks say S1 and S2 , we use S1 to push elements , when en-queue operation of queue is called, and when de-queue is called we pop everything out of S1 and push to S2, and pop the top element from S2, and again push everything to S1 by popping out from S2.

Summarizing:
Enqueue Operation:
push to S1

Dequeue Operation:
1. Pop everything from S1 and push to S2.
2. Pop top element of S2 when S1 gets empty.
3. Push everything back to S1 from S2.

Here clearly our Dequeue operation is costly , and there lies one more approach by which we can improve on this.

2nd Approach: (Efficient)
This approach is slight modification to the above logic in order to achieve efficiency in the "dequeue"operation.
In the above approach we are unnecessarily pushing elements from S2 to S1 , i.e. Step 3 of Dequeue operation as shown above. The trick is to pick the top element of S2 if its not empty , if it is then push everything from S1 to S2 and return top element of S2.

Summary :
Enqueue Operation:
1. push to S1

Dequeue Operation:
1. If S2 is not Empty
- pop top element of S2
2. If S2 is empty
- push everything from S1 to S2 and pop top element of S2.

The link to the code is given above please refer to it.

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

Stack Reversal

Problem Statement:
In-place stack reversal using recursion.

Fig: In-place Stack Reversal

Source Code
Solution:
Using recursion start from the bottom most element in the stack using the 1st Function Call(reverse()) , push each element to the bottom of the stack through recursion using another function call(pushToBottom()).

Below is the implementation.

/**
 *  Inplace reversal of Stack
 * @author Prateek
 */
public class ReverseStackRecursion {
 /**
  * Subroutine to Reverse the element of stack 
  * @param stack : input stack
  */
 public void reverseStack(Stack<Integer> stack){
  if(stack.isEmpty())
   return ;

  int val= stack.pop();
  reverseStack(stack);

  pushToBottom(stack,val);
  return ;
 }

 /**
  * Pushes the incoming element or item to the bottom of the stack 
  */
 private void pushToBottom(Stack<Integer> stack,int item){
  if(stack.isEmpty()){
   stack.push(item);
   return ;
  }

  int val= stack.pop();
  pushToBottom(stack,item);
  stack.push(val);
 }
}

Happy Coding !! :)

Sort Stack

Problem Statement:

Recursive In-place Stack Sorting.

Fig: Sort given Stack in O(1)

Source Code

Solution:

In this problem we will empty the stack and hold in values in the function call Stack. Then each element from the Function Call Stack is picked and compared with the given stack elements, which again is handled by another nested Function Call Stack. No extra space is used in sorting the stack.

Sort() Subroutine empties the stack

Below is the implementation:

/**
 * Recursive Inplace Stack Sorting 
 * @author Prateek
 */
public class SortStack {
 //input stack
 private Stack<Integer> stack; 
 
 public SortStack(Stack<Integer> stack) {
 this.stack=stack;
 }
 
 /**
  * Sorting Subroutine 
  */
 public void sort(){
  if(stack.isEmpty())
   return;
  
  int item=stack.pop();
  sort();
  compareAndPush(item);
 }
 
 /**
  * Pushing each element of stack by recursion
  * @param item: each item of stack which is compared and pushed to stack
  */
 public void compareAndPush(int item){
  if(stack.isEmpty() || item <= stack.peek())
   stack.push(item);
  else {
   int val=stack.pop();
   compareAndPush(item);
   stack.push(val);
  }
 }
}

Please comment and post suggestions if any.
Happy Coding !! :)

Stack & Queues: Stack using Queues

Problem Statement:
Implement Stack using two Queues.

Fig: Stack And Queue

Source Code LINK
Solution:
We will be using two queues for achieving efficiency instead of one.
The code that we will be implementing will have pop operation with some over head compared to push.
Assume we two queues Q1 and Q2.

Push : enqueue item to Q1

Pop: dequeue all the element from Q1 and and enqueue them to Q2 except the last element, Flip the name of the queues and return the element of Q1.

Below is the implementation of PUSH and POP operations:

/**
	 * Push operation of Stack
	 * Item pushed into Queue1
	 */
	@Override
	public void push(Integer item) {
		System.out.println("Push : "+item);
		queue1.offer(item);
	}

	/**
	 * Pop operation of Stack
	 * last item of queue1 is returned, 
	 * order is reversed using queue2
	 */
	@Override
	public Integer pop() {
		Integer item=null;
		if(!queue1.isEmpty())
		{
			while (!queue1.isEmpty()) 
			{
				 item=queue1.poll();
				if(!queue1.isEmpty())
					queue2.add(item);
			}
			flip();
		}
		else
			System.out.println("Stack is Empty");
		System.out.println("Poped : "+ item);
		return item;
	}

The PEEK operation will be similar to POP operation, but all the items of Q1 will be pushed to Q2 , and names will be swapped.

/**
	 * Peek operation, similar to pop , 
	 * with slight modification
	 */
	@Override
	public Integer peek() {
		Integer item=null;
		while (!queue1.isEmpty()) {
			 item=queue1.poll();
				queue2.add(item);
		}
		flip();
		System.out.println("Peek : "+ item);
		return item;
	}

Other implementations is given below

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

	/**
	 * Flipping of Queues
	 */
	public void flip(){
		Queue<Integer> tQueue=  queue1;
		queue1=queue2;
		queue2 = tQueue;
	}

Please post your suggestions if any.

References: Stackoverflow
Happy Coding!! :)