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

Design a doubly linked list and perform the following operations: 1)Add nodes to both front and rear 2)Display the list, 3)Delete nodes at front.tail and nth position

#include

using namespace std;

class Node
{
    public:
    int data;
    Node *prev, *next;
    Node()
    {
        data=NULL;
        prev=NULL;
        next=NULL;
    }   
};

class dll
{
    private:
        Node *header;
    public:
        dll(){
            header=NULL;
        }
        void createList();
        void displayList();
        void insertEnd();
        void deleteFirstNode();
        void deleteLastNode();
        void deleteNthNode();
};

void dll::deleteFirstNode()
{
    if(header)
    {
        Node *temp;
        temp=header;
        header=temp->next;
        header->prev=NULL;
        delete temp;
    }
    else
    {cout<<"\nThe list is empty!\n";}
    return;
}

void dll::deleteLastNode()
{
    if(header)
    {
        Node *temp, *last;
        temp=header;
        while(temp)
        {
            last=temp;
            temp=temp->next;
        }
        last->prev->next=NULL;
        delete last;
        delete temp;       
    }
    else
    {cout<<"\nThe list is empty!\n";}
    return;
}

void dll::deleteNthNode()
{
    if(header)
    {
        Node *temp, *last;
        temp=header;
        int position=0, counter=0;
        cout<<"Enter the node position that you want to delete: \t";
        cin>>position;
        if(position>=0)
        {
            while(counter!=position && temp)
            {
                last=temp;           
                temp=temp->next;
                counter++;
            }
            if(temp)
            {
            cout<<"\nThe node that you want to delete has value:\t\n"<data;
            last->prev->next=temp;
            temp->prev=last->prev;
            delete last;           
            }
            else{cout<<"\nThe list does not contain that many elements\n";}
        }
    }
    return;
}

void dll::insertEnd()
{
    if(header==NULL)
    {
        createList();
    }
    else
    {
        Node *newNode, *temp, *last;
        newNode=new Node;
        cout<<"Enter the value for the node:\t";
        cin>>newNode->data;
        temp=header;
        while(temp)
        {
            last=temp;
            temp=temp->next;
        }
        newNode->next=NULL; //newNode is the new last node
        newNode->prev=last;
        newNode->prev->next=newNode;           
    }
    return;
}

void dll::createList()
{
    int in_val;
    Node *temp;
    temp=new Node;
    cout<<"Enter the value for the node:\t";
    cin>>temp->data;
    if(header == NULL)
    {
        //This is the first node in the double linked list
        temp->next=NULL;
        temp->prev=NULL;       
    }
    else
    {
        //If this is a new node at the front of an already populated linkedlist
        temp->next=header;
        temp->next->prev=temp;
        header=temp;
    }
    header=temp;
    return;
}

void dll::displayList()
{
    Node *temp, *last;
    temp=header;
    cout<<"Display the list from first to last using the NEXT pointer.\n";
    while(temp)
    {   
        cout<data<<"\t"<<endl;
        last=temp;
        temp=temp->next;
    }
    /*if(last)
    {
        cout<<"Display the list from last to last using the PREV pointer.\n";
        while(last)
        {
            cout<data<<"\t"<<endl;
            last=last->prev;       
        }
    }*/
}

void main()
{
    cout<<"******This is a Doubly Linked List Demo******"<<endl;
    int choice=0;
    dll objDLL;
    do{
        cout<<"Enter the opration you want to perform: ";
        cout<<"\n1). Add a node at front of the list";
        cout<<"\n2). Display a node";
        cout<<"\n3). Add a node at end of the list";
        cout<<"\n4). Delete the node at head of the list";
        cout<<"\n5). Delete the node at tail of the list";
        cout<<"\n6). Delete the node at nth position of the list";
        cout<<"\n7). Exit\t";
    cin>>choice;
    switch(choice)
    {
        case 1: objDLL.createList(); break;
        case 2: objDLL.displayList(); break;
        case 3: objDLL.insertEnd(); break;
        case 4: objDLL.deleteFirstNode();break;
        case 5: objDLL.deleteLastNode();break;
        case 6: objDLL.deleteNthNode();break;
        case 7: exit(0);
        default: cout<<"\n Invalid operation/input detected. Please try again later.";
    }   
    }while(choice!=7);
}   

Cross Site Scripting – PART 1

Hi there…I have been looking around for XSS related information and most of the demos I saw are either around displaying an alert in a web page or too advanced for a beginner like me. So as a toddler in the security world I tried to create my own dummy application to see how this attack is executed. What I write below is a documentation of my learning: there may be faults as I am still learning.

So feel free to drop a comment incase anything is not correct, I will surely incorporate any suggestions.

Cross Site Scripting – A little exploit demo to help understand the basics of this attack – I

Application background:

1. We have a simple web forum that uses Form based authentication.
2. The users can comment on the topics discussed by other users.
3. New users visiting this site are required to register by creating a new user name and password.
4. A registered user can: view/write the posts, write comments on the posts and view the comments written by other users.
5. The following code snippet is added to the web.config file for this application. Please note that when request validation is disabled, any content can be submitted to a page; it is the responsibility of the page developer to ensure that content is properly encoded or processed.

Use Scenario:
1. A malicious user registers and logs in to the forum.
2. He picks a topic and clicks on Write comments. Here is what he writes and submits:

This comment will appear as below on the view comments page:


To a normal user this looks like a perfectly harmless piece of text that directs you to another location that has more information around, eh…well Cross Site scripting exploit!
So a good user (let’s call him GoodUser) logs in and clicks on the hyperlink “here” to get some more information around this type of exploits. Here is what he will see:

In our example we used a simple alert statement but in real world scenarios this can contain scripts that can steal your cookie, other important information, etc. These stolen information can be used to impersonate a user, launch a more knowledgeable attack on the application or its user and also can case loss of data that can have financial and reputational implications on both the end user as well as the web site owner.

Hope someone will find this useful to understand how XSS can be exploited. I will posting my rendezvous with XSS.

Happy Reading!