Monday, February 22, 2010

Find all possible palindromes in a String in Java C++

This is not the regular palindrome finder. Given a string, we should be able to print all the possible palindromes. Let me quickly give a brief example.
For the following text : abccbab
All the possible palindromes are,
bab
abccba
bccb
cc
If you could see there are two possible outcomes in palindrome, one is odd and other is even. My initial solution was very worse. What I actually did was did a permutation/combination of all the possible texts and send it to a palindrome() method. It will run in the worst possible time.
However, there is even a simpler solution available. First do a parse for odd occurring palindromes followed by even palindromes.
For odd palindromes run through each character from the text. For each character, see if there the pre and post occuring characters are equal, if they are equal print them and do the same for the next levels. In the following example shown below, assume you are at 'y' and see the previous and next characters are equal. If they are see further more until the palindrome functionality ceases. Print all of them whilst this time.

 

Thats it. Do the same for all the characters. Since there is no meaning in doing this for first and last characters, we can very well omit them.
Similar logic holds for even sized palindromes. Here we wont be holding the center character. Rest of the logic remains the same. The java code follows,

package dsa.stringmanipulation;

/**
 * Program to print all palindromes in a string
 * @author Bragaadeesh
 */
public class FindAllPalindromes {
 public static void main(String[] args){
  FindAllPalindromes finder = new FindAllPalindromes();
  finder.printAllPalindromes("abcddcbaABCDEDCBA");
 }
 
 public void printAllPalindromes(String inputText){
  if(inputText==null){
   System.out.println("Input cannot be null!");
   return;
  }
  if(inputText.length()<=2){
   System.out.println("Minimum three characters should be present");
  }
  //ODD Occuring Palindromes
  int len = inputText.length();
  for(int i=1;i<len-1;i++){
   for(int j=i-1,k=i+1;j>=0&&k<len;j--,k++){
    if(inputText.charAt(j) == inputText.charAt(k)){
     System.out.println(inputText.subSequence(j,k+1));
    }else{
     break;
    }
   }
  }
  //EVEN Occuring Palindromes
  for(int i=1;i<len-1;i++){
   for(int j=i,k=i+1;j>=0&&k<len;j--,k++){
    if(inputText.charAt(j) == inputText.charAt(k)){
     System.out.println(inputText.subSequence(j,k+1));
    }else{
     break;
    }
   }
  }

 }
}
/*
Sample Output:
DED
CDEDC
BCDEDCB
ABCDEDCBA
dd
cddc
bcddcb
abcddcba
*/

The code in C++
#include <iostream>
using namespace std;

void printAllPalindromes(char*);

char* subSequence(char*,int,int);

int main() {
 char *s = "abcddcbaABCDEDCBA";
 printAllPalindromes(s);
 return 0;
}

char* subSequence(char* mainSequence, int from, int to){
 char * tgt = new char[to-from+1];
 for(int i=0;i<(to-from);i++){
  tgt[i] = mainSequence[i+from];
 }
 tgt[to-from] = '\0';
 return tgt;
}

void printAllPalindromes(char* inputText) {
 if(!inputText) {
  printf("Input cannot be null!");
  return;
 }
 if(strlen(inputText)<=2) {
  printf("Minimum three characters should be present\n");
 }
 //ODD Occuring Palindromes
 int len = strlen(inputText);
 for(int i=1;i<len-1;i++) {
  for(int j=i-1,k=i+1;j>=0&&k<len;j--,k++) {
   if(inputText[j] == inputText[k]) {
    char* subSeq = subSequence(inputText,j,k+1);
    cout<<subSeq<<endl;
    delete subSeq;
   } else {
    break;
   }
  }
 }
 //EVEN Occuring Palindromes
 for(int i=1;i<len-1;i++) {
  for(int j=i,k=i+1;j>=0&&k<len;j--,k++) {
   if(inputText[j] == inputText[k]) {
    char* subSeq = subSequence(inputText,j,k+1);
    cout<<subSeq<<endl;
    delete subSeq;
   } else {
    break;
   }
  }
 }

}
/*
 Sample Output:
 DED
 CDEDC
 BCDEDCB
 ABCDEDCBA
 dd
 cddc
 bcddcb
 abcddcba
 */

Cheers,
Bragaadeesh.

Sunday, February 21, 2010

Stack using Linked Lists in Java

Stack is a data structure that follows the simple FILO (First In, Last out) or LIFO (Last In, First Out) rule. Imagine a real world stack where you arrange Notebooks one over the other. The first notebook you insert will be at the bottom and that will come only at last. The implementation of stack can be done in many ways. We are going to see how to make use of a Singly Linked List to the use.
We can implement stack using a Linked List in the below shown ways. One is to have the END node on top and other is to have the START node at the top. If we recollect the singly linked list data structure, insertAtFirst() is an operation which can be done in O(1) time and insertAtLast() will take O(n) time (because we need to traverse till the last node). So, we can make use of the second method to use stack using linkedlists.


