Tricky question.....

Que: You have 2 arrays each containing a set of numbers. Write an
algorithm that gets the elements present in the first array and missing
from the second. It should have n complexity.

void fun(int a[], int b[], int N){
 int max = a[0];
 for(int i =0; i < N;i++)
  if(max < a[i])
  max = a[i];
 
 int c[max]={0};
 for(int i =0; i < N;i++)
 c[a[i]]++;
 
 for(int i =0; i < N;i++)
 c[b[i]]--;
 
 for(int i =0; i < N;i++)
 if(c[a[i]]==1)
 print a[i];
}

How to find median of a BST?

If the no of keys are odd, there will be only one median, if it is even there will be two median.

• Execute two InOrder traversal, the first one runs as the double speed the second one. It means the first one visits two nodes while the second one visits one nodes. So when the first one finish traverse, the second one point the mid value!

Creating Own exception class in java.

Note: Exception class must be inherited

class OutOfRange extends Exception{
   String message;
   OutOfRange(){
      message = new String("Please Enter No's between 0 and 100");
   }
   String toStr(){
      return message;
   }
}

public class MainCls{
   public static void main(String args[]){
      int input;
      String inputStr;
      InputStreamReader isr = new InputStreamReader(System.in);
      BufferedReader br = new BufferedReader(isr);
      
      inputStr = br.readLine();
      input = Integer.parseInt(inputStr);
      
      try{
         if(input < 0 || input > 100)
         throw new OutOfRange();
      }
      catch(OutOfRange e){
         System.out.println(e.toStr());
      }
      //Rest of code...
   }
}

Difference between compiler and Interpretor.

Interpreter
An interpreter reads the source code one instruction (a line) at a time, converts this line into machine code and executes it. The current machine code is then discarded and the next line is read. Examples of interpreters are Basic and script interpreters such as Tcl script, JavaScript etc.

Advantages
The advantage of this is it's simple and you can interrupt it while it is running, change the program and either continue or start again.

Disadvantages
Every line has to be translated every time it is executed, because of this interpreters is relatively slow.

Compiler
A compiler reads the whole source code and translates it into a complete machine code output as a new file(object file). This completely separates the source code from the executable file. Examples of compilers are Visual Basic, C, C++, C#, Fortran, Cobol, Ada, Pascal etc.

Advantages
Advantage of this is that the translation is done once only and as a separate process. The program that is run is already translated into machine code so is much faster in execution.

Disadvantages
The disadvantage is that you cannot change the program without going back to the original source code, editing that and recompiling.

trick to access a private member of class through its object

#include < iostream >

using namespace std;

class Base{
      public: virtual void fun()=0;
};

class derived:private Base{
 private: void fun(){
  cout < < "accessing private method" < < endl;
 }
};

int main(){
    Base *base;
    derived *dptr = new derived();
    base = (Base *)dptr;
    base- > fun();
    return 0;
}

Find out tolal no of triangles...........

Find total no of triangle in the following diagram.....
It takes too much time to count. The counting will we too difficult on increasing the no of levels........

Here i am going to give a general procedure to solve such type of problems......






Lets start with level one........If there is only one triangle
then total no of triangle will be one.

T(1) = Tri(1)
= 1



Now for the level two....
The total no of triangle will be

T(2) = Tri(1) +Tri(2)
= 4 + 1
= 5

Here T(n) represent the total no of triangle and Tri(n) represents the triangles of size n.


For level 3 you can see there is 9 triangles of size 1, 3 triangles of size 2 and 1 of size 3......

T(3) = Tri(1) + Tri(2) + Tri(3)
= 9 + 3 + 1
= 13

For level 4 you can see there is 16 triangles of size 1, 7 triangles of size 2, 3 of size 3 and 1 of size 4.



T(4) = Tri(1) + Tri(2) + Tri(3) + Tri(4)
= 16 + 7 + 3 + 1
= 27


Now we have a sequence 1,5,13,27..........
put this sequence on "http://www.research.att.com/~njas/sequences/"
you will get the formula for the any sequence which exist.

