29 January 2010

Binary Search Trees in Java

Now that we've seen how a binary tree is structured, lets take a look at one of the most common and powerful implementations - Binary Search Trees.
Binary Search trees are binary trees with some defined rules. Binary search trees can be formed only to nodes which are comparable. By Comparable, i mean which objects in real life that can be compared with each giving outputs as equal, greater or lesser. Numerals are the simplest example of comparables.
The rule of binary search tree follows that all the nodes that are lesser than the root will be on the left and the nodes that are greater than will be on the right. Equal valued nodes can come on either side.
Following is a simple illustration of a binary search tree formed using numerals



The following is a comprehensive Java code on how to construct and then manipulate from a binary tree.

The abstract Data Structure for Tree and the class Node.
package dsa.tree;

public interface Tree {
 public void add(int currentData);
 public Node search(int data);
}

package dsa.tree;

public  class Node {
 Node left;
 Node right;
 Node parent;
 int data;
}

package dsa.tree;

public class BinarySearchTree implements Tree{
 
 private Node root;
 
 public void add(int currentData){
  if(root == null){
   root = new Node();
   root.data = currentData;
   return;
  }
  add(currentData, root);
 }
 
 private void add(int currentData, Node position){
  if(currentData<position.data){
   if(position.left==null){
    position.left = new Node();
    position.left.data = currentData;
    position.left.parent = position;
    return;
   }
   add(currentData, position.left);
  }else{
   if(position.right==null){
    position.right = new Node();
    position.right.data = currentData;
    position.right.parent = position;
    return;
   }
   add(currentData, position.right);
  }
 }
 
 public Node search(int searchData){
  if(root == null){
   return null;
  }
  return search(searchData, root);
 }
 
 /*
  * O(log n) on average case
  */
 private Node search(int searchData, Node node){
  if(node.data == searchData){
   return node;
  }
  if(searchData < node.data){
   return search(searchData, node.left);
  }else{
   return search(searchData, node.right);
  }
 }
 
 public void printOrdered(){
  if(root == null){
   return;
  }
  printOrdered(root);
 }
 
 //DO A IN ORDER TRAVERSAL
 //VISIT LEFT
 //VISIT ROOT
 //VISIT RIGHT
 public void printOrdered(Node node){
  if(node.left != null){
   printOrdered(node.left);
  }
  System.out.println(node.data);
  if(node.right!=null){
   printOrdered(node.right);
  }
 }
 
 public void printValues(){
  print(root);
 }
 
 private void print(Node node){
  if(node == null){
   return;
  }else{
   print(node.left);
   print(node.right);
  }
 }
 
 public static void main(String args[]){
  BinarySearchTree bTree = new BinarySearchTree();
  for(int i=0;i<10;i++){
   int t = (int)(Math.random()*20);
   System.out.println(t);
   bTree.add(t);
  }
  bTree.printValues();
  for(int i=0;i<10;i++){
   int t = (int)(Math.random()*20);
   System.out.println("For i="+t+": "+bTree.search(t));
  }
  System.out.println();
  bTree.printOrdered();
 }
}

We shall discuss about the various features used in this program in the following post.

Bragaadeesh.

20 January 2010

Binary Trees in Java

One of the coolest data structures that is both highly efficient and very simple is a Binary Tree. Binary Tree is a data structure where a there will be a node having at most two child nodes.

Lets briefly define the concepts of a binary tree and lets take look at a working Java program in the future posts. Binary Tree has three pointers, one pointing to the left child, one pointing to the right child and one pointer to the parent. These are the terms we use with respect to a binary tree.

  • Root - The uppermost node in a binary tree. The parent node is always null for a root or we can say Root does not have a parent.
  • Child - A child is a sub-node to a parent node. A child can be either a left child or a right child
  • Leaf - A node which does not have any right or left nodes to it.
  • Node - constitutes to an element of a tree which has three pointers one to parent, one to right child and one to left child. And it has a place holder to store the data as well.

There are more jargons available with regard to a binary tree but as of now these terms are sufficient.

One of the most common misunderstanding that many have is to tell the definition of a "Binary search tree" when asked for a "Binary tree". They are not the same!!. Although we can say binary search tree is a form of binary tree with some condition. All Binary search trees are Binary trees and not vice versa!!!!