The three methods that stands out for a stack are pop(), push() and peek().
push() - push elements into a stack. We will use the insertAtFirst() method of LinkedList. Throws StackOverflowException when the stack is full.
pop() - remove and returns the top element from a stack. We will use the removeAtFirst() method of LinkedList. Throws StackEmptyException when the stack is empty.
peek() - return the top element from the stack without removing it. We will use the getFirst() method of LinkedList. Throws StackEmptyException when the stack is empty.

The java code for this looks very simpler. We will make use of the existing SinglyLinkedList class that we have used before.

package dsa.stack;

import dsa.linkedlist.SinglyLinkedList;

public class Stack<E> extends SinglyLinkedList<E>{
 
 public static final int MAX_STACK_SIZE = 100;
 
 public E pop() throws StackEmptyException{
  if(this.size()==0){
   throw new StackEmptyException();
  }
  return this.removeAtFirst();
 }
 
 public E peek() throws StackEmptyException{
  if(this.size()==0){
   throw new StackEmptyException();
  }
  return this.getFirst().data;
 }
 
 public void push(E data) throws StackOverflowException{
  if(this.size()>MAX_STACK_SIZE){
   throw new StackOverflowException();
  }
  this.insertAtFirst(data);
 }
 
 public static void main(String args[]){
  Stack<Integer> stack = new Stack<Integer>();
  try{
   System.out.println("Pushing 1, 2, 3, 4, 5");
   stack.push(1);
   stack.push(2);
   stack.push(3);
   stack.push(4);
   stack.push(5);
   System.out.println("Pop once  : "+stack.pop());
   System.out.println("Peek once : "+stack.peek());
   System.out.println("Pop once  : "+stack.pop());
   System.out.println("Pop once  : "+stack.pop());
   System.out.println("Pop once  : "+stack.pop());
   System.out.println("Pop once  : "+stack.pop());
   System.out.println("Pop once  : "+stack.pop());
  }catch(StackEmptyException e){
   System.out.println(e.getMessage());
  }catch(StackOverflowException e){ 
   System.out.println(e.getMessage());
  }
 }
}
/*
SAMPLE OUTPUT:
Pushing 1, 2, 3, 4, 5
Pop once  : 5
Peek once : 4
Pop once  : 4
Pop once  : 3
Pop once  : 2
Pop once  : 1
Stack is empty!
*/

package dsa.stack;

public class StackEmptyException extends Exception{
 public StackEmptyException(){
  super("Stack is empty!");
 }
}
package dsa.stack;

public class StackOverflowException extends Exception{
 public StackOverflowException(){
  super("Stack Overflown");
 }
}

Cheers,
Bragaadeesh.

Find kth node from the last in a singly linked list without using counter

The objective for this program is to find the kth node from the last without actually finding the size of the singly linked list.
For this problem, we need to have two pointers, lets call them FAR and NEAR. We need to initialize them by pointing them to the start. After doing that, move the FAR pointer 'k-1' times ahead. After moving that run a loop until FAR becomes null, amidst that increment both FAR and NEAR pointers.
The below picture shown is done for k=3. In step1, we are moving the pointer k-1=2 times. After that by moving parallely FAR and NEAR pointers, we can find the kth element from the last by getting the data from NEAR pointer.


The Java code for this simple program is given below. To try the below program please copy this class as well.
package dsa.linkedlist;

public class FindKthElementFromLast {
 public static void main(String args[]){
  FindKthElementFromLast kthFromLastFinder = new FindKthElementFromLast();
  SinglyLinkedList<Integer> originalList = kthFromLastFinder.getLabRatList(8);
  System.out.println("Original List : "+originalList.toString());
  kthFromLastFinder.findFromLast(originalList, 3);
 }
 
 private void findFromLast(SinglyLinkedList<Integer> singlyLinkedList, int k) {
  Node far, near;
  //initialize far and near pointers
  far = near = singlyLinkedList.start;
  //Move the far pointer k times from the starting position
  System.out.print("kth node from last for k = "+k+" is ");
  while((k--)!=0){
   far = far.next;
  }
  while(far!=null){
   near = near.next;
   far = far.next;
  }
  System.out.println(near.data);
 }

 private SinglyLinkedList<Integer> getLabRatList(int count){
  SinglyLinkedList<Integer> sampleList = new SinglyLinkedList<Integer>();
  for(int i=1;i<=count;i++){
   sampleList.add(i);
  }
  return sampleList;
 }
}
//SAMPLE OUTPUT
//Original List : 1, 2, 3, 4, 5, 6, 7, 8
//kth node from last for k = 3 is 6
Cheers,
Bragaadeesh.

Friday, February 19, 2010

Mars Rovers coding problem

This is one of the coding problems I got when I attended one of the famous MNCs. I am providing the question and the solution having the complete Java code for the same. They give these kinds of problems not to see whether you get the right answer, but to check your Object Oriented skills and comprehensiveness in coding. I cleared this round. :)

