Given a character array as input. Array contains only three types of characters 'R', 'G' and 'B'. Sort the array such that all 'R's comes before 'G's and all 'G's comes before 'B's. Constraint: - No extra space allowed (except O(1) space like variables) and minimize the time complexity. You can only traverse the array once.

/*
 *   1. Initialise 2 variables Rpos = 0 and Bpos = size-1.
 *   2. Scan the array from left to right.
 *      For i=0 to i<size
 *      a. if Array[Rpos] == ‘R’ then Rpos++
 *      b. If Array[Bpos] == ‘B’ then Bpos--
 *      c. if Array[i] == ‘R’ and i > Rpos then swap Array[Rpos], Array[i] and Rpos++
 *      d. If Array[i] == ‘B’ and I < Bpos then swap Array[Bpos], Array[i] and Bpos—
 */

 int main()
 {
     char Array[]={'R','B','B','G','B','R','B','G','R','R','B','G','R','G','B','B','G','R','R','G'};
     int size = sizeof(Array)/sizeof(Array[0]);
     int Rpos=0, Bpos = size-1;
     for(int i=0; i < size ; i++)
     {
             if(Array[Rpos] == 'R' )
             {
                            Rpos++;
             }
             if(Array[Bpos] == 'B')
             {
                            Bpos--;
             }
             if(Array[i] == 'R' && i >Rpos)
                         swap(Array,Rpos++,i);
             if(Array[i] == 'B' && i < Bpos)
                         swap(Array,Bpos--,i);
     }
     display(Array,size);
     cout<<"\n";
     system("pause");
 }

There is a sequence where alphabets are written like this.. a,b,c,d,.......,x,y,z,aa,ab,ac........,az,ba,bb,bc,bd......bz,ca,cb.........cz........,aaa,aab,aac.....aaz,............zzz,aaaa...........zzzz..... and so on..WAP to find out the string value at kth position. like if k= 28 the string on 28 will be "ab".

/*
 * This question is picked from Amazon Interview question on career cup.
 * The question can also be rephrased as convert number from decimal (base 10) number system to base 26 number system.
 *
 * ALGORITHM
 * 1. Get input number in variable “num”
 * 2. Call ConvertDecimal function and pass “num-1” and “base = 26” :
 * a. Initialize “len” = No. of digits, base 26 representation of number num will occupy.
 * b. Create an integer array of “len” number of elements and store each digit of base26 representation of num in this array.
 * 3. Initialise i=len and while i>=0
 * 4. Print character (base26[i]+97).
 *
 * PS:
 * we converted num-1 to base 26 and not num. consider num = 26  when we convert it to base26 it is 10
 * in our base26 representation 0 = a and 1=b so it will print ba but it should print z.
 * so to produce desire result we pass num-1 and not num.
 * if num = 26 we convert 25 to base26 which is z.  
 * It will always produce the desire result.
 */

  int getLength(int number, int base)
  {
      int length = 0;
      while(number > 0 )
      {
                   number /= base;
                   length++;
      }  
      return length;
  }
 
  int* convertDecimal(int toBase, int number)
  {
       int len = getLength(number,toBase);
       int *base26 = new int[len];
       int remainder;
       for(int i=0; i < len ; i++)
       {
                       base26[i] = number % toBase;
                       number /= toBase;
       }
       return base26;
  }
 
  int main()
  {
      int number ;
      cout<<"Enter the number : ";
      cin>>number;
      int *base26 = convertDecimal(26,number-1);
      int length = getLength(number-1,26);
      for(int i=length-1; i>=0; i--)
      {
              cout<<"  "<<char(97+base26[i]);
      }
      cout<<"\n\n";
      system("pause");
  }

Given an array of arbitrary integers, count the no. of inversion pairs where inversion pair is defined as A[i] > A[j] and i < j .

/*

 * The idea is to use Merge sort since it takes o(nlogn) time.

 * Merge function will not only merge the subarrays but select inversion pairs also.
 * If an array is divided into left and right halves.
 * If any element is copied into merge array before all the elements of left sub-array is copied into merge array then it is an inversion pair.
 * This task is extra apart from merging but still merge function performs in o(n) time preserving the overall o(nlogn) time.
 */

#include <iostream.h>

using namespace std;

void MergeSort(int [] , int , int);

void MergeAndCount(int [], int , int , int );

void display(int a[] , int n)

{

     for(int i=0; i< n; i++)

             cout<<a[i]<<"  ";

}

void MergeSort(int array[], int low, int high)

{

     if(low < high)

     {

            int mid = (high+low)/2;

            MergeSort(array,low, mid);

            MergeSort(array,mid+1,high);

            MergeAndCount(array,low,mid,high);

     }

}

void MergeAndCount(int array[], int low, int mid, int high)

