Java Code that finds the shortest path in a matrix from point A to point B

static List<Integer> minSeen = new ArrayList<Integer>();
 public static void main (String[] args) throws java.lang.Exception
 {
  Scanner sc = new Scanner(System.in);
  int t = sc.nextInt();
  for(int i=0;i<t;i++) {
      int n = sc.nextInt();
      int m = sc.nextInt();
      char[][] arr = new char[n][m];
      sc.nextLine();
      int startI = -1;
      int startJ = -1;
      for(int j=0;j<n;j++) {
          int count=0;
          String str = sc.nextLine();
          StringTokenizer tok = new StringTokenizer(str, " ");
          while(tok.hasMoreTokens()) {
              String s = tok.nextToken();
              arr[j][count++] = s.charAt(0);
              if(s.charAt(0) == 'B') {
                  startI = j;
                  startJ = m-1;
              }
          }
      }
      Map<String, Boolean> tracker = new HashMap<String, Boolean>();
      catchP(arr, tracker, 0, n, m, startI, startJ);
      // find min over minSeen here.
      int min = Integer.MAX_VALUE;
      for(Integer minI : minSeen) {
          if( min > minI) {
              min = minI;
          }
      }
      System.out.println(min);
  }
 }
 
 static boolean seenAlready(Map<String, Boolean> tracker, int n, int m) {
     String key = Integer.toString(n) + "." + Integer.toString(m);
     return tracker.containsKey(key);
 }
 
 static boolean isValid(int row, int col, int n, int m) {
     if( row >= 0 && row <= n-1 && col >=0 && col <= m-1) {
         return true;
     }
     return false;
 }
 
 static void catchP(char[][] arr, Map<String, Boolean> tracker, int len, int n, int m, int startI, int startJ) {
     Map<String, Boolean> currentTracker = new HashMap<String, Boolean>();
     if(arr[startI][startJ] == 'C') {
         minSeen.add(len);
     } else if ( arr[startI][startJ] == 'D' || arr[startI][startJ]=='.' && seenAlready(tracker, startI, startJ) ) {
         return;
     } else if ( arr[startI][startJ]=='.' && !seenAlready(tracker, startI, startJ) || arr[startI][startJ] == 'B' ) {
         // copy currentTracker same as tracker.
         tracker.forEach(currentTracker::putIfAbsent);
         String newKey = Integer.toString(startI) + "." + Integer.toString(startJ);
         currentTracker.put(newKey, true);
         if( isValid(startI, startJ-1, n, m)) {
             catchP(arr, currentTracker, len+1, n, m, startI, startJ-1);
         }
         if( isValid(startI-1, startJ, n , m)) {
             catchP(arr, currentTracker, len+1, n, m, startI-1, startJ);
         }
         if( isValid(startI, startJ+1, n, m) ) {
             catchP(arr, currentTracker, len+1, n, m, startI, startJ+1);
         }
         if( isValid(startI+1, startJ, n, m) ) {
             catchP(arr, currentTracker, len+1, n, m, startI+1, startJ);
         }
     }
 }

Test execute it here.

PHP CURL PUT json with username password

Recently I faced a lot of difficulty in requesting a put to RESTful service. If you have faced the similar issue to PUT to a RESTful service with username password, here is a sample snippet. Hope this helps. 

$file_contents_string = file_get_contents("");

$request = curl_init(); 

curl_setopt($request, CURLOPT_URL, "http://dummyhost:dummyport/");


curl_setopt($request, CURLOPT_CUSTOMREQUEST, "PUT");


curl_setopt($request, CURLOPT_RETURNTRANSFER, true);


curl_setopt($request, CURLOPT_HTTPHEADER, array(

'Content-Type: application/json', 'Content-Length: ' . strlen($file_contents_string)));


curl_setopt($request, CURLOPT_POSTFIELDS, $file_contents_string); 


curl_setopt($request, CURLOPT_USERPWD, "$username:$password");


curl_setopt($request, CURLOPT_HTTPAUTH, CURLAUTH_BASIC);


