Ramblings of a techie

Problem:
Generating Fibonacci series using only one variable.

There are many ways to achieve this. I have given three ways to do this in the following methods.

Method #1:
We can have a simple function to do this.

Method #2:
The following recursive function would do the job.

Method #3:
The following one works great as well!

Cheers!!
Jack

This problem may look very simple and indeed it is because the solution can be arrived at very easily. But to arrive at a clean and an efficient may take sometime. This question is asked to test the cleanliness and simplicity in providing solutions. Enough hype, here is the question.







The solution to this problem is seemingly simple and the same has been implemented in Java below.


Cheers!
Bragaadeesh.

This problem again is asked as a coding question in one of the top companies. I have provided the solution for this in C++.

Question:
Given an array of integers (unsigned integers > 0), find three numbers in that array which form the maximum product. [O(nlogn), O(n) solutions are available ].
int[] MaxProduct(int[] input, int size)

Solution:
The program expects both the solutions, one in O(n) time and the other one in O(nlogn). To achieve O(nlogn), sort the entire set by using quick sort or merge sort and take the top three values.
I have provided the code for the O(n) case. It does a single scan on the entire set of elements once and finds the largest three numbers with the logic as shown below.

//============================================================================
// Name : three_largest_elems.cpp
// Author : Prabhu Jayaraman (My honorable room mate, college mate, work colleague)
// Version : v1
// Copyright : open
// Description : To find three largest numbers in an array in C++, Ansi-style
//============================================================================
#include <iostream>
using namespace std;
int main()
{
 int a[10] = {1,2,33,4,15,6,7,28,9,10};
 int largest_1 = 0, largest_2 = 0, largest_3 = 0;
 for(int i=0;i<10;i++)
 {
 if(a[i] > largest_3 && a[i] < largest_2)
 {
 largest_3 = a[i];
 }
 else if(a[i] > largest_2 && a[i] < largest_1)
 {
 largest_3 = largest_2;
 largest_2 = a[i];
 }
 else if(a[i] > largest_1)
 {
 largest_3 = largest_2;
 largest_2 = largest_1;
 largest_1 = a[i];
 }
 }
 cout << "largest :" << largest_1 << endl;
 cout << "2nd largest :" << largest_2 << endl;
 cout << "3rd largest :" << largest_3 << endl;
 return 0;
}

Cheers!!
Bragaadeesh

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.

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.

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.

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.


TestMain would be the point of entry.

Cheers,
Bragaadeesh.

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.

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(n²) 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.

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

Cheers,
Bragaadeesh

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.

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;
 }
}

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.





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.

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

This is one of the problems that have been asked in a company called Progress Software, Hyderabad. I have posted the question as well as the working Java code for the same.

Question

Sports Associations in India
-------

The Sports Associations in India (SAI) wants to choose 2 teams of 4 people each
to send to Asain games. There are 13 people who want to be members of
the teams. The SAI tries grouping them in various ways to see which
athletes perform well together. Each grouping gets one test run on the
test track and their time is recorded. Your task is to help the SAI
choose two disjoint teams of 4 such that the sum of their practice times
is minimal.

Input
-----

There will be several input instances. The first line of each instance
gives the total number of practice runs. This will be followed by n lines.
Each of those lines will contain 5 numbers: p1 p2 p3 p4 t
t is the time taken (in milliseconds) by the team consisting of p1, p2, p3 and p4.

The time taken will not be more than 2 minutes.

The end of the input will be indicated by a line with n=0.

Output
------

Output the best total time for the two teams that you choose.
If it is impossible to choose two disjoint teams from the test runs given, output -1.

Sample Input
------------

6
1 2 3 4 30000
10 11 12 13 15000
5 6 7 8 37800
1 5 10 12 20000
5 6 9 11 43000
1 9 12 13 11000
3
1 4 7 9 10000
3 5 7 11 17890
6 7 12 13 20000
0

Sample Output
-------------

45000
-1

Along this you will get a file consisting of an input and they ask you to send the output. I am sharing the solution to this problem.

package main;
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
public class Main {
 /**
 * @param args
 */
 public static void main(String[] args) {
 new Main().start();
 }
 private ArrayList<Event> events = null;
 public static final String DIR = "D:/Question2/";
 private String filename = DIR + "input.txt";
 public void start() {
 readInput();
 printInput();
 solve();
 writeToFile();
 }
 
 private void printInput() {
 Event eventRound = null;
 for (int i = 0; i < events.size(); i++) {
 eventRound = events.get(i);
 System.out.println("Round Count: " + eventRound.roundCount);
 System.out.println("Rounds : " + eventRound.toString());
 }
 }
 
