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);   
    }

}

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.