PROBLEM : MARS ROVERS
A squad of robotic rovers are to be landed by NASA on a plateau on Mars. This plateau, which is curiously rectangular, must be navigated by the rovers so that their on-board cameras can get a complete view of the surrounding terrain to send back to Earth.

A rover's position and location is represented by a combination of x and y co-ordinates and a letter representing one of the four cardinal compass points. The plateau is divided up into a grid to simplify navigation. An example position might be 0, 0, N, which means the rover is in the bottom left corner and facing North.

In order to control a rover, NASA sends a simple string of letters. The possible letters are 'L', 'R' and 'M'. 'L' and 'R' makes the rover spin 90 degrees left or right respectively, without moving from its current spot. 'M' means move forward one grid point, and maintain the same heading.

Assume that the square directly North from (x, y) is (x, y+1).

INPUT:
The first line of input is the upper-right coordinates of the plateau, the lower-left coordinates are assumed to be 0,0.

The rest of the input is information pertaining to the rovers that have been deployed. Each rover has two lines of input. The first line gives the rover's position, and the second line is a series of instructions telling the rover how to explore the plateau.

The position is made up of two integers and a letter separated by spaces, corresponding to the x and y co-ordinates and the rover's orientation.

Each rover will be finished sequentially, which means that the second rover won't start to move until the first one has finished moving.

OUTPUT
The output for each rover should be its final co-ordinates and heading.

INPUT AND OUTPUT

Test Input:
5 5
1 2 N
LMLMLMLMM
3 3 E
MMRMMRMRRM

Expected Output:
1 3 N
5 1 E
==========


SOLUTION

The solution follows. You may download the complete program here.

package nasa.main;

import nasa.exceptions.InvalidInputException;
import nasa.exceptions.OutOfRangeException;

public class Nasa {
 
 private ISignal signal;
 
 private ControlPanel controlPanel;
 
 public Nasa(ISignal signal){
  this.signal = signal;
 }
 
 public void execute() throws InvalidInputException, OutOfRangeException {
  
  controlPanel = new ControlPanel(signal.getBounds());
  
  controlPanel.setRoverPos(new Heading(signal.getInitialPos()));
  
  controlPanel.setData(signal.getData());
  
 }
 
 public String getFinalPosition(){
  
  Heading finalHeading = controlPanel.getRoverPos();
  
  return finalHeading.toString();
 }
 
}
package nasa.main;

import java.util.StringTokenizer;

import nasa.exceptions.InvalidInputException;
import nasa.exceptions.OutOfRangeException;

public class Heading {
 
 private int x;
 
 private int y;
 
 private byte direction;
 
 public Heading(){
  
 }
 
 public Heading(String position) throws InvalidInputException, OutOfRangeException{
  parse(position);
 }
 
 private void parse(String position) throws InvalidInputException, OutOfRangeException {
  
  StringTokenizer tokens = new StringTokenizer(position);
  if(tokens.hasMoreTokens()){
   
   try{
    x = Integer.parseInt(tokens.nextToken());
   
    y = Integer.parseInt(tokens.nextToken());
   }catch(NumberFormatException ne){
    throw new InvalidInputException("Invalid number!!");
   }
   
   direction = tokens.nextToken().getBytes()[0];
  }
  
  if(!verifyBounds()){
   throw new OutOfRangeException("Invalid inital position!!!");
  }
 }
 
 public void parseCommand(byte command) throws InvalidInputException, OutOfRangeException{
  
  switch(command){
  case Constants.ROTATE_LEFT:
   rotateLeft();
   break;
  case Constants.ROTATE_RIGHT:
   rotateRight();
   break;
  case Constants.MOVE:
   move();
   break;
  default:
   throw new InvalidInputException("Invalid signal");
  }
 }

 private void move() throws OutOfRangeException{
  switch (direction) {
  case Constants.DIRECTION_NORTH:
   y += 1;
   break;
  case Constants.DIRECTION_EAST:
   x += 1;
   break;
  case Constants.DIRECTION_SOUTH:
   y -= 1;
   break;
  case Constants.DIRECTION_WEST:
   x -= 1;
   break;
  }
  if(!verifyBounds()){
   throw new OutOfRangeException("Rover exceeding range!!!");
  }
 }

 private boolean verifyBounds() {
  if((x>ControlPanel.BOUNDS_X || y>ControlPanel.BOUNDS_Y)
    || x<0 || y<0){
   return false;
  }
  return true;
 }

 private void rotateRight() {
  switch(direction){
  case Constants.DIRECTION_NORTH:
   direction = Constants.DIRECTION_EAST;
   break;
  case Constants.DIRECTION_EAST:
   direction = Constants.DIRECTION_SOUTH;
   break;
  case Constants.DIRECTION_SOUTH:
   direction = Constants.DIRECTION_WEST;
   break;
  case Constants.DIRECTION_WEST:
   direction = Constants.DIRECTION_NORTH;
   break;
  }
 }

