Write a C Program to reverse a stack "in place" using recursion ?

You can only use the following ADT functions on Stack:
IsEmpty
IsFull
Push
Pop
Top 

#include
#include
using namespace std;
stack S;

void func(int n){
    if(S.empty())
        S.push(n);
    else{
        int t= S.top();
        S.pop();
        func(n);
        S.push(t);
    }
}

void Rec(){
    if(!S.empty()){
        int t = S.top();
        S.pop();
        Rec();
        func(t);
    }
}

void printStack(){
    if(!S.empty()){
        int t= S.top();
        S.pop();
        cout<<<",";
        printStack();
        S.push(t);
    }
    else{
        cout<
    }
  
}

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

    S.push(4);
    S.push(3);
    S.push(2);
    S.push(1);

    printStack();
  
    Rec();
    printStack();
  
    return 0;
}

You are given a datatype, say X in C. The requirement is to get the size of the datatype, without declaring a variable or a pointer variable of that type, And, of course without using sizeof operator !

Sol:- #define size(type) ( (int)((type *)0+1) - (int)((type *)0)) 

What can be maximum memory that a process can have in 32-bit machine? What assigns a process this memory?

What should be done when an exception occurs in the constructor?

How do you know where the memory leaks when you have multiple files?

One Way to detect the memory leaks is to check that while using Inheritance and Virtual Functions some where we have initialized baseclass pointer with the derived class object but when calling destructor the destructor that u have used in the baseclass is not declared as Virtual.
eg:
#include
using namespace std;

class Base1 {
public:
  ~Base1() { cout << "~Base1()\n"; }
};

class Derived1 : public Base1 {
public:
  ~Derived1() { cout << "~Derived1()\n"; }
};

class Base2 {
public:
  virtual ~Base2() { cout << "~Base2()\n"; }
};

class Derived2 : public Base2 {
public:
  ~Derived2() { cout << "~Derived2()\n"; }
};

int main() {
  Base1* bp = new Derived1; // Upcast
  delete bp;
  Base2* b2p = new Derived2; // Upcast
  delete b2p;
}

The output of the following program is :--
~Base1()
~Derived2()
~Base2()

In this example we can see that after declaring the destructor of class Base2 as virtual when we delete a pointer to class Base2 then first the Derived2() destructor is called first then the base class destructor. So during upcasting this can introduce a memory leak.This is the case that i know which can introduce memory leak in multiple files.(Reference: TICPP Vol1 Bruce Eckel Chapter 15(polymorphism and Virtual functions))

WAP to find the number containing all the digits (1-9, no 0) such that number till nth digit is divisible by n

wo teen women wali puzzle ka sol..

Q : Three very intelligent women (rare case :P) are sitting across a circular table. A fourth person notifies them that he will blind fold them and put either blue or red mark mark on their forehead. Then he will open their eyes. If any woman sees a red mark on the forehead of any of the women, she should raise her hand. And as soon as, one can logically deduce the mark of her forehead, she should then lower her hand, if she raised it earlier.
The fourth person then proceeds and mark all their foreheads with red mark and then open their eyes. All three raised her hand initially, after some moment, the most intelligent of the lot lower her hand.
What and how did she conclude about the mark color of her forehead?
A : Possible cases : (2 R, 1 W) and  3 R as all three initially raised their hand which caused the confusion and the corresponding delay in lowering the hands.
For (2R, 1W) case, one of the women with red mark would have thought, that since third lady has white mark, the only reason the other lady raised her hand is that she had red mark on her forehead. Hence would have lowered her hand almost instantaneously.
The most intelligent woman after analyzing all the cases, must have thought that the only reason for none of the women being able to deduce the color of her forehead instantaneously is due to the 3 R case.

how to chk if a no. is integer or not.

Source : http://stackoverflow.com/questions/784563/c-check-whether-is-number-is-int-float/784825

#include
using namespace std;
int main(){
 double num1;
 cin>>num1;
 if(static_cast(num1) == num1)//casts num1 to type int
  cout<<"Integer"<
 else
  cout<<"Not Integer"<
  return 0;
  }

Another method is

char *test = "asdf1234";
int i;
for (i = 0; i < strlen (test); i++)
{
    if (isdigit (test[i]))
        fprintf (stdout, "test[%d] is a digit!\n", i);
}

print 1-100 no.swithout loop in c