curl_setopt($request, CURLOPT_VERBOSE, true);

// output the response


var_dump(curl_exec($request));

Restore every command typed!

For all those software engineers out there, how many times have you wondered "There must be some command for this occasion" and completely forgot what it was.
To cope with those moments, especially when a new project is being set up,  shell script provides a cool and easy method to backup every command that is typed in it. Just put this in your bash profile or bashrc file.

export HISTCONTROL=erasedups

export HISTSIZE=25000

shopt -s histappend

cp /*home directory*/.bash_history /*home directory*/*backup directory*/"history.before.$(date +%F_%R)"

Now each and every command you typed would be in a backup. I go to the backup directory and grep with some pattern I slightly remember about the command I want to search. This saved me a lot of time. I hope this helps you too.

Java Code that finds Least Common Ancestor in a binary tree

This problem is broken down into 3 pieces.

1. Find the paths to the target nodes.
2. Push them in a stack.
3. Reverse the stacks to find the element just before a mismatch.

Crux is this:

========================================================================

public static Node leastCommonAncestor(Node root, Node one, Node two)

{

if( one == null ) return two;

if( two == null ) return one;

Stack s1 = new Stack();

Stack s2 = new Stack();

s1.push(root);

s2.push(root);

boolean oneFound = findPath(root, one, s1);

boolean twoFound = findPath(root, two, s2);

if( ! oneFound || ! twoFound ) return null;

Stack rev1 = reverseStack(s1);

Stack rev2 = reverseStack(s2);

Node first = (Node) rev1.pop();

Node second = (Node) rev2.pop();

Node lca = first;

while( first.value == second.value )

{

lca = first;

if( ! rev1.empty() ) 

{

first = (Node) rev1.pop();

}

if( ! rev2.empty() )

{

second = (Node) rev2.pop();

}

}

return lca;

}

========================================================================

Code that reverses the stack should be easy. But findPath is the one needs attention.

========================================================================

public static boolean findPath(Node current, Node destNode, Stack s)

{

if( current == null ) return false;

if( current.value == destNode.value )

{

return true;

}

if( current.left != null )

{

s.push(current.left);

boolean found = findPath(current.left, destNode, s);

if(  found ) return true;

else s.pop();

}

if( current.right != null )

{

s.push(current.right);

boolean found = findPath(current.right, destNode, s);

if(  found ) return true;

else s.pop();

}

return false;

}

========================================================================

Test execute it here.

Java Code that converts String to Integer. Standard atoi function.

As a first thing, we need to sanitise the string.

1. It could be null.
2. It could have leading and trailing spaces.
3. It could have an additional +/- symbols.
4. It could have invalid characters, spaces and what not. 

As a next thing, for all we know the string could contain values more than Integer.MAX_VALUE. So, we don't accept strings of length more than that. 

Now, we simply pluck out each character, get it's integer value and add the corresponding exponent's according to the digit's position. We need to take caution when trying to add each characters because the string could still have a value more than Integer.MAX_VALUE. 

If we add the new value like this

    convertedInt + newValueToAdd > Integer.MAX_VALUE

it might overflow. 

So we do the opposite.
  convertedInt <= Integer.MAX_VALUE - newValueToAdd

Here is the implementation.
========================================================================

public static void main (String[] args) throws java.lang.Exception
{
String a = "2147483647";
System.out.println("Integer : " + atoi(a));
}

public static int atoi(String a) throws Exception
{
String sane = checkSanity(a);
if( sane == null )
{
throw new Exception("Not compatible");
}

if( sane.length() > 10 )
{
throw new Exception("Overflow");
}

if( sane.length() <= 0 )
{
throw new Exception("Underflow");
}

int convertedInt = 0;
int exponent = 0;
for( int i = sane.length() - 1; i >= 0 ; i-- )
{
int newDigit = Character.getNumericValue( sane.charAt(i) );

int newValueToAdd = (int) ( Math.pow(10, exponent) * newDigit );

if( convertedInt <= Integer.MAX_VALUE - newValueToAdd )
{
convertedInt += newValueToAdd;
}
else
{
throw new Exception("Overflow");
}

exponent++;
}

return convertedInt;
}