 private void rotateLeft() {
  switch(direction){
  case Constants.DIRECTION_NORTH:
   direction = Constants.DIRECTION_WEST;
   break;
  case Constants.DIRECTION_WEST:
   direction = Constants.DIRECTION_SOUTH;
   break;
  case Constants.DIRECTION_SOUTH:
   direction = Constants.DIRECTION_EAST;
   break;
  case Constants.DIRECTION_EAST:
   direction = Constants.DIRECTION_NORTH;
   break;
  }
 }

 public String toString(){
  String toString = null;
  
  toString = x+" "+y+" "+toChar(direction);
  
  return toString;
 }

 private char toChar(byte direction) {
  String s = String.valueOf(direction);
  
  char c = (char)Integer.parseInt(s);
  
  return c;
 }

 
}
package nasa.main;

public interface ISignal {
 
 /**
  * This returns the upper right corner of the Rectangle in string format
  */
 public String getBounds();

 /**
  * This returns the data which includes movement and rotation commands
  */
 public String getData();

 /**
  * This returns the initial position of the rover
  */
 public String getInitialPos();
}
package nasa.main;

import nasa.exceptions.InvalidInputException;
import nasa.exceptions.OutOfRangeException;

public class Rover {
 ControlPanel parentControl;
 
 Heading currentHeading;
 
 public Rover(ControlPanel control){
  this.parentControl = control;
 }

 public Heading getCurrentHeading() {
  return currentHeading;
 }

 public void setCurrentHeading(Heading currentHeading) {
  this.currentHeading = currentHeading;
 }

 public void setData(String data) throws InvalidInputException, OutOfRangeException{
  parseData(data);
 }

 private void parseData(String data) throws InvalidInputException, OutOfRangeException{
  
  byte[] bytes = data.trim().getBytes();
  
  for(int i=0;i<bytes.length;i++){
   currentHeading.parseCommand(bytes[i]);
  }
 }
}
package nasa.main;

public class Constants {
 
 public static final byte DIRECTION_NORTH = 'N';
 
 public static final byte DIRECTION_EAST = 'E';
 
 public static final byte DIRECTION_SOUTH = 'S';
 
 public static final byte DIRECTION_WEST = 'W';
 
 public static final byte ROTATE_LEFT = 'L';
 
 public static final byte ROTATE_RIGHT = 'R';
 
 public static final byte MOVE = 'M';
 
}
package nasa.main;

import java.util.StringTokenizer;

import nasa.exceptions.InvalidInputException;
import nasa.exceptions.OutOfRangeException;

public class ControlPanel {

 private Rover rover;

 /**
  * Default bounding value for X
  */
 public static int BOUNDS_X = 5;

 /**
  * Default bounding value for Y
  */
 public static int BOUNDS_Y = 5;

 public ControlPanel(String bounds) throws InvalidInputException {
  parse(bounds);
  rover = new Rover(this);
 }

 private void parse(String bounds) throws InvalidInputException {

  StringTokenizer tokens = new StringTokenizer(bounds);

  if (tokens.hasMoreTokens()) {

   try {
    BOUNDS_X = Integer.parseInt(tokens.nextToken());

    BOUNDS_Y = Integer.parseInt(tokens.nextToken());
   } catch (NumberFormatException e) {
    throw new InvalidInputException("Invalid bounding values");
   }
  }

  if (BOUNDS_X <= 0 || BOUNDS_Y <= 0) {
   throw new InvalidInputException(
     "Bounding values should be greater than or equal to 1");
  }

 }

 public void setRoverPos(Heading heading) {
  rover.setCurrentHeading(heading);
 }

 public Heading getRoverPos() {
  return rover.getCurrentHeading();
 }

 public void setData(String data) throws InvalidInputException,
   OutOfRangeException {
  rover.setData(data);
 }

}
package nasa.implementation;

import nasa.main.ISignal;

public class TestSignal implements ISignal {
 
 private String bounds = "5 5";
 
 private String data = "LMLMLMLMM";
 
 private String initalPos = "2 2 N";

 public String getBounds() {
  return bounds;
 }

 public String getData() {
  return data;
 }

 public String getInitialPos() {
  return initalPos;
 }
 
}
package nasa.implementation;

import nasa.main.Nasa;

public class TestMain {

 public static void main(String args[]) {
  try {
   TestSignal test = new TestSignal();

   Nasa n = new Nasa(test);

   n.execute();

   String finalPos = n.getFinalPosition();

   System.out.println("Final position is : " + finalPos);
  } catch (Exception e) {
   e.printStackTrace();
  }

 }
}
package nasa.exceptions;

public class OutOfRangeException extends Exception {

 /**
  * 
  */
 private static final long serialVersionUID = 1L;
 
 public OutOfRangeException(String msg){
  super(msg);
 }
 
}
package nasa.exceptions;

public class InvalidInputException extends Exception{

 /**
  * 
  */
 private static final long serialVersionUID = 1L;
 
 public InvalidInputException(){
  super();
 }
 
 public InvalidInputException(String msg){
  super(msg);
 }
 
}

TestMain would be the point of entry.

Cheers,
Bragaadeesh.