Basically the Question generally is to Write a C function to print all numbers from 1 to m (m is the input no) without any loop specifically for, while, switch, do and recursion
#include
#include
char globalStr[1000000];
void nprint(int n)
{

  char strn[7], *cp;

  sprintf(strn,"%d\n", n);
  cp = strstr(globalStr, strn);
  *(cp + strlen(strn)) = 0;

  printf("%s",globalStr);
}
int main(){
  int n,i;
  globalStr[0] = 0;
  /* Lopp is not allowed only in the function nprint()......still if not convinced, you are free to form the string manually :P*/
  for(i = 1;i<32768;i++)
    sprintf(globalStr,"%s%d\n", globalStr,i);

  scanf("%d",&n);
  nprint(n);
  return 0;
}

For CPP, there is a better method,
#include

class a{
public:
a(){std::cout<<++i<}
private:
static int i;
};

int a::i;

int main(){
int n=0;
std::cout<<"Enter the maximum number that you want to print: ";
std::cin>>n;
a* array=new a[n];
//system("pause");
return 0;
}

print 1-100 no.swithout loop in c

globalStr,i);

  scanf("%d",&n);
  nprint(n);
  return 0;
}

For CPP, there is a better method,
#include

class a{
public:
a(){std::cout<<++i<}
private:
static int i;
};

int a::i;

int main(){
int n=0;
std::cout<<"Enter the maximum number that you want to print: ";
std::cin>>n;
a* array=new a[n];
//system("pause");
return 0;
}

Write a C program which when compiled and run, prints out a message indicating whether the compiler that it is compiled with, allows /* */ comments to nest.

#include
int allowed(){
     int a=1;
     /* /* */ a=0; // */
    return  a;
}

int main(){
   if (allowed())
       printf("Nested comments Allowed\n");
   else
       printf("Nested comments not Allowed\n");
   return 0;
}

In case of nested comments not allowed, we have it as /*/* */ a=0;// */
Bigger font show commented area........


What if the single line comment style is not supported?
After all, single line style comments were introduced with C++...........
#include
int allowed(){
    int i=0, k=1;
    int *j = &k;
    return  /* /* */ i */*j;/* */1;
}

int main(){
   if (allowed())
       printf("Nested comments Allowed\n");
   else
       printf("Nested comments not Allowed\n");
   return 0;
}

So in case of nested comments allowed we have /*/* *\ *\.....
but in case its allowed it is : /*/* *\ *\

Given a string s1 and a string s2, write a snippet to say whether s2 is a rotation of s1 using only one call to strstr routine? (eg given s1 = ABCD and s2 = CDAB, return true, given s1 = ABCD, and s2 = ACBD , return false)

Syntax of strstr 

const char * strstr ( const char * str1, const char * str2 );

 Returns a pointer to the first occurrence of str2 in str1, or a null pointer if str2 is not part of str1.
The matching process does not include the terminating null-characters.

Approach1
Append str1 to itself and do a strstr for str2. That should work.
(I am assuming strstr looks for string x within string y).
But this fails sometime...for eg. s1 = ABCDA, s2 = BCDA, s2s2 = BCDABCDA
s2s2 now contains s1, but it is not a rotation of s1.
probably other corner cases exist. 

So we can improve it...by first checking whether s1 and s2 have equal number of characters or not.

Reverse a singly linked listeverse a singly linked list

//Iterative reverse 

Void ReverseList(node* head)
{
        node *temp,*current,*result;
        temp=null;
        result=null;
        current=head;
        while(current!=null)
        {
                temp=current->next;//point to next element
                current->next=result;//point current element's next to prev element
                result=current;//point prev element to current element
                current=temp;
        }
   head=result;

} 

Remove duplicates from a sorted linked list

As the linked list is sorted, we can start from the beginning of the list and compare adjacent nodes. When adjacent nodes are the same, remove the second one. There's a tricky case where the node after the next node needs to be noted before the deletion.


// Remove duplicates from a sorted list
void RemoveDuplicates(struct node* head) 
{
  struct node* current = head;
  if (current == NULL) return; // do nothing if the list is empty

  // Compare current node with next node
  while(current->next!=NULL)
  {
      if (current->data == current->next->data)
      {
         struct node* nextNext = current->next->next;
         free(current->next);
         current->next = nextNext;
      }
      else
      {
         current = current->next; // only advance if no deletion
      }
   }
}

Insert nodes into a linked list in a sorted fashion

The solution is to iterate down the list looking for the correct place to insert the new node. That could be the end of the list, or a point just before a node which is larger than the new node.

Note that we assume the memory for the new node has already been allocated and a pointer to that memory is being passed to this function.