public static String checkSanity(String a)
{
// could be null
if( a == null )
{
return null;
}

// Trim leading and trailing spaces.
String b = a.trim();

// Should it have + or - symbol, consider.
String c;
if( b.charAt(0) == '+' || b.charAt(0) == '-' )
{
c = b.substring(1);
}
else
{
c = b.substring(0);
}

// could have special characters and non numbers.
for( int i = 0; i < c.length(); i++ )
{
if( ! Character.isDigit(c.charAt(i)) )
{
return null;
}
}

return c;
}
}

========================================================================

Test execute it here.

Java code that adds '1' to linked list of digits by reversing the list.

The idea is to reverse the list first. Keep adding the carry from the start to the end and perhaps, create a carry node at the end and then reverse back to normal order.

========================================================================

class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// create LL
                 ..
                 ..          
                 ..
                 ..
Node reversedHead = reverseLL(head);
incrementLL(reversedHead);
Node normal = reverseLL(reversedHead);
}

public static void incrementLL(Node head)
{
Node current = head;
Node previous = current;
int carry = 1;

while( current != null && carry > 0 )
{
int temp = current.value;

temp += carry;
carry = temp / 10;
temp %= 10;

current.value = temp;
previous = current;
current = current.next;
}

if( carry > 0 )
{
Node last = createNewNode(carry);
previous.next = last;
}

}

public static Node reverseLL(Node head)
{
Node current = head;
Node previous = null;

while( current != null )
{
Node temp = current.next;

current.next = previous;
previous = current;
current = temp;
}

return previous;
}

}
========================================================================

Test Execute it here.

Smartest way to clone a Linked List that has a random pointer

Solution is to clone the list by modifying 'next' in this way first:

Original
-->1        2-------|       3-------|      4-------|
     |        /|\        |       /|\        |       /|\      |
    \|/        |        \|/       |        \|/       |      \|/
-->1------ |        2-------|       3-------|       4
Cloned

And then, map all the random pointers in the original list to the cloned list. Their correspondence makes this easy now.

And finally, map the next pointers to their original nodes.

--------------------------------------------------------------------------------------------------------------------------

import java.util.*;
import java.lang.*;
import java.io.*;

class CloneLinkedList
{
public static void main (String[] args) throws java.lang.Exception
{
// create LL
Node head = createNewNode(1);
Node two = createNewNode(2);
Node three = createNewNode(3);
Node four = createNewNode(4);

head.next = two;
two.next = three;
three.next = four;

head.random = three;
two.random = four;

Node clonedList = clone(head);
Node current = clonedList;
while(current != null)
{
System.out.println("val: "+ current.value );
if( current.random != null)
System.out.println(" random: " + current.random.value);
current = current.next;
}
}

public static Node clone(Node head)
{
if( head == null )
{
return null;
}

Node current = head;
while( current != null)
{
Node temp = createNewNode(current.value);
temp.next = current.next;
current.next = temp;
current = temp.next;
}

Node clonedHead = head.next;

current = head;
while( current != null )
{
if( current.random != null)
{
current.next.random = current.random.next;
}

current = current.next.next;
}

current = head;
while( current != null )
{
Node temp = current.next;
current.next = temp.next;
current = current.next;
if( current != null)
{
temp.next = current.next;
}
}

return clonedHead;
}

public static Node createNewNode(int value)
{
Node node = new Node(value);
return node;
}
}

class Node
{
int value;
Node next;
Node random;

public Node(int val)
{
value = val;
}
}

--------------------------------------------------------------------------------------------------------------------------

Cases that need caution:

1. Random could be null or might point in reverse direction.
2. Edge case when mapping next pointers back. temp.next can only point to current.next when current  is non null.
--------------------------------------------------------------------------------------------------------------------------
Test Execute it here