Tuesday, February 16, 2010

Reverse a number in Java/Reverse an integer in Java

This is a well known program but quite frequently asked. Given an integer, reverse it. There are many ways to do that. And the ideal way is to use an extra variable and using a loop. The program is very simple, please find it below.

package misc.integers;

public class RevNum {
 public static void main(String args[]){
  int sampleNum = 12345678;
  System.out.println("Input Num : "+sampleNum);
  int reversedNum = 0;
  while(sampleNum!=0){
   reversedNum = reversedNum*10 + sampleNum%10;
   sampleNum = sampleNum/10;
  }
  System.out.println("Reversed Num : "+reversedNum);
 }
}
//SAMPLE OUTPUT
//Input Num : 12345678
//Reversed Num : 87654321

Saturday, February 13, 2010

Given an array find any pair that sums up into a number

This problem is quite largely discussed and is very famous for its various ways to attack. This can be constrained in time and in space. The most primitive way of attacking this problem would yield an solution that runs in O(n2) time.
Let me define the problem clearly. Given an array of size n and a number X, you are supposed to find a pair of numbers that sums to X. Only one pair would be enough.
Lets see how we can find the solution for this in O(n) using a HashSet. Yes, HashSet is a costly data structure to use, but lets consider this primitive just due to the linear order it provides.

package dsa.arrays;

import java.util.HashSet;
import java.util.Set;

public class FindSumHashSet {
 public static void main(String a[]){
  FindSumHashSet sumFinder = new FindSumHashSet();
  sumFinder.begin();
 }
 
 public void begin(){
  int[] sampleArray = getRandomArray(20);
  int randomSum = sampleArray[15] + sampleArray[10];
  System.out.print("ARRAY : ");
  for(int i:sampleArray){
   System.out.print(i+" ");
  }
  System.out.println();
  findPair(sampleArray,randomSum);
 }

 public void findPair(int[] sampleArray, int randomSum) {
  Set<Integer> sampleArraySet = new HashSet<Integer>();
  for(int i=0;i<sampleArray.length;i++){
   sampleArraySet.add(sampleArray[i]);
   int valueToFind = randomSum - sampleArray[i];
   if(sampleArraySet.contains(valueToFind)){
    System.out.println("SUM : "+randomSum);
    System.out.println("PAIR : "+valueToFind+","+sampleArray[i]);
    break;
   }
  }
 }

 private int[] getRandomArray(int size) {
  int[] randomArray = new int[size];
  for(int i=0;i<size;i++){
   randomArray[i] = (int)(Math.random()*10);
  }
  return randomArray;
 }
}
//SAMPLE OUTPUTS

//ARRAY : 7 3 6 4 3 4 7 7 5 1 4 6 2 4 1 7 5 8 9 7 
//SUM : 11
//PAIR : 7,4

//ARRAY : 0 2 9 6 0 7 6 5 1 7 9 0 7 1 2 4 4 3 9 0 
//SUM : 13
//PAIR : 6,7


We shall improvise on this problem in space domain using fancy sorts and those we shall see in the coming posts.

Cheers,
Bragaadeesh

Least Common Ancestor without using a parent node in java

We already saw how to find the Least Common Ancestor for a binary tree. The problem gets a bit tricky when the node structure is like this.

class Node {
  Node left;
  Node right;
  int data;
 }
If you look at the above structure, there are no parent nodes and the given tree is not a Binary Search Tree which makes the problem all the more complicated.
To attack this problem we need to follow the below steps.
  1. Find the path of the first node using in-order traversal - Cost: O(n)
  2. Find the path of the second node using in-order traversal - Cost: O(n)
  3. Put the nodes of the first path in a set - Cost: O(logn)
  4. For each node in the second path check if it exists in the first path. The matching one would be the Least Common Ancestor - Cost: O(logn)
The total cost for this program would be - O(n) + O(n) + O(logn) + O(logn) = O(n).



Now for the java code. I am going to use the Trace Algorithm from the previous post for this solution to make life easier. Hope you were able to learn something.

package dsa.tree;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * Program to find the Least Common Ancestor without
 * for a Binary Tree (Not a BST). The Node does not have
 * a parent pointer. The direction of the tree is one sided
 * @author Braga
 *
 */
public class LCSBinaryTree {
 private Node n1,n2;
 
 public static void main(String args[]){
  LCSBinaryTree nodeFinder = new LCSBinaryTree();
  nodeFinder.find();
 }
 
 public void find(){
  Tree t = getSampleTree();
  Node commonParent = findCommonParent(t,n1,n2);
  if(commonParent == null){
   System.out.println("Common Parent for "+n1.data+" and "+n2.data+" is null");
  }else{
   System.out.println("Common Parent for "+n1.data+" and "+n2.data+" is "+commonParent.data);
  }
 }

 private Tree getSampleTree() {
  Tree bsTree = new BinarySearchTree();
  int randomData[] = {43,887,11,3,8,33,6,0,46,32,78,76,334,45};
  for(int i=0;i<randomData.length;i++){
   bsTree.add(randomData[i]);
  }
  n1 = bsTree.search(76);
  n2 = bsTree.search(334);
  return bsTree;
 }
 
