LINKEDLIST FLATTENING

Start with a standard doubly-linked list. Now imagine that in addition to next and
previous pointers, each element has a child pointer, which may or may not point to a
separate doubly-linked list. These child lists may have one or more children of their
own, and so on, to produce a multilevel data structure, as shown in Figure 4-3.
Flatten the list so that all the nodes appear in a single-level, doubly-linked list. You
are given the head and tail of the first level of the list. Each node is a C struct with
the following definition:
typedef struct Node {  
struct Node *next;
struct Node *prev;
struct Node *child;
int          value;
} Node;


This algorithm is as follows:
Start at the beginning of the first level
While you are not at the end of the first level
If the current node has a child
  Append the child to the end of the first level
  Update the tail pointer
Advance to next node


The code for this algorithm is as follows:

void flattenList( Node *head, Node **tail)
Node *curNode =  head;
while( curNode ){
/* The current node has a child */
if( curNode->child ){
append( curNode->child, tail );
}
curNode = curNode->next;
}
}

/* Appends the child list to the end of the tail and updates  ;
* the tail.
*/

void append( Node *child, Node **tail ){
Node *curNode;
/* Append the child child list to the end */
(*tail)->next = child;
child->prev = *tail;

/*Find the new tail, which is the end of the child child   ;
*list.
*/

for( curNode = child; curNode->next;
curNode = curNode->next )
; /* Body intentionally empty */
/* Update the tail pointer now that curNode is the new 
* tail.
*/
*tail = curNode;
}

TRAVERSAL AND INSERTION IN LINKED LIST

A simple LinkedList program that deletes and insert node at a particular location .

#include <iostream>       

using namespace std;

 struct node {
 node *next ;

     int data ;

    } ;

 struct node *head ;   
node* init(int a[] , int n)

 {
  node *head = NULL , *p ;

  for(int i=0;i<n;i++)

   {

    node *nd = new node() ;

    nd->data = a[i] ;

    if(i==0)

    {
    head = p = nd ;   

    }

    p->next = nd ;

    p = p->next ;

      

   }

   return head ;

    

 }

 void display (node *head)

 {

     node *p ;

     p = head ;

    while(p!=NULL)

     {

           cout<<p->data<<endl;

           p = p->next ;

        

     }

    

 }

 bool deleteMe(int x)

  {

   node *p = head ;

   if(head->data ==x)

    {

        head = head->next ;

    }

    else

    {

    while(p->next->data != x)

     {

        

         p = p->next ;

     }

     if(p->next->data == x)

      {

         

          p->next = p->next->next ;

          return 1 ;

      }

    }

          return 0 ;

  }

 void insertMe(int loc , int data)

  { 

      node *nd = new node();

      nd->data =  data ;

     node *p = head ;

     if(loc==1)

      {

          nd->next = head ;

          head = nd ;

         

      }else

      {

          for(int i=1 ; i<loc-1 ; i++)

           {

               p = p->next ;

              

           }

           nd->next = p->next ;

           p->next = nd ;

         

      }

     

  }

int main()

{

  int a[] = {1,2,3,4,5,6,7,8,9} ;

  head = init(a , 9) ;

  display(head) ;

  deleteMe(1) ; //delete the node with the given data

  cout<<endl<<endl ;

  display(head) ;

  cout<<endl<<endl ;

  insertMe(3 , 10);

  display(head) ;

  return 0;

}

IMPLEMENTING STACK VIA LINKED-LIST 

We all know what stack do . Its follows a  Last In First Out methodology and here in this program i have implemented the same via LinkedList . I hope you all know what a LinkedList does . 
struct node
{
  node *next ;
  int data ;
};
struct node *head = NULL , *p=NULL ;
void display()
{
  node *temp = new node() ;
  temp = head ;
  while(temp!=NULL)
  {
    printf("%d\n",temp->data) ;
    temp = temp->next ;
  }
}
void push(int x)
{
  node *nd = new node() ;
  nd->data = x ;
  if(head==NULL)
  {
    head = p = nd ;

  }else
  {
    p->next  = nd ;
    p = p->next ;
  }
  display() ;
}
void pop ()
{
  node *temp = new node() ;
  temp = head ;
  while(temp->next->next!=NULL)
  {
      temp = temp->next ;
  }
  printf("popped element %d\n",temp->next->data) ;
  temp->next = NULL ;
  display() ;
}
int _tmain(int argc, _TCHAR* argv[])
{
    int value , x , v ;
    do
    {
        printf("1. push") ;
        printf("2. pop");
        printf("choose...") ;
        scanf_s("%d",&value) ;
        switch(value)
        {
        case 1 :
            printf("Enter data");
            scanf_s("%d",&x);
            push(x) ;
            break;
        case 2 :
            pop() ;
        }
        printf("press 3 to continue") ;
        scanf_s("%d",&v) ;
    }while(v==3) ;

    return 0;
}
 

Arrays and Strings : Write a method to replace all spaces in a string with ‘%20’.

