Matrix Problems

Some matrix (2D array) problems

1. Given two matrices, perform Matrix Addition

2. Given two matrices, perform Matrix Subtraction

3. Given two matrices, perform Matrix Multiplication

4. Given two matrices, perform Matrix Division

5. Given a matrix , output the mirror of the matrix

6. Given a matrix , output 90 degree left rotation 

7. Given a matrix , output 90 degree right rotation

8. Given a matrix , make diagonal elements zero

9. Given a matrix , make elements zero except diagonal

10. Given a matrix , Make upper triangular matrix zero

11. Given a matrix , Make lower triangular matrix zero

12. Given two matrix , Check whether both are identical

13. Given a matrix , some element mXn is zero. Make the Mth row & Nth column zero.

14. Given a matrix, Adding upper & lower triangular matrix

15. Given a matrix , Swapping upper & lower triangular matrix elements

16. Given a matrix , Make the elements in the border are zero.

17. Given a matrix , Make the corner elements zero.

18. Given a matrix , perform binary search in a matrix

Quick Sort

#include<stdio.h>
#define MAX 10
void qsort(int A[], int p, int r);
int partition(int A[], int p, int r);

main()
{
int Arr[MAX]={10,4,5,6,2,3,8,1,9,7};
int i;
qsort(Arr,0,MAX);

for(i=0;i<MAX;i++)
printf("%d ",Arr[i]);
}

void qsort(int A[], int p, int r)
{
int q;
if(p<r)
{
q=partition(A,p,r);
qsort(A,p,q-1);
qsort(A,q+1,r);
}
}

int partition(int A[], int p, int r)
{
int i , j , x,tmp;
x=A[r];
j=p;
i=p-1;
while(j<r)
{
if(A[j]<x)
{
i=i+1;
// Exchange A[i] & A[j]
tmp=A[j];
A[j]=A[i];
A[i]=tmp;
}
j++;
}
// Exchange A[i+1] & A[r]
tmp=A[i+1];
A[i+1]=A[r];
A[r]=tmp;

return i+1;
}

Output:
1 2 3 4 5 6 7 8 9 10

Time Complexity:
Best - O( n log n )
Average - O(n log n )
Worst - O( n^2)

Pair Wise Swapping in a Linked List

#include<stdio.h>
#include<stdlib.h>

typedef struct list
{
int info;
struct list *next;
}node;

node * head;

void insert(int data);
void display();
void pairwise_swapping(node *ptr);
void swap(int *a, int *b);

void insert(int data)
{
node *ptr , *tmp;
ptr=(node*)malloc(sizeof(node));

if(ptr==NULL)
return;

(*ptr).info=data;
(*ptr).next=NULL;
if(head==NULL)
{
head=ptr;
}
else
{
tmp=head;
while((*tmp).next!=NULL)
tmp=(*tmp).next;

(*tmp).next=ptr;
}
}

void display()
{
node * ptr;

if(head==NULL)
{
printf("list is empty\n");
return;
}

for(ptr=head;ptr!=NULL;ptr=(*ptr).next)
printf("%d ",(*ptr).info);
}

void swap(int *x , int *y)
{
int temp;
temp=*x;
*x=*y;
*y=temp;
}

void pairwise_swapping(node *ptr)
{
node *tmp , *tmp_next;
tmp= ptr;
while (tmp!=NULL && (*tmp).next!=NULL)
{
tmp_next = (*tmp).next;
swap(&(*tmp).info , &(*tmp_next).info);
tmp=(*tmp_next).next;
}
}

main()
{
insert(1);
insert(2);
insert(3);
insert(4);
insert(5);
insert(6);
pairwise_swapping(head);
display();
}

Output:
2 1 4 3 6 5 

Merge Sort

#include<stdio.h>
#define MAX 10

void MergeSort(int Arr[],int low, int high);
void Merge(int Arr[],int low, int mid,int high);

main()
{
    int A[MAX]={9,8,7,6,5,4,3,2,1,10};
    int i;
    MergeSort(A,0,MAX-1);
    for(i=0;i<MAX;i++)
    printf("%d ",A[i]);
}

void MergeSort(int Arr[], int low, int high)
{
    int mid;
    if(low<high)
    {
        mid=(low+high)/2;
        MergeSort(Arr,low,mid);
        MergeSort(Arr,mid+1,high);
        Merge(Arr,low,mid,high);
    }
}

