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

}