 public void readInput() {
 FileRead read = new FileRead(filename);
 events = read.getEvents();
 }
 public void solve() {
 Event eventRound = null;
 for (int i = 0; i < events.size(); i++) {
 eventRound = events.get(i);
 eventRound.findMinTime();
 eventRound.printVal();
 }
 }
 
 private void writeToFile() {
 try {
 BufferedWriter out = new BufferedWriter(new FileWriter(DIR
 + "output.txt"));
 Event eventRound = null;
 for (int i = 0; i < events.size(); i++) {
 eventRound = events.get(i);
 out.write(eventRound.minTime+System.getProperty("line.separator"));
 }
 out.close();
 }catch(IOException e) {
 e.printStackTrace();
 }
 }
}

package main;
import java.util.StringTokenizer;
/**
 * Class to reprsent a round. A round consist of an array of players and time taken 
 * by them on that particular round.
 * @author Bragadeesh
 *
 */
public class Round {
 public int[] players;
 public int time;
 
 /**
 * Represents the player count for the event
 */
 public static final int PLAYER_COUNT = 4;
 
 public Round(String line){
 StringTokenizer tokens = new StringTokenizer(line);
 players = new int[PLAYER_COUNT];
 for(int i=0;i<PLAYER_COUNT;i++){
 players[i] = Integer.parseInt(tokens.nextToken());
 }
 time = Integer.parseInt(tokens.nextToken());
 }
 
 /**
 * Returns the formatized string for a particular Round
 */
 public String toString(){
 String op = "";
 for(int i=0;i<players.length;i++){
 op = op + players[i] + " ";
 }
 
 op = op + time;
 
 return "[" + op + "]";
 }
 
}

package main;
/**
 * Event is a class which is comprises an array of Rounds.
 * @author Bragadeesh
 *
 */
public class Event {
 
 public Round[] rounds;
 public int roundCount;
 private static final int MAX_VAL = 99999999;
 
 public int minTime = -1;
 
 /**
 * Variable used to show the the minimum round1 should there be any
 */
 public Round minRound1;
 
 
 /**
 * Variable used to show the the minimum round2 should there be any
 */
 public Round minRound2;
 
 
 /**
 * Returns the formatized string for a particular Event
 */
 public String toString(){
 
 String op = "";
 
 for(int i=0;i<rounds.length;i++){
 op+=rounds[i].toString();
 }
 
 return "{" + op + "}";
 }
 
 /**
 * Method to calculate the minimum time
 * @return
 */
 public int findMinTime(){
 int min = MAX_VAL;
 Round roundA = null;
 Round roundB = null;
 
 for(int i=0;i<roundCount;i++){
 for(int j=0;j<roundCount&&i!=j;j++){
 roundA = rounds[i];
 roundB = rounds[j];
 
 if(!disjoint(roundA, roundB)){
 if(roundA.time + roundB.time < min){
 minRound1 = roundA;
 minRound2 = roundB;
 }
 min = Math.min(roundA.time + roundB.time, min);
 }
 }
 }
 
 if(min != MAX_VAL){
 minTime = min; 
 }
 
 return minTime;
 }
 
 /**
 * Method to print the Round values and the minimum time for a 
 * given event. Prints -1 if there is no minimum time set.
 */
 public void printVal(){
 if(minRound1!=null){
 System.out.println(minRound1.toString());
 System.out.println(minRound2.toString());
 System.out.println(minTime);
 }else{
 System.out.println("-1");
 }
 }
 
 /**
 * Simple bubble sort that does the sorting of the events based on the round time
 * @return void
 */
 public void sortRounds() {
 for(int i=0;i<roundCount;i++){
 for(int j=i;j<roundCount;j++){
 if(rounds[i].time > rounds[j].time){
 Round temp = rounds[i];
 rounds[i] = rounds[j];
 rounds[j] = temp;
 }
 }
 }
 }
 
 /**
 * Given two arbitrary rounds A and B, returns whether they are disjoint or not
 * @param roundA
 * @param roundB
 * @return boolean value whether given set is disjoint or not
 */
 public boolean disjoint(Round roundA, Round roundB){
 for(int i=0;i<Round.PLAYER_COUNT;i++){
 for(int j=0;j<Round.PLAYER_COUNT;j++){
 if(roundA.players[i] == roundB.players[j]){
 return true;
 }
 }
 }
 return false;
 }
 
}

