Java Code to find all paths in a grid from start to end.

/*

 1  2 3  4
 5  6   7  8
 9 10 11 12
 13 14  15  16

TC1: invalid grid.
TC2: smaller than len-1 x len-1.
TC3: Functional
           all possible routes.

Returns: number of possible routes from (0,0) to (len-1,len-1) if success,
         -1 on failure.
*/

public int numberOfPossibleRoutes(int[][] grid, int currentRow, int currentColumn, int length)
{
    if( grid  == null )
    {
        return -1;
    }
   
    if( currentRow == length-1 && currentColumn == length-1)
    {
        return 1;
    }
   
    int countToReturn=0;
    // Count the number downwards.
    if( currentRow < length - 1)
    {
        countToReturn += numberOfPossibleRoutes(grid, currentRow+1, currentColumn, length);  
    }
    else if( currentRow == length - 1)
    {
        // Only right count.
        return numberOfPossibleRoutes(grid, currentRow, currentColumn+1, length);
    }
    else
    {
        throw new ArrayIndexOutOfBoundsException();
    }
   
    // Count right possibilities
    if( currentColumn < length-1)
    {
        countToReturn += numberOfPossibleRoutes(grid, currentRow, currentColumn+1, length);   
    }
    else if( currentColumn == length-1)
    {
        return numberOfPossibleRoutes(grid, currentRow+1, currentColumn, length);
    }
    else
    {
        throw new ArrayIndexOutOfBoundsException();
    }
    
    return countToReturn;
}

Java Code to Convert Binary Tree to Circular Doubly Linked List

/*
This function processes Binary Tree as show below
                               1
                 2                           3
      4                5
to circular doubly linked list as shown


4 <-> 2 <-> 5 <-> 1 <-> 3

Also links to 4 and 3 are updated.
*/

public void convertBTToCDLL(Node current, Node toReturnHead, Node toReturnTail)
{
    // Exit conditions and Null handling here.
    if( current == null )
    {
        return;
    }
   
    // convert left sub tree to CDLL
    Node leftSubTreeHead=null;
    Node leftSubTreeTail=null;
    if( current->left )
    {
        convertBTToCDLL(current->left, leftSubTreehead, leftSubTreeTail);
    }
   
    // convert right sub tree to CDLL
    Node rightSubTreeHead=null;
    Node rightSubTreeTail=null;
    if(current->right)
    {
        convertBTToCDLL(current->right, rightSubTreeHead, rightSubTreeTail);
    }
  
    // Convert the current node to CDLL 
    if(! leftSubTreeTail)
    {
        leftSubTreeTail = leftSubTreeHead = current;
  
    }
       
    if(! rightSubTreeHead)
    {
        rightSubTreeHead = rightSubTreeTail = current;
    }


    leftSubTreeTail->right = current;
    current->left = leftSubTreeTail;

    rightSubTreeHead->left = current;
    current->right = rightSubTreeHead;

    // Make this circular
    toReturnHead = leftSubTreeHead;
    toReturnTail = rightSubTreeTail;
}

Best way to engineer software products!

1. Gather Requirements thoroughly.
2. Make High Level Architecture.
3. Write Sequence diagrams.
4. Make Low Level design.
5. Make Data Model.
6. Write Use Case based Test Cases.
7. Identify Objects, Methods and APIs.
8. Identify Design patterns, files organization, library structure.
9. And Coding should be brain dead job (mostly). 

Gather Requirements thoroughly:
This is where it starts. The right questions to ask at this point is :

1. What problem does this product solve?
2. How will it impact customers?
3. In what way will the end-product look like? 
4. In what way shall the requirements change?
5. How much load should the product serve?
6. To what extent, should it scale reasonably?

Make High Level Architecture:
At this step, identifying large pieces (or blocks) that contain reasonable ambiguity. See how those blocks are connected to each other. Right questions to ask at this point is:

1. What could be the role of each block in serving customers?
2. How many different types of customers exist in the system?
3. What choice of database would be most suitable?
4. How many varieties of data stores (or tables ) would be needed?

Write Sequence diagrams:
These define the interactions between each block in the high level architecture.

Make Low level design:
This point is to break a lot of ambiguity by breaking each block into various smaller components. Making flow charts of how each smaller components would interact with each other should be done here.

Make Data Model: 
At this point, define how the data in the system flows from the customer to the database and from the database to the customer. Typically identification of what exact fields are required in the database would be done here.

