Explore topic-wise InterviewSolutions in .

A[35][15] => rows R=35, columns C=15

Let base address be B

Given element width W=4 bytes and A[2][2]=3000

In Row major,

 A[I][J]=B+W(C(I=lr)+(j-lc))

where lr=lowest row and lc=lowest column

A[2][2]=B+W(C(2-0)+(2-0))

3000=B+4(15(2)+2) 

3000=B+128

Base Address B=3000-128=2872

Using same formula

 A[20][5]=2872+4(15(20-0)+(5-0))

= 2872+1220

= 4092

Arr[15][35]

No. of Rows(i.e., R) = 15

No. of Cols(i.e., C) = 35

Element size(W) = 8 bytes 

Arr[I][J] = Arr[2][5] => I=2, J=5

Address of Arr[5][10] = 4000

Base Address (B) =? 

Lowest Row (i.e., lr) = 0

Lowest Col (i.e., lc) = 0

Formula to calculate address in Column Major arrangement is: 

Arr[P][Q] = B + W[(P - lr ) + R(Q - lc )] 

Arr[5][10] = B + 8((5 – 0) + 15(10 – 0)) 

4000 = B + 8(155) 

4000 = B + 1240 

=> B = 4000-1240= 2760

Parallely, Arr[I][J] = B + W[(I - lr ) + R(J - lc )] 

Arr[2][5] = 2760 + 8[(2 – 0) + 15(5 – 0)]

= 2760 + (8 x 77)

= 2760 + 616

= 3376

For applying binary search algorithm the array, to be scanned, must be sorted in any order (ascending or descending).

Algorithm:

1. Set beg=0,last=12

2. REPEAT steps 3 through 6 UNTIL beg>last //INT() is used to extract integer part

3. mid=INT((beg+last)/2)

4. if A[mid]==ITEM then

{

print "Search Successful" 

print ITEM,"fount at",mid 

break          /* go out of the loop*/

} 

5. if A[mid]ITEM then

last=mid-1 /* END of repeat */ 

7. if beg!=last

print "Unsuccessful Search" 

8. END

Intermediate Results:

(i) Search for 66.

Step 1: beg=1; last=13; mid=INT(1+13)/2=7

Step 2: A[mid] i.e., A[7] is 45 45<66 then

beg=mid+1 i.e., beg=7+1=8

Step 3: mid=Int((beg+last)/2)=INT((8+13)/2)=10 

A[10] i.e., 89>66 then last = mid-1=10-1=9

Step 4: mid=((8+9)/2)=8 

A[8] is 71 71>66 than last = mid-1=8-1=7

Step 5: mid=((8+7)/2)=7 

A[7] is 45 45 < 66 then beg = mid+1=7+1=8 

Step 6: mid=((8+8)/2)=8 (beg=last=8)

 A[8] is 71 => 71!=66 

“Search Unsuccessful!!!”

(ii) Search for 71. 

Step 1: beg=1; last=13; mid=INT(1+13)/2=7

Step 2: A[mid] i.e., A[7] is

45 45<71 then

beg=mid+1 i.e., beg=7+1=8 

Step 3:

mid=Int((beg+last)/2)=INT((8+13)/2)=10 

A[10] i.e., 89>71 then last = mid-1=10-1=9

Step 4: mid=((8+9)/2)=8 

A[8] is 71 71=>71 

“Search Successful!!!”

Program: 

#include<iostream.h>

int Bsearch(int [],int); 

int main()

{ int A[]={3,4,7,11,18,29,45,71,87,89,93,96,99};

int index; 

index=Bsearch(A,71); 

if(index==-1)

cout<<"Element not found.."; 

else

 cout<<"Element found at

index:"<A[mid]) beg=mid+1; else last=mid-1;   } 

rerurn -1;

 }

int Bsearch(int A[],int item) 