// Special case code for the head end
void linkedListInsertSorted(struct node** headReference, struct node* newNode) 
{
  // Special case for the head end
  if (*headReference == NULL || (*headReference)->data >= newNode->data)
  {
     newNode->next = *headReference;
     *headReference = newNode;
  }
  else
  {
     // Locate the node before which the insertion is to happen!
     struct node* current = *headReference;
     while (current->next!=NULL && current->next->data < newNode->data)
     {
        current = current->next;
     }
     newNode->next = current->next;
     current->next = newNode;
   }
}


Return the nth node from the end of a linked list

Here is a solution which is often called as the solution that uses frames.

Suppose one needs to get to the 6th node from the end in this LL. First, just keep on incrementing the first pointer (ptr1) till the number of increments cross n (which is 6 in this case)


STEP 1    :   1(ptr1,ptr2) -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

STEP 2    :   1(ptr2) -> 2 -> 3 -> 4 -> 5 -> 6(ptr1) -> 7 -> 8 -> 9 -> 10



Now, start the second pointer (ptr2) and keep on incrementing it till the first pointer (ptr1) reaches the end of the LL.


STEP 3    :   1 -> 2 -> 3 -> 4(ptr2) -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 (ptr1)


So here you have!, the 6th node from the end pointed to by ptr2!


Here is some C code..


struct node
{
  int data;
  struct node *next;
}mynode;


mynode * nthNodeFrmEnd(mynode *head, int n /*pass 0 for last node*/)
{
  mynode *ptr1,*ptr2;
  int count;

  if(!head)
  {
    return(NULL);
  }

  ptr1  = head;
  ptr2  = head;
  count = 0;

  while(count < n)
  {
     count++;
     if((ptr1=ptr1->next)==NULL)
     {
        //Length of the linked list less than n. Error.
        return(NULL);
     }
  }

  while((ptr1=ptr1->next)!=NULL)
  {
    ptr2=ptr2->next;
  }

  return(ptr2);
}

Binary search on a linked list

The answer is ofcourse, you can write a C program to do this. But, the question is, do you really think it will be as efficient as a C program which does a binary search on an array?

Think hard, real hard.

Do you know what exactly makes the binary search on an array so fast and efficient? Its the ability to access any element in the array in constant time. This is what makes it so fast. You can get to the middle of the array just by saying array[middle]!. Now, can you do the same with a linked list? The answer is No. You will have to write your own, possibly inefficient algorithm to get the value of the middle node of a linked list. In a linked list, you loosse the ability to get the value of any node in a constant time.

One solution to the inefficiency of getting the middle of the linked list during a binary search is to have the first node contain one additional pointer that points to the node in the middle. Decide at the first node if you need to check the first or the second half of the linked list. Continue doing that with each half-list.

C program to free the nodes of a linked list

Before looking at the answer, try writing a simple C program (with a for loop) to do this. Quite a few people get this wrong.


This is the wrong way to do it

struct list *listptr, *nextptr;
for(listptr = head; listptr != NULL; listptr = listptr->next)
{
  free(listptr);
}


If you are thinking why the above piece of code is wrong, note that once you free the listptr node, you cannot do something like listptr = listptr->next!. Since listptr is already freed, using it to get listptr->next is illegal and can cause unpredictable results!



This is the right way to do it


struct list *listptr, *nextptr;
for(listptr = head; listptr != NULL; listptr = nextptr)
{
  nextptr = listptr->next;
  free(listptr);
}
head = NULL;


After doing this, make sure you also set the head pointer to NULL!

Copy of a linked list

Check out this C program which creates an exact copy of a linked list.


copy_linked_lists(struct node *q, struct node **s)
{
    if(q!=NULL)
    {
        *s=malloc(sizeof(struct node));
        (*s)->data=q->data;
        (*s)->link=NULL;
        copy_linked_list(q->link, &((*s)->link));
    }
}


Compare two linked lists

int compare_linked_lists(struct node *q, struct node *r)
{
    static int flag;
   
    if((q==NULL ) && (r==NULL))
    {
         flag=1;
    }
    else
    {
        if(q==NULL || r==NULL)
        {
            flag=0;
        }
        if(q->data!=r->data)
        {
            flag=0;
        }
        else
        {
           compare_linked_lists(q->link,r->link);
        }
    }
    return(flag);
}


Middle of a linked list

Method1 (Uses one slow pointer and one fast pointer)
// The slow pointer is advanced only by one node
// and the fast pointer is advanced by two nodes!



typedef struct node
{
  int value;
  struct node *next;
  struct node *prev;
}mynode ;



