Coding Recipies: April 2014

27 Apr 2014

Max Repeating Number

Problem Statement:

Find the number with maximum frequency in the given array.

Maximum element is 2

Solution:

One of the solution to the above problem can be using the concept of hashtable, to find the max frequency element. In which it would require extra space and 2 traversals. For each number we encounter we increment the count by 1.

Now we will be still utilizing the concept of hashing without extra space. This time when ever we find a number we add a number x , which is greater than any other number in the given array to the corresponding index of the number encountered.

/**
 * Find the element with maximum frequency
 * @author PRATEEK
 */
public class MaxRepeatingNumer {
 public static void main(String[] args) {

  int arr[] = { 3, 1, 3, 2, 1, 2, 2 };
  int x = 5;
  System.out.println(maxRepeatingNumer(arr, x));
 }

 private static int maxRepeatingNumer(int arr[],int k) {
  
  int i = 0, max = arr[0], result = 0;
  for (; i < arr.length; i++)
   arr[arr[i] % k] += k;

  i = 1;
  for (; i < arr.length; i++) {
   if (arr[i] > max) {
    max = arr[i];
    result = i;
   }
  }

  i = 0;
  for (; i < arr.length; i++)
   arr[i] = arr[i] % k;

  return result;
 }
}

Please comment and post your suggestions.
Happy Coding !!:)

Equilibrium Index

Problem Statement:
Find the index in an array where sum of the numbers to its right is equal to the sum of the number to its right.

Fig1: Calculate total sum of element

Fig2: Keep subtracting right sum from total sum and compare

Solution:
Run Source Code

In the above example we first calculate the TotalSum of all the numbers in one traversal.
Maintain another cumulative sum from the right end of the array except the current element and keep on subtracting the RightSum from TotalSum. If at any point TotalSum becomes equal to RightSum, return the index.

Below is the implementation:

/**
 * Find the index in an array where sum to left is equal to sum to its right
 * @author PRATEEK
 */
public class EquilibriumIndex {

 /**
  * @param arr: input arr
  * @return : equilibrium index in the array
  */
 private int equilibrium(int[] arr) {
  int i = 0, sum = 0, rightSum = 0;
  for (; i < arr.length; sum += arr[i++]);

  for (i--; i > 0; sum -= arr[i], rightSum += arr[i])
   if (sum == rightSum - arr[i--])
    return i;

  return -1;
 }

 public static void main(String[] args) {

  int arr[] = { -7, 1, 6, 2, -4, 3, 1 };
  EquilibriumIndex obj = new EquilibriumIndex();
  int mid = obj.equilibrium(arr);
  System.out.println(mid);

 }
}

Time Complexity: O(n)
Space Complexity: O(1)

Please comment and post if any suggestions.
Happy Coding !!:)

Validate Brackets

Problem Statement:
Given a sequence of brackets, validate if the sequence is valid.

Solution:
Run Source Code

We all must have solved this problem during college as common application of stack for solving mathematical expressions. Below is the implementation to validate given sequence of brackets.

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * Given an sequence of brackets , confirm if sequence is valid
 * @author PRATEEK
 */
public class ValidateBrackets {
 
 private static Map<Character,Character> hash = new HashMap<>();
 
 static {
  hash.put('{','}');
  hash.put('[',']');
  hash.put('(',')');
 }
 
 /**
  * Sub-routine to validate the sequence of brackets
  * @param s
  * @return
  */
 public static boolean validate(String s){
  char[] arr = s.toCharArray();
  
  Stack<Character> stack = new Stack<>();
  for(Character c:arr)
  {
     switch (c) {
   case '[':
   case '{':
   case '(':
    stack.push(c);
    break;
    
   case ']':
   case '}':
   case ')':
   {
    if(hash.values().contains(c))
    {
     if(!stack.isEmpty() && hash.get(stack.peek())==c)
      stack.pop();
     else if(stack.isEmpty())
      return false;
    }
    
   }
    break;
   default:
    break;
   }
  }
  return stack.isEmpty();
 }
 
 public static void main(String[] args) {
  String s= "{()}[]";
  boolean isValid = validate(s);
  System.out.println("input: "+s);
  System.out.println("output: " +isValid);
 }
}

Download Source Code
Please comment and post your suggestions.
Happy Coding !! :)

Division without operator

Problem Statement:
Find the quotient without using the operator ('/').

Solution:
Run Source Code

Below is the implementation:

/**
 * Division without using '/' operator
 * @author PRATEEK
 */
public class Division {