{ int beg,last,mid; 

beg=0; last=13-1; 

while(beg<=last) 

{ mid=(beg+last)/2; 

if(item==A[mid]) return mid;

else if (item>A[mid]) beg=mid+1;

else last=mid-1;

}

rerurn -1;

}

#include <iostream.h>

void Merge(int X[],int M,int Y[],int N,int Z[]);

int main()

{ int X[50],Y[50],Z[50],MN=0,M,N;

cout<<"How many elements do U want to create first array with? ";

cin>>M;

cout<<"Enter First Array's elements [descending]..."; for(int i=0;i>X[i];

cout<<"How many elements do U want to create second array with? ";

cin>>N; MN=M+N;

cout<<"Enter Second Array's elements [descending]..."; 

for(int i=0;i>Y[i];

Merge(X,M,Y,N,Z);

cout<<"The merged array is....";

for(i=0;i<MN;i++)

cout<<Y[i]<<" ";

cout<<end1;

return 0;

}

void Merge(int X[],int M,int Y[],int N,int Z[])

{ int x,y,z;

for(x=-1,y=-1,z=-1;x>=0&&y>=0;)

{  if(X[x]<=Y[y]) Z[z--]=X[x--];

else Z[z--]=Y[y--];

}

if(x<0)

{  while(x>=0)

Z[z--]=X[x--];

}

else

{

while(y>=0)

Z[z--]=Y[y--];

}

}

#include<iostream.h>

void Merge(int A[],int M,int B[],int N,int C[]);

int mai()

{ int A[50],B[50],C[50],MN=0,M,N;

cout<<"How many elements do U want to create first array with? ";

cin>>M;

cout<<"Enter First Array's elements [ascending]...";

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

cin>>A[i];

cout<<"How many elements do U want to create second array with? ";

cin>>N;

MN=M+N;

cout<<"Enter Second Array's elements [descending]...";

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

cin>>B[i];

Merge(A,M,B,N,C);

cout<<"The merged array is....";

for(i=0;i<MN;i++)

cout<<C[i]<<" ";

cout<<endl;

return 0;

}

void Merge(int A[],int M,int B[],int N,int C[])

 { int a,b,c;

for(a=0,b=-1,c=0;a=0;)

{

if(A[a]<=B[b]) C[c++]=A[a++]

else C[c++]=B[b--];

}

if(a<M)

{ while(a<M)

C[c++]=A[a++];

}

else

{  while(b>=0)

 C[c++]=B[b--];

}

}

Assuming that L = 0 and U = m-1,n-1 and (m+n)-1 respectively for A, B, and C

1.  ctrA=m-1; ctrB=n-1; ctrC=0;

2.  while ctrA>=0 and ctrB>=0 perform steps 3 through 10

3.  {  If A[ctrA]<=B[ctrB] then

4.  {  C[ctrC]=A[ctrA]

5.  ctrC=ctrC+1

6.  ctrA=ctrA-1 } 

7.  else

8.  { C[ctrC]=B[ctrB]

9.  ctrC=ctrC+1

10.  ctrB=ctrB-1  }

}

11.  if ctrA<0 then

12.  {  while ctrB>=0 perform steps 13 through 15

{ 

13.  C[ctrC]=B[ctrB]

14.  ctrC=ctrC+1

15.  ctrB=ctrB-1

}

}

16. if ctrB<0 then

17.  { while ctrA>=0 perform steps 18 through 20

18.  {  C[ctrC]=A[ctrA]

19.  ctrC=ctrC+1

20.  ctrA=ctrA-1

}

}

void MERGE(int X[],int Y[],int n,int m)

{ int Z[20],i=0,j=0,k=0,l=m+n-1;

while(i<n&&k<20)

{ if(X[i]%2!=0)

{ Z[k]=X[i];

k++;

i++;

}

else

{ Z[l]=X[i];

l--;

i++;

}

}

while(j<m&&k<20)

{ if(Y[j]%2!=0)

{ Z[k]=Y[j];

k++;

j++;

}

else

{ Z[l]=Y[j];

l--;

j++;

}

}

cout<<"The elements of an array C is:";

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

cout<<"\n"<<Z[i];

}

Assuming that L=0 and U=6-1,5-1 and (6+5)-1 respectively for X, Y, and Z 

1. ctrX=6-1; ctrY=5-1; ctrZ=0; 

2. while ctrX>=0 and ctrY>=0 perform steps 3 through 10 

3. { If X[ctrX]<=Y[ctrY] then 

4. { Z[ctrZ]=X[ctrX] 

5. ctrZ=ctrZ+1 

6. ctrX=ctrX-1 } 

7. else

8. { Z[ctrZ]=Y[ctrY] 

9. ctrZ=ctrZ+1 

10. ctrY=ctrY-1 }

} 

11. if ctrX<0 then 

12. { while ctrY>=0 perform steps 13 through 15

{ 

13. Z[ctrZ]=Y[ctrY] 

14. ctrZ=ctrZ+1 

15. ctrY=ctrY-1 

} 

} 

16. if ctrY<0 then 

17. { while ctrX>=0 perform steps 18 through 20

18. { Z[ctrZ]=X[ctrX]

19. ctrZ=ctrZ+1 

20. ctrX=ctrX-1 

}

}

/* Read the two matrices */ 

1. for i=1 to 3 perform step 

2 through 4 2. { for j=1 to 3 perform step 3 through 4 

3. { Read A[i,j] 

4. Read B[i,j] 

}

} 

/* Calculate the sum of the two and store it in third matrix C */ 

5. for i=1 to 3 perform step 6 through 8

{

6. for j=1 to 3 perform step

7 through 8 7. { C[i,j]=0

8. C[i,j]=A[i,j]+B[i,j]

}

}

void RowSum(int A[5][6])

{ int SUMC[5];

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

{ SUMC[i]=0;

for(int j=0;j<6;j++)

SUMC[i]+=A[i][j];

cout<<"Sum of row"<<i+1<<"="<< SUMC[i]<<end1;

}

}

const int S=7; // or it may be 3 or 5

int DispMRowMCol(int Arr[S][S],int S)

{ int mid=S/2;

int i;

//Extracting middle row

cout<<"\n Middle Row:";

for(i=0;i<S;i++)

cout<<Arr[mid][i]<<" ";

//Extracting middle column

cout<<"\n Middle Column:";

for(i=0;i<S;i++)

cout<<Arr[i][mid]<<" ";

}

X[4][3]=B+W(C(I-1)+(J-1))

=1000+4(4(4-1)+(3-1))

=1000+4(4(3)+(2))

=1000+56

=1056

const int n=5;

void Diagonals(int A[n][n], int size)

{

int i,j;

cout<<"Diagonal One:";

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

cout<<A[i]ij]<<" ";

cout<<"\n Diagonal Two:"

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

cout<<A[i][n-(i+1)]<<" ";

}

Insertion sort:

Step-1 - ∞, 42, 29, 74, 11, 65, 58

Step-2 - ∞, 29, 42, 74, 11, 65, 58 

Step-2 - ∞, 29, 42, 11, 74, 65, 58

Step-4 - ∞, 29, 42, 11, 65, 74, 58

Step-5 - ∞, 29, 42, 11, 58, 65, 74

Step-6 - ∞, 11, 29, 42, 58, 65, 74

void Showhundred(int T[4][4])

{

for(int I = 0; I<4; I++)

{

for(int J = 0; J<4; J++)

{

if (T[I][J]%100 = = 0)

cout<<"Elemets which are divisible by 100 are:”

<<A[I][J]<<endl;

}

}

}

void SORTPOINTS(Game G[ ], int N)

{

Game Temp;

for (int I=0; I<N-1;I++)

for (int J=0;J<N-I-1;J++)

if (G[J].Points <G[J+1].Points)

{

Temp = G[J];

G[J] = G[J+1];

G[J+1] = Temp;

}

}

void SWAPCOL(int A[ ][100], int M, int N)

{

int Temp, I;

for (I=0;I<M;I++)

{

Temp = A[I][0];

A[I][0] = A[I][N-1];

A[I][N-1] = Temp;

}

}

int DSUM(int A[],int N)

{ int i,dsum1=0,dsum2=0;

for(i=0;i<N;i++)

{ dsum1+=A[i][i];

dsum2+=A[N-(i+1)][i];

}

return(dsum1+dsum2-A[N/2][N/2]);

//because middle element is added twice

}

/* Read the two matrices */ 

1. for i=1 to 4 perform step 2 through 4 

2. { for j=1 to 4 perform step 3 through 4 

3. { Read A[i,j] 

4. Read B[i,j] 

} 

} 

/* Calculate the sum of the two and store it in third matrix C */

5. for i=1 to 4 perform step 6 through 8

{

6. for j=1 to 4 perform step 7 through 8 

7. { C[i,j]=0

8. C[i,j]=A[i,j]-B[i,j]

}

 }

float diagonalSum(float MATRIX[6][6], int r, int c)

{

int i,j;

float sum=0;

//We are calculating sum of diagonal elements considering both diagonals

//We are adding intersecting element on two diagonal twice

for(i=0;i<r;i++)

{

for(j=0;j<c;j++)

{

if(i==j) //elements on first diagonal

sum+= MATRIX [i][j];

if((i+j)==(r-1)) // elements on off-diagonal

sum+= MATRIX [i][j];

}

}

return sum;

}

Students I am giving you the program for printing Non Diagonal elements of a matrix X[4x4], try to convert this code into algorithm.

#include<conio.h>

#include<iostream.h>

void accept(int a[4][4],int size)

{

cout<<"Diagonal One:";

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

for(int j=0;j<size;j++)

if (i != j && i != size-j-1)

cout<<a[i][j];

}

void main()

{

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

};

clrscr();

accept(a,4); 

getch();

}