#include <iostream>
#include <cstring>
#include <conio.h>

char* replace1(char *c){
    if(c == NULL) return NULL;
    int len = strlen(c);
    if(len == 0) return NULL;
    int cnt = 0;
    for(int i=0; i<len; ++i)
    {
        if(c[i] == ' ')
            ++cnt;
    }
    char *cc = new char[len+2*cnt+1];
    int p = 0;
    for(int i=0; i<len; ++i)
    {
        if(c[i] == ' ')
        {
            cc[p] = '%';
            cc[p+1] = '2';
            cc[p+2] = '0';
            p += 3;
        }
        else
        {
            cc[p] = c[i];
            ++p;
        }
    }
    cc[p] = '\0';
    return cc;
}
int main(){
    const int len = 100;
    char c[len] = "abcd efgh";
    cout<<replace1(c)<<endl;
    getch();
    return 0;
}

Arrays and Strings : Write a method to decide if two strings are anagrams or not.

Two strings are anagrams if both strings contain the same characters could be in different orders . For example "abcd" , "dcba" , "bcda" all are anagrams . 
In the given question we have to check whether two strings are anagrams or not 

#include<iostream.h>
#include<conio.h>
#include<cstring.h>
bool isAnagram(string s1 , string s2)
 {
   if(s1=="" || s2=="") return false ;
   if(s1.length()!=s2.length()) return false ;
   int c[256] ;
   memset(c,0,sizeof(c));
   int len = s1.length() ;
   for(int i=0;i<len;++i)
    {
      ++c[(int)s1[i]] ;
      --c[(int)s2[i]] ;
    }

    for(int i=0 ; i<256;i++)
     {
       if(c[i]!=0) return false ;

     }
    return true ;
 }
int main ()
{
  string s1 = "abcd" ;
  string s2 = "abdc" ;
  bool ans = isAnagram(s1,s2) ;
  cout<<ans ;
  getch();
}

this problem has a very simple trick all you have to do is use a buffer int array and initialize every element to 0 . Now in a loop increment the respective ascii position of character of string s1 and at the same time decrement for s2 .  If the array elements are all 0 that means they are anagrams .
That simple :)

Arrays and Strings : Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine. An extra copy of the array is not.

#include<iostream.h>
#include<conio.h>
#include<cstring.h>
string remove(string s)
{
    int len = s.length();
    if(len < 2) return s;
    string str = "";
    for(int i=0; i<len; ++i)
    {
        if(s[i] != '\0')
        {
            str += s[i];
            for(int j=i+1; j<len; ++j)
                if(s[j]==s[i])
                    s[j] = '\0';
        }
    }
    return str;
}
int main ()
{
  string s1 = "abcdefgha" ;
  cout<<remove(s1) ;
  getch();
}

In this code we pick a character from the string assign it and then compare every Ith character with each and every I+1th character till the last character if we encounter a match we null that position .
In the end we return the string
 

Arrays and Strings : Write code to reverse a C-Style String. (C-String means that “abcd” is represented as five characters, including the null character.)

As the question itself explains what a C-Style string is "C-String means that “abcd” is represented as five characters, including the null character."

lets start the code :-

#include<iostream.h>
#include<conio.h>
void swap(char &a, char &b)
 {

    a = a^b;
    b = a^b;
    a = a^b;

 }
void reverse(char *s)
 {
   char *p = s , *q = s ;
 while(*q)
  q++ ;
q-- ;
while(p<q)
swap(*p++ , *q--) ;
 }
int main ()
 {
   char s[] = "abcdefghijkl" ;
   reverse(s) ;
 cout<<s<<endl ;
 }

Here i did nothing but used pointers ,  reverse function receives a character pointer and assign its value to two other pointers . pointer q iterates till the end and after that q has the address of the last character and  p contains the address of the first .
nothing much important left after that all you have to do is swap first character with the last one .  Increment p's value and decrement q's value at the same time
 

Arrays and Strings : Implement an algorithm to determine if a string has all unique characters.

This problem can be easily solved by using a buffer array of the type bool which will act as a check parameter to see if the character already occurred in string or not .

lets start coding :-


#include<iostream.h>
#include<conio.h>
#include<cstring.h>

bool checkUnique(string s)
{
 bool a[256];
 memset(a,0,sizeof(a)) ;
 int len = s.length();
for(int i=0;i<len;i++)
 {
             int pos =  (int)s[i] ;
             if(a[pos]) return false ;
            a[pos] = 1  ;

}
return true ;
}
int main (){
  string s1 = "Hello this is my first post" ;
  string s2 = "qwertyuiopasdfgghjklzxcvbnm" ;
 cout<<checkUnique(s1)<<endl ;
 cout<<checkUnique(s2)<<endl  ; 
 return 0 ;
}

Here what i used is a for loop in which i pick a character convert it into integer (its ascii value) and check at that location what array "a" holds .
if its "1" that means the character is repeated and its not unique otherwise continue the loop .