If asked to write a binary tree structure in Java, the following code would be more than sufficient. Note: This is just a raw structure.
public class BinaryTree{
 
 class Node {
  Node left;
  Node right;
  Node parent;
  int data;
 }
 
 private Node root;

}
More trees to come in the following posts.
Cheers,
Bragaadeesh.

19 January 2010

Quick Sort in Java

Quick sort is one of the coolest algorithms available in sorting and its performance is measured most of the time in O(nlogn), although the worst case sorting times of bubble sort and this are equal.
Inspite its worst case time, this always performs superiorly when the input is completely shuffled/randomized. This is one of the modest sorts available :).

Quick sort is an example of in-place sort. No extra space is needed as in merge sort where we have to use one full extra array to hold all the merged values. The only space that quick sort uses may be the counter variables and the extra space required for swapping.

Below is a pictorial representation of how this quick sort works,


I ran this sort for a well randomized data of million elements again and again and it beats the Merge sort hands down having a 75% quicker speed. Its always advisable to have shuffle the data upfront before running this algorithm.
Here is the source code for the same,
package dsa.sorting;

/**
 * A wonderful inplace sorting technique
 * @author Braga
 */
public class QuickSort {
 
 public static int SIZE = 1000000;

 public int[] sort(int[] input) {
  quickSort(input, 0, input.length-1);
  return input;
 }
 
 public static void main(String args[]){
  int[] a = new int[SIZE];
  for(int i=0;i<SIZE;i++){
   a[i] = (int)(Math.random()*SIZE);
  }
  QuickSort mNew = new QuickSort();
  long start = System.currentTimeMillis();
  mNew.sort(a);
  long end = System.currentTimeMillis();
  System.out.println("Time taken to sort a million elements : "+(end-start)+" milliseconds");
 }
 
 public void print(int[] inputData) {
  for(int i:inputData){
   System.out.print(i+" ");
  }
  System.out.println();
 }
 
 private void quickSort(int arr[], int left, int right) {
  int index = partition(arr, left, right);
  if (left < index - 1)
   quickSort(arr, left, index - 1);
  if (index < right)
   quickSort(arr, index, right);
 }
 
 private int partition(int arr[], int left, int right) {
  int i = left, j = right;
  int tmp;
  int pivot = arr[(left + right) / 2];
  while (i <= j) {
   while (arr[i] < pivot)
    i++;
   while (arr[j] > pivot)
    j--;
   if (i <= j) {
    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
    i++;
    j--;
   }
  }
  return i;
 }
}
//Time taken to sort a million elements : 156 milliseconds


Pros:
1) Efficient average case compared to any algorithm.
2) Recursive definition and popularity because of its high efficiency.

Cons:
1) Worst case scenario sucks.

As we discussed the worst case can be easily overcome by deliberately shuffling the input. I would rate quick sort as one of the best techniques available in sorting till date.

More sorting methods yet to come.
Cheers,
Bragaadeesh.

An inefficient implementation of Merge Sort in Java

It is not always enough just to understand how an algorithm works and do some theoretical calculations on the running time. We need to go to that extra step to actually implement for ourselves and check the performance. That is the only way to understand it piece by piece and that is the way that it remains in you forever.
This scenario happened to me with merge sort algorithm. I learnt how the algorithm actually worked and even implemented it in java. But found out that the performance of it was worse than a simple bubble sort!! I followed all the steps that was given in the 'theoretical' portion of the algorithm. But still my output was worse.
First take a brief look at the code
package dsa.sorting;

import java.util.Arrays;


