Rotate a NxN 2D matrix by 90 degrees – C Program Source Code

The below program does the following:

1. Creates a 2D matrix whose size can be input through Command Line arguments.
2. Prints the 2D Matrix.
3. Rotates the matrix by right angle (90 degrees) clockwise.

Source Code:

#include<stdio.h>
#include<stdlib.h>
#define DEFN 6

int** CreateMatrix(int**, int N);
void PrintMatrix(int**, int N);
int** RotateMatrix(int**,int N);

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

 int **matrix = NULL;
 int N;
 if(argc==2)
 N = atoi(argv[1]);
 else
 N = DEFN;
 matrix = CreateMatrix(matrix, N);
 printf("\nInitialMatrix:\n");
 PrintMatrix(matrix,N);
 printf("\n");
 matrix = RotateMatrix(matrix,N);
 printf("\nRotated Matrix:\n");
 PrintMatrix(matrix,N);

 char c = getchar();

 return(0);
}
int** CreateMatrix(int **matrix, int N)
{
 int i,j;
 matrix = (int**) calloc(N,sizeof(int*));
 for(i=0; i<N; i++)
 {
 *(matrix+i) = (int*) calloc(N, sizeof(int));
 for(j=0; j<N; j++)
 *(*(matrix+i)+j) = rand();
 }
 return(matrix);
}
void PrintMatrix(int **matrix, int N)
{
 int i,j;
 for(i=0; i<N; i++)
 {
 for(j=0; j<N; j++)
 printf("%6d ", *(*(matrix+i)+j));
 printf("\n");
 }
} 

int** RotateMatrix(int **matrix, int N)
{
 int i,temp,layer;

 for(layer=0; layer<(N/2); layer++)
 for(i=layer; i<N-layer-1; i++)
 {

 temp = *(*(matrix+N-i-1)+layer);
 *(*(matrix+N-i-1)+layer) = *(*(matrix+N-layer-1)+N-i-1);
 *(*(matrix+N-layer-1)+N-i-1) = *(*(matrix+i)+N-layer-1);
 *(*(matrix+i)+N-layer-1) = *(*(matrix+layer)+i);
 *(*(matrix+layer)+i) = temp;
 }
 return(matrix);
}

OUTPUT:

InitialMatrix:
 41 18467 6334 26500 19169 15724
11478 29358 26962 24464 5705 28145
23281 16827 9961 491 2995 11942
4827 5436 32391 14604 3902 153
292 12382 17421 18716 19718 19895
5447 21726 14771 11538 1869 19912
Rotated Matrix:
 5447 292 4827 23281 11478 41
21726 12382 5436 16827 29358 18467
14771 17421 32391 9961 26962 6334
11538 18716 14604 491 24464 26500
1869 19718 3902 2995 5705 19169
19912 19895 153 11942 28145 15724

Check if Strings are Permutations – JAVA Program Source Code

The following program verifies if 2 input strings are permutations of each other and displays the result.

Source Code:

package javasamples;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class JavaSamples 
{
 public static HashMap CreateStringHash(String s)
 {
 HashMap mapStr = new HashMap();
 char str[] = s.toCharArray();
 int i = 1;
 for(char c : str)
 {
 if(mapStr.get(c)==null)
 mapStr.put(c,i);
 else
 {
 mapStr.put(c,i+(int)mapStr.get(c));
 }
 }
 return(mapStr);
 }
 public static boolean CheckStringPerm(String s1, String s2)
 {
 HashMap mapStr1 = CreateStringHash(s1);
 char str2[] = s2.toCharArray();
 for(char c : str2)
 {
 if(mapStr1.get(c)==null || (int)mapStr1.get(c)==0)
 return(false);
 else
 mapStr1.put(c,(int)mapStr1.get(c)-1);
 }
 Iterator itr = mapStr1.entrySet().iterator();
 Map.Entry strEntry;
 while(itr.hasNext())
 {
 strEntry = (Map.Entry) itr.next();
 if((int)strEntry.getValue()!=0)
 return(false);
 }
 return(true);
 }
 public static void main(String[] args) 
 {
 String str1 = "Elephants are great";
 String str2 = "great Elephant arse";
 System.out.println("String1 = " + str1);
 System.out.println("String2 = " + str2);
 System.out.print("Strings are Permutation = ");
 if(CheckStringPerm(str1,str2))
 System.out.println("Yes");
 else
 System.out.println("No");
 }
}

OUTPUT:

run:
String1 = Elephants are great
String2 = great Elephant arse
Strings are Permutation = Yes
BUILD SUCCESSFUL (total time: 0 seconds)

