cpppro

Archive for the ‘Question Patterns’ Category

C/C++ Interview algorithms

In Algorithms, Data Structures in C/C++, Question Patterns on April 17, 2007 at 10:35 pm

1. Reverse a singly linked list

//
// iterative version
//
Node* ReverseList( Node ** List )
{
  Node *temp1 = *List;
  Node * temp2 = NULL;
  Node * temp3 = NULL;

  while ( temp1 )
  {
    //set the head to last node
    *List = temp1;

    // save the next ptr in temp2
    temp2= temp1->pNext;

    // change next to privous
    temp1->pNext = temp3;
    temp3 = temp1;
    temp1 = temp2;
  }

  return *List;
}

2. Delete a node in double linked list

void deleteNode(node *n)
{
  node *np = n->prev;
  node *nn = n->next;
  np->next = n->next;
  nn->prev = n->prev;
  delete n;
}

3. Sort a linked list

//sorting in descending order
struct node
{
  int value;
  node* NEXT;
}
//Assume HEAD pointer denotes the first
//element in the linked list
//only change the values? don't have to
//change the pointers
Sort( Node *Head)
{
  node* first,second,temp;
  first= Head;
  while(first!=null)
  {
    second=first->NEXT;
    while(second!=null)
    {
      if(first->value value)
      {
        temp = new node();
        temp->value=first->value;
        first->value=second->value;
        second->value=temp->value;
        delete temp;
      }
      second=second->NEXT;
    }
    first=first->NEXT;
  }
}

4. Reverse a string

void ReverseString (char *String)
{
  char *Begin = String;
  char *End = String + strlen(String) - 1;
  char TempChar;

  while (Begin < End)
  {
    TempChar = *Begin;
    *Begin = *End;
    *End = TempChar;
    Begin++;
    End- -;
  }
}

5. Insert a node a sorted linked list

void sortedInsert(Node * head, Node* newNode)
{
  Node *current = head;

  // traverse the list until you find
  //item bigger the new node value
  //
  while ((current!= NULL) &&
         (current->data data))
  {
    current = current->next;
  }
  //
  // insert the new node before the big item
  //
  newNode->next = current->next;
  current = newNode;
}

6. Covert a string to upper case

void ToUpper(char * S)
{
  while (*S!=0)
  {
    *S=(*S >= 'a' && *S <= 'z')?(*S-'a'+'A'):*S;
    S++;
  }
}

7. Multiple a number by 7 without using * and + operator.