Java code for Iterative Inorder Traversal of a Binary Tree

import java.util.*;
import java.lang.*;
import java.io.*;

class BinaryTreeInorderTraversal
{
    public static Stack stack = new Stack();
    public static void main (String[] args) throws java.lang.Exception
    {
        // create some input
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.right.left = new Node(4);
       
        iterativeInorder(head);
    }
   
    static void iterativeInorder(Node head)
    {
        Node current = head;
        while( current != null )
        {
           
            if( current.left != null && current.left.visited == false)
            {   
                stack.push( current );
                current = current.left;
                continue;
            }
            else
            {
                visit(current);
                current.visited = true;
            }
           
            if( current.right != null )
            {
                current = current.right;
            }
            else
            {
                if( ! stack.empty() )
                {
                    current = (Node) stack.pop();   
                }
                else
                {
                    current = null;
                }
               
            }
           
        }
    }
   
    static void visit(Node current)
    {
        System.out.println(current.value+"\n");
    }
}

class Node
{
    public Node left=null;
    public int value;
    public boolean visited=false;
    public Node right=null;
   
    public Node(int value)
    {
        this.value = value;
    }
}

Test Execute it here.

Java code that maximizes Buy-Sell + Buy-Sell profit on Stock prices for past week when Introspected.

import java.util.*;
import java.lang.*;
import java.io.*;


class StockPricesIntrospection
{
    public static void main (String[] args) throws java.lang.Exception
    {
                // Test Input here
        int[] inputArr = new int[] {38, 40, 42, 35, 23, 50};
       
        int size = inputArr.length;
        int[][] maxValuesFrom = new int[6][6];
       
        for( int start=0; start < size-1; start++)
        {
            int minimumStartingPrice = inputArr[start];
            int maximumEndingPrice = inputArr[start];
           
            for( int end=start+1; end < size; end++)
            {
                if( maximumEndingPrice < inputArr[end] )
                {
                    maximumEndingPrice = inputArr[end];   
                }
               
                maxValuesFrom[start][end] = ( maximumEndingPrice - minimumStartingPrice );
            }
        }
       
        int finalMaxStockPrice=0;
        for( int startIndex=0; startIndex < size; startIndex++)
        {
            int localMax=maxValuesFrom[startIndex][size-1];
            for(int endIndex=startIndex+1; endIndex < size; endIndex++)
            {
                int sumValue;
                if ( endIndex == size - 1 )
                {
                    sumValue = localMax;
                }
                else
                {
                    sumValue = maxValuesFrom[startIndex][endIndex] +
                                        maxValuesFrom[endIndex+1][size-1];   
                }
               
               
                if( sumValue > maxValuesFrom[startIndex][size-1] && sumValue > localMax )
                {
                    localMax = sumValue;
                }
            }
           
            if( finalMaxStockPrice < localMax )
            {
                finalMaxStockPrice = localMax;
            }
        }
       
    System.out.println("Max stock price profit could have been " + finalMaxStockPrice);
    }
}

Time complexity: O( n squared)
Space complexity: O(n squared)
Test Execute it here.

Java Code to find Max ones in a 2D array of 0's and 1's row wise sorted.

import java.util.*;
import java.lang.*;
import java.io.*;

class FinderOfOnes
{
    static int maxOnes=0;
   
    public static void main (String[] args) throws java.lang.Exception
    {
        // Test input.
        int[][] inputArr = new int[5][5];
        for(int i = 0; i < 5; i++)
        {
            for( int j =0; j < 5; j++)
            {
                inputArr[i][j] = 1;
            }
        }
        System.out.println( "Max ones are "  + findMaxOnes(inputArr) );
    }
   
    static int findMaxOnes(int[][] Arr)
    {
        int start = 0;
        int end = Arr.length;
        int mid = (start + end )/ 2;
        binarySearch(Arr, start, mid, end);
        return maxOnes;
    }
   