Implement a queue with versions to fetch the contents at any version – C++ Program Source Code

The below program performs the following operations:

1. Implements a Queue with standard Enqueue and Dequeue operations to insert and retrieve an element respectively in First In First Out order. The data stored in this case are integers.
2. Implements a versioning system for the Queue to maintain a unique version number of the Queue at every Enqueue and Dequeue operations.
3. Retrieve the contents of the Queue at any given state with the version number.

#include <iostream>
#include <vector>

using namespace std;

void PrintArray(int*);

class The_Queue
{
    vector<int> value;
    vector<float> version_in;
    vector<float> version_out;
    int topIndex, bottomIndex;
    float current_version;

    int getStartIndex(float ver)
    {
        int index;
        for(index=0; index<=topIndex; index++)
        {
            if((version_out[index] > ver) || (version_out[index]==''))
            {
                return(index);
            }
        }
        return(topIndex+1);
    }

    int getEndIndex(float ver)
    {
        int index;
        for(index=0; index<=topIndex; index++)
        {
            if(version_in[index] > ver)
            {
                return(index);
            }
        }
        return(index-1);
    }

    public:
        The_Queue()
        {
            topIndex = -1;
            bottomIndex = 0;
            current_version = 0.9;
        }

        void Enqueue(int val)
        {
            current_version += 0.1;
            value.push_back(val);
            version_in.push_back(current_version);
            version_out.push_back('');
            topIndex++;
        }

        int Dequeue()
        {
            if(topIndex == bottomIndex-1)
            {
                return('');
            }
            else
            {
                current_version+=0.1;
                version_out[bottomIndex] = current_version;
                bottomIndex++;
                return(value[bottomIndex-1]);
            }
        }

        int* GetAtVersion(float ver)
        {
            int index, startIndex=0, endIndex=topIndex;
            int size;
            startIndex = getStartIndex(ver);
            endIndex = getEndIndex(ver);

            if(startIndex == (endIndex+1))
            {
                size = 0;
            }
            else
            {
                size = endIndex - startIndex + 1;
            }
            int *Result;
            Result = new int[size+1];
            for(index=startIndex; index<=endIndex; index++)
            {
                Result[index-startIndex] = value[index];
            }
            Result[index-startIndex] = '';
            return(Result);
        }

        float getCurrentVersion()
        {
            return(current_version);
        }

        void PrintAll()
        {
            int index;
            for(index=0; index<=topIndex; index++)
            {
                cout<<value[index]<<"  ";
            }
            cout<<endl;
        }

        void PrintAllIn()
        {
            int index;
            for(index=0; index<=topIndex; index++)
            {
                cout<<version_in[index]<<"  ";
            }
            cout<<endl;
        }

        void PrintAllOut()
        {
            int index;
            for(index=0; index<=topIndex; index++)
            {
                cout<<version_out[index]<<"  ";
            }
            cout<<endl;
        }
};

void PrintArray(int *arr)
{
     int i;
     for(i=0; arr[i]!=''; i++)
     {
         cout<<arr[i]<<"  ";
     }
     cout<<endl;
}

int main(void)
{
    The_Queue q = The_Queue();

    int option,val;
    float ver;
    int *Res;

    while(1)
    {
        cout<<"Enter option:"<<endl<<"1.Enqueue"<<endl<<"2.Dequeue"<<endl<<"3.Print at Version"<<endl<<"Q.Quit"<<endl;
        cin>>option;
        if(option == 1)
        {
             cout<<"Enter the value to Enqueue :"<<endl;
             cin>>val;
             q.Enqueue(val);
        }
        else if(option == 2)
        {
             val = q.Dequeue();
             if(val == '')
             {
                 cout<<"Cannot deque. Queue is empty"<<endl;
             }
             else
             {
                 cout<<"The Dequeued value was : "<<val<<endl;
             }

        }
        else if(option == 3)
        {
             cout<<"Enter the version number for getting the state of Queue :"<<endl;
             cin>>ver;
             if(ver<1.0)
             {
                 cout<<"No such version present."<<endl;
             }
             else
             {
                 if(ver > q.getCurrentVersion())
                 {
                     cout<<"No such version present.Returning results for latest version "<<q.getCurrentVersion()<<" instead."<<endl;
                 }
                 Res = q.GetAtVersion(ver);
                 PrintArray(Res);
             }
        }
        else
        {
            return 0;
        }

    }

    return(0);
}

INPUT / OUTPUT