{

     int i= low, j = mid+1, k=0;

     int *c = new int[high-low+1];

     while(i <= mid && j <= high)

     {

             if(array[i] < array[j])

                         c[k++] = array[i++];

             else

             {

                 cout<<"\n( "<<array[i]<<" , "<<array[j]<<" ) ";

                 c[k++] = array[j++];

             }

     }

     while(i <= mid)

             c[k++] = array[i++];

     while(j <= high )

             c[k++] = array[j++];

     int s = 0;

     while( s < k)

     {

            array[s+low] = c[s];

            s++;

     }

     delete[] c;

}

int main()

{

    int array[] = {1,5,3,6,2,4};

    int length = sizeof(array)/sizeof(array[0]);

    MergeSort(array,0,length-1);

    display(array,length);

    system("pause");

}

Given a very large number (any number of digits), find the next greater number formed by permutation of digits of this number.

/*
     * The Naive approach will be to generate all permutations of the string and check the next greater number.
     * Another Approach:
     * Start traversing from second Last digit of the number.
     * Check on right of current digit (starting from rightmost digit) if there is any digit greater than current digit.
     * If there is any then return its position.
     * else return -1.
     * swap currentPosition digit with returnedPosition digit.
     * Now Reverse the String after currentPosition till end.
     * As from currentPosition till end digits will be in descending order but to find next greatest digits should be in ascending order.
     * Reversing ascending order means descending order hence, reversing string after currentPosition digit.
     * If leftmost digit is reached and no such digit is found then display NO SUCH NUMBER EXIST.
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Solution {

     private String number ;
 
     public void initialize()
     {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          try
          {
               number = br.readLine();
          } catch (IOException e)
          {
               e.printStackTrace();
          }
          System.out.println("Next Greater Number is : " + getNextGreaterNumber());
     }
 
     public int getGreaterinRightHalf(int digit , int pos)
     {
          for(int i = number.length()-1 ; i > pos ; i--)
          {
               if(digit < Integer.parseInt(Character.toString(number.charAt(i))))
               {
                    return i;
               }
          }
          return -1;
     }
 
     public String getReverseString(String str)
     {
          String reverseStr = "";
          for(int i = str.length()-1 ; i>=0 ; i--)
          {
               reverseStr += str.charAt(i) +"";
          }
          return reverseStr;
     }
   
   
     public String getNextGreaterNumber()
     {
          int swapPos = -1;
          int i = number.length()-2 ;
          for( ; i > 0 ; i--)
          {
               swapPos = getGreaterinRightHalf(Integer.parseInt(Character.toString(number.charAt(i))),i );
               if(swapPos != -1)
               {
                    break;
               }
          }
          String finalString;
          if(swapPos == -1)
          {
               finalString = "NO SUCH NUMBER EXIST";
          }
          else
          {
           
               finalString = number.substring(0, i) + number.charAt(swapPos) + getReverseString(number.substring(i+1, swapPos) + number.charAt(i) + number.substring(swapPos+1));
          }
          return finalString;
     }

 
     public static void main(String args[])
     {
          Solution s = new Solution();
          s.initialize();
       
     }
}

Add 2 linked lists where each node represents a digit of the number formed by the linked lists.

/*

     LinkedList1 : 7 -> 4 -> 6 -> 9 -> 3
     LinkedList2 :          2 -> 5 -> 4
     SumList : 7 -> 4 -> 9 -> 4 -> 7
   
   
     LinkedList1 :     1 -> 2 -> 3 -> 4
     LinkedList2 : 5 -> 4 -> 3 -> 2 -> 8
     SumList : 5 -> 5 -> 5 -> 6 -> 2
   
   
     LinkedList1 :     8 -> 7 -> 6 -> 5 -> 4
     LinkedList2 :     4 -> 3 -> 2 -> 1 -> 0
     SumList : 1 -> 3 -> 0 -> 8 -> 6 -> 4

*/

class linkedList
{
         /*
         * This function returns the difference in length of both the linkedLists.
         * If length of linkedList1 is greater than length of linkedList2 then +ve difference in no. of elements returned.
         * If length of linkedList1 is less tahn length of linkededList2 then -ve difference in no. of elements is returned.
         * If both the linkedLists have equal no. of nodes then 0 is returned.
         */
         public int getLengthDifference(node ptr1, node ptr2)
         {
                int lengthList = 0;
                while(ptr1!=null)
                {
                ptr1=ptr1.getNext();
                lengthList++;
                }
                while(ptr2 != null)
                {
                ptr2=ptr2.getNext();
                lengthList--;
                }
                return lengthList;
         }
       
