Find width of a tree pointed by head

Considering that the width of the tree is defined as the maximum number of nodes at any one level, the following code should hold good. Drop a comment if you think that this code s***s [:)]

public void maxWidthBST(NodeType rootNode)
        {
            int level=depthBST(rootNode);           
            int maxWidth=0;
            int intNodeCount=0;
            for(int counter=1; counter<=level;counter++)
            {
                intNodeCount = NodeCount(rootNode, counter);
                if(intNodeCount>maxWidth)
                {
                    maxWidth = intNodeCount;
                }   
            }
            Console.WriteLine(“The maximum width is: ” + maxWidth);
        }       

        public int NodeCount(NodeType root, int level)
        {
            int LWidth=0;
            int RWidth=0;
            int totalNodesAtLevel=0;
            if(level<=0) return 0;
            if(level==1)return 1;
            if(level>1)
            {
                if(root.Left !=null) LWidth=NodeCount(root.Left, level-1);
                if(root.Right !=null) RWidth= NodeCount(root.Right, level-1);
                totalNodesAtLevel = LWidth+RWidth;           
            }
            return totalNodesAtLevel;
        }

Advertisements

Implement a Stack in C#

<<This is stupid to write my own implementation of stack when .Net framework provides inbuilt structures to do the same. But just checking if things can be done the C++ way.>>

The steps will be like this:

1. Create a class, structNode, that will represent the linked list node that will be the stack item. The node should have containers for data as well as pointers to the next item in the stack.

2. Create a second class that will define the PUSH and the POP methods. The PUSH method will create the new node and add the node to the front of the linked list. Note that in a stack the last item added is the first item removed. Also make sure that the PUSH method updates the NEXT field of the class structNode as follows:

i. if the node is the first item in the stack then NEXT==NULL

ii. if the node is added to a stack that already contains items then  make sure that the NEXT field is updated to point to the CURRENT top node; that is the node that was the top node before we added this node.

3. The second class should also contain the Pop() method to return/display the stack item that is currently at the top. You should ensure that a check for an empty stack is done before you try to pop a value. In this operation also the NEXT item needs to be updated as below:

i. set tempObjNode = currentTopNode;

ii. set currentTopNode = currentTopNode.NEXT;

iii.return tempObj;

A sample code will look like:

using System;
using System.IO;

public class structNode
{
    protected int data;

    protected structNode nextNode;

    public structNode NextNode
    {
        set{nextNode = value;}
        get{return nextNode;}
    }

    public int NodeData
    {
        set{data=value;}
        get{return data;}
    }

    public structNode(structNode nextStackNode, int stackData)
    {
        NodeData=stackData;
        NextNode = nextStackNode;
    }
}

public class NStack
{
    public structNode Push(structNode objNode, int data)
    {

        Console.WriteLine(“Create a new Node for the stack.\n”);
        structNode _elementN = new structNode(null, 0);
        _elementN.NodeData = data;   
        Console.WriteLine(“The node is now ready. Check if this is the first node in the stack Linked list.\n”);
        if(objNode == null)   
        {
            Console.WriteLine(“Yes. This is the first node of the stack Linked list.\n”);
            _elementN.NextNode = null;
            return _elementN;
        }
        else
        {
            Console.WriteLine(“Inserting the new node.\n”);
            _elementN.NextNode = objNode;
            Console.WriteLine(“Node inserted successfully!!!!!”);
            return _elementN;           
        }

    }

    public structNode Pop(structNode objNode)
    {
        Console.WriteLine(“In Pop Method. Check if the stack is empty…”);
        if(objNode == null)
        {
            throw new InvalidOperationException(“The stack is empty!”);
        }
        if(objNode.NextNode == null)
        {
            Console.WriteLine(“This is the last node of the stack\n”);
            Console.WriteLine(“:{0}”, objNode.NodeData);   
            objNode = null;
        }
        else
        {
            Console.WriteLine(“:{0}”, objNode.NodeData);
            objNode = objNode.NextNode;
        }
        return objNode;
    }

}

class mainController
{
    static void Main()
    {
        NStack objNStack = new NStack();
        structNode objstructNode = null;   
        int intChoice = 0;
        do
        {
            Console.WriteLine(“Enter the Choice.\n”);
            intChoice = Convert.ToInt32(Console.ReadLine());
            switch(intChoice)
            {
            case 1:
                Console.WriteLine(“Enter Stack Data:\t”);
                int intCounter = Convert.ToInt32(Console.ReadLine());
                objstructNode  = objNStack.Push(objstructNode, intCounter); break;

            case 2: if(objstructNode != null)
                {
                    objstructNode = objNStack.Pop(objstructNode);
                }
                break;
            case 3: break;
            }
        }while(intChoice!=3);
    }
}

Remove Duplicates from an Unsorted single linked list

void SLList::removeDuplicates()
{
    if(header)
    {
        Node *temp, *curChkNode, *last;
        temp=curChkNode=header;
        int curVal=0, length=0, counter=0;
        length=sllLength();
        cout<<"\nThe length of the list is:\t"<<length;
        while(counter!=length && curChkNode)
        {
            temp=curChkNode->next;
            curVal=curChkNode->data;
            while(temp)
            {
                if(curVal==temp->data)
                {
                    cout<<"\nA DUPLICATE IS PRESENT FOR:\t"<<curVal;
                    last->next=temp->next;
                }
                last=temp;
                temp=temp->next;
            }
            curChkNode=curChkNode->next;
            counter++;
        }   
    }
    else
    {
        cout<<"\nThe list is empty\n";
    }
    return;
}

SQL Injection – the way I learnt it

I am writing some T-SQL code for one of the assignments and am told to watch out for SQL injection as a possible attack vector.
So I took a look around to see what it is and how it really works from a very high level. A good resource to start with SQL Injection (for that matter any attack) is the OWASP.
To try hands on with how dynamic SQL executed using the Execute statement,  I created a dummy Database in my local SQL Server instance and created some tables on it. For the purpose of this write up, I will only use one of the tables in the DB that I call “ZipCodes”. There are three dummy records in the table and here is the snapshot:
image
I created a Stored procedure to get me the record count from this table. Here is the code:
image

As you see I do not do anything fancy. The Stored procedure takes some parameters and then constructs a sql statement, @SQL which is then executed.
I execute the stored procedure using the following statement to confirm that the procedure is working just fine:
image
To check whether the stored procedure is validating the input parameters, I inserted the following value as part of  in execute statement:

Exec [dbo].[StoredProcedureToCheckForSQLInjection] ””, ‘ABC’, 123, ‘ZipCodes’`

Well that irritated my SQL Server and the Stored procedure cried out the following error:
image
Look at the query that the SP tried to execute (that’s why I used the Print statement in the stored procedure code).
Ok I am on the right track and this procedure is a possible candidate of an injection attacks. I as an attacker will know this looking at the result above which shows that:
1. The Stored procedure is NOT validating the inputs.
2. The stored procedure is doing something by concatenation (Remember that I as an attacker will not have access to the SP code and hence it will be an analysis of the result/error above that will give me these details.)
That’s good news. So can I get all the records in this table? Lets check out using a crafted input that looks like the one below:
image
Once this query is run, the result that is thrown back is below:
image

Well that is not what the SP is supposed to do.
Lets check the query that the SP executed to get to the result above:
image
This is a very very very simple scenario and hopefully all the smart developers out there are not writing code like this in there Stored Procedures. But since I just started and it took me a while to get my query going, I thought of putting this here for reference.
I will comeback to this with more tricky cases. Till then its Happy Learning to me!!