Enter option:
1.Enqueue
2.Dequeue
3.Print at Version
Q.Quit
1
Enter the value to Enqueue :
5
Enter option:
1.Enqueue
2.Dequeue
3.Print at Version
Q.Quit
1
Enter the value to Enqueue :
12
Enter option:
1.Enqueue
2.Dequeue
3.Print at Version
Q.Quit
1
Enter the value to Enqueue :
19
Enter option:
1.Enqueue
2.Dequeue
3.Print at Version
Q.Quit
2
The Dequeued value was : 5
Enter option:
1.Enqueue
2.Dequeue
3.Print at Version
Q.Quit
1
Enter the value to Enqueue :
212
Enter option:
1.Enqueue
2.Dequeue
3.Print at Version
Q.Quit
1
Enter the value to Enqueue :
14
Enter option:
1.Enqueue
2.Dequeue
3.Print at Version
Q.Quit
2
The Dequeued value was : 12
Enter option:
1.Enqueue
2.Dequeue
3.Print at Version
Q.Quit
1
Enter the value to Enqueue :
299
Enter option:
1.Enqueue
2.Dequeue
3.Print at Version
Q.Quit
2
The Dequeued value was : 19
Enter option:
1.Enqueue
2.Dequeue
3.Print at Version
Q.Quit
1
Enter the value to Enqueue :
1000
Enter option:
1.Enqueue
2.Dequeue
3.Print at Version
Q.Quit
1
Enter the value to Enqueue :
2949
Enter option:
1.Enqueue
2.Dequeue
3.Print at Version
Q.Quit
1
Enter the value to Enqueue :
789
Enter option:
1.Enqueue
2.Dequeue
3.Print at Version
Q.Quit
2
The Dequeued value was : 212
Enter option:
1.Enqueue
2.Dequeue
3.Print at Version
Q.Quit
2
The Dequeued value was : 14
Enter option:
1.Enqueue
2.Dequeue
3.Print at Version
Q.Quit
2
The Dequeued value was : 299
Enter option:
1.Enqueue
2.Dequeue
3.Print at Version
Q.Quit
3
Enter the version number for getting the state of Queue :
2.1
212  14  299  1000  2949  789
Enter option:
1.Enqueue
2.Dequeue
3.Print at Version
Q.Quit
3
Enter the version number for getting the state of Queue :
1.5
12  19  212  14
Enter option:
1.Enqueue
2.Dequeue
3.Print at Version
Q.Quit
3
Enter the version number for getting the state of Queue :
1.1
5  12  19
Enter option:
1.Enqueue
2.Dequeue
3.Print at Version
Q.Quit
3
Enter the version number for getting the state of Queue :
2.2
14  299  1000  2949  789
Enter option:
1.Enqueue
2.Dequeue
3.Print at Version
Q.Quit

Reverse Single Linked List – C Program Source Code

The below program performs the following:

1. Takes input of the size of the Linked List as Command Line argument.
2. Creates a Singly Linked List of input size (default: 20 members) filled with random numbers.
3. Prints the members of the Linked List.
4. Reverses the Linked List and prints it again.

Source Code:

#include<stdio.h>
#define NELEMENTS 20
struct node
{
 int value;
 struct node *next;
};
struct node* CreateLinkedList(int, struct node*);
void printList(struct node*);
struct node* Reverse(struct node*);
int main(int argc, char *argv[])
{
 struct node *head;
 int NofElements;
 if(argc == 2)
 NofElements = atoi(argv[1]);
 else
 NofElements = NELEMENTS;
 head = CreateLinkedList(NofElements, head);
 printList(head);
 head = Reverse(head);
 printList(head);

 char c;
 c = getchar();
 return(0);
}
struct node* CreateLinkedList(int NElements, struct node *head)
{ 
 struct node *temp = NULL;
 temp = (struct node*) malloc(sizeof(struct node));
 head = temp;

 for( ; NElements>0; NElements--, temp=temp->next)
 {
 temp->value = rand();
 temp->next = (struct node*) malloc(sizeof(struct node));

 }
 temp->value = '';
 temp->next = NULL;

 return(head);
}
void printList(struct node *head)
{
 struct node *temp;

 for(temp=head; (temp->value)!=''; temp=temp->next)
 printf("%8d", temp->value);
printf("\n");
}
struct node* Reverse(struct node *head)
{
 struct node *temp_prev, *temp, *temp_post;

 for(temp_prev=head,temp=head->next; (temp_prev->next)!=NULL && (temp->next)!= NULL; )
 {
 temp_post = temp->next;
 temp->next = temp_prev;
 temp_prev = temp;
 temp = temp_post;
 }
 head->next = temp;
 head = temp_prev;