Write Use Case based Test Cases:
Use cases are typically defined as one task a customer achieves in the product. Writing these as exhaustively as possible helps a lot while going to the next level. These test cases would come really handy in absorbing ambiguity while coding.


Rest are self-explanatory.

At each of these steps, one needs to keep an eye on how fast things could change and each step should reasonably adapt to changes in the environment.

Java Code to create Prefix Tree and run string matcher on it

/* package whatever

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

/* Name of the class has to be "Main" only if the class is public. */
class PrefixTreeUser
{
    public static void main (String[] args) throws java.lang.Exception
    {
        //Basic exact match
        {
            StringMatcher matcher = new StringMatcher();
            matcher.add_exact_match("contactus", 1);
            assert(matcher.lookup("contactus") == 1);
        }
        //Basic prefix test
        {
            StringMatcher matcher = new StringMatcher();
            matcher.add_prefix_match("img", 1);
            assert(matcher.lookup("imgcutepuppy") == 1);
            assert(matcher.lookup("htmlcutepuppy") == -1);
        }
        //Basic longest match test
        {
            StringMatcher matcher = new StringMatcher();
            matcher.add_prefix_match("img", 1);
            matcher.add_prefix_match("imghd", 2);
            assert(matcher.lookup("imgcutepuppy") == 1);
            assert(matcher.lookup("imghdcutepuppy") == 2);
        }

    }
}

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

class StringMatcher
{

final private PrefixTree prefixTree;

public StringMatcher()
{
    prefixTree = new PrefixTree();
}
   
/// Add an exact string match, i.e. ÒabcÓ in
/// the documentation above. Adding an exact match for an
/// existing `exact_str` will overwrite the previous `id`.
/// @param exact_str string to match with the id.
/// @param id that is mapped to this string.
public void add_exact_match(String exact_str, int id) {
    prefixTree.createPathFor(exact_str, true, id);
}

/// Add a prefix string match
/// the documentation above. Adding a prefix match for an
/// existing `prefix_str` will overwrite the previous `id`.
/// @param prefix_str to match with the id.
/// @param id(>=0) that is mapped to this string.
public void add_prefix_match(String prefix_str, int id) {
    prefixTree.createPathFor(prefix_str, false, id);
}

/// Get the id for the specified string.
/// @param input to lookup the id for
/// @returns -1 if there is no match or the id
public int lookup(String input) {
    return prefixTree.scanPathFor(input);
}

/// Delete the exact matches for the given string, i.e. if we have
/// an add_exact_match(str 2), delete_exact_match will remove the
/// match of str to 2.
/// @param exact_str exact match to delete.
/// @return true if a match was deleted.
boolean delete_exact_match(String exact_str) {
    return false;
}

/// Delete the prefix matches for the given string, i.e. if we have
/// a add_prefix_match(str, 2), delete_prefix_match will remove the
/// match of str to 2.
/// @param prefix_str prefix match to delete.
/// @return true if a match was deleted.
boolean delete_prefix_match(String prefix_str) {
    return false;
}

}

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

class Node
{
    private char alphabet;
    protected Node[] next;
    private int partialMatch;
    private int exactMatch;
   
    public Node(char c)
    {
        next = new Node[Util.MAX_ALPHABETS_RANGE];
        setAlphabet(c);
    }
   
    // @return get's char value
    public char getAlphabet()
    {
        return alphabet;
    }
   
    // @param alphabet value to be set
    public void setAlphabet(final char alphabetValue)
    {
        alphabet = alphabetValue;
    }
   
    // @return partialMatch of the node alphabet
    public int getPartialMatch()
    {
        return partialMatch;
    }
   
    // @param partialMatchValue to be set for node's alphabet
    public void setPartialMatch(final int partialMatchValue)
    {
        partialMatch = partialMatchValue;
    }
   
    // @return exactMatch of this node's alphabet
    public int getExactMatch()
    {
        return exactMatch;
    }
   
    // @param exactMatchValue to be set for this node's alphabet
    public void setExactMatch(final int exactMatchValue)
    {
        exactMatch = exactMatchValue;
    }
   
    // @param childNumber is alphabet's numeric value
    // @return child node corresponding to that numeric value
    public Node getChildAt(final int childNumber)
    {
        if(childNumber >= Util.MAX_ALPHABETS_RANGE)
        {
            // Can do better here. For now, lets not worry about exceptions too much.
            throw new RuntimeException("Your tree is expecting more than alphabets range");
        }
       
        return next[childNumber];
    }
   
