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