void getTheMiddle(mynode *head)
{
  mynode *p = head;
  mynode *q = head;

  if(q!=NULL)
  {
       while((q->next)!=NULL && (q->next->next)!=NULL)
       {
          p=(p!=(mynode *)NULL?p->next:(mynode *)NULL);
          q=(q!=(mynode *)NULL?q->next:(mynode *)NULL);
          q=(q!=(mynode *)NULL?q->next:(mynode *)NULL);
       }
       printf("The middle element is [%d]",p->value);
  }
}









Here p moves one step, where as q moves two steps, when q reaches end, p will be at the middle of the linked list.

Method2(Uses a counter)

Function CAll
   middle = getTheMiddle(head);
Function definition

// Function to get to the middle of the LL
mynode *getTheMiddle(mynode *head)
{
  mynode *middle = (mynode *)NULL;
  int i;

  for(i=1; head!=(mynode *)NULL; head=head->next,i++)
  {
     if(i==1)
        middle=head;
     else if ((i%2)==1)
        middle=middle->next;
   }
 
   return middle;
}


Basic functions of link list - Add and print

// Function to add new nodes to the linked list
void add(node * head , int value)
{
   temp = (mynode *) malloc(sizeof(struct node));
   temp->next=(mynode *)0;
   temp->value=value;

   if(head==(mynode *)0)
   {
      head=temp;
      tail=temp;
   }
   else
   {
     tail->next=temp;
     tail=temp;
   }
}

// Function to print the linked list...
void print_list(struct node *head)
{
  mynode *temp;

  printf("\n[%s] -> ", listName);
  for(temp=head;temp!=NULL;temp=temp->next)
  {
    printf("[%d]->",temp->value);
  }

  printf("NULL\n");

}

Function to add node to double link list

2 struct pointers (Double link list)
typedef struct node
{
  int value;
  struct node *next;
  struct node *prev;
}mynode ;

// Function to add a node
void add_node(struct node **head, int value)
{
  mynode *temp, *cur;
  temp = (mynode *)malloc(sizeof(mynode));
  temp->next=NULL;
  temp->prev=NULL;

  if(*head == NULL)
  {
     *head=temp;
     temp->value=value;
  }
  else
  {
   for(cur=*head;cur->next!=NULL;cur=cur->next);
   cur->next=temp;
   temp->prev=cur;
   temp->value=value;
  }
}

Detecting a loop in a linked list (C program)

Brute force method

Have a double loop, where you check the node pointed to by the outer loop, with every node of the inner loop.


typedef struct node
{
  void *data;
  struct node *next;
}mynode;


mynode * find_loop(NODE * head)
{
  mynode *current = head;

  while(current->next != NULL)
  {
    mynode *temp = head;
    while(temp->next != NULL && temp != current)
    {
      if(current->next == temp)
      {
        printf("\nFound a loop.");
        return current;
      }
      temp = temp->next;
    }
    current = current->next;
  }
  return NULL;
}



Visited flag

Have a visited flag in each node of the linked list. Flag it as visited when you reach the node. When you reach a node and the flag is already flagged as visited, then you know there is a loop in the linked list.

Fastest method

Have 2 pointers to start of the linked list. Increment one pointer by 1 node and the other by 2 nodes. If there's a loop, the 2nd pointer will meet the 1st pointer somewhere. If it does, then you know there's one.

Here is some code


p=head;
q=head->next;

while(p!=NULL && q!=NULL)
{
  if(p==q)
  {
    //Loop detected!
    exit(0);
  }
  p=p->next;
  q=(q->next)?(q->next->next):q->next;
}

// No loop.


Examples of printf

19. main()
{
printf("\nab");
printf("\bsi");
printf("\rha");
}

Answer
hai

Explanation
\n - newline
\b - backspace
\r - linefeed 

Comparing floats

Problem
 int main()
{

float me = 1.1;
double you = 1.1;
if(me==you)
printf("I love U");
else
printf("I hate U");
}

Output - I hate U
Explanation
For floating point numbers (float, double, long double) the values cannot be predicted exactly. Depending on the number of bytes, the precession with of the value represented varies. Float takes 4 bytes & long double takes 10 bytes. So float stores 0.9 with less precision than long double. 

Solutions 

//compares if the float f1 is equal with f2 and 

//returns 1 if true and 0 if false
 int compare_float(float f1, float f2)
 {
  float precision = 0.00001;
  if (((f1 - precision) < f2) && 
      ((f1 + precision) > f2))
   {
    return 1;
   }
  else
   {
    return 0;
   }
 }

You can set the precision of the comparison between the 

floating point numbers by changing the "precision" variable.