    // @param childNumber to be set
    // @param childNode to be set for this node
    public void setChildAt(final int childNumber, final Node childNode)
    {
        if(childNumber >= Util.MAX_ALPHABETS_RANGE)
        {
            // Can do better here. For now, lets not worry about exceptions too much.
            throw new RuntimeException("Your tree is expecting more than alphabets range");
        }
       
        next[childNumber] = childNode;
    }
}

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

class Util
{
    public static final int MAX_ALPHABETS_RANGE=52;
   
    public static int convertCharToNumber(char c)
    {
        int i = c;
        if( i >= 65 && i <= 90 )
        {
            return ( i - 65 );
        }
        else if ( i >= 97 && i <= 122 )
        {
            // Arithmetic not solved for readability
            return ( i - 97 + 26);
        }
        else
        {
            throw new RuntimeException("Only [azAZ+] characters please!");
        }
    }
}

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

class PrefixTree
{
    public Node[] head;
   
    public PrefixTree()
    {
        head = new Node[Util.MAX_ALPHABETS_RANGE];
    }
   
    // Creates prefix tree path
    // @param prefixStr string for which path is created
    // @param isExactMatchvalue true if called for exact match
    // @param matchValue value to store for nodes in the path
    public void createPathFor(final String prefixStr, final Boolean isExactMatchValue, final int matchValue)    
    {
        int index = Util.convertCharToNumber( prefixStr.charAt(0) );
        Node currentNode = head[ index ];
       
        if( currentNode == null )
        {
            head[ index ] = currentNode = new Node( prefixStr.charAt(0) );
            if( prefixStr.length() == 1 )
            {
                if( isExactMatchValue == true )
                {
                    currentNode.setExactMatch(matchValue);
                }
                else
                {
                    currentNode.setPartialMatch(matchValue);
                }
           
                return;
            }
        }
       
       
        for(int i=1; i < prefixStr.length(); i++ )
        {
            char c = prefixStr.charAt(i);
            int currentIndex = Util.convertCharToNumber(c);
           
            if( currentNode.next[currentIndex] == null )
            {

                currentNode.next[currentIndex] = new Node(c);
                currentNode = currentNode.next[currentIndex];
               
                if( isExactMatchValue )
                {
                    if( i == prefixStr.length() - 1 )
                    {
                        currentNode.setExactMatch(matchValue);
                    }
                }
                else
                {
                    currentNode.setPartialMatch(matchValue);
                }
            }
            else
            {
                if ( !isExactMatchValue && currentNode.getPartialMatch() != 0 )
                {
                    currentNode.setPartialMatch(matchValue);
                }
               
            }
        }
    }
   
    // Scans prefix tree to return the matched value for the given string
    // @param prefixStr string in question for which value is to be returned
    // @param isExactMatch either to return exact or partial match
    public int scanPathFor(final String prefixStr)
    {
        int prefixMatch=-1;
        Node currentNode = head[ Util.convertCharToNumber( prefixStr.charAt(0) ) ];
       
        if( currentNode == null )
        {
            return -1;
        }
       
        int i;
        for( i=1; i < prefixStr.length(); i++)
        {
            char c = prefixStr.charAt(i);
            int currentIndex = Util.convertCharToNumber(c);           
           
            if( currentNode.next[currentIndex] != null )
            {
                prefixMatch = currentNode.getPartialMatch();
                currentNode = currentNode.next[currentIndex];
            }
            else
            {
                break;
            }
        }
       
        if( i == 0 )
        {
            return -1;
        }

        if( i == prefixStr.length() )
        {
            return currentNode.getExactMatch();
        }
        else
        {
            return prefixMatch;
        }
    }
}
=========================================================================

PHP Code to create a BST and print it in Breadth First Order

/* take an array
 class node. take an element. traverse until the bst condition satisfies.

*/


class node
{
  public $value;
  public $left;
  public $right;
}

$input = array(5,7,3,4,2,6,9);

//  create a parent.

/*
  5
      3                  7
 2       4       6            9      

*/

$current = 0;

$parent = new node();
$parent->value = $input[$current++];
$parent->left = null;
$parent->right = null;

// take next element. see the bst condition.

$currentNode = $parent;

while( $current < count($input) )
{
// take the comparison here.
// move to the left or right accordingly.
// is it ready to insert  ?
if( $input[$current] >= $currentNode->value )
{
// currentNode needs to move to right.
// check if right is null.
if( $currentNode->right == null )
{
$currentNode->right
                        = createNewNode(& $input, & $current);
}
else
{
// advance current to its right.
$currentNode = $currentNode->right;
}
}
else if ( $input[$current] < $currentNode->value )
{

if( $currentNode->left == null )
{
$currentNode->left
                        = createNewNode(& $input, & $current);
}
else
{
// advance current to its left
$currentNode = $currentNode->left;
}
}
}

