Array Gate Questions

Introduction

As we all know, an array is one of the most powerful and frequently used Data Structures in programming languages. An array is a data structure that can store similar kinds of data. It helps the programmer store operations like insertion and deletion searching quickly.

Ex:

Questions 

1. An array arr consists of n integers in locations indexing from 0 to n-1. The task is to shift the elements of an array cyclically to the left by t places, where (1 <= t <= (n-1)). An incomplete code is given below. Complete the algorithm.
    

min = n; i = 0;
while (___________) { 
    temp = arr[i]; j = i;
    while (________) {
    A[j] = ________ 
    j= (j + t) mod n ;
    If ( j < min ) then
        min = j;
}
arr[(n + i -- t) mod n] = _________
i = __________

1. i < min; j != (n+i-t)mod n; arr[( j + t ) mod n]; temp; i + 1;
2. i > min; j != (n+i+t)mod n; arr[( j + t )]; temp; i + 1;
3. i < min; j != (n+i)mod n; arr[ j + t ]; temp; i + 1;
4. i > min; j != (n+i)mod n; arr[ j + t ]; temp; i + 1 ;
    

Solution: a. i < min; j != (n+i-t)mod n; arr[( j + t ) mod n]; temp; i + 1;
For the last two blanks, the answer will be temp and i+1 because it is the same in all the options. Blank first will check all cases inside the while loop, so " i<min " So a) and c) could be a possible option, but c) option will go out of "while loop," so option a) is correct.
 

2. A program X reads about 500 integral values in the range from 0 to 100, representing the marks of 500 students. Now it has to print the frequency of each mark above 50. What would be the best size of an array for X to store the frequencies?

1. An array of size 50
2. An array of size 100
3. An array of size 500
4. A dynamically allocated array of 550 
    

Solution: a. Array of size 50. 
We have to store frequencies from 51 to 100, so 50 sizes are required.
 

3. Which operations can not be done in O(1) for an array of sorted data.

1. Print the nth largest element
2. Print the nth smallest element
3. Delete element
4. None of the above
    

Solution: c. Delete element.
If we have to delete x and its index is last, it would take O(n).
 

4. Find the return value of function Myx in C programming if the size is the number of elements in array E.

int MyX(int *E, unsigned int size){
 int Y = 0;
 int Z;
 int i,j,k;
 for(i = 0; i < size; i++)
      Y = Y + E[i];
 for(i = 0; i < size; i++)
  for(j = i; j < size; j++){
    Z = 0;
    for(k = i; k <= j; k++)
        Z = Z + E[k];
    if(Z > Y)
        Y = X;
  }
  return Y;
}

1. For any sub-array maximum possible sum of elements
2. Maxime number of an array
3. The smallest number of any sub-array
4. Sum of all elements of an array
    

Solution: a. For any sub-array maximum possible sum of elements.

For any sub-array maximum possible sum of elements.
 

5. Minimum comparison is required to determine whether an integer appears more than n / 2 times in the sorted array of n integers.

1. O(n)
2. O(logn)
3. O(nlogn)
4. O(1)
    

Solution: b. O(logn )

The best way to find is to sort an Array by binary search approach.

The first and last occurrence can be found out in (O(log(n)) time by using the divide and conquer rule.

Total number of occurrence would be counted as (O(log(n))+(O(log(n))+1=O(logn)

 

6. Find the output. Consider the below program and assume S to be a square matrix of nxn.

C = 100
for i = 1 to n do
    for j = 1 to n do
    {
        Temp = S[i][j] + C
        S[i][j] = S[j][i]
        S[j][i] = Temp - C
    } 
for i = 1 to n do
    for j = 1 to n do
        Output(S[i][j]);

1. Matrix S itself
2. Transpose of matrix S
3. Inverse of matrix S
4. None of the above
    

Solution: a. Matrix S itself. 

Go through the algorithm by taking a sample example.
 

7. The algorithm performs (logN)^1/2 find function, (logN)^1/2 delete operation, N inserts process, and (logN)^1/2 decrease key operation in a set of data items with a number drawn in a linearly ordered set. For the delete operation, a pointer assigned to the record must be deleted. The pointer is given a record with its decrease key for the decrease-key function for the decrease-key operation. The best-suited data structure that can be used for the following algorithm if the goal is to find the best asymptotic complexity when considering all activities is?

1. Min-heap
2. Sorted Doubly Linked List
3. Sorted array
4. Unsorted array
    

Solution: d. Unsorted array. 

The time complexity of the unsorted Array is O(1). So here, we would directly insert the number at the end.
 

8. An array consists of –ve and +ve numbers. What would be the complexity of the worst time algorithm to segregate the numbers with precisely the same sign altogether ( all +ve on one side and then all -ve on the other )?

1. O(n)
2. O(logn)
3. O(nlogn)
4. O(1)
    

Solution: a. O(n)

We can use the partition algorithm (quicksort) for segregation, and time complexity will be O(N).
 

9. Let X be an array of form 1 to n different numbers. If X[i] > X[j] and i < j , then the pair (i, j) is called an inversion of X. In the permutation of n elements, the numbers of inversions are:-

1. n(n-1)/2
2. 2n[logn]
3. n(n-1)/4
4. n(n+1)/4 
    

Solution: c. n(n-1)/4

n(n-1)/2 pairs are like i<j. So inversion would be n(n-1)/4.

 

10. The output of the C program:-

int main () {
    int arr [4] [5] = {
{1, 2, 3, 4, 5},
                              {6, 7, 8, 9, 10},
                              {11, 12, 13, 14, 15},
                              {16, 17, 18, 19, 20}
};
    printf ("%d\n", *(*(a+**a+2) +3));
    return (0);
}

1. 18
2. 19
3. 20
4. 21
    

Solution: b. 19

Go through the algorithm by taking a sample example.
 

11. A three-dimensional array in C language’ is declared as int arr[x][y][z]. Consider those array elements are stored such that it is row-major order and indexing start from 0. Find the formula for computing the address of an item of location arr[p][q][r]. (take 'w' like the word length of an integer):

1. &arr[0][0][0] + w (y * z * q + z * p + r)
2. &arr[0][0][0] + w (y * z * p + z * q + r)
3. &arr[0][0][0] + w (x * y * p + z * q + r)
4. &arr[0][0][0] + w (x * y * q + z * p + r)
    

Solution: b. &arr[0][0][0] + w (y * z * p + z * q + r)

To calculate the address, find the total number of elements before it and multiply the count with w.

 

12. The correct way to declare an array is?

1. int ninja[20];
2. int ninja;
3. ninja{20};
4. array ninja[20];
    

Solution: a. int ninja[20];

An array is declared as int ninja[20];
 

13. Let a two-dimensional array arr[20][10] with four words per memory cell. Let the base address of array arr be 100; elements are stored in row-major order, and the first element is arr[0][0]. Find the address of arr[11][5]?

1. 570
2. 580
3. 460
4. 560
    

Solution: d. 560

Similarly, find the number of elements before arr[11][15] and multiply it by 4.

Must Read Algorithm Types