Tag Archives: algorithm

DeterminantOfMatrix


4. Determinant of a 2D matrix

Problem:

Given a 2D matrix, Determine it’s Determinant.

Solution:

This implementation is done using C#.NET. Rectangular Matrix is declared using int[,] syntax.

public static long EvaluateDeterminant(int[,] matrix)
{
long determinant = 0;

if (matrix == null || matrix.GetUpperBound(0) != matrix.GetUpperBound(1))
{
Console.WriteLine("Non-square matrix can't have a determinant");

return determinant;
}

int row_UB = matrix.GetUpperBound(0);

determinant = Determinant(matrix, row_UB + 1);

return determinant;
}

private static long Determinant(int[,] matrix, int size)
{
long determinant = 0;

if (size == 1) // 1x1 MAtrix
{
determinant = matrix[0, 0];
}
else if (size == 2) // 2x2 MAtrix
{
determinant = matrix[0, 0] * matrix[1, 1] - matrix[0, 1] * matrix[1, 0]; // can hash this multiplication
}
else
{
int multiplier = 1;

for (int i = 0; i < size; i++)
{
multiplier = (i % 2 == 0) ? 1 : -1;

determinant += multiplier * matrix[0, i] * Determinant(GetMinor(matrix, size, 0, i), size - 1);
}
}

return determinant;
}

/// <summary>
/// Gets the Minor of a Square Matrix
/// </summary>
/// <param name="matrix"></param>
/// <param name="size"></param>
/// <param name="rowIndex"></param>
/// <param name="colIndex"></param>
/// <returns></returns>
/// <remarks>
/// If function has to be Public, Certain checks on rowIndex, ColIndex should be made and size need not to be passed
/// </remarks>

private static int[,] GetMinor(int[,] matrix, int size, int rowIndex, int colIndex)
{
int minorSize = size - 1;
int[,] minor = new int[minorSize, minorSize];

for (int i = 0; i < rowIndex; i++)
{
for (int j = 0; j < colIndex; j++)
{
minor[i, j] = matrix[i, j];
}
}

for (int i = rowIndex + 1; i < size; i++)
{
for (int j = 0; j < colIndex; j++)
{
minor[i - 1, j] = matrix[i, j];
}
}

for (int i = 0; i < rowIndex; i++)
{
for (int j = colIndex + 1; j < size; j++)
{
minor[i, j - 1] = matrix[i, j];
}
}

for (int i = rowIndex + 1; i < size; i++)
{
for (int j = colIndex + 1; j < size; j++)
{
minor[i - 1, j - 1] = matrix[i, j];
}
}

return minor;
}

Advertisements

Infix to Prefix Conversion


3. Convert Infix Expression to Prefix Expression

Problem:

Given an infix expression, output the expression in Prefix (Polish Notation) form.

For e.g.

Solution:

This implementation is done using C#.NET.

ALGORITHM:

This algorithm maintains two stacks. 1st stack for all operators and 2nd stack to store the operands.

1)  Validate the Infix Expression for correctness

a) ‘(‘ and ‘)’ are in pairs

b) Operator is in between 2 operands (Binary operators are considered only)

2)  If Infix Expression is Valid then

a)  Push ‘(‘ to Operator Stack and Append ‘)’ to Infix Expression

b)  Scan each character in the Infix expression

i)  If scanned character is ‘(‘

Then

Push it to Operator Stack

ii)  Else If scanned character is ‘)’

Then

(a)  Repeat the below steps until ‘(‘ is popped out from Operator Stack

(b)  Pop from Operator Stack into OPERATOR

(c)  If OPERATOR  != ‘(‘

(i)  Pop twice from Operand Stack into OPERAND2 and OPERAND1

(ii)  Push “OPERATOR OPERAND1 OPERAND2” in Operand Stack

iii)  Else If scanned character is an Operator

Then

(a) Repeat the below steps until Operator having low precedence than  Scanned character is popped out from Operator Stack

(b) Pop from Operator Stack into OPERATOR

(c)  If OPERATOR  has Higher or Equal Precedence than scanned character

(i)  Pop twice from Operand Stack into OPERAND2 and OPERAND1

(ii)  Push “OPERATOR OPERAND1 OPERAND2” in Operand Stack

(d) Otherwise,

(i) Push the last Popped operator back in Operator Stack

(ii) Push the scanned character in Operator Stack

iv) Otherwise, Scanned character is an operand. Thus, Push it in Operand Stack

c) Pop from Operand Stack which is the final expression and return;


Microsoft (CPS) IN