A[5][4] => rows R=5, columns C=4

Let base address be B

Given element width W=1 bytes and A[1][1]=2000

In Row major,

A[I][J]=B+W(C(I=lr)+(j-lc))

where lr=lowest row and lc=lowest column 

A[1][1]=B+W(C(1-0)+(1-0))

2000=B+1(4(1)+1)

2000=B+5

Base Address B=2000-5=1995

Using same formula

 A[4][4]=1995+1(4(4-0)+(4-0)) 

=1995+20

=2015

1. ctr=pos

2. Repeat steps 3 and 4 until ctr<=1

3.  A[ctr]=A[ctr-1]

4.  ctr=ctr-1

/* End of Repeat*/

5. Display the new list of element 

6. End

The data structures are named group of data of some data types.

The data structures can be classified into following two types: 

1. Simple Data Structure: These data structure are normally built from primitive data types like integers, reals, characters, boolean. Simple data structure can be classified into following two categories:

(a) Array: Arrays refer to a named list of a finite number n of similar data elements. For example, int ARR[10]; Above array ARR have 10 elements, each elements will be referenced as Arr[0], ARR[1]………….ARR[9].

(b) Structure: Structure refers to a named collection of variables of different data types. For example, a structure named as STUD contais (Rno, Name, Mark), then individual fields will be referenced as STUD.fieldname such as, STUD.Rno, STUD.Name etc. 