public class MergeSort{

public static int SIZE = 100000;

public static void main(String args[]){
int[] a = new int[SIZE];
for(int i=0;i<SIZE;i++){
a[i] = (int)(Math.random()*SIZE);
}
long start = System.currentTimeMillis();
MergeSort mSort = new MergeSort();
mSort.sort(a);
long end = System.currentTimeMillis();
System.out.println("Time taken to sort a 100,000 elements : "+(end-start)+" milliseconds");
}

public int[] sort(int[] input) {
if(input.length<=1){
return input;
}
int[] left, right, result;

int mid = input.length/2;

left = Arrays.copyOfRange(input, 0, mid);
right = Arrays.copyOfRange(input,mid,input.length);

left = sort(left);
right = sort(right);

result = merge(left,right);

return result;
}

public int[] merge(int[] left, int[] right){
int[] result = new int[left.length+right.length];
int indexOfResult = 0;
while(left.length>0 && right.length>0){
if(left[0]<right[0]){
result[indexOfResult++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}else{
result[indexOfResult++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
if(left.length>0){
for(int i=0;i<left.length;i++){
result[indexOfResult++] = left[i];
}
}else{
for(int i=0;i<right.length;i++){
result[indexOfResult++] = right[i];
}
}
return result;
}
}
//Time taken to sort a 100,000 elements : 13401 milliseconds


After seeing the output, i kind of went nuts. I was clueless at the start on why my program was performing this bad! Later I realized that I was using up resources like anything through the Array.copyOfRange() method! It is a raw array copy which is simply not acceptable both in space and in time aspect.
Space - because of the in-numerous arrays that are getting created and Time - because of the heavy copy operations.

Later i realized i can use indexes to manipulate on the algorithms and just use only one extra array to do all my operations!! That is when i arrived at this.
A lesson well learnt!

Cheers,
Bragaadeesh.

17 January 2010

Merge Sort in Java

Now that we've examined one of the most simplest and inefficient sorting algorithms (Bubble Sort), lets have a look at O(nlogn) sorts. To start with, we shall look into Merge Sort.
Merge Sort follows divide and conquer technique. The following is a simple pictorial illustration of the same.

There will be two parts in this sort. One would be halving the input numbers O(logn) and the other would be merging them back O(n) which results in a comprehensive O(nlogn) time. Wait till you see the running version of this sort technique and the time taken to sort a million entries.

First for the code part,
package dsa.sorting;

public class MergeSortOptimized
{

    public static int SIZE = 1000000;

    public static void main(String args[])
    {
        int[] a = new int[SIZE];
        for (int i = 0; i < SIZE; i++) {
            a[i] = (int) (Math.random() * SIZE);
        }
        long start = System.currentTimeMillis();
        MergeSortOptimized mNew = new MergeSortOptimized();
        mNew.sort(a);
        long end = System.currentTimeMillis();
        System.out.println("Time taken to sort a million elements : "
                + (end - start) + " milliseconds");
    }

    public int[] sort(int[] input)
    {
        int[] temp = new int[input.length];
        mergeSort(input, temp, 0, input.length - 1);
        return input;
    }

    public void mergeSort(int[] fromArray, int[] toArray, int left, int right)
    {
        if (left < right) {
            int center = (left + right) / 2;
            mergeSort(fromArray, toArray, left, center);
            mergeSort(fromArray, toArray, center + 1, right);
            merge(fromArray, toArray, left, center + 1, right);
        }
    }

    public void merge(int[] fromArray, int[] toArray, int leftPos,
            int rightPos, int rightEnd)
    {
        int leftEnd = rightPos - 1;
        int tempPos = leftPos;

        int numElements = rightEnd - leftPos + 1;

        while (leftPos <= leftEnd && rightPos <= rightEnd) {
            if (fromArray[leftPos] < fromArray[rightPos]) {
                toArray[tempPos++] = fromArray[leftPos++];
            }
            else {
                toArray[tempPos++] = fromArray[rightPos++];
            }
        }

        while (leftPos <= leftEnd) {
            toArray[tempPos++] = fromArray[leftPos++];
        }
        while (rightPos <= rightEnd) {
            toArray[tempPos++] = fromArray[rightPos++];
        }

        for (int i = 0; i < numElements; i++, rightEnd--) {
            fromArray[rightEnd] = toArray[rightEnd];
        }

    }

}
// Time taken to sort a million elements : 247 milliseconds

As you may observe, the above technique just took 247 milliseconds to sort a million elements whereas the bubble sort tooks almost 28 seconds to sort a hundred thousand elements!!!!! This is due to the logarithmic order of the sort.

Pros:
1) Works in O(nlogn) time.
2) Worst case of merge sort is equal to best case of a quick sort! (We shall discuss more about in the coming sections).

Cons:
1) Consumes extra space.
2) Due to the recursive nature of the algorithm, may eat up stack.