 public Node findCommonParent(Tree t, Node node1, Node node2){
  TracePath pathTracer = new TracePath();
  
  /**
   * If either of the nodes is root, then there is no common
   * parent
   */
  if(node1.equals(t.getRoot()) || node2.equals(t.getRoot())){
   return null;
  }
  //Using the path tracer, find the path of two nodes in 2*O(n) time.
  Stack<Node> path1 = pathTracer.trace(t, node1);
  Stack<Node> path2 = pathTracer.trace(t, node2);
  
  //All that is left to do is to find the common parent now.
  Set<Node> firstPath = new HashSet<Node>();
  for(Node iNode:path1){
   firstPath.add(iNode);
  }
  while(!path2.isEmpty()){
   Node currentNode = path2.pop();
   if(firstPath.contains(currentNode)){
    if(!path2.isEmpty() && firstPath.contains(currentNode = path2.peek())){
     return path2.peek();
    }
    return currentNode;
   }
  }
  return null;
 }
}
//SAMPLE OUTPUTS
//Common Parent for 887 and 334 is 43
//Common Parent for 43 and 334 is null
//Common Parent for 6 and 334 is 43
//Common Parent for 76 and 334 is 46
Cheers,
Bragaadeesh.

Thursday, February 11, 2010

Trace path of a node in a BINARY TREE in Java

The problem is simple. Given a node, we should be able to show the path from the root to that node in a BINARY TREE (NOT A BINARY SEARCH TREE). This solution would help us how to traverse through a binary tree. Here I am going to do an inorder traversal. More on traversals on a binary tree can be found here.
Consider the following binary tree, we can see the path to be found and the node supplied to find it. We will be provided with a tree, its root and the node to be found.



76 is the item that we need to find. Although the example looks like a BINARY SEARCH TREE, we are not going to use the binary search tree way to find 76. So, we would have no other way than doing either of inorder, post-order or pre-order traversals. 
To attack this problem,we maintain a stack. The stack will always maintain the path. Whenever we encounter the node to be found, we will stop our process and the path in the current stack will give the path to be found. The solution for this problem shown would be : 43,887,46,78,76

I was having problem in returning from the recursive method in a proper manner. Thanks to the help of stackoverflow.com  and its code gurus, I was redirected to the right path.

Now, for the Java code part,
package dsa.tree;

import java.util.Stack;

public class TracePath {
 private Node n1;
 private Stack<Node> mainStack = null;
 
 public static void main(String args[]){
  TracePath nodeFinder = new TracePath();
  nodeFinder.find();
 }
 
 public void find(){
  Tree t = getSampleTree();
  trace(t,n1);
  for(Node iNode:mainStack){
   System.out.println(iNode.data);
  }
 }

 private Tree getSampleTree() {
  Tree bsTree = new BinarySearchTree();
  int randomData[] = {43,887,11,3,8,33,6,0,46,32,78,76,334,45};
  for(int i=0;i<randomData.length;i++){
   bsTree.add(randomData[i]);
  }
  n1 = bsTree.search(76);
  return bsTree;
 }
 
 public Stack<Node> trace(Tree t, Node node){
  mainStack = new Stack<Node>();
  trace(t.getRoot(),node);
  return mainStack;
 }
 
 private boolean trace(Node parent, Node node){
  mainStack.push(parent);
  if(node.equals(parent)){
   return true;
  }
  if(parent.left != null){
   if (trace(parent.left, node))
    return true;
  }
  if(parent.right!=null){
   if (trace(parent.right, node))
    return true;
  }
  mainStack.pop();
  return false;
 }
}

Wednesday, February 10, 2010

Find common parent in a binary search tree in Java

This is a very famous question that many already are aware of. But I wanted to give a comprehensive working program in java to implement this with illustration. Consider the following binary tree which infact is a binary search tree.



The idea is very simple. For the first node traverse up till you reach root, while doing so, put the nodes in a hash set. Then do the same for the second node ie, try to traverse towards the root. Amidst doing that search for the existence of this node in the hash set we already created for the first traversal.
The place where those two nodes matches will be the common node. For any two nodes in a tree, there will be at least one common node which will be the root. I have given two examples below. One having a node other than root as the common parent and the other with root as the common parent.
The green line shows the traversal of first node path. Red shows the second node's path. The intersection or the common parent is shown in a blue circle.





Now for the Java source.
package dsa.tree;

import java.util.HashSet;
import java.util.Set;

public class FindCommonNode {
 private Node n1,n2;
 
 public static void main(String args[]){
  FindCommonNode nodeFinder = new FindCommonNode();
  nodeFinder.find();
 }
 
 public void find(){
  Tree t = getSampleTree();
  Node commonParent = findCommonParent(t,n1,n2);
  System.out.println("Common Parent : "+commonParent.data);
 }