    static void binarySearch(int[][] Arr, int start, int mid, int end)
    {
        if( end == start+1 )
        {
            if( end == Arr.length - 1 )
            {
                updateMaxIfFoundOn(end, Arr);
            }
            else
            {
                updateMaxIfFoundOn(start, Arr);
            }
           
            return;
        }
       
        if( updateMaxIfFoundOn(mid, Arr) )
        {
            end = mid;
        }
        else
        {
            start = mid;
        }
       
        mid = (start + end)/2;
        binarySearch(Arr, start, mid, end);
    }
   
    static boolean foundOneOn(int columnNumber, int[][] Arr)
    {
        for( int row=0; row < Arr.length; row++ )
        {
            if( Arr[row][columnNumber] == 1 )
            {
                return true;
            }
        }
       
        return false;
    }
   
    static boolean updateMaxIfFoundOn(int columnNumber, int[][] Arr)
    {
        boolean found = foundOneOn(columnNumber, Arr);
        if( found &&
            maxOnes < ( Arr.length - columnNumber) )
        {
            maxOnes = Arr.length - columnNumber;
        }
        return found;
    }
}

Test Execute it here: http://ideone.com/c9Xs0n

PHP Code that evaluates Expressions in spreadsheets using DFS on Forest

/* Author: Sunil Kata

** Filename: ExpressionEvaluator.php
** Date: 10 May 2014
** Input: Expects a file name which has spreadsheets information with the test cases
** Output: Evaluates expression of each test case for those spreadsheets
** Description: This program creates a hash map of all cells per spreadsheet, considers mapping via expressions as edges of a tree.
                This will result in disconnected collection of trees, which could be called as Forest.
                The program does DFS on each of disconnected tree and evalutes the expression while traversing.
** PreConditions: The format of the input file has to be in certain order. Order shown below
                  No of test cases as T
                  S1 :No of cells
                  c1: Expression
                  c2:
                  .
                  .              
                  S2: No of cells
                  c1: Expression
                  .
                  .
                  S Tth: No of cells
                  c1: expression
                  .
                  .
*/


if( sizeof($argv) < 2 )
{
    echo "Usage: ExpressionEvaluator.php input_file_name\n";
    exit(1);
}

$testCasesArray = createHashedArrayOfCells( $argv[1] );

foreach($testCasesArray as $testCaseNumber => $spreadsheet)
{

    depthFirstForests($spreadsheet);

    $singleSheetEvaluated = array();
    foreach($spreadsheet as $key => $cell )
    {
        $singleSheetEvaluated[$key]=$cell['value'];
    }
    ksort($singleSheetEvaluated);
    $outputArray[]=$singleSheetEvaluated;
}
writeOutput($outputArray);

/************** End of Processing **********************/

/* Input: Takes the file name that contains spreadsheets info
** Description: Read the cell info from the file line-by-line and stores the info in a hashed array of spreadsheets info
** Output: One element is one test case info. Gives out hashed array of all test cases info.
** Precondition: Valid input file name.
** Modifies: None
*/