Thanks for reading my post. We shall explore more sorting techniques in the coming days. Till then, bye for now from,
Bragaadeesh.

Bubble Sort in Java

Bubble sort is the most simplest form of sorts available. In real lives, the bubbles formed under water tend to come up to the surface. Larger the bubble, faster it will come up. Same way in this sorting technique, we would try to push the larger value up in case of descending or vice versa.

Pros:
1. Simple to implement.
2. Very easy to understand.

Cons:
1. Runs in O(n2) complexity.
2. Severe performance issues if the sample size increases.

The java code for this sorting technique is as follows,
package dsa.sorting;

public class BubbleSort {

 public static int SIZE = 100000;

 public static void main(String args[]) {
  int[] a = new int[SIZE];
  for (int i = 0; i < SIZE; i++) {
   a[i] = (int) (Math.random() * SIZE);
  }
  long start = System.currentTimeMillis();
  BubbleSort mNew = new BubbleSort();
  mNew.sort(a);
  long end = System.currentTimeMillis();
  System.out.println("Time taken to sort a 100000 elements : "
    + (end - start) + " milliseconds");
 }

 public int[] sort(int[] input) {
  int temp;
  for (int i = 0; i < input.length; i++) {
   for (int j = i; j < input.length; j++) {
    if (input[i] > input[j]) {
     temp = input[i];
     input[i] = input[j];
     input[j] = temp;
    }
   }
  }
  return input;
 }
}
// Time taken to sort a 100000 elements : 28554 milliseconds

You may see from the above example that it takes insanely higher time for sorting only a hundred thousand elements. 29 seconds is a very poor outcome. We will look into O(nlogn) sort types on why and how it reduces this running time.

Cheers,
Bragaadeesh.

Java Sorting techniques

I thought i would start exploring the Sorting mechanisms in Data Structures and try to comprehensively implement them in Java.

We have many types of sorting techniques readily available and there are numerous amount of resources in the net with ready made coding in all the common languages. What I have done here is, did some research on each of the sorting techniques and tried to present the most commonly used sorting techniques with its pros and cons. I have not dealt or dug deep into 'alternate' techniques but have provided a sufficient overview with running code.

Today I will present two of the most familiar sorting techniques namely bubble sort and merge sort and discuss its pros and cons in the following posts.

Cheers,
Bragaadeesh

16 January 2010

Find Loops in a Singly Linked List in Java

This is a very simple yet efficient program written in Java to find whether a Singly Linked List has loops or not. If you need the SingleLinkedList class, please click this link.
The logic is simple, there will be two pointers one traversing once and the other traversing twice. If at all we get a NullPointerException in the process we can be very sure that there are no loops. In the other case, there is definitely a loop. You may play with it. Dont forget to copy this class.
package dsa.linkedlist;

public class FindLoopsInLinkedList {
 public static void main(String args[]){
  FindLoopsInLinkedList finder = new FindLoopsInLinkedList();
  SinglyLinkedList<Integer> randomList = finder.giveMeALoopedList();
  System.out.println("Loop Existence : "+finder.doesLoopExist(randomList));
 }
 
 public boolean doesLoopExist(SinglyLinkedList<Integer> listToCheck){
  Node<Integer> singleJump = listToCheck.start;
  Node<Integer> doubleJump = listToCheck.start;
  
  try{
   while(true){
    singleJump = singleJump.next;
    doubleJump = doubleJump.next.next;
    if(singleJump == doubleJump){
     return true;
    }
   }
  }catch(NullPointerException ne){
   return false;
  }
 }
 
 private SinglyLinkedList<Integer> giveMeALoopedList(){
  SinglyLinkedList<Integer> sampleList = new SinglyLinkedList<Integer>();
  //First Insert randomly ten elements in a linked list
  for(int i=0;i<9;i++){
   sampleList.add(i);
  }
  //Force the list to have a loop in this fashion
  Node<Integer> lastNode = sampleList.getLast();
  lastNode.next = sampleList.getNodeAt(3);
  return sampleList;
 }
}
//-------OUTPUT--------
//Loop Existence : true