         /*
         * This function requires "START" node of both the linkedLists.
         * start refers to start node of linkedList which called this function (list1 in our case)
         * startList2 gets start node of second linkedList.
         * It returns new linkedList object which is sum of both the linked lists.
         */
         public linkedList getSumOfLinkedLists(node startList2)
         {
                int diff = getLengthDifference(start, startList2);
                linkedList sum = new linkedList();
                if(addLinkedLists(start, startList2, diff,sum) == 1)
                sum.insertAtFront(1);
                return sum;
         }
       
         /*
         * To overcome difference in lenths of linkedLists "integer n" is passed to this function.
         * n = difference in length of LinkedList1 and LinkedList2.
         * n > 0 => LinkedList1 > linkedList2 so only elements of linkedList1 should be incremented until n =0  ( n = n-1 ).
         * n < 0 => LinkedList2 > LinkedList1 so only elements of linkedList2 should be incremented until n = 0 ( n = n+1 ).
         * n =0  => Equal elements now both lists should be incremented.
         */
         public int addLinkedLists(node ptr1, node ptr2, int n,linkedList sumList)
         {
                if(ptr1 != null && ptr2 != null)
                {
                      int val = 0;
                      int sum = 0;
                      if(n > 0)
                      {
                      val = addLinkedLists(ptr1.getNext(), ptr2, n-1 , sumList);
                      sum = ptr1.getData() + val;
                      }
                      else if(n < 0)
                      {
                      val = addLinkedLists(ptr1, ptr2.getNext(), n+1 , sumList);
                      sum =  ptr2.getData() + val;
                      }
                      else
                      {
                      val = addLinkedLists(ptr1.getNext(), ptr2.getNext(), n , sumList);
                      sum = ptr1.getData()+ptr2.getData()+val ;
                      }
                      sumList.insertAtFront(sum%10);
                      return sum/10;
                }
                return 0;
         }
         
         public static void main(String args[])
         {
                linkedList list1 = new linkedList();
                linkedList list2 = new linkedList();
               
                //Insert elements in list1 and list2.
                System.out.println("\nLIST AFTER ADDITION");
               
                linkedList l = list1.getSumOfLinkedLists(list2.getStart());
                l.displayList();
         
         }
}

Boundary traversal or printing border nodes of a binary tree.

/*
 Tree :
50
30    70
 20  40  60  80
        35  45
   

 Boundary Traversal : 50 30 20 35 45 60 80 70

 Logic:
 1. Print Root Node.
 2. Print Leftmost Branch except Leaf Node.
 3. Print all leaf nodes.
 4. Print Rightmost branch except Leaf Node.
*/

 public void boundaryTraversal()
 {
printRootNode();
printLeftBranch(root.getLeftChild());
printLeafNodes(root);
printRightBranch(root.getRightChild());
 }

 public void printRootNode()
 {
System.out.println(root.getData());
 }

 public void printLeftBranch(BSTNode n)
 {
if(n.getLeftChild() != null)
{
System.out.println(n.getData());
printLeftBranch(n.getLeftChild());
}
 }

 public void printLeafNodes(BSTNode n)
 {
if(n.getRightChild() ==null && n.getLeftChild() == null)
{
System.out.println(n.getData());
return;
}
printLeafNodes(n.getLeftChild());
printLeafNodes(n.getRightChild());
 }

 public void printRightBranch(BSTNode n)
 {
if(n.getRightChild() != null)
{
System.out.println(n.getData());
printRightBranch(n.getRightChild());
}
 }

Given a 2-D Matrix find path from starting cell to Goal cell, a bot can move in 8 directions (North, North east, east , south east, south, south west, west, north west). if cell value =0 implies block and if cell Value =1 implies Path exist.

/*
start : (row = 1, col = 3)
Goal  : (row = 6, col = 3)
   
            c1  c2 c3  c4  c5
    row1    0   0   1   0   0
    row2    0   0   0   1   0
    row3    0   1   1   0   0
    row4    0   1   0   0   0
    row5    0   0   1   0   0
    row6    0   0   1   0   0
    row7    1   0   0   0   0
       
Path:
    Start(r1 c3) -> (r2 c4) -> (r3 c3) -> (r4 c2) -> (r5 c3) -> (r6 c3) Goal

Below is the java code.

*/

public class Solution {
    private int[][] moves = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
    private int[][] maze = {{0,0,1,0,0},{0,0,0,1,0},{0,1,1,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,1,0,0},{1,0,0,0,0}};
    private int[][] sol = maze.clone();
    private int mazeWidth = maze[0].length;
    private int mazeHeight = maze.length;
    private int xStart = 0;
    private int yStart = 2;
    private int xGoal = 5;
    private int yGoal = 2;
    private boolean result = false;
   
    public void startBot()
    {
        sol[xStart][yStart] = 2;
        result = moveToGoal(xStart,yStart);
        displayResult();
    }
   
    public boolean movePossible(int r, int c)
    {
        if(r <0 || r>= mazeHeight || c >= mazeWidth || c<0)
        {
            return false;
        }
       
        if(sol[r][c] ==1)
        {
            return true;
        }
        return false;
    }
   