 return(head);
}

Selection Sort using linked list – C program source code

#include<stdio.h>
#include<stdlib.h>
#define DEFNELEMENTS 50
struct node
{
 int value;
 struct node *next;
};

struct node* GenerateNumbers(int, struct node*);
struct node* SelectionSort(struct node*);
void PrintList(struct node*);

int main(int argc, char *argv[])
{
 int NofElements;
 struct node *head;

 if(argc == 2)
 NofElements = atoi(argv[1]);
 else
 NofElements = DEFNELEMENTS;
 head = GenerateNumbers(NofElements, head);
 PrintList(head);
 head = SelectionSort(head);
 PrintList(head); 

 char c;
 c = getchar();

 return(0);
}

struct node* GenerateNumbers(int NElements, struct node *head)
{
 struct node *temp; 
 int count;
 temp = (struct node*) malloc((int)sizeof(struct node));
 head = temp;
 for(count=0; count<NElements; count++)
 {
 temp->value = rand();
 temp->next = (struct node*) malloc(sizeof(struct node));
 temp = temp->next;
 }
 temp->value = '';
 temp->next=NULL;
 return(head);
}

struct node* SelectionSort(struct node *head)
{
 struct node *tempout;
 struct node *tempin;
 struct node *tempoutpre = NULL;
 struct node *tempinpre = NULL;
 struct node *smallest = NULL;
 struct node *smallestpre = NULL;

 for(tempout=head; (tempout->value)!= ''; tempoutpre=tempout, tempout=tempout->next)
 {
 smallest = tempout;
 tempinpre = tempout;
 smallestpre = tempoutpre;
 for(tempin=tempout->next; (tempin->value)!=''; tempinpre=tempin, tempin=tempin->next)
 {
 if((tempin->value)<(smallest->value))
 {
 smallest = tempin;
 smallestpre = tempinpre;
 }
 }
 if(smallest!=tempout)
 {
 smallestpre->next = smallest->next;
 smallest->next = tempout;
 if(tempout == head)
 head = smallest;
 else
 tempoutpre->next = smallest;
 tempout = smallest;
 }
 }
 return(head);
}

void PrintList(struct node *head)
{
 struct node *temp;

 for(temp=head; (temp->value)!=''; temp=temp->next)
 {
 printf("%6d ",temp->value);
 }
 printf("\n");
}

Insertion Sort using linked list – C program source code

#include<stdio.h>
#include<stdlib.h>
#include<stddef.h>
#define DEFNELEMENTS 500
struct node
{
 int value;
 struct node *next;
};
struct node* GenerateNumbers(int, struct node*);
struct node* InsertionSort(struct node*);
void PrintList(struct node*);
int main(int argc, char *argv[])
{
 int NofElements;
 struct node *head;

 if(argc == 2)
 NofElements = atoi(argv[1]);
 else
 NofElements = DEFNELEMENTS;
 head = GenerateNumbers(NofElements, head);
 PrintList(head);
 head = InsertionSort(head);
 PrintList(head); 
 char c;
 c = getchar();

 return(0);
}

struct node* GenerateNumbers(int NElements, struct node *head)
{
 struct node *temp; 
 int count;
 temp = (struct node*) malloc((int)sizeof(struct node));
 head = temp;
 for(count=0; count<NElements; count++)
 {
 temp->value = rand();
 temp->next = (struct node*) malloc(sizeof(struct node));
 temp = temp->next;
 }
 temp->value = '';
 temp->next=NULL;
 return(head);
}

struct node* InsertionSort(struct node *head)
{
 struct node *tempout;
 struct node *tempin;
 struct node *tempoutpre = NULL;
 struct node *tempinpre = NULL;

 for(tempout=head; (tempout->value)!= ''; tempoutpre=tempout, tempout=tempout->next)
 {
 for(tempin=head; (tempin->value)<=(tempout->value) && (tempin->next)!=(tempout->next); tempinpre=tempin, tempin=tempin->next);

 if((tempin->next)!=(tempout->next))
 {
 tempoutpre->next = tempout->next;
 tempout->next = tempin;
 if(tempin == head)
 head = tempout; 
 else 
 tempinpre->next = tempout;
 } 
 }
 return(head);
}

void PrintList(struct node *head)
{
 struct node *temp;

 for(temp=head; (temp->value)!=''; temp=temp->next)
 {
 printf("%6d ",temp->value);
 }
 printf("\n");
}