 private Tree getSampleTree() {
  Tree bsTree = new BinarySearchTree();
  int randomData[] = {43,887,11,3,8,33,6,0,46,32,78,76,334,45};
  for(int i=0;i<randomData.length;i++){
   bsTree.add(randomData[i]);
  }
  n1 = bsTree.search(45);
  n2 = bsTree.search(334);
  return bsTree;
 }
 
 public Node findCommonParent(Tree t, Node node1, Node node2){
  Set<Node> firstNodeAddrSet = new HashSet<Node>();
  //Traverse till root
  while(node1!=null){
   firstNodeAddrSet.add(node1);
   node1 = node1.parent;
  }
  while(!firstNodeAddrSet.contains(node2) && node2!=null){
   node2 = node2.parent;
  }
  return node2;
 }
}

The implementations for Tree and BinarySearchTree can be found here.

Cheers,
Bragaadeesh.

Monday, February 8, 2010

Program to find center of a singly linked list in java

This is a very common data structure problem, to find the center of a singly linked list. And the following is the famous solution. I have tried to give a comprehensive code coverage for this problem. The list count can either be odd or even. If its odd, we have only one value as the center and two for even case. I have covered both in the following code. Please do take a look at the SinglyLinkedList class for this program for reference.
This is how it works, there will be two pointers, one jumping once and another one jumping twice. When the double jumper ends/terminates, the single jump fellow's data would be the center.




package dsa.linkedlist;

public class FindCenterOfAList {
 public static void main(String args[]){
  FindCenterOfAList ratList = new FindCenterOfAList();
  ratList.test(10);//TEST FOR EVEN
  ratList.test(17);//TEST FOR ODD
  ratList.test(1);//TEST FOR SINGLE
  ratList.test(0);//TEST FOR ZERO OR LESS
 }
 
 public int[] getMidItem(SinglyLinkedList<Integer> listToCheck){
  Node<Integer> singleJump = listToCheck.start;
  Node<Integer> doubleJump = listToCheck.start;
  
  while(doubleJump.next!=null && doubleJump.next.next!=null){
   singleJump = singleJump.next;
   doubleJump = doubleJump.next.next;
  }
  
  int[] midItem = null;
  
  if(doubleJump.next == null){
   midItem = new int[1];
   midItem[0] = singleJump.data;
  }else if(doubleJump.next.next == null){
   midItem = new int[2];
   midItem[0] = singleJump.data;
   midItem[1] = singleJump.next.data;
  }
  
  return midItem;
 }
 
 private void test(int sampleSize){
  if(sampleSize<1){
   System.out.println("List is empty!");
   return;
  }
  SinglyLinkedList<Integer> randomList = giveMeAList(sampleSize);
  System.out.print("For list : ");stringify(randomList);
  int[] midItem = getMidItem(randomList);
  if(midItem.length == 1){
   System.out.println("Middle Item : "+midItem[0]);
  }else if(midItem.length == 2){
   System.out.println("Middle Items : "+midItem[0]+", "+midItem[1]);
  }
  System.out.println();
  
 }
 
 private SinglyLinkedList<Integer> giveMeAList(int length){
  SinglyLinkedList<Integer> sampleList = new SinglyLinkedList<Integer>();
  for(int i=1;i<=length;i++){
   sampleList.add(i);
  }
  return sampleList;
 }
 
 private void stringify(SinglyLinkedList<Integer> ratList) {
  for(int i=0;i<ratList.size;i++){
   System.out.print(ratList.getNodeAt(i).data+" ");
  }
  System.out.println();
 }
}
/*
-------OUTPUT--------
For list : 1 2 3 4 5 6 7 8 9 10 
Middle Items : 5, 6

For list : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 
Middle Item : 9

For list : 1 
Middle Item : 1

List is empty!
*/

Cheers,
Bragaadeesh

Sunday, February 7, 2010

Traversals in a binary search tree in Java

Now that we have seen how a binary tree is structured and doing a search operation over the same, lets look at how we can traverse over that data structure. There are three types of traversals that can be done.

  1. In-order traversal
  2. Pre-order traversal
  3. Post-order traversal
In-order traversal follows the route VISIT LEFT / VISIT ROOT / VISIT RIGHT. For a given binary tree, first visit the left most node and if no left node exists, visit the root and then visit the right. By this fashion traversal can be done. As a matter of fact, a simple In-order traversal in a binary search tree would give the sorted result! How cool is that!?

If you take a look at the above picture (yes, it looks a bit crowded, but you can track the numbers from 1 through twenty and the green ones are the values that we take), we start the process from the root and end up in the root. First search for the left most node. If there is none available take the immediate root and apply the same algorithm to the current node's right node. What i say may be a bit confusing but follow the numbers, you'l know.

Pre-order traversal follows the route VISIT ROOT / VISIT LEFT / VISIT RIGHT and the Post-order traversal follows the VISIT LEFT, VISIT RIGHT, VISIT ROOT.

For the above given example, the sequence that we get for various traversals is listed in the table below. You can cross-check it for yourself.