 public static int division(int dividend, int divisor) {
  if (divisor == 0)
   throw new ArithmeticException("Division by Zero");

  boolean isPositive = true; // flag for negative number

  if (dividend < 0) {
   isPositive = !isPositive; // toggle flag, i.e.negative
   dividend *= -1; // make divident positive
  }

  if (divisor < 0) {
   isPositive = !isPositive;
   divisor *= -1;
  }

  int temp, mul, result = 0;
  for (; dividend >= divisor; dividend -= temp >> 1, result += mul >> 1)
   for (mul = 1, temp = divisor; temp <= dividend; temp <<= 1, mul <<= 1);
 
  return result;
 }

 public static void main(String[] args) {
  int numerator = 56;
  int denominator = 5;
  int ans = division(numerator, denominator);
  System.out.println(numerator+"/"+denominator+"="+ans);
 }
}

Download Source Code
Please comment and post your suggestions.
Happy Coding !! :)

Maze: Count all possible paths

Problem Statement:
Count all the possible paths in the given maze.
Note: Only right and bottom moves allowed.

Solution:
Run Source Code
We would using recursion to count the possible pats, as (N-1,N-1) is reached count is incremented each time.

Below is logic implemented.

/**
 * Find count of possible paths in the maze
 * @author PRATEEK
 */
public class CountPaths {

 private static int rowLen, colLen, count;
 public static void paths(int[][] maze, int row, int col) {
  if (row == rowLen && col == colLen) {
   count++;
   return;
  }
  /*// move left
  if (col > 0 && maze[row][col - 1] == 1)
   paths(maze, row, col - 1);*/

  // move right
  if (col < colLen && maze[row][col + 1] == 1)
   paths(maze, row, col + 1);

  /*// move up
  if (row > 0 && maze[row - 1][col] == 1)
   paths(maze, row - 1, col);*/

  // move down
  if (row < rowLen && maze[row + 1][col] == 1)
   paths(maze, row + 1, col);

 }

 public static void main(String[] args) {
  int[][] maze = { 
    {1, 1, 0, 0, 1, 1 }, 
    {1, 1, 1, 1, 0, 0 },
    {1, 0, 0, 0, 1, 0 }, 
    {1, 1, 1, 1, 0, 0 },
    {1, 0, 1, 0, 0, 0 },
    {1, 1, 1, 1, 1, 1 }
  };
  
  rowLen = maze.length-1;
  colLen = maze[0].length-1;
  
  paths(maze,0,0);
  System.out.println("Number of Paths: "+count);
 }
}

Please comment and post your suggestions.
Happy Coding !! :)

Rotated Strings

Problem Statement:
Check if the given strings are rotated form of each other.

Check if S2 is the rotated version of S1

Solution:
Run Source Code

The approach is to check if the strings are of same length, then check if s2 is sub-string of s1 concatenated with itself.

Implementation:

/**
 * Check if Given strings are roated form of each other
 * @author PRATEEK
 */
public class RotatedStrings {

 public static void main(String[] args) {
  System.out.println(isRotated("coding","dingco"));
 }
 
 /**
  * @return: true if strings are rotated form of each other
  */
 public static boolean isRotated(String s1,String s2){
  return s1.length()==s2.length() && (s1+s1).indexOf(s2)!=-1 ;
 }
}

Please comment and post your suggestions.
Happy Coding !! :)

Matrix: Spiral Printing

Problem Statement:
Print the given matrix (m X n) in spiral form.

Fig: Matrix: print elements spirally

Solution:
Run Source Code

This question was asked to my buddy in Tower Research Capital.
This problem is not difficult but, you will be tested if you can get the output in one go.
We would require 5 loops, out of which 4 loops will be for printing the elements in
LEFT, DOWN, RIGHT and UP. Below i have given the implementation of the problem.

/**
  * Spiral order printing
  * @param matrix
  */
 public static void printSpiral(int[][] matrix) {
  int rowSize = matrix.length;
  int colSize = matrix[0].length;

  int row = 0, col = 0, i;

  while (row < rowSize && col < colSize) {
   i = col;
   for (; i < colSize - col; i++)
    System.out.print(matrix[row][i] + "  ");

   i = row + 1;
   for (; i < rowSize - row; i++)
    System.out.print(matrix[i][colSize - col - 1] + "  ");

   i = (colSize - 1 - col) - 1;
   for (; i >= col; i--)
    System.out.print(matrix[rowSize - row - 1][i] + "  ");

   i = (rowSize - 1 - row) - 1;
   for (; i > row; i--)
    System.out.print(matrix[i][col] + "  ");

   row++;
   col++;
  }
 }

Download Source Code
Please comment and post your suggestions.
Happy Coding !! :)

Arrays: K Closest ELements

