1. Consider an array which may contains the alphabets from A to Z. Suppose consider the below examples
A[9] = {A,C,D,G,D,E,A,C,A}; then the output should be in the format of A=3; C=2; D=2; E=1; G=1
A[9] = {A,B,D,C,D,B,A,B,A}; then the output should be in the format of A=3; B=3; C=1; D=2
Write the logic in C. The values in array may vary. The output should count the alphabets in the array.
Solution:

void countAlphabet(char a[], int n)
{
    int count[26] = {0}, i, kind = 0;
    //count
    for(i = 0; i < n; ++i) ++count[a[i] - 'A'];
    //output
    for(i = 0; i < n; ++i)
    {    if(a[i] > 0)
        {
            ++kind;
            if(kind > 1) putchar(';');
            printf("%c=%d", 'A'+i, count[i]);
        }
    }
}

2. Write an algorithm to generate a mirror (copy) of the binary tree without using recursion.
Solution:

Use a stack.
Initialization: push the root in
Iterative steps :

  1. pop the top element
  2. Swap left right pointers
  3. put them in stack
  4. Repeat until stack is empty

 

3. You are given an array say 5,4,2,7,9,6. You need to convert it to a sorted array in minimum operation where only operation allowed is decrement.
For example above array becomes 2,2,2,6,6,6 (operations=9)..
Solution:

Start at the end of the array and set current = a[n-1]
Iterate backwards
While a[i] > current : decrement
If(a[i]< current : current = a[i]

 

4. Insert a element in a sorted circular linked list.
Solution: Algorithm

Allocate memory for the newly inserted node and put data in the newly allocated node. Let the pointer to the new node be new_node. After memory allocation, following are the three cases that need to be handled.

  1. Linked List is empty:
    1. Since new_node is the only node in CLL(circular linked list), make a self loop.
      new_node->next = new_node;
    2. Change the head pointer to point to new node.
      *head_ref = new_node;
  2. New node is to be inserted just before the head node:
    1. Find out the last node using a loop.
      While(current->next != *head_ref)
      current = current->next;
    2. Change the next of last node.
      current->next = new_node;
    3. Change next of new node to point to head.
      new_node->next = *head_ref;
    4. Change the head pointer to point to new node.
      *head_ref = new_node;
  3. New node is to be inserted somewhere after the head:
    1. Locate the node after which new node is to be inserted.
      While ( current->next!= *head_ref && current->next->data < new_node->data)
      current = current->next;
    2. Make next of new_node as next of the located pointer
      new_node->next = current->next;
    3. Change the next of the located pointer
      current->next = new_node;

Code:

#include<iostream.h>
#include<conio.h>
/* structure for a node */
struct node
{
  int data;
  struct node *next;
};

/* function to insert a new_node in a list in sorted way. Note that this function expects a pointer to head node as this can modify the head of the input linked list */
void sortedInsert(struct node** head_ref, struct node* new_node)
{
  struct node* current = *head_ref;
  // Case 1 of the above algorithm
  if (current == NULL)
  {
     new_node->next = new_node;
     *head_ref = new_node;
  }
  // Case 2 of the above algorithm
  else if (current->data >= new_node->data)
  {
    /* If value is smaller than head's value then we need to change next of last node */
    while(current->next != *head_ref)
        current = current->next;
    current->next = new_node;
    new_node->next = *head_ref;
    *head_ref = new_node;
  }
  // Case 3 of the above algorithm
  else
  {
    /* Locate the node before the point of insertion */
    while (current->next!= *head_ref && current->next->data < new_node->data)
           current = current->next;
    new_node->next = current->next;
    current->next = new_node;
  }
}
/* Function to print nodes in a given linked list */
void printList(struct node *start)
{
  struct node *temp;
  if(start != NULL)
  {
    temp = start;
    printf("\n");
    do 
    {
      printf("%d ", temp->data);
      temp = temp->next;
    } while(temp != start);
  }
}
/* Driver program to test above functions */
int main()
{
  int arr[] = {12, 56, 2, 11, 1, 90};
  int list_size, i;

  /* start with empty linked list */
  struct node *start = NULL;
  struct node *temp;

  /* Create linked list from the array arr[].
    Created linked list will be 1->2->11->56->12 */
  for(i = 0; i< 6; i++)
   {   temp = (struct node *)malloc(sizeof(struct node));     
       temp->data = arr[i];
       sortedInsert(&start, temp);
  }
  printList(start);
  getchar();
  return 0;
}

Output:

1 2 11 12 56 90

Time Complexity: O(n) where n is the number of nodes in the given linked list.

Case 2 of the above algorithm/code can be optimized.

// Case 2 of the above algorithm
  else if (current->data >= new_node->data)
  {
    // swap the data part of head node and new node
    swap(&(current->data), &(new_node->data));  // assuming that we have a function swap(int *, int *)

    new_node->next = (*head_ref)->next;
    (*head_ref)->next = new_node;
  }