Calling the function:

 //we compare our numbers
 if (compare_float(x1,x2))
 {
   //do something if equal
 }
 else
 {
   //do something if not equal
 }

Method2 - using fabs i.e.  epsilon absolute error
if (fabs(me - you) < 0.00001)
printf("I love U");
else
printf("I hate U"); 

Absolute error calculations have their place, but they aren’t what is most often used. When talking about experimental error it is more common to specify the error as a percentage. Absolute error is used less often because if you know, say, that the error is 1.0 that tells you very little. If the result is one million then an error of 1.0 is great. If the result is 0.1 then an error of 1.0 is terrible.

C aptitude 1

void main()

{

int const * p=5;

printf("%d",++(*p));

}

Answer:
Compiler error: Cannot modify a constant value.
Explanation:
p is a pointer to a "constant integer". But we tried to change the value of the "constant integer".


 

Solution - #104 Project Euler

//p104
// Find the Fibonacci sequence for which the first nine digits and the last nine digits are 1-9 pandigital

#include
#include

char number_string[100000];

char isPandigital( unsigned long int num )
{
   if ( num < 123456789 )
   {
      return 0;
   }

   char num_of_unique_digits = 0;

   char number_array[9];

   unsigned long int temp = num;

   int i;
   int j;

   for ( i = 0; i < 9; i++ )
   {
      number_array[i] = temp - ((temp / 10) * 10);
      if ( number_array[i] == 0 )
      {
         return 0;
      }

      temp /= 10;
   }

   char is_unique = 1;

   for ( i = 0; i < 9; i++ )
   {
      for ( j = 0; j < 9; j++ )
      {
         if ( i != j )
         {
            if ( number_array[i] == number_array[j] )
            {
               is_unique = 0;
            }
         }
      }

      if ( is_unique )
      {
         num_of_unique_digits++;
      }

      is_unique = 1;
   }

   if ( num_of_unique_digits == 9 )
   {
      return 1;
   }
   else
   {
      return 0;
   }
}

int numOfDigits( mpz_t num )
{
   int num_of_digits = 0;

   char *number_pointer;
   mpz_get_str( number_string, 10, num );

   number_pointer = number_string;

   while( *number_pointer != '\0' )
   {
      num_of_digits++;
      number_pointer++;
   }

   return num_of_digits;
}

char areBothSidesPandigital( mpz_t num )
{
   mpz_t mod;
   mpz_init_set_str( mod, "1000000000", 10 );

   mpz_t temp;
   mpz_init( temp );

   unsigned long int number_group = 0;

   mpz_mod( temp, num, mod );

   number_group = mpz_get_ui( temp );

   if ( isPandigital( number_group ) )
   {
      mpz_ui_pow_ui( temp, 10, (numOfDigits( num ) - 9) );

      mpz_tdiv_q( temp, num, temp );

      number_group = mpz_get_ui( temp );

      if ( isPandigital( number_group ) )
      {
         mpz_clear( temp );
         mpz_clear( mod );

         return 1;
      }
   }

   mpz_clear( temp );
   mpz_clear( mod );

   return 0;
}

int main()
{
   mpz_t num1;
   mpz_init_set_str( num1, "1", 10 );

   mpz_t num2;
   mpz_init_set_str( num2, "1", 10 );

   char add_to_first = 1;
   char are_we_up_to_ten_digits = 0;
   int current_sequence = 2;

   while( 1 )
   {
      current_sequence++;

      if ( add_to_first )
      {
         mpz_add( num1, num1, num2 );
         add_to_first = 0;
      }
      else
      {
         mpz_add( num2, num1, num2 );
         add_to_first = 1;
      }

      if ( add_to_first )
      {
   //      printf( "\nNumber of digits: %d\n", numOfDigits( num2 ) );
         if ( areBothSidesPandigital( num2 ) )
         {
            printf( "\n\nThe double pandigital Fibonacci sequence was found at: %d\n\n", current_sequence );
            return 0;
         }
      }
      else
      {
         //printf( "\nNumber of digits: %d\n", numOfDigits( num1 ) );
         if ( areBothSidesPandigital( num1 ) )
         {
            printf( "\n\nThe double pandigital Fibonacci sequence was found at: %d\n\n", current_sequence );
            return 0;
         }
      }
   }

   //mpz_ui_pow_ui( temp, base, exp );

   //mpz_out_str( out_file, 10, temp );

   //printf("\n");
   //mpz_out_str( stdout, 10, temp );
   //printf("\n\n");

   printf("\n\n");

   return 0;
}