Cheers!
Bragaadeesh.

Java Program to reverse a Singly Linked List

Hi folks,

I have written an efficient way to reverse a Singly Linked List using three pointers/nodes for traversal/temporary purposes. I have given a pictorial representation of what happens with near, mid and far pointer. The program is mostly self explanatory. Remember, we are using our implementation of Singly Linked List. You may visit this link if you need that class.



Note : You may click on the above image to get a clearer picture.

Now, for the source code.


Cheers,
Bragaadeesh.

Singly Linked Lists in Java

Hi folks,

Linked list is one of the most discussed data structures and is frequently asked in interviews in many higher level companies like google, amazon etc., I have tried to implement the Single List comprehensively in Java.

Don't we already have a LinkedList in Java?
Yes we do. But the one that I have given here is a Single Linked List which means that we can traverse only one side. This code will be the base for all the problems in linked list that we are going to solve. I have provided both the class and its testcase.

Supporting Node datastructure for the singly linked list
package dsa.linkedlist;

public class Node<E>{
 E data;
 Node<E> next;
}

The SingleLinkedList class,
package dsa.linkedlist;

/**
 * This is a singly linked list with no prev pointer.
 * @author Braga
 * @param <E>
 */
public class SinglyLinkedList<E> {
 
 Node<E> start;
 int size;
 
 public SinglyLinkedList(){
  start = null;
  size = 0;
 }
 
 //insertAtLast
 public void add(E data){
  insertAtLast(data);
 }
 
 public void insertAtLast(E data){
  if(size==0){
   start = new Node<E>();
   start.next = null;
   start.data = data;
  }else{
   Node<E> currentNode = getNodeAt(size-1);
   Node<E> newNode = new Node<E>();
   newNode.data = data;
   newNode.next = null;
   currentNode.next = newNode;
  }
  size++;
 }
 
 public void insertAtFirst(E data){
  if(size==0){
   start = new Node<E>();
   start.next = null;
   start.data = data;
  }else{
   Node<E> newNode = new Node<E>();
   newNode.data = data;
   newNode.next = start;
   start = newNode;
  }
  size++;
 }
 
 public Node<E> getNodeAt(int nodePos) throws ArrayIndexOutOfBoundsException{
  if(nodePos>=size || nodePos<0){
   throw new ArrayIndexOutOfBoundsException();
  }
  Node<E> temp = start;//Move pointer to front
  int counter = 0;
  for(;counter<nodePos;counter++){
   temp = temp.next;
  }
  return temp;
 }
 
 public void insertAt(int position, E data){
  if(position == 0){
   insertAtFirst(data);
  }else if(position==size-1){
   insertAtLast(data);
  }else{
   Node<E> tempNode = getNodeAt(position-1);
   Node<E> newNode = new Node<E>();
   newNode.data = data;
   newNode.next = tempNode.next;
   tempNode.next = newNode;
   size++;
  }
 }
 
 public Node<E> getFirst(){
  return getNodeAt(0);
 }
 
 public Node<E> getLast(){
  return getNodeAt(size-1);
 }
 
 public E removeAtFirst(){
  if(size==0){
   throw new ArrayIndexOutOfBoundsException();
  }
  E data = start.data;
  start = start.next;
  size--;
  return data;
 }
 
 public E removeAtLast(){
  if(size==0){
   throw new ArrayIndexOutOfBoundsException();
  }
  Node<E> tempNode = getNodeAt(size-2);
  E data = tempNode.next.data;
  tempNode.next = null;
  size--;
  return data;
 }
 
 public E removeAt(int position){
  if(position==0){
   return removeAtFirst();
  }else if(position == size-1){
   return removeAtLast();
  }else{
   Node<E> tempNode = getNodeAt(position-1);
   E data = tempNode.next.data;
   tempNode.next = tempNode.next.next;
   size--;
   return data;
  }
 }
 
 public int size(){
  return size;
 }
 
