Tuesday, 9 September 2014

Program to find shortest distance to particular value in a matrix

Given a matrix of -1's and 0's, display a matrix which contains minimum distance to reach nearest 0 from that particular position.
Example:
Input1: 
-1,0,-1
-1,-1,-1
-1,-1,-1
Output: 
1,0,1
2,1,2
3,2,3

Input2: 
-1,0,-1
-1,-1,-1
-1,0,-1
Output:
1,0,1
2,1,2
1,0,1

Algorithm:
1. Figure out the all positions in matrix having zero and cache them.
2. Calculate the distance from each position to the cached zero positions by summing absolute distance of x and y co-ordinates.
3. Put the minimum value in the result matrix.


package com.prasune.coding;

import java.util.ArrayList;
import java.util.List;

public class ShortestDistance {

      public static void main(String[] args) {
            int matrix[][] = {
                                  {-1,0,-1},
                                  {-1,-1,-1},
                                  {-1,0,-1}
                                 };
            printAsMatrix(matrix);
            printDistanceToZero(matrix);
      }

      private static void printDistanceToZero(int[][] matrix) {
            int[][] resultMatrix = new int[matrix.length][matrix.length];
            List<Position> zeroPositions = new ArrayList<Position>();
           
            for (int i = 0; i < matrix.length; i++) {
                  for (int j = 0; j < matrix[i].length; j++) {
                        if(matrix[i][j] == 0){
                              zeroPositions.add(new Position(i,j));
                        }                      
                  }
            }
           
            for (int i = 0; i < matrix.length; i++) {
                  for (int j = 0; j < matrix[i].length; j++) {
                        if(matrix[i][j] == 0){
                              resultMatrix[i][j] = 0;
                        } else{
                              int minValue = Integer.MAX_VALUE;
                              for (Position position : zeroPositions) {
                                    int tempMinValue = Math.abs(i - position.getRowNum()) +
                                                               Math.abs(j - position.getColNum());
                                    if(tempMinValue < minValue){
                                          minValue = tempMinValue;
                                    }
                              }
                              resultMatrix[i][j] = minValue;
                        }                                        
                  }
            }
            printAsMatrix(resultMatrix);
      }

      private static void printAsMatrix(int[][] matrix) {
            for (int i = 0; i < matrix.length; i++) {
                  for (int j = 0; j < matrix[i].length; j++) {
                        System.out.print(matrix[i][j]);
                        if(j < matrix[i].length-1){
                              System.out.print(",");
                        }                      
                  }
                  System.out.println();
            }
      }
}

Position.java

package com.prasune.coding;

public class Position {

      private int rowNum;
      private int colNum;
     
      public Position(int rowNum, int colNum) {
            this.rowNum = rowNum;
            this.colNum = colNum;
      }
      public int getRowNum() {
            return rowNum;
      }
      public void setRowNum(int rowNum) {
            this.rowNum = rowNum;
      }
      public int getColNum() {
            return colNum;
      }
      public void setColNum(int colNum) {
            this.colNum = colNum;
      }
}




Sunday, 7 September 2014

Add two large numbers that cannot be stored in numeric data types

You are given two numbers as String which are so large that it cannot be stored in any of the numeric data types. You need to return the sum of these numbers as String.

"it cannot be stored in any of the numeric data types" means it includes Long, BigDecimal etc.. Assume around 1000 digits in the number

package com.prasune.coding;

import java.util.Stack;

public class AddBigNumbers {

      public static void main(String[] args) {
            String number1 = "123456789129";
            String number2 = "345343";
            System.out.println(add(number1, number2));
      }

      public static String add(String number1, String number2){
            String result = "";
            Stack<Integer> n1 = new Stack<Integer>();
            Stack<Integer> n2 = new Stack<Integer>();
            Stack<Integer> sum = new Stack<Integer>();
            int carryForwardValue = 0;
            for (int i = 0; i < number1.length(); i++) {
                  n1.push(Integer.parseInt("" + number1.charAt(i)));
            }
            for (int i = 0; i < number2.length(); i++) {
                  n2.push(Integer.parseInt("" + number2.charAt(i)));
            }
            while(!n1.empty() || !n2.empty()){
                  int digit1 = 0;
                  int digit2 = 0;
                  if(!n1.empty()){
                        digit1 = n1.pop();
                  }
                  if(!n2.empty()){
                        digit2 = n2.pop();
                  }                
                  int sumOfNumbers = digit1 + digit2 + carryForwardValue;
                  sum.push(sumOfNumbers % 10);
                  carryForwardValue = sumOfNumbers/10;
            }
            while(!sum.empty()){
                  result = result + sum.pop();
            }
            return result;
      }
}



Friday, 5 September 2014

Program to reverse a given sentence in java

Write a program to reverse a sentence in Java

For example if you have a sentence "Quick brown fox jumped over a lazy dog",
your output should be "dog lazy a over jumped fox brown Quick"


package com.prasune.coding;

import java.util.Stack;
import java.util.StringTokenizer;

public class ReverseSentence {

      public static void main(String[] args) {
            System.out.println(getReverseString("Quick brown fox jumped over a lazy dog"));
      }

      public static String getReverseString(String str){
        StringTokenizer tokenizer = new StringTokenizer(str);
        Stack<String> stack = new Stack<String>();
        String reversedString = "";
        while(tokenizer.hasMoreTokens()){
          stack.push(tokenizer.nextToken());
        }
        while(!stack.empty()){
              reversedString = reversedString + stack.pop() + " ";
        }
        return reversedString.trim();
      }
}



Java Stack Iterator does not work in LIFO order

While attending solutions using Java stack, be careful not to use iterator. The java Stack iterator will return the values to you in FIFO order instead of your expected LIPFO order.