Problem Statement:
Given a number in a sorted array , find K closest elements to that number.

Closest Integers in the vicinity of 8 are : 5,6,7,10

Solution:
Run Source Code

Since the given array is sorted , binary search can be applied to get the index of the given number.
We will then place two pointers viz left and right , which will decremented and incremented respectively based on the minimum difference with the given number.

Below is the logic implementation.

     public static int[] KClosestElements(int[] arr, int index, int k){
  int left = index -1;
  int right = index +1;
  int[] result = new int[k];

  while(right - left -2 < k )
  {
   if(arr[right] - arr[index] > arr[index]- arr[left])
   {
    if(left>0)
     result[right - left - 2] = arr[left--];
    else 
     result[right - left - 2]=arr[right++];
   }
   else
   {
    if(right < arr.length)
     result[right - left - 2]=arr[right++];
    else
     result[right - left - 2] = arr[left--];
   }
   
   //result[right - left] = arr[right] - arr[index] > arr[index]- arr[left] ?  if(left>0){arr[left--]} : arr[right++] ;
  }
  System.out.println(Arrays.toString(result));
  
  return result;
 }

Binary Search Sub-routine

       private static int binarySearch(int[]arr,int num,int low,int high) {
  while(low<=high)
  {
   int mid=(low+high)/2;
   if(arr[mid]==num)   return mid;
   else if(arr[mid] < num)  low=mid+1;
   else if (arr[mid] > num) high=mid-1;
  }
  return -1;
 }

Please post comments and suggestions.
Happy Coding !! :)

13 Apr 2014

Fold Linked List

Problem Statement:
Fold the given Linked List

Solution:

Download Source Code

As a Scarf is folded , the above linked list is also folded and merged.

The recursive Logic in-order to achieve this is given below. I would recommend you to
try it yourself and also refer to Check Pallindrome List , which involves similar logic.

      public static Node foldList(Node head) {
  return fold(head, head);
 }

 /**
  * Linked List Folding Sub-routine
  * @param head: head pointer
  * @param curr: current pointer
  * @return: head of the folded list
  */
 private static Node fold(Node head, Node curr) {
  if (curr == null)
   return head;

  Node result = fold(head, curr.next);

  // condition to stop execution if result is head and curr is not the
  // last node
  if (result != head || curr.next == null) 
  {
   // handling odd and even number of nodes
   if (result != curr && result.next!=curr) 
   {
    curr.next = result.next;
    result.next = curr;
    return curr.next;
   }
   curr.next = null;
  }
  return head;
 }

Please comment and post your suggestions , any suggestion for enhancing the solution is most-welcome.

Happy Coding !! :)

Next Palindrome

Problem Statement:
Given a number find the next Palindrome Number

Solution:

In the given problem , we take two pointers one at left and the other on right, we start comparing i and n-i.
The difference of left and right digit (which are multiplied by bases) is added to the number , in case the right digit is greater, we match up the effect introduced by the difference which was added in the previous step.

Time Complexity: O(n)
Space Complexity: O(1)

/**
  * Get next pallindrome
  */
 public static int nextPanlindrome(int num) {

  if(isPalindrome(num))
   num++;

  String temp = num + "";
  int end=temp.length() -1;
  int base=1;

  for(int start = 0; start < end; start++, end--)
  {

   // Gives the right digit
   int right = Integer.parseInt(temp.charAt(end)+"") * base;

   // Gives the left digit
   int left = Integer.parseInt(temp.charAt(start)+"") * base;

   // add differnce to the number
   num += left - right  ;   //------(1)

   base *=10;

     
   if(right > left) 
   {
    num += base;  // for incresing the value of number which got decreased at (1)

        //number of digits are even,
    if(start == end - 1) 
     num += base/10;
   }
   temp = num + "";
  }

  return num;
 }

 /**
  * Checks if a number is pallindriome
  * @param num
  * @return
  */
 public static boolean  isPalindrome(int num) {
  int reverse = 0, temp=num;

  while( temp != 0 ) {
   reverse = reverse * 10;
   reverse = reverse + temp%10;
   temp = temp/10;
  }
  return (num == reverse ? true: false);
 }

In case of any clarification , suggestion or enhancement of code , please comment.
Happy Coding !! :)

Trees: Iterative Pre-order traversal

Problem Statement:
Perform iterative pre-order traversal using Stack on the given binary tree.

Output:
Pre-order : 1 , 2 , 4 , 8 , 5 , 3 , 6 , 7 , 9

Solution:
Download Source Code

By pre-order traversal I mean , process the Node, then Left Node , and then Right Node, all this processing happens in Depth First Search fashion. I assume that you know the recursive way to iterate a binary tree.