    public void makeMove(int r, int c)
    {
        sol[r][c] = 2;
    }
   
    public void unmakeMove(int r , int c)
    {
        sol[r][c] = 1;
    }
   
    public boolean moveToGoal(int x , int y)
    {
        if(x == xGoal && y == yGoal)
        {
            return true;
        }
       
        for(int i =0 ; i<moves.length; i++)
        {
            if(movePossible(x+moves[i][0], y+moves[i][1]))
            {
                makeMove(x+moves[i][0] , y+moves[i][1]);
                if( moveToGoal(x+moves[i][0], y+moves[i][1]) )
                {
                    return true;
                }
                unmakeMove(x+moves[i][0], y+moves[i][1]);
            }
        }
        return false;
    }
   
    public void displayResult()
    {
        if(result)
        {
            System.out.println("SOLUTION FOUND");
       
            for(int i =0 ; i<mazeHeight; i++)
            {
                for(int j =0 ; j<mazeWidth; j++)
                {
                    if(sol[i][j] ==2)
                    {
                        System.out.println("xpos : " + i + "   ypos : " + j);
                    }
                }
            }
        }
        else
        {
            System.out.println("NO SOLUTION");
        }
    }
   
    public static void main(String args[])
    {
        Solution s = new Solution();
        s.startBot();
    }
   
}

Construct Binary tree from given inorder and pre-order traversal of Binary Tree.

/*
        1. Scan pre-order from left to right and search the encountered node in given in-order array.
        2. Store position of element in pos.
        3. Construct node having value inorder[pos].
        4. Divide inorder in left (start, pos-1) and right (pos+1,end).

preOrder = {50,30,20,40,35,45,70,60,80};
inOrder =  {20,30,35,40,45,50,60,70,80};


1. 50

50
20,30,35,40,45 60,70,80


2. 30
50
30 60,70,80
20 35,40,45

3. 20 (Return node as start = end.

4. 40
50
30 60,70,80
20 40
35 45

5. 35 (start = end)
6. 45 (start = end)
7. 70 (start = end)
50
30 70
20 40 60 80
35 45
8. 60 (start = end)
9. 80 (start = end)

*/
private int[] preOrder = {50,30,20,40,35,45,70,60,80};
private int[] inOrder =  {20,30,35,40,45,50,60,70,80};
private int prePos = 0;


public int searchInOrder(int s , int e , int n)
{
for(int i =s ; i <= e; i++)
{
if(inOrder[i] == n)
return i;
}
return -1;
}


public BSTNode createTree(int start, int end)
{
if(prePos >= preOrder.length)
return null;

BSTNode newNode = new BSTNode();
newNode.setData(preOrder[prePos++]);

if(start == end)
{
return newNode;
}

int pos = searchInOrder(start,end,newNode.getData());
newNode.setLeftChild(createTree(start, pos-1));
newNode.setRightChild(createTree(pos+1, end));

return newNode;
}


public void buildTree()
{
prePos = 0;
root = createTree(0,preOrder.length-1);
}


BST tree = new BST();
tree.buildTree();

Given 2 sorted arrays of size m and n+m(with n elements) , merge them into the latter..

/*
 * Java Program
*/


public class Solution {

      private int[] arr1;
      private int[] arr2;
      private int elementsInarr1 = 0;   //variable stores no. of elements in arr1 (n)
     
      //Initialize arr1 with n elements and arr2 with n+m elements
      public void initialize()
      {
             arr1 = new int[13];
             arr2 = new int[6];
             arr1[0]=7;
             arr1[1]=12;
             arr1[2]=14;
             arr1[3]=20;
             arr1[4]=25;
             arr1[5]=35;
             arr1[6]=40;
             elementsInarr1 = 7;
             arr2[0]=2;
             arr2[1]=5;
             arr2[2]=16;
             arr2[3]=24;
             arr2[4]=32;
             arr2[5]=34;
      }
     
      //Diplay contents of array.
      public void displayArray()
      {
             for(int n:arr1)
             {
                   System.out.print(" "+ n);
             }
      }
     
      public void inPlaceMerge()
      {
             int i = elementsInarr1-1;
             int pos = arr1.length-1;
             int j = arr2.length-1;
             while(i>=0 && j>=0)
             {
                    if(arr1[i] > arr2[j])
                    {
                          arr1[pos--] = arr1[i--];
                    }
                    else
                    {
                          arr1[pos--] = arr2[j--];
                    }
             }
           
             while(j>=0)
             {
                   arr1[pos--] = arr2[j--];
             }
      }
     
      public static void main(String args[])
      {
             Solution s = new Solution();
             s.initialize();
             s.inPlaceMerge();
             s.displayArray();
      }
}