Wednesday, October 24, 2012

Implement circular queue using array.


/**
 * This class implements Circular queue using array of size N.
 */
public class CircularQueue
{
/** Array used for circular queue.*/
int[] _userArray;
/** Sizeof the array/queue.*/
int _size;
/** Head location.*/
int _head;
/** Tail location.*/
int _tail;
/** Number of elements on queue.*/
int _count;

/**
* Constructor.
* @param size Sizeof queue/array.
*/
public CircularQueue(int size)
{
if (size < 0)
{
throw new IllegalArgumentException("Invalid Size Requested!");
}
_size = size;
}

/**
* Initialize all data.
*/
public void initialize()
{
_userArray = new int[_size];
_head = _count =0;
_tail = -1;
}

/**
* Enqueue element on the queue.
* @param item Item to enque.
* @throws Exception If queue is full.
*/
public void enqueue(int item) throws Exception
{
if (_count == _size)
{
throw new Exception("Queue is Full");
}
// add element
synchronized (_userArray)
{
_userArray[(++_tail) % _size] = item;
_count ++;
}
}

/**
* Dequeue element from queue.
* @return Item.
* @throws Exception If queue is empty.
*/
public int dequeue() throws Exception
{
int retVal;
if (_count == 0 )
{
throw new Exception("Queue is Empty");
}
// remove element
synchronized (_userArray)
{
retVal = _userArray[_head];
_head = (_head  + 1) % (_size);
_count --;
}
return retVal;
}
}

Algorithm for Determining Tic Tac Toe Game Over


In Tic-Tac-Toe of any size for every move it is always for some row and some column and in addition it may or may not be for particular diagonal, and this is fact we are going to use for designing our algorithm.

Algorithm:
Initialize row, col and diagonal Score to 0 for size n.
Maintain score for each player different.
For every move of [row,col]
1. Update the score by 1 for given row if new score is = n declare player as winner
2. Update the score by 1 for given col if new score is = n declare player as winner
3. If move is for diagonal 1 update the score by 1 for diagonal 1 if new score is = n declare player as winner.
4. If move is for diagonal 2 update the score by 1 for diagonal 2 if new score is = n declare player as winner.
--------------------------------------------------------------------------------------------------------
/**
 * This class is to determine winner in game of TicTacToe.
 */
public class TicTacToe
{
/**
* Class to keep track of score for a player.
*/
 private class Score
 {
/** Size of TicTacToe Board.*/
  int _size;
  /** Array for row score.*/
  int[] _rowsScore;
  /** Array for colmun score.*/
  int[] _colsScore;
  /** Array for diagonal score.*/
  int[] _diagsScore = new int[2];

  /**
   * Constructor.
   * @param size Size of the board.
   */
  public Score(int size)
  {
   _size = size;
   _rowsScore = new int[_size];
   _colsScore = new int[_size];
  }

  /**
   * Update the score with given move.
   * @param row Row value.
   * @param col Column value.
   * @return Returns true if player is the winner else false.
   */
  public boolean updateScore(int row, int col)
  {
 // Every move has to be for one row as well as col
 // Check the row.
   if (++_rowsScore[row] == _size)
    return true;
   // Check the col.
   if (++_colsScore[col] == _size)
    return true;
   // Check for diagonal 1
   if (row == col)
   {
    if (++_diagsScore[0] == _size)
     return true;
   }
   // Check for diagonal 1
   for (int i = 0 ; i < _size; i++)
   {
    if (row == i && col == (_size -1 -i))
     if (++_diagsScore[1] == _size)
      return true;
   }
   return false;
  }
 }

 /** Score for player 1.**/
 private Score _player1;
 /** Score for player 2.**/
 private Score _player2;

 /**
  * Constructor.
  * @param size Size of the board.
  */
 public TicTacToe(int size)
 {
  _player1 = new Score(size);
  _player2 = new Score(size);
 }

 /**
  * Function for player 1 move.
  * @param row Row of move.
  * @param col Col of move.
  * @return True if Player 1 is winner for this move else false.
  */
 public boolean movePlayer1(int row, int col)
 {
  System.out.println("Moving player 1  row " + row + " column " + col);
  return _player1.updateScore(row, col);
 }

 /**
  * Function for player 2 move.
  * @param row Row of move.
  * @param col Col of move.
  * @return True if Player 2 is winner for this move else false.
  */
 public boolean movePlayer2(int row, int col)
 {
  System.out.println("Moving player 2  row " + row + " column " + col);
  return _player2.updateScore(row, col);
 }

 /**
  * @param args
  */
 public static void main(String[] args)
 {
  TicTacToe play = new TicTacToe(3);
  System.out.println(play.movePlayer1(1, 1));
  System.out.println(play.movePlayer2(0, 0));
  System.out.println(play.movePlayer1(1, 2));
  System.out.println(play.movePlayer2(1, 0));
  System.out.println(play.movePlayer1(2, 2));
  System.out.println(play.movePlayer2(2, 0));


 }
}
--------------------------------------------------------------------------------------------------------
For every move just call the respective move for the player and check the result if it's true that player is winner.

Saturday, October 13, 2012

Efficiently implement N stacks in a single array.


General algorithm to solve this problem is as follows,
 1. For given stack count determine start/top count for every stack.
 3. Determine maximum value every stack can reach.
 4. While pushing element on a particular stack use it'sown top and max value to determine the push location as well as check is stack is full.
 5. While poping out element from particular stck use max/top values for that stack and update the same as well as check if stack is empty.