Pre-order Traversal : Node, Left Node, Right Node - +AB
In-order Traversal : Left Node, Node , Right Node - A+B
Post-order Traversal: Left Node, Right Node, Node - AB+

Iterative Traversal can also be done by Morris traversal , which uses the concept of Threaded Binary Trees
Morris Traversal

Below is the algorithm and implementation of in-order traversal using Stack.

 Algorithm Involved:   
 1. Push root to stack  
 2. while stack is not empty  
    a. pop from stack, and print  
    b. if left child is not null , push to stack  
    c. If right child is not null , push to stack  
 3.End

Implementation:

/**
  * Iterative Preorder Traversal Using Stack
  * @param root: root of tree
  */
 public void iterativePreorder(Node root)
 {
  Stack<Node> stack = new Stack<Node>();
  
  if(root!=null)
  stack.push(root);

  while(!stack.isEmpty())
  {
   Node item = stack.pop();
   System.out.print(item + "\t");
   if(item.right!=null)
    stack.push(item.right);
   if(item.left!=null)
    stack.push(item.left);

  }
 }

Please post your comments and suggestions.
Happy Coding!!:)

Trees: Iterative Inorder Traversal

Problem Statement:
Perform In-order traversal of the given binary tree using stack.

Output:
In-order : 6 , 7 , 8 , 10 , 12 , 14 , 16 , 18 , 20

Solution:
Download Source Code

By in-order traversal I mean , process the Left Node , then Node , and then Right Node, all this processing happens in Depth First Search fashion. I assume that you know the recursive way to iterate a binary tree.

Pre-order Traversal : Node, Left Node, Right Node - +AB
Inorder Traversal : Left Node, Node , Right Node - A+B
Post-order Traversal: Left Node, Right Node, Node - AB+

Iterative Traversal can also be done by Morris traversal , which uses the concept of Threaded Binary Trees

Below is the algorithm and implementation of in-order traversal using Stack.

 Algorithm Involved:   
 1. root!=null  
 2. current = root   
 3. for(;;)  
 A. If current is not null   
     a. push to stack  
     b. move current to left  
 B. If current is null and stack is not empty  
     a. pop from stack  
     b. print poped item  
     c. puch poped items right child if not null  
 C. If stack is empty , END

Implementation:

/**
  * Iterative Inorder Traversal using Stack
  * @param node
  */
 public void iterativeInorder(Node node) 
 {
  Stack<Node> stack = new Stack<Node>();
  for (;;) 
  {
   if (node != null) 
   {
    stack.push(node);
    node = node.left;
   }
   else 
   {
    if (!stack.isEmpty()) 
    {
     node = stack.pop();
     System.out.print(node + "\t");
     node = node.right;
    }
    else
     break;
   }
  }
 }

Please post your suggestion and comments.
Happy Coding !!:)

Trees: Iterative Post-order traversal using Single Stack

Problem Statement:
Perform iterative post-order traversal on a binary tree using Single Stack.

Output:
Post-order : 8 , 4 , 5 , 2 , 6 , 9 , 7 , 3 , 1

Solution:
Download Source Code

By post-order traversal I mean , process the Left Node ,then Right Node, and then Node all this processing happens in Depth First Search fashion. I assume that you know the recursive way to iterate a binary tree.

Pre-order Traversal : Node, Left Node, Right Node - +AB
In-order Traversal : Left Node, Node , Right Node - A+B
Post-order Traversal: Left Node, Right Node, Node - AB+

Iterative Traversal can also be done by Morris traversal , which uses the concept of Threaded Binary Trees.
Here we are performing iteration using a Single Stack, also refer to my post using two stacks.

Below is the algorithm and implementation of in-order traversal using Single Stack.

/**
  * Iterative Pre-order traversal using single stacks
  */
 public void iterativePostOrder(Node root) {
  Stack<Node> stack = new Stack<Node>();
  Node curr = root;
  for (;;) 
  {
   if (curr != null) 
   {
    if (curr.right != null)
     stack.push(curr.right);
    
    stack.push(curr);
    curr = curr.left;
   } 
   else 
   {
    if (!stack.isEmpty())
    {
     curr = stack.pop();
     // odd case, exchange curr and top element
     if (!stack.isEmpty() && curr.right == stack.peek()) 
     {
      stack.pop();
      stack.push(curr);
      curr = curr.right;
     }
     else
     {
      System.out.print(curr+"\t");
      curr=null; //move to right or null
     }

    } else
     break;
   }
  }
 }

Please post your suggestions and comments
Happy Coding !!:)