 public String toString(){
  if(size==0){
   return "";
  }else{
   StringBuilder output = new StringBuilder();
   Node<E> tempNode = start;
   while(tempNode.next!=null){
    output.append(tempNode.data).append(", ");
    tempNode = tempNode.next;
   }
   output.append(tempNode.data);
   return output.toString();
  }
 }
 
}


The JUnit test for the SingleLinkedList class
package dsa.linkedlist;

import junit.framework.TestCase;

public class SinglyLinkedListTest extends TestCase{
 
 private int labRats;
 
 public void setUp(){
  labRats = 10;
 }
 
 public void testAdd(){
  SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
  sampleList.add(100);
  assertEquals(sampleList.getLast().data.intValue(),100);
 }
 
 public void testInsertAtLast(){
  SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
  sampleList.insertAtLast(100);
  assertEquals(sampleList.getLast().data.intValue(),100);
 }
 
 public void testInsertAtFirst(){
  SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
  sampleList.insertAtFirst(100);
  assertEquals(sampleList.getFirst().data.intValue(),100);
 }
 
 public void testInsertAt(){
  SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
  sampleList.insertAt(2, 100);
  assertEquals(sampleList.getNodeAt(2).data.intValue(),100);
 }
 
 public void testGetNodeAt(){
  SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
  assertEquals(sampleList.getNodeAt(2).data.intValue(),2);
 }
 
 public void testGetFirst(){
  SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
  assertEquals(sampleList.getFirst().data.intValue(),0);
 }
 
 public void testGetLast(){
  SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
  assertEquals(sampleList.getLast().data.intValue(),labRats-1);
 }
 
 public void testRemoveAtFirst(){
  SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
  int returnValue = sampleList.removeAtFirst();
  assertEquals(returnValue,0);
  assertEquals(sampleList.getFirst().data.intValue(),1);
 }
 
 public void testRemoveAtLast(){
  SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
  int returnValue = sampleList.removeAtLast();
  assertEquals(returnValue,labRats-1);
  assertEquals(sampleList.getLast().data.intValue(),labRats-2);
 }
 
 public void testRemoveAt(){
  SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
  int returnValue = sampleList.removeAt(4);
  assertEquals(returnValue,4);
  assertEquals(sampleList.getNodeAt(4).data.intValue(),5);
 }
 
 public void testToString(){
  SinglyLinkedList<Integer> sampleList = getLabRatList(labRats);
  assertEquals(sampleList.toString(),"0, 1, 2, 3, 4, 5, 6, 7, 8, 9");
 }
 
 private SinglyLinkedList<Integer> getLabRatList(int count){
  SinglyLinkedList<Integer> sampleList = new SinglyLinkedList<Integer>();
  for(int i=0;i<count;i++){
   sampleList.add(i);
  }
  return sampleList;
 }
}


Cheers,
Bragaadeesh.

15 January 2010

Java/C++ Program to reverse words in a sentence but still maintain the space position

This is a slight modification to the previous program. Here we should maintain the space as well. For doing that, I am simultaneously tracking the spaces and the words. I have made an assumption that there wont be any trailing or leading spaces in the sentence as such. Even if its there, a slight tweak of the following code would give me the output i desire.

package dsa.stringmanipulation;

import java.util.ArrayList;
import java.util.List;

public class RevWordWhiteSpace {

public static final String SPACE = " ";

private List<Integer> spaceTracker = new ArrayList<Integer>();
private List<String> wordTracker = new ArrayList<String>();

public static void main(String args[]){
RevWordWhiteSpace rev = new RevWordWhiteSpace();
System.out.println(rev.getRevWithWhiteSpace("This     should  maintain the space in place"));
}

/*
* Lets assume that our input text will not have any spaces before and after
*/
public String getRevWithWhiteSpace(String inputText){
if(inputText!=null && inputText.length()>0){
int lenOfText = inputText.length();
if(lenOfText==1){
return inputText;
}else{
constructLists(inputText);
StringBuilder output = new StringBuilder();
for(int i=wordTracker.size()-1,j=0; i>0; i--,j++){
output.append(wordTracker.get(i));
output.append(constructSpace(spaceTracker.get(j)));
}
output.append(wordTracker.get(0));
return output.toString();
}
}else{
System.out.println("Invalid Sentence");
return null;
}
}

private CharSequence constructSpace(Integer integer) {
String op="";
for(int i=0;i<integer;i++){
op+=" ";
}
return op;
}

private void constructLists(String inputText) {
int tempBufSpace = 0;
String bufWord = "";
for(int i=0;i<inputText.length();i++){
if(inputText.charAt(i)!=' '){
if(tempBufSpace>0){
spaceTracker.add(tempBufSpace);
tempBufSpace=0;
}
bufWord+=inputText.charAt(i);
}else{
if(bufWord.length()>0){
wordTracker.add(bufWord);
bufWord = "";
}
tempBufSpace++;
}
}
if(bufWord.length()>0){
wordTracker.add(bufWord);
}
}
}