function createHashedArrayOfCells( $inputFileName )
{
    $testCasesArray = array();
    $expressionArray = array();
    $expectingTotalTestCasesNumber=true;
    $totalNumberOfCases=0;
    $expressionRead=0;
    $testCasesRead=0;

    $handle = fopen($inputFileName,'r');

    if( $handle )
    {
        while( ( $buffer = fgets($handle) ) != false )
        {
            $buffer = trim($buffer);
            $length = strlen($buffer);

            if( $length == 0 ) continue;

            if( $expectingTotalTestCasesNumber )
            {
                $expectingTotalTestCasesNumber = false;
                $expectingTestCaseLength = true;

                $totalNumberOfCases = intval($buffer) != 0 ? intval($buffer) : 0;
                if( ! $totalNumberOfCases )
                {
                    echo "Not a valid test cases number."; exit(1);   
                }

                continue;
            }

            if( $expectingTestCaseLength )
            {
                $expectingTestCaseLength = false;
                $testCasesRead++;
                $expectingExpression = true;

                $totalNumberOfExpressions = intval($buffer) != 0 ? intval($buffer) : 0;
                if( ! $totalNumberOfExpressions )
                {
                    echo "Not a valid number of expressions.";
                }
                continue;
            }

            if( $expectingExpression )
            {
                $expressionRead++;
                if( $length >= 3 )
                {
                    $expressionEquation = explode("=",$buffer);
                    $expressionEquation[0] = trim($expressionEquation[0]);
                    $expressionEquation[1] = trim($expressionEquation[1]);
                    if( sizeof($expressionEquation) > 2 )
                        echo "invalid expression";
                    else
                    {
                        $isExpression = ( intval($expressionEquation[1]) == 0 );
                        $expressionArray[$expressionEquation[0]] = array('expression'=>$expressionEquation[1],'value'=>intval($expressionEquation[1]),'visited'=>false);
                    }     
                }
                else
                {
                    echo "expression cannot have 2 characters";
                }
               
                if( $expressionRead == $totalNumberOfExpressions )
                {
                    $testCasesArray[] = $expressionArray;
                    $expressionArray = array();
                    $expressionRead=0;
                    $expectingExpression = false;

                    if( $testCasesRead == $totalNumberOfCases )
                        $expectingTestCaseLength=false;
                    else
                        $expectingTestCaseLength=true;   
                }
            }
        }

        fclose($handle);
        return $testCasesArray;
    }
    else
    {
        echo "Cannot open file name. Path to file could be incorrect";
        exit(1);
    }

}

/* Input: An array of cells for one spreadsheet
** Output: An array of cells with expression evaluted for all trees in one spreadsheet.
** Description: Calls DepthFirstSearch i.e., expressionEvaluator here, for all unvisited
                trees in the spreadsheet forest.
*/

function depthFirstForests(&$spreadsheet)
{
    foreach($spreadsheet as $cell => $value )
    {
        if(!$spreadsheet[$cell]['visited'])
            expressionEvaluator($spreadsheet, $cell);
    }
}

/* Input: An array of cells for one spreadsheet.
** Output: Array of cells with expression evaluted to value field.
** Modifies: The input array is modified
** Description: Evaluates expression using Depth First search on cells.
                Extract each cell from expression, recursively calls the
                same function until all cells are evaluated to integers.
*/

function expressionEvaluator(&$spreadsheet, $currentCell)
{
    if( ! $spreadsheet[$currentCell]['visited'] )
    {
        $spreadsheet[$currentCell]['visited']=true;
        $expression = $spreadsheet[$currentCell]['expression'];
        $newExpression = str_replace(array('+','-','/','*'),"+",$expression);
        $valuesArray = explode("+", $newExpression);

        foreach( $valuesArray as $cell )
        {
            $cell = trim($cell);
            if( intval($cell) == 0 && array_key_exists($cell, $spreadsheet) )
            {
                // found a cell. visit it before evaluating
                if( ! $spreadsheet[$cell]['visited'] )
                {
                    expressionEvaluator($spreadsheet, $cell);
                }
                $spreadsheet[$currentCell]['expression'] = str_replace($cell, $spreadsheet[$cell]['value'], $spreadsheet[$currentCell]['expression']);
            }
        }
        // evaluate this expression
        eval("\$expression=intval(".$spreadsheet[$currentCell]['expression'].");");
        $spreadsheet[$currentCell]['value']=$expression;
    }
    return;
}

/*Input: Expects the output of the program
**output: Write to a file called output.txt
** Description: If it could not write to output.txt, it just prints the result.
*/

function writeOutput(&$outputArray)
{

    $handle = fopen('output.txt','w');
    if($handle)
    {
        foreach($outputArray as $spreadsheet )
        {
            foreach($spreadsheet as $cell => $value )
            {
                $line=$cell." = ".$value."\n";
                fputs($handle,$line);
            }
            fputs($handle, "\n");
        }
        fclose($handle);
    }
    else
    {
        echo "Cannot open file, so printing output here ";
        print_r($outputArray);   
    }

}