2. Compound Data Structure: Simple data structure can be combine in various waus to form more complex structures called compound data structures which are classified into following two categories:

(a) Linear data structure: These data structures are a single level data structures representing linear relationship among data. Following are the types of linear data structure:

(i) Stacks: Stack is a LIFO (Last In First Out) list. For example, stack of plates on counter, as that plates are inserted or removed only from the top of the stack.

(ii) Queue: Queue is a FIFO (First In First Out) list. For example, line of people waiting for their turn to vote.

(iii) Linked List: Linked lists are special lists of some data elements liked to one another. For example, peoples seating in a cinema hall where each seat is connected to other seat.

(b) Non-Linear data structure: These data structures are multilevel data structure representing hierarchical relationship among data. For example, relationship of child, parent and grandparent.

Base Address B

No of rows m=30

Element size W=8

Lowest Row and column indices lr, lc=0 

Address of Ith, jth element of array in column major order is: 

Address of MAT[I][J] = B + W(m(J - lc) + (I - lr))

MAT[5][7] = 1000

1000 = B + 8(30(7-0)+(5-0)) 

1000 = B + 8(30(7)+(5)) 

1000 = B + 8(210 + 5) 

1000 = B + 8(215) 1000 = B + 1720

B = 1000 – 1720

B = -720