Order
Sequence
In-order
9, 12, 14, 17, 19, 23, 50, 54, 67, 72, 76
Pre-order
50, 17, 9, 14, 12, 23, 19, 76, 54, 72, 67
Post-order
12, 14, 9, 19, 23, 17, 67, 72, 54, 76, 50

In order traversal's application is clearly visible in this example (it gives a sorted list). Pre and post order traversals too have some powerful applications which we will look in the following posts.

Cheers,
Bragaadeesh.

Saturday, February 6, 2010

Columnar Transposition technique using TMS 320C 5402


Although this is totally not related to Java or data structures for which this blog is intended to, I thought I would post this here anyway. This is my project work that I did during college. This implements Columnar Transposition technique of encryption using TMS 320C 5402 which is Digital Signal Processor. Full project report for this can be found here (you may require to sign in using your Google Account). License would be free to distribute and use anywhere.

ABSTRACT

Aim:
            To implement the columnar transposition technique, a famous encryption technique on the input message using TMSC5402.

Columnar Transposition technique:
           
            Here the message or plain text is encrypted into a decrypted message using the random arrangement of the plain text. The arrangement of the resulting cipher text although seems random to the hacker (unauthorized intermediate person trying to read the message), it is in certain order and that order is been decided by a key. The key is simply numbers from 1 to ‘k’, where ‘k’ is the key size. The numbers are in some random order, mostly decided by the user or the sender. A simple example is shown below.

Plain text                     :           ABSTRACT

Let the key ‘k’ be 7, 3, 2, 8, 1, 5, 4, 6

1
2
3
4
5
6
7
8
A
B
S
T
R
A
C
T

Then the encrypted cipher text is (according to our key)

Cipher text                  :           CSBTARTA

            This is the simplest form. As we can see the decryption can be done using the secret key that we have used for the encryption.

7
3
2
8
1
5
4
6
C
S
B
T
A
R
T
A

Decrypted text                        :           ABSTRACT

            This might look simple since we have used a small message. But this message is almost impossible to hack when we use rows and columns and increase the key size. Lets see another example which could explain it better.

Plain text         :           PACK$MY$BOX$WITH$FIVE$DOZEN$LIQUOR$JUGS$


1
2
3
4
5
6
7
8
P
A
C
K
$
M
Y
$
B
O
X
$
W
I
T
H
$
F
I
V
E
$
D
O
Z
E
N
$
L
I
Q
U
O
R
$
J
U
G
S
$

Here we have used the ‘$’ symbol instead of spaces.

Cipher text      :           YTDQSCXIN$AOFER$HOU$PB$ZO$WELUK$V$JMI$IG

Now the encrypted message is impossible to hack. We can even apply again this method to the encrypted message to make it further random. In this case we can use the same key or other key. Same key can be used for simplicity.


Decryption:

Decryption is as simple as encryption. Just use the same key and rewrite the indexed values. Lets do the decryption for the Cipher text 1.

Cipher text      :           YTDQSCXIN$AOFER$HOU$PB$ZO$WELUK$V$JMI$IG


7
3
2
8
1
5
4
6
Y
C
A
$
P
$
K
M
T
X
O
H
B
W
$
I
D
I
F
O
$
E
V
$
Q
N
E
U
Z
L
$
I
S
$
R
$
O
U
J
G

Now the original table can be formed using the indexing technique as said earlier.

1
2
3
4
5
6
7
8
P
A
C
K
$
M
Y
$
B
O
X
$
W
I
T
H
$
F
I
V
E
$
D
O
Z
E
N
$
L
I
Q
U
O
R
$
J
U
G
S
$

Decrypted text            : PACK$MY$BOX$WITH$FIVE$DOZEN$LIQUOR$JUGS$



Advantages of Columnar Transposition technique :

            The columnar transposition technique of encryption is easy to understand but still complex to break by brutal force attack or cryptanalysis. This method get enhances as the key size is increased and by re applying the same technique. The hacker or the intermediate person cannot break this code unless otherwise he knows the method. Even he knows the method, it is still impossible to decrypt the encrypted cipher text without the knowledge of the key and the length of it and the no. of columnar transpositions that were made. As we’ve seen, we can enhance this technique by applying to the encrypted text over and over. In that case, we have to decrypt that many times we have encrypted and use the keys in the reverse order (FILO).



Columnar Transposition technique using TMSC5402:
           
            This technique can be implemented in the 5402 processor. We can enter the text message from a starting address say 3FFFh. The key is got from the user or is specified in some predefined location rather than getting in the run time. Then the transposition technique as given above is done using the instruction set available and is stored from say some starting address 43FFh. The data is transmitted serially(assumption) and is retrieved in the same manner.
            The decryption is done in the same scale. Here we assume that the received message is error free and is available from the location 43FFh. The decryption is similarly performed as encryption with slight difference and is put in some other location. We might be using a special symbol in order to mark the end of message. In this method we will be implementing depth1 columnar transposition for simplicity and ease of use.