---------------------------------------------------------------------------------


/**
 * This class implements N stacks in given size of array.
 */
public class NStack
{
/** Array in which we will implement Stack.*/
int[] _array;
/** Size of the array.*/
int _size;
/** Array to hold top for all N stacks.*/
int[] _topCount;
/** Array to hold max value for all N stacks.*/
int[] _maxSize;
/** Value of N for number of stacks to implement.*/
int _stackCount;

/**
* Constructor.
* @param size Size of an array.
* @param stackSize Number of stacks to implement.
*/
public NStack(int size, int stackSize)
{
// Initialize.
_size = size;
_stackCount = stackSize;
_topCount = new int[_stackCount];
_maxSize = new int[_stackCount];
// Get initializes top count as well as max count for all N stacks.
for (int i = 0 ; i < _stackCount ; i++)
{
_topCount[i] = i - _stackCount;
_maxSize[i] = _size/_stackCount * _stackCount + i ;
if (i >= _size % _stackCount)
{
_maxSize[i] -= _stackCount;
}
}
_array = new int[_size];
}

/**
* Push element on given stack.
* @param item Item to push on stack.
* @param stackNum Stack number 1<->N.
*/
public void push(int item, int stackNum)
{
if (_topCount[stackNum - 1] + _stackCount <= _maxSize[stackNum - 1])
{
_topCount[stackNum - 1] += _stackCount;
_array[_topCount[stackNum - 1]] = item;
System.out.println("Pushing Element " + item + " @ position " + _topCount[stackNum - 1]);
}
else
{
System.out.println("Stack " + stackNum + " is Full :(.");
}
}

/**
* Pop item from given stack.
* @param stackNum Stack from which item is poped.
* @return Item poped -1 if stack is empty.
*/
public int pop(int stackNum)
{
int val = -1;
if (_topCount[stackNum -1] < 0)
{
System.out.println("Stack " + stackNum + " is Empty :(.");
}
else
{
val = _array[_topCount[stackNum -1]];
_topCount[stackNum -1] -= _stackCount;
}
return val;
}
}

Sunday, October 7, 2012

Binary Search Algorithm (Java)


        public int findBinary(int[] array, int min, int max, int item)
{
if (min > max)
return -1;
int mid = min + (max - min)/2;
if (array[mid] == item)
return mid;
else if (array[min] < array[mid] && item < array[mid])
return findBinary(array, min, mid, item);
else if (array[max] > array[mid] && item > array[mid])
return findBinary(array, mid, max, item);
else
return -1;
}

If an array is having integers/Char/special Char... Ex: "PST456DA85M2A!!23++46", find out the sum of integers.


/**
* Find the sum of numbers from given String.
* @param data Given String data.
* @return Sum of numbers from string.
*/
public int findSumOfNumbers(String data)
{
int sum = 0;
int count = 0;
if (data == null)
return sum;
for(int i =0 ; i< data.length(); i++)
{
int val = Character.getNumericValue(data.charAt(i));
if (val >= 0 && val < 10)
{
count = count * 10 + val;
}
else
{
System.out.println("Number : " +count);
sum += count;
System.out.println("Sum : " +sum);
count = 0;
}
}
sum += count;
return sum;
}

Write a function that takes three integers corresponding to the lengths of sides and returns what kind of triangle can be made out of those 3 sides.


/**
* Validates given values for 3 sides of triangle.
* @param side1 Side1.
* @param side2 Side2.
* @param side3 Side3.
* @return 1=scalene, 2=isosceles, 3=equilateral, 4=error.
*/
public int validateTriangle(final int side1, final int side2, final int side3)
{
// Check for validity of all sides
if ((side1 + side2 > side3) && (side2 + side3 > side1) && (side3 + side1 > side2))
{
//  Equilateral
if (side1 == side2 && side2 == side3 && side1 == side3)
{
return 3;
}
// Isosceles
if (side1 == side2 || side2 == side3 || side1 == side3)
{
return 2;
}
// Scalene

return 1;
}
else
{
return 4;
}
}

Find the first index of the substring.


public int findIndex(String mainString, String subString)
{
int result = -1;
 if (mainString == null || subString == null)
                         return result;
int mainLength= mainString.length();
int subLength = subString.length();

                 if(mainLength < subLength)
return result;
for(int i =0 ;i < mainLength; i++)
{
char cur = mainString.charAt(i);
if (cur == subString.charAt(0))
{
if (i + subLength <= mainLength)
{
if ((mainString.substring(i, subLength + i).equals(subString)))
return i;
}
else
return result;

}
}
return result;
}

write a function fib(n,k) which gives you first n numbers of a Fibonacci series and k is the number of previous numbers you have to add.


public int fibonacci(int n, int k)
{
if (n <= 0)
return 0;
if (n==1)
return 1;
int result =0 ;
for (int i = 1; i <= k; i++)
{
result += fibonacci(n-i, k);
}
return result;
}

Given a string generate permutations of all possible lengths and print them in any order.


public void permutations(String data)
{
for( int i =0 ;i < data.length();i++)
{
for(int j=i+1; j<= data.length() ; j++)
{
String subsring = data.substring(i, j);
System.out.println(subsring);
if (subsring.length() > 1)
{
System.out.println(reverse(subsring.toCharArray()));
}
}
}
}

public String reverse(char[] array)
{
int length = array.length;
for (int i =0 ;i < length/2; i++)
{
char temp = array[i];
array[i] = array[length - 1 - i];
array[length - 1 - i] = temp;
}
return new String(array);
}