package main;
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class FileRead {
 
 private String filename = null;
 private ArrayList<Event> events;
 
 public FileRead(String filename){
 this.filename = filename;
 events = new ArrayList<Event>();
 load();
 }
 
 private void load(){
 
 FileInputStream fstream = null;
 DataInputStream in = null;
 BufferedReader br = null;
 Event event = null;
 
 
 try {
 fstream = new FileInputStream(filename);
 in = new DataInputStream(fstream);
 br = new BufferedReader(new InputStreamReader(in));
 
 for(;;){
 event = new Event();
 event.roundCount = Integer.parseInt(br.readLine());
 if(event.roundCount == 0){
 break;
 }
 event.rounds = new Round[event.roundCount];
 for(int i=0;i<event.roundCount;i++){
 event.rounds[i] = new Round(br.readLine());
 }
 event.sortRounds();
 events.add(event);
 }
 
 
 } catch (Exception e) {
 System.err.println("Error: " + e.getMessage());
 } finally{
 try {
 in.close();
 } catch (IOException e) {
 e.printStackTrace();
 }
 }
 }
 
 public ArrayList<Event> getEvents(){
 return events;
 }
}

Input file : Input.txt
Output file : Output.txt
Cheers,
Bragaadeesh.

Although Java is my forte, I started my early days by coding with C. The below program is to get the difference in days between two dates. The program is simple and has well defined comments to explain for itself. Thought I would post it here.

#include<stdio.h>
#include<conio.h>
#include<dos.h>
int datecmp(struct date,struct date);
int leap(int);
void main()
{
 struct date a,b;
 int leep;
 clrscr();
 b.da_year=2000;
 b.da_mon=7;
 b.da_day=1;
 getdate(&a);
 printf("%u\t%u\t%u\t",b.da_day,b.da_mon,b.da_year);
 printf("\n%u\t%u\t%u\t",a.da_day,a.da_mon,a.da_year);
 datecmp(a,b);
 /*if((leep=leap(b.da_year))==1)
 printf("\nThe year is leep year");
 else
 printf("\nThe year is an ordinary year");*/
 getch();
}
int datecmp(struct date a,struct date b)
{
 struct date c;
 char days[12]={31,28,31,30,31,30,31,31,30,31,30,31};
 int y=365;
 int i,j;
 int td=0;
 c.da_year=a.da_year-b.da_year;
 c.da_mon=a.da_mon-b.da_mon;
 if(c.da_year==0)//SAME YEAR BUT DIFFERENT MONTH OR SAME MONTH
 {
 if(c.da_mon==0)
 td=a.da_day-b.da_day;
 else
 {
 for(i=0,j=b.da_mon;i<(c.da_mon-1);i++,j++)
 td+=days[j];
 td+=days[b.da_mon-1]-b.da_day;
 td+=a.da_day-1;
 }
 }
 else if(c.da_year>1 && c.da_mon>1)//YEAR DIFF B/W TWO INPUTS IS >THAN 1 YEAR
 {
 if(b.da_mon<3 && leap(b.da_year)==1)
 td=1;
 else
 td=0;
 for(i=0,j=b.da_year+1;i<(c.da_year);i++,j++)
 td=td+365+leap(j);
 if(c.da_mon==0)
 td+=a.da_day-b.da_day;
 else
 {
 for(i=0,j=b.da_mon;i<(c.da_mon-1);i++,j++)
 td+=days[j];
 td+=days[b.da_mon-1]-b.da_day;
 td+=a.da_day-1+leap(a.da_year);
 }
 }
 else if(c.da_year==1)//YEAR DIFF B/W TWO INPUTS IS==1 YEAR
 {
 if(c.da_mon>0)
 {
 if(b.da_mon>1 && leap(b.da_year)==1)
 td=1;
 else
 td=0;
 for(i=0,j=b.da_year+1;i<(c.da_year);i++,j++)
 td=td+365+leap(j);
 if(c.da_mon==0)
 td+=a.da_day-b.da_day;
 else
 {
 for(i=0,j=b.da_mon;i<(c.da_mon-1);i++,j++)
 td+=days[j];
 td+=days[b.da_mon-1]-b.da_day;
 td+=a.da_day-1+leap(a.da_year);
 }
 }
 else if(c.da_mon==0 && c.da_day>0)
 {
 if(b.da_mon>1)
 td=0;
 else
 td=1;
 for(i=0,j=b.da_year+1;i<(c.da_year);i++,j++)
 td=td+365+leap(j);
 td+=a.da_day-b.da_day;
 }
 }
 else if(c.da_year==1)
 {
 }
 printf("\n The days are %d",td);
 getch();
}
int leap(int year)//LEAP YEAR FUNCTION
{
 if(year%4==0)
 {
 if(year%100==0)
 {
 if(year%400==0)
 return(1);
 else
 return(0);
 }
 else
 return(1);
 }
 else
 return(0);
}

Cheers,
Bragaadeesh.

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.

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.

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.

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 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(n²) 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.