//The output produced would be
//place     in  space the maintain should This

Also code in C++,

#include <iostream>
#include <string.h>

using namespace std;

void str_rev(char s[], int start, int end)
{
    int len = end - start;
    for(int i=0;i<len/2;i++)
    {
        char t = s[i+start];
        s[i+start] = s[end-i-1];
        s[end-i-1] = t;
    }
}

int main()
{
    char a[] = "my     name is prabhu";
    cout << "[" << a << "] ==> ";
    str_rev(a,0,strlen(a));

    cout << "[" << a << "] ==> ";

    int start_index = 0;
    for(size_t i=0;i<=strlen(a);i++)
    {
      if(a[i] == ' ' || a[i] == '\0')
      {
         str_rev(a,start_index,i);
         start_index = i+1;
      }
    }
    cout << "[" << a << "] ==> ";
    char b[strlen(a)+1];
    int i=0, k=0, j=strlen(a)-1;
    while(a[i] != '\0')
    {
        if(a[i] != ' ')
            b[k++] = a[i];
        else
        {
            while(a[j] != ' ' && j>=0)
                j--;
            while(a[j--] == ' ' && j>=0)
                b[k++] = ' ';
        }
        i++;
    }
    b[k] = '\0';
    cout << "[" << b << "]" << endl;
  
    return 0;
}


Cheers,
Bragaadeesh.

Java/C++ Program to reverse the words in a sentence

As an attempt to preparation for data structures and ready-to-code for programs, I thought I will start coding on my own and publish it here. Any discrepancies, bugs if you may find , plz leave a comment.

So, this is a program in java written to reverse the words in a sentence. I thought this was pretty easy using inbuilt method such as split() and StringBuilder(). I could have 'not' used them, but again its writing the whole JFC (Java Foundation Class) implementation. Screw it :), I am on a journey to write lots of programs such as this...

package dsa.stringmanipulation;

public class SentenceReverser {

    public static final String SPACE = " ";

    public static void main(String args[]) {
        SentenceReverser rev = new SentenceReverser();
        System.out.println(rev
                .printReversed("This  is my first attempt at a program in ds"));
    }

    public String printReversed(String inputText) {
        if (inputText != null && inputText.length() > 0) {
            int lenOfText = inputText.length();
            if (lenOfText == 1) {
                return inputText;
            } else {
                String[] texts = inputText.split(SPACE);
                StringBuilder output = new StringBuilder();
                for (int i = texts.length - 1; i > 0; i--) {
                    output.append(texts[i]).append(SPACE);
                }
                output.append(texts[0]);
                return output.toString();
            }
        } else {
            System.out.println("Invalid Sentence");
            return null;
        }
    }
}


Now, for the code in C++,

#include <iostream>

using namespace std;

void str_rev(char s[], int start, int end)
{
        int len = end - start;
        for(int i=0;i<len/2;i++)
        {
                char t = s[i+start];
                s[i+start] = s[end-i-1];
                s[end-i-1] = t;
        }
}

int main()
{
        char a[] = "my name is prabhu";
        cout << "[" << a << "] ==> ";

        str_rev(a,0,strlen(a));

        int start_index = 0;
        for(size_t i=0;i<=strlen(a);i++)
        {
                if(a[i] == ' ' || a[i] == '\0')
                {
                        str_rev(a,start_index,i);
                        start_index = i+1;
                }
        }
        cout << "[" << a << "]" << endl;
}

Cheers,
Bragaadeesh.