public void ConvertInfixToPrefix(string infixExpression)
    {
        try
        {
            ValidateInfixExpression(ref infixExpression);
        }
        catch (Exception ex)
        {
            Console.WriteLine(“Invalid infix expression. Error Details:{0}”, ex.Message);
            return null;
        }

        Stack operatorStack = new Stack();
        Stack operandStack = new Stack();

        operatorStack.Push(‘(‘);
        infixExpression += ‘)’;

        foreach (char ch in infixExpression)
        {
            if (ch == ‘(‘)
            {
                operatorStack.Push(ch);
            }
            else if (ch == ‘)’)
            {
                // Pop from operator Stack until ‘(‘ is encountered
                char poppedOperator = operatorStack.Pop();
                while (poppedOperator != ‘(‘)
                {
                    operandStack.Push(PrefixExpressionBuilder(operandStack, poppedOperator));
                    poppedOperator = operatorStack.Pop();
                }
            }
            else if (IsOperator(ch))
            {
            // Pop all operators from Operator Stack which have same or higher precedence
            char poppedOperator = operatorStack.Pop();
            bool sameOrHighPrecedence = CheckSameOrHighPrecedence(poppedOperator, ch);
            while (sameOrHighPrecedence)
            {
                operandStack.Push(PrefixExpressionBuilder(operandStack, poppedOperator));
                poppedOperator = operatorStack.Pop();
                sameOrHighPrecedence = CheckSameOrHighPrecedence(poppedOperator, ch);
            }

            operatorStack.Push(poppedOperator);
            operatorStack.Push(ch);

            }
            else
            {
                operandStack.Push(ch.ToString());
            }
        }
        return operandStack.Pop();
    }

    /// Validates the infix expression for correctness
    /// 
    /// Infix expression to be validated
    /// True if expression is valid
    private static void ValidateInfixExpression(ref string expression)
    {
        expression = expression.Replace(” “, string.Empty);
        // Rule 1: ‘(‘ and ‘)’ pair
        // Rule 2: Every two operands must have one operator in between
    }

    /// Checks if character is a listed operator or not
    /// 
    /// Charaxter to be tested
    /// False if not otherwise True
    private static bool IsOperator(char character)
    {
        if ((character == ‘+’) || (character == ‘-‘) || (character == ‘*’) || (character == ‘/’))
        {
            return true;
        }
        return false;
    }

    /// Checks if popped operator has same or higher precedence than Current operator
    /// 
    /// Popped operator
    /// Current operator in the expression
    /// True if equal or higher precedence
    private static bool CheckSameOrHighPrecedence(char elementToTest, char checkAgainst)
    {
        bool flag = false;
        switch (elementToTest)
        {
            case ‘/’:
            case  ‘*’:
                flag = true;
                break;
            case ‘+’:
            case ‘-‘:
                if ((checkAgainst == ‘+’) || (checkAgainst == ‘-‘))
                {
                    flag = true;
                }
                break;
            default: // for any other popped element
                flag = false;
                break;
        }
        return flag;
    }

    private static string PrefixExpressionBuilder(Stack operandStack, char operatorChar)
    {
        string operand2 = operandStack.Pop();
        string operand1 = operandStack.Pop();
        string infixExpression = string.Format(“{0}{1}{2}”, operatorChar, operand1, operand2);

        return infixExpression;
    }

SPONSORED


Hotels.com CPA


TAME YOUR HAIR

Is Binary Tree a Binary Search Tree?


2. Is tree BinarySearchTree?

Problem:

Given a binary tree, determine if it is a Binary Search Tree (BST) or not?

Definition:

What is BST?

BST is a binary tree in which value of root is always greater than the value of every node on it’s left and is less than or equal to the value of every node on it’s right.

Solution:

This implementation is done using C#.NET.

class BinaryTree
{
public BinaryTreeNode Root { get; set; }

public bool IsBinarySearchTree()
{
Console.WriteLine("Checking if Tree is BST or not:");

if (this.Root != null)
{
int value = 0;

return this.Check(this.Root, ref value);
}

return true;
}

private bool Check(BinaryTreeNode currentNode, ref int lastNodeValue)
{
bool isTreeBST = false, leftTreePresent, rightTreePrsent ;

leftTreePresent = currentNode.LeftTree == null ? false : true;
rightTreePrsent = currentNode.RightTree == null ? false : true;

if (leftTreePresent)
{
isTreeBST = this.Check(currentNode.LeftTree, ref lastNodeValue);
}
else
{
isTreeBST = true;
}

if (isTreeBST && currentNode.Info > lastNodeValue)
{
Console.WriteLine("Processing Node With Value:{0}", currentNode.Info);

lastNodeValue = currentNode.Info;

isTreeBST = true;
}
else
{
isTreeBST = false;
}

if (isTreeBST && rightTreePrsent)
{
isTreeBST = this.Check(currentNode.RightTree, ref lastNodeValue);
}

return isTreeBST;
}
}

class BinaryTreeNode
{
public BinaryTreeNode LeftTree { get; set; }
public BinaryTreeNode RightTree { get; set; }
public int Info { get; set; }
}

Problem with the above code is that if a tree has Duplicate Values, it will fail.

The approach could be then to pass the Range in terms of Minimum and the Maximum Value of a particular node. Since we are traversing down from Root and knowing the min and max value of a root, we can appropriately limit the range and pass on to Left and Right Trees.


private bool Check(BinaryTreeNode node, int min, int max)
{
if (node == null)
return true;

if (node.Info max)
return false;
else
{
return this.Check(node.LeftTree, min, node.Info) && this.Check(node.RightTree, node.Info + 1, max);
}
}

SpiralTraversalOfMatrix


1. Spiral Traversal of a 2D matrix

Problem:

Given a 2D matrix, traverse all it’s elements in a spiral form.
Referring the below matrix as an input (Red line shows a spiral traversal),

output should be: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Solution:

This implementation is done using C#.NET. Rectangular Matrix is declared using int[,] syntax.

public void DoSpiralTraversal(int[, ]rectArray) {
        if (rectArray != null && rectArray.Length > 0) {
            Console.WriteLine("Doing Spiral Traversal on a 2D array:");

            int noOfElementsTraversed = 0, row_LB = 0, row_UB = rectArray.GetUpperBound(0), col_LB = 0, col_UB =
                    rectArray.GetUpperBound(1), iter;

            while (noOfElementsTraversed = row_LB; iter–)
                {
                    Console.Write(rectArray[iter, col_UB] + ” “);
                    noOfElementsTraversed++;
                }

                if (noOfElementsTraversed == rectArray.Length) {
                    break;
                }

                col_UB–-;

                // Move right to Left
                for (iter = col_UB; iter >= col_LB; iter–)
                {
                    Console.Write(rectArray[row_LB, iter] + ” “);
                    noOfElementsTraversed++;
                }
                row_LB++;
            }
        }
    }