Amazon Text lInk for IR Testing

Image and link Iframe -
Here To Stay

Programming Questions with code in Ruby

Insertion Sort

INSERTION-SORT(A)
   for i = 1 to n
    key ← A [i]
     j ← i – 1
    while j > = 0 and A[j] > key
     A[j+1] ← A[j]
     j ← j – 1
    End while 
    A[j+1] ← key 
   End for

# Insertion Sort in Ruby
def insertion_sort(array)
    (1..array.size - 1 ).each do |i|
        position = array[i]
        j = i-1
        while (j >= 0 && array[j] > position)
           array[j+1] = array[j]
           j = j - 1
       end
       array[j+1] = position
    end
    array
end
p insertion_sort([12,21,32,7,2])

Worst Case Time Complexity [ Big-O ]: O(n2)

Best Case Time Complexity [Big-omega]: O(n)

Average Time Complexity [Big-theta]: O(n2)

Merge Sort

# Merge Sort in Ruby
def merge(array1, array2)
    iter1=iter2=iter=0
    result = []
    while(iter1 < array1.size || iter2 < array2.size)
        if(iter1 >= array1.size)
            result[iter] = array2[iter2]
            iter2=iter2+1
        elsif(iter2 >= array2.size)
            result[iter] = array1[iter1]
            iter1 = iter1+1
        elsif(array1[iter1] < array2[iter2])
            result[iter] = array1[iter1]
            iter1 = iter1+1
        else
            result[iter] = array2[iter2]
            iter2=iter2+1
        end
        iter=iter+1
    end
    result
end

def merge_sort(array)
    return array if (array.size == 1)
    mid = (array.size/2.0).round
    split_array = array.each_slice(mid).to_a 
    array1 = split_array[0]
    array2 = split_array[1]
    array1 = merge_sort(array1)
    array2 = merge_sort(array2)
    return merge(array1, array2)
end

p merge_sort([12,21,32,7,2,34])

Time Complexity : Ο(n log n)

Space Complexity : O(n)

Quick Sort

# Quick Sort in Ruby
def partition(array, low, high)
    pivot = array[high]
    i = low -1
    (low..high-1).each do |j|
        if(array[j] <= pivot)
            i = i+1
            temp = array[i]
            array[i] = array[j]
            array[j] = temp
        end
    end
    temp = array[i+1]
    array[i+1] = array[high]
    array[high] = temp
    return i+1
end

def quick_sort(array, low, high)
    if (low < high)
        index = partition(array, low, high)
        quick_sort(array, low, index-1)
        quick_sort(array, index+1, high)
    end
end

array = [12,21,32,7,2,14]
quick_sort(array, 0, array.size-1)
p array

Time Complexity : O(n2)

Space Complexity : In-Place

Problem:

Given a non-negative number represented as an array of digits, add 1 to the number ( increment the number represented by the digits ).The digits are stored such that the most significant digit is at the head of the list.
Example:
If the vector has [1, 2, 3]
the returned vector should be [1, 2, 4]
as 123 + 1 = 124.

class Solution
    # @param a : array of integers
    # @return an array of integers
    def plusOne(a)
        num = a.join.to_i+1
        num.to_s.split('')
    end
end

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.

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

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