// Traverse the tree in BFT
// take the top, push all children. print current node.
// go to next level if all done with current level
// same logic almost.

$BFTQueue = array();

array_unshift($BFTQueue,  $parent);

echo "visit: ".$parent->value;

while( count($BFTQueue) > 0 )
{
// next level.
$BFTCurrent = array_pop($BFTQueue);

// print the value and push
echo "visit: ".$BFTCurrent->value;

if($BFTCurrent->left)
{
        array_unshift($BFTQueue, $BFTCurrent->left);
}
if($BFTCurrent->right)
{
        array_unshift($BFTQueue, $BFTCurrent->right);
}

}


function createNewNode($input, $current)
{
$newNode = new node();
$newNode->value = $input[$current++];
$newNode->left=null;
$newNode->right=null;

return $newNode;
}

PHP Code to Create Binary Tree and Breadth First Traversal

/*
        create a binary tree with some input given.

see what level I'm in.
level x, see if I have so many elements in the input
pop 2^(x-1) elements from queue. keep adding left and rights to those.

        1
    2       3
  4  5    6   7
 8 9

*/


class node
{
        public $left;
        public $right;
        public $value;
}

$input = array(1,2,3,4,5,6,7,8,9);

$queue = array();

$i = 0;

$level = 2;
$max = count($input);

$current = new node();
$current->value = $input[$i++];
$current->left = null;
$current->right = null;

array_unshift($queue,  $current);

echo $current->value." ";

while ( $i < $max )
{
        $j = pow(2,$level-1);

        // create nodes until 2^(level-1) and
        while( $j > 0  && $i < $max )
        {

                $parent = array_pop($queue);

                // create a left node
                $newLeft = new node();
                $newLeft->value = $input[$i++];
                $newLeft->left = null;
                $newLeft->right = null;

                $parent->left =  $newLeft;
                array_unshift($queue, $newLeft);

                $j--;

                if($i >= $max || $j <= 0)
                {
                   break;
                }

                // create right node
                $newRight = new node();
                $newRight->value = $input[$i++];
                $newRight->left = null;
                $newRight->right = null;

                $parent->right = $newRight;
                array_unshift($queue, $newRight);

                $j--;
                echo print_r($parent,1);

        }

        $level++;
        echo "level :".$level;
        //echo print_r($queue,1);
}

// Traverse the tree in BFT
// take the top, push all children. print current node.
// go to next level if all done with current level
// same logic almost.

$BFTQueue = array();

array_unshift($BFTQueue,  $current);

echo "visit: ".$current->value;

while( count($BFTQueue) > 0 )
{
// next level.
$BFTCurrent = array_pop($BFTQueue);

// print the value and push
echo "visit: ".$BFTCurrent->value;

if($BFTCurrent->left)
{
        array_unshift($BFTQueue, $BFTCurrent->left);
}
if($BFTCurrent->right)
{
        array_unshift($BFTQueue, $BFTCurrent->right);
}

}

PHP Code for Unique Pairs of Elements in an array

Find all unique pairs of element in an array that sum to S. For ex. If array = {2,4,6,4,6} and S = 8 then answer is {(2,6), (4,4)}


// take the array.
$elements = array(1,2,3,4,6,4, 1);
$sum = 2;
sort($elements);

// now that it took nlogn, we should do away with O(n) next.
$left = 0;
$right = count($elements)- 1;

echo "left value=".$left." right value=".$right;

// goto the sum value. one value lesser than sum actually
for ( $i = $right; $elements[$i] > $sum; $i--)
{}


// final logic. now loop thru
// left should never be greater than right.
// if sum-right is greater than left -> increment left
// if sum-right is less than left -> stop there. this element has no pair. and decrement right.
for( ; $left < $right; )
{
        if( ($sum - $elements[$right]) > $elements[$left])
        {
                // increment left
                $left++;
        }
        else if( ($sum - $elements[$right]) < $elements[$left] )
        {
                // decrement right. no pair found
                $right--;
        }
        else
        {
                // equals output a pair. and decrement right.
                echo "Pair: (".$elements[$left].",".$elements[$right].")";
                // now decrement right until duplicates are all skipped.
                for( $dec = $elements[$right];
                       $dec == $elements[$right];
                       $right--){}
        }
}

The solution is O(n logn) .. can we do better ?