Base address is -720

Now address of MAT[20][5] is computed as:

MAT[20][5] = -720 + 8(30(5 – 0) + (20 – 0))

= -720 + 8(30(5) + (20))

= -720 + 8(150 + 20)

= -720 + 8(170)

= -720 + 1360

= 640

T[50][20]

No. of Rows(i.e., R) = 50

No. of Cols(i.e., C) = 20

Element size(W) = 4 bytes

T[I][J] = T[30][15] => I=30, J=15

Address of T[25][10] = 9800

Base Address (B) =?

Lowest Row (i.e., lr) = 0

Lowest Col (i.e., lc) = 0

Formula to calculate address in Column Major arrangement is:

T[P][Q] = B + W[(P - l_r) + R(Q - l_c )] 

T[25][10] = B + 4((25 – 0) + 50(10 – 0))

9800 = B + 4(525) (∵ T[25][10] = 9800 given)

9800 = B + 2100

=> B = 9800 – 2100 

= 7700 Parallely, T[I][J] = B + W[(I - lr ) + R(J - lc )] 

T[30][15] = 7700 + 4[(30 – 0) + 50(15 – 0)] 

= 7700 + (4 x 780) 

= 7700 + 3120

= 10820

void SWAPARR (int A[100][], int M, int N)

{

int Temp, I;

for (I=0;I<M;I++)

{

Temp = A[0][I];

A[0][I] = A[N-1][I];

A[N-1][I] = Temp;

}

}

int bsearch(float P[10],int DATA,int N)

{ int beg=0,last=N-1,mid;

while(beg<=last)

{ mid=(beg+last)/2;

if(P[mid]==DATA) return 1; //element is present in array 

else if(DATA>P[mid]) beg=mid+1;

else last=mid-1;

}

return 0;  //element is absent in array

}

void ElementSwap(int A[],int size)

{ int lim,tmp;

if(size%2!=0)  //if array has odd no. of element

lim = size-1;

else

lim = size;

for(int i=0;i<lim;i+=2)

{  tmp = A[i];

A[i] = A[i+1];

A[i+1]=tmp;

}

}

void COLSUM(int R[7][7])

{int SUMC;

for (int j=0;j<7;j++)

{

SUMC=0;

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

SUMC=SUMC + R[i][j];

Cout<< "Sum of Column "<<j<<" = "<<SUMC ;

}

}

void REASSIGN (int Arr[ ], int Size)

{

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

if (Arr[i]%5==0)

Arr[i]/=5;

else

Arr[i]*=2;

}

void RearrangeArray(int A[],int size)

{

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

{ if(A[i]%2==0)

A[i]*=2;

else

A[i]*=3;

}

}

void RowProduct(int A[4][3],int R,int C)

{ int Prod[R];

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

{ Prod[i]=1;

for(int j=0;j<c;j++)

Prod[i]*=A[i][j];

cout<<"Product of row"<<i+1<<"="<<Prod[i]<<endl;

}

}

void ColProd(int A[4][3],int r,int c)

{ int Prod[C],i,j;

for(j=0;j<c;j++)

{ Prod[j]=1;

for(i=0;i<r;i++)

Prod[j]*=A[i][j];

cout<<"Product of Column" <<j+1<<"="<<Prod[j]<<end1;

}

}