void Merge(int Arr[], int low, int mid, int high)
{
    int l,m,i,k;
    int temp[MAX];

    l=i=low;
    m=mid+1;

    while((l<=mid) && (m<=high))
    {
        if(Arr[l]<=Arr[m])
        {
            temp[i]=Arr[l];
            l++;
        }
        else
        {
            temp[i]=Arr[m];
            m++;
        }
        i++;
    }

    if(l>mid)
    {
        for(k=m;k<=high;k++)
        {
        temp[i]=Arr[k];
        i++;
        }
    }
    else
    {
        for(k=l;k<=mid;k++)
        {
            temp[i]=Arr[k];
            i++;
        }
    }

    for(k=low;k<=high;k++)
    Arr[k]=temp[k];
}

Time Complexity: O(n logn)

Insertion Sort ( reverse)

 

Orginal insertion sort will sort elements from starting of the array. This program will sort the elements from end of the array.

/*Insertion Sort*/

#include<stdio.h>
void insertion(int A[], int n);
void print_array(int A[],int n);
main()
{
    int arr[]={7,6,5,4,2,3,1,8,10,9}; // Input Array

    int size = (int)(sizeof(arr)/sizeof(arr[0])); //Calculate size of array

    int itr ; // Iterator

    insertion(arr,size); // Insertion function

    print_array(arr,size);
}

void print_array(int A[], int n)
{
    int itr;

    // Printing array after sorting
    for(itr=0;itr<n;itr++)
    printf("%d ",A[itr]);
}

void insertion(int A[], int n)
{
    int i , j , key;
    for(j=n-1;j>=0;j--)
    {
        key=A[j];
        i=j+1;
        while((i<=n)&&(A[i]<key))
        {
            A[i-1]=A[i];
            i=i+1;
        }
        A[i-1]=key;
    }
}

Insertion Sort (orginal)

 

/*Insertion Sort*/

#include<stdio.h>
void insertion(int A[], int n);
main()
{
    int arr[]={7,6,5,4,2,3,1,8,10,9}; // Input Array

    int size = (int)(sizeof(arr)/sizeof(arr[0])); //Calculate size of array

    int itr ; // Iterator

    insertion(arr,size); // Insertion function

    // Printing array after sorting
    for(itr=0;itr<size;itr++)
    printf("%d ",arr[itr]);
}

void insertion(int A[], int n)
{
    int i , j , key;
    for(j=1;j<n;j++)
    {
        key=A[j];
        i=j-1;
        while((i>=0)&&(A[i]>key))
        {
            A[i+1]=A[i];
            i=i-1;
        }
        A[i+1]=key;
    }
}

Output:

1 2 3 4 5 6 7 8 9 10

 

Time Complexity: O(n^2)

GroupOn Telephonic Interview Questions

 

Questions will be simple. But, working code is MUST. Telephonic Interview over Skype. Writing code is mandatory.

Questions are

1. Program to print the elements in a tree vertically
2. Given an input tree. Program to create a new tree which is the mirror of an input tree.
3. Root to leaf path which is having the given sum
4. Given the output of runlength encoding. Construct the array
5. Array implementation of stack & queues
6. N-stacks implement in an single array.

IBM ISL Interview

 

This interview is for AIX testing position.

Round – 1 was around 2 hours. it includes C, datastructures, OS , multithreading , Linux, Shell.

1. Difference between process & threads
2. How the following system calls will work: fork , read, open , write.
3. Difference between open & fopen.
4. A program that creates a thread.
5. A program with multi thread
6. A program with  the implementation of thread join & synchronization.

OS concepts & linux
7. Fragmentation & types
8. Paging & type  of allocation
9. Scheduling
10. Process memory layout
11. Process states
12. Difference between zombie & orphan process
13. How to find zombie & orphan process in linux using commands.
14. uses of chown , chmod, df , free, top, /proc & some other linux admin commands.
15. question s in sed , awk , grep
16. pipe & examples
17. writing simple shell scripting programs

C programs
18. Program to reverse a string (with & without recursion)
19. Program to reverse a linked list
20. Program to add two numbers (in linked list)
21. program to sort the linked list (own logic)
22. function call by value, call by reference
23. program to swap bytes in an integer
24. questions in padding
25. questions in pointers

26. what is meant by system testing
27. what all testing i have done in previous experience

Round –2 : it was around half an hour. it consists of unix & shell questions.

1. System programming questions like, using a system call in a program
2. writing makefiles
3. shell script program;
Input: hello
Output: h  e  l l  0
4. some other simple shell script programs & some command functionalities in linux

Round – 3 : It was around half an hour. It is a HR + Manager round

1. some questions about testing
2. why leaving the old company
3. why IBM ISL
4. Other general HQ questions