I found the that the above sequence does not exist but it is approximate to
a sequence so the formula for the nth term is Floor[n*(n+2)*(2n+1)/8........


using formula for the size 5 (level 5)

T(5) = Floor(5*7*11/8)
= Floor(48.12500)
= 48

hence for the size 6 (level 6)

T(6) = Floor(6*8*13/8)
= Floor(78)
= 78

Including a Header Files Only Once.................

  To prevent multiple copy of header file, a header file can be 
written to detect whether it has already been included. The 
following is an example of how this can be done:
    /* header.h */
    #ifndef HEADER_H
    #define HEADER_H
    /* The body of the header file */
    #endif /* HEADER_H */
In this example, the header file is named header.h. The first 
line tests whether HEADER_H has been defined. If it has, the 
entire header file is skipped. If HEADER_H has not been defi-
ned, it is immediately defined and the header file is proces-
sed. The system header files all use this technique. The names
defined in them all begin with an underscore character to 
prevent them from interfering with any names you define. The 
convention is for the defined name to be in all uppercase and 
to contain the name of the file.


Example:
=============================================================
        /*test.h*/

        #ifndef _TEST_H     /*if not defined */
        #define _TEST_H    /*then define */

        class test
        {
            private:
                int data;
            public:
                test();
                void functionOne();
                   
        };

        test::test()
        {
            cout <   <  "i got nothing to do here" <   
            <  endl;  
        }

        void test::functionOne()
        {
            cout <   <  " I m in function One" <   <  
            endl;
        }
        #endif     /*End of definition */
 ____________________________________________________________

        /* main.cpp */

        #include   "test.h"
        #include   "test.h"
        #include   "test.h"

        #include <  iostream > 

        using namespace std;


        int main()
        {
            test obj;
            obj.functionOne();
            return 0;
        }
=============================================================

Now you can  see the work of only preprosessor by using the 
compilation option:
    g++ -E main.cpp  <   output.txt

    Now an output file "output.txt"  will be created which 
contains all the source code after the work of preprocessor 
has been done. At the begining it can be seen that the test.h 
is defined only once. then after this iostream is defined and 
at last source code of main.cpp

About Macrossss...................

A macro definition is contained on one line. If we need to write it on multiple
lines because of its length, we can do so by using the backslash as
a line continuation character
Example:
#define ran(low,high) \
((int)random() % (high-low+1)) \
+ low

========================================================

To change the definition of a macro, it is necessary to delete it and define it
again.
Example:
#define MLKEYVAL 889
#undef MLKEYVAL
#define MLKEYVAL 890
=========================================================

For a macro to be defined as having parameters, there must be no spaces
between the name of the macro and the parentheses.
Example:
#define ADD(a,b) printf("%d\n",a+b)
#define incrint (a) a++

showint(30,10);
incrint(bbls);
following is the result of preprocessing the previous lines:

printf("%d\n",30+10);
(a) a++(bbls)

==========================================================

Macro names are not substituted inside strings, as in the following
Eexample:

#define Gaggu 8192
printf("THE Gaggu KNOWS HOW TO DO.\n");

The output looks like the following:

THE Gaggu KNOWS HOW TO DO.

==========================================================

An argument passed to a macro can be “stringized” by preceding its name with
a hash (#) character. In the following example, the macro named GAGGU contains
a stringized version of its argument, which is combined with other strings (by
being placed adjacent to them):
Example:
#define GAGGU(ZINGALALA) \
printf("The term " #ZINGALALA " is a string\n")

MONCK(KARLOSE);
The output looks like the following:

The term KARLOSE is a string

===============================================================

Directives and Preprocessor.....................

Directive

The instructions to the preprocessor appear in the source as directives and
can be easily spotted in the source code because they all begin with a hash (#) character,
appearing as the first non blank character on a line. The hash character usually appears
on column 1 and is immediately followed by the directive keyword

Example

#define
#include
#ifndef

Preprocessor

The preprocessor reads the source code and responds to directives
embedded in it to produce a modified version of the source, which is fed to the
compiler. The preprocessor is still an important part of C, C++,

Macro

The macro has a name that,when found elsewhere in the text, is replaced with the string of characters defined as the value of the macro. It is possible to specify parameters that are to be used as part of the macro expansion.

Example

#define min(a,b) ((a) < (b) ? (a) : (b))

Directive	Description
#define	Defines a name as a macro that the preprocessor will expand
#elif	Provides an alternative expression to be evaluated by an #if directive.
#else	Provides an alternative set of code to be compiled if an #if, #ifdef, or #ifndef is false.
#error	Produces an error message and halts the preprocessor.
#if	Compiles the code between this directive and its matching #endif only if evaluating an arithmetic expression results in a nonzero value.
#ifdef	Compiles the code between this directive and its matching #endif only if the named macro has been defined.
#ifndef	Compiles the code between this directive and its matching #endif only if the named macro has not been defined.
#include	Searches through a list of directories until it finds the named file; then it inserts the contents of the file just as if it had been inserted by a text editor.
#include_Next	The same as #include, but this directive begins the search for the file in the directory following the one in which the current file was found.
#line	Specifies the line number, and possibly the file name, that is reported to the compiler to be used to create debugging information in the object file.
#pragma	A standard method of providing additional information that may be specific to one compiler or one platform.
#undef	Removes a definition previously created by a #define directive.
#warning	Produces a warning message from the preprocessor.
##	The concatenation operator, which can be used inside a macro to combine two strings into one.

Recursive Method to list all the file present in a Directory using cpp

#include < iostream > 
#include < dirent.h > 

using namespace std;

class recDir
{
    private:
        int fileCount;
    public:
        recDir()
        {
            fileCount = 0;
        }
        void showFileList(char *dirPath)
        {
            char *subDir="",*temp;
            DIR *curDir;
            struct dirent *entry;
            if(curDir = opendir(dirPath))
            {
                while(entry = readdir(curDir))
                {
                    if(strcmp(entry- > d_name,".") != 0 && 
                        strcmp(entry- > d_name,"..") != 0)
                    {
                        temp=strstr(entry- > d_name,".");
                        if(temp!=NULL
                        {
                            fileCount++;
                            cout <<  "File [" <<  
                            fileCount <<  "]  " <<
                            entry- > d_name <<  endl;
                        }
   else
   {
           subDir = dirPath;
              strcat(subDir,"/");
           strcat(subDir,entry- > d_name);
           showFileList(subDir);
   } 
                    }
                }
                closedir(curDir);
            }
            else
            cout << "Error:Could not open directory/file\n";
        }
        int totalFiles()
        {
            return fileCount;
        }
};


int main(int argc,char *argv[])
{
    recDir obj;
    obj.showFileList(argv[1]);
    cout <<  endl <<  "Total Files = 
    " <<  obj.totalFiles() <<  endl;
}

Simple Example to extract data from xml file using expat............

takes an xml file and extract attributes into a file .rtf

#include "stdio.h"

#include "expat.h"

#include"string.h"

#define BUFFSIZE        8000







FILE *rtfFile;





static void startElement(void *cargo, const char *el,const char **attr) 

{

}

static void endElement(void *cargo, const char *el) 

{ 

}

static void characters(void *cargo, const char *ch, int len) 

{

    int i;

    for (i=0; i	putc(ch[i],rtfFile);

}



int main(int argc, char *argv[]) 

{

    if(argc!=3)

    {

        printf("\nUsage :  
\n");

        exit(0);

    }

    char Buff[BUFFSIZE];

    FILE *fp;

   

    fp = fopen(argv[1],"r");

    rtfFile = fopen(strcat(argv[2],".rtf"),"w");



   XML_Parser parser = XML_ParserCreate(NULL);

   XML_SetElementHandler(parser, startElement, endElement);

   XML_SetCharacterDataHandler(parser, characters);

   

   for (;;) 

   {

      int len  = fread(Buff, 1, BUFFSIZE, fp);

      int done = feof(fp);

      if (! XML_Parse(parser, Buff, len, done))

        exit(-1);

      if (done) break;

   }

   fclose(fp); 

   printf("\n");

    fclose(rtfFile);

   return 0;

}

for Example we can use following content of a

< ?xml version="1.0"?>

< story>

  < storyinfo>

    < author>Ranjeet Kumar</author>

    < datewritten>October 15,1985 </datewritten>

    < keyword>Don</keyword>

  < /storyinfo>

  < body >

    < headline > It's not gonna to help you < /headline >

    < para > Don't be fool < /para >

  < /body >

< /story >

Extracting data from the XML files Using expat on linux (XML parser)

1)Download .tar.gz files on from

http://webscripts.softpedia.com/script/Development-Scripts-js/XML-Tools/Expat--26466.html

2)extract into a folder
3) Move to this folder and run following well known commands

./configure
make
make install

4)now the times comes to check weather it is working or not.............
for this purpose expat people are very good as they have given two examples (too much i guess) in the folder expat.version/examples/. what you have have to do for checking, obviously copy a xml file from any where as you wish and run these programs.......
$>gcc examples.c -l expat
$>./a.out < xmlfile.xml

i hope you will see something which you need.

Mine Sweeper...........

//////////////////////////////////////////////////////////////////////////////////////////
The goal of the game is to find where all the mines are located within a M × N field.
The game shows a number in a square which tells you how many mines there are
adjacent to that square. Each square has at most eight adjacent squares. The 4 × 4 field
on the left contains two mines, each represented by a “*” character. If we represent the
same field by the hint numbers described above, we end up with the field on the right:
*... ===== *100
.... ===== 2210
.*.. ===== 1*10
.... ===== 1110
Input
The input will consist of an arbitrary number of fields. The first line of each field
contains two integers n and m (0 < n, m ≤ 100) which stand for the number of lines
and columns of the field, respectively. Each of the next n lines contains exactly m
characters, representing the field.
Safe squares are denoted by “.” and mine squares by “*,” both without the quotes.
The first field line where n = m = 0 represents the end of input and should not be
processed.
Output
For each field, print the message Field #x: on a line alone, where x stands for the
number of the field starting from 1. The next n lines should contain the field with the
“.” characters replaced by the number of mines adjacent to that square. There must
be an empty line between field outputs.
Sample Input ===== Sample Output
4 4 ===== Field #1:
*... ===== *100
.... ===== 2210
.*.. ===== 1*10
.... ===== 1110
3 5=====Field #2:
**... ===== **100
..... ======33200
.*...===== 1*100
0 0
////////////////////////////////////////////////////////////////////////////////////////////

//===============================================================================//
#include
#include

using namespace std;

int matrix[20][20];

void locate(int i,int j,int row,int column)
{
if(i-1 >=0 && i-1 < row && j-1 >=0 && j-1 < column && matrix[i-1][j-1] ==-1)
matrix[i][j] ++;
if(i-1 >=0 && i-1 < row && j >=0 && j < column && matrix[i-1][j] ==-1)
matrix[i][j]++;
if(i-1 >=0 && i-1 < row && j+1 >=0 && j+1 < column && matrix[i-1][j+1] ==-1)
matrix[i][j]++;
if(i >=0 && i < row && j-1 >=0 && j-1 < column && matrix[i][j-1] ==-1)
matrix[i][j]++;
if(i >=0 && i < row && j+1 >=0 && j+1 < column && matrix[i][j+1] ==-1)
matrix[i][j]++;
if(i+1 >=0 && i+1 < row && j-1 >=0 && j-1 < column && matrix[i+1][j-1] ==-1)
matrix[i][j]++;
if(i+1 >=0 && i+1 < row && j >=0 && j < column && matrix[i+1][j] ==-1)
matrix[i][j]++;
if(i+1 >=0 && i+1 < row && j+1 >=0 && j+1 < column && matrix[i+1][j+1] ==-1)
matrix[i][j]++;
}

void locatebombs(int row,int column)
{
for(int i=0;i < row;i++)
{
for(int j=0;j {
if(matrix[i][j] !=-1)
locate(i,j,row,column);
}
}
}

int main()
{
int row,column;
FILE *fp;
freopen("input.txt","r",stdin);
cin>>row>>column;
scanf("\n");
char m[20][20];
for(int i=0;i<=row;i++)
gets(m[i]);
cout< for(int i=0;i {
for(int j=0;j {
if(m[i][j] == '.')
matrix[i][j] = 0;
else
matrix[i][j] = -1;
}
cout< }
for(int i=0;i {
for(int j=0;j cout< cout< }

cout<<"\n"< locatebombs(row,column);
for(int i=0;i {
for(int j=0;j if(matrix[i][j] !=-1)
cout< else
cout<<"*\t";
cout< }
return 0;
}
//====================================================================================//

Recursive Method to Find Total no of ways in which a positive number K can be written as sum of integers smaller than K

consider the a number 5. It can be represented as following sets {1+1+1+1+1},{1+1+1+2},{1+2+2},{1+1+3},{1+4},{2+3},{5+0} hence there are total seven.

recursive solution for finding total no of ways...

T(n) = Sigma (-1)^(m+1)*[ T(n-m*(3*m-1)/2) + T (n-m*(3*m+1)/2)]

where m = 1,2,3.........until (n-m*(3*m+1)/2) > 0;
Example:
T(5) = T(4) +T(3) - T(0)

//------------------------------------------------------------------------------------------------------------//

          int T(int n)
        {
            if(n <  0)
                return 0;
            else
            {
                if(n == 0)
                    return 1;
                else
                {
                    int temp = 1;
                    int tempr = 0;
                    int m = 0;
                    while(temp  >   0)
                    {
                        m++;
                        temp = n-m*(3*m+1)/2;
                        tempr += pow(-1,m+1)*T(n-m*(3*m-1)/2) +
                                          pow(-1,m+1)*T(n-m*(3*m+1)/2);
                    }
                    return tempr;
                }
            }
        }
         
       int main()
       {
             int number;
             scanf("%d",number;);
             printf("\nTotal ways = %d",T(number));
       } 

//------------------------------------------------------------------------------------------------------------//

Network Packet sniffing........

A "Packet Sniffer" is a utility that sniffs without modifying or redirecting the data packets. Packet sniffers merely watch, display, and log the traffic of Network.

Network Adapter Card:
Network adapter works in two modes......
Non-promiscuous: Network adapters running in this mode receive only those data packets which is coming for the host computer.
Promiscuous mode: Network adapters running in promiscuous mode receive not only the data directed to the machine hosting, but also all of the traffic on the physically connected local network.

Network Type:
Non-Switched: Sniffing is easy if the network is non-switched. In Non-switched network hub is used. hence each host recieves all the packets coming in the network but discards those which is not coming for it(In non-promiscuous).
Switched: In switched network sniffer is little bit tricky. It can be done by flooding ARP requests which will cause the switch to start behaving like a hub, or other trick that causes switch to redirect traffic to the sniffer system.

ARP Protocol
Address Resolution Protocol (ARP) is a stateless protocol, was designed to map Internet Protocol addresses (IP) to their associated Media Access Control (MAC) addresses. It does not required authentication.

ARP Cache Poisoning:
Broadcasting forged ARP replies on a local network. In a sense, "fooling" nodes on the network. This can be done because ARP lacks authentication features, thus blindly accepting any request and reply that is received or sent.

MAC Address Flooding:
An ARP cache poisoning attack that is mainly used in switched environments. By flooding a switch with fake MAC addresses, a switch is overloaded. Because of
this, it broadcasts all network traffic to every connected node. This outcome is referred to as "broadcast mode" because, all traffic passing through the switch is broadcasted out like a Hub would do. This then can result in sniffing all network traffic.

Packet Filter:
The Linux kernel implements a generic-purpose protocol, called PF_PACKET, which allows to create a socket that receives packets directly from the network card driver. Hence, any other protocols' handling is skipped, and any packets can be received.