Category: Data Structures & Algorithms Objective Questions

Data Structure Problems on “Maximum Sum Rectangle in a 2D Matrix”.

1. Given a 2D matrix, find a submatrix that has the maximum sum. Which of the following methods can be used to solve this problem?
a) Brute force
b) Recursion
c) Dynamic programming
d) Brute force, Recursion, Dynamic programming
View Answer

Answer: d
Clarification: Brute force, Recursion and Dynamic programming can be used to find the submatrix that has the maximum sum.

2. In which of the following cases, the maximum sum rectangle is the 2D matrix itself?
a) When all the elements are negative
b) When all the elements are positive
c) When some elements are positive and some negative
d) When diagonal elements are positive and rest are negative

Answer: a
Clarification: When all the elements of a matrix are positive, the maximum sum rectangle is the 2D matrix itself.

3. Consider the following statements and select which of the following statement are true.
Statement 1: The maximum sum rectangle can be 1X1 matrix containing the largest element If the matrix size is 1X1
Statement 2: The maximum sum rectangle can be 1X1 matrix containing the largest element If all the elements are zero
Statement 3: The maximum sum rectangle can be 1X1 matrix containing the largest element If all the elements are negative
a) Only statement 1 is correct
b) Only statement 1 and Statement 2 are correct
c) Only statement 1 and Statement 3 are correct
d) Statement 1, Statement 2 and Statement 3 are correct

Answer: d
Clarification: If the matrix size is 1×1 then the element itself is the maximum sum of that 1×1 matrix. If all elements are zero, then the sum of any submatrix of the given matrix is zero. If all elements are negative, then the maximum element in that matrix is the highest sum in that matrix which is again 1X1 submatrix of the given matrix. Hence all three statements are correct.

4. Consider a matrix in which all the elements are non-zero(at least one positive and at least one negative element). In this case, the sum of the elements of the maximum sum rectangle cannot be zero.
a) True
b) False

Answer: a
Clarification: If a matrix contains all non-zero elements with at least one positive and at least on negative element, then the sum of elements of the maximum sum rectangle cannot be zero.

5. Consider the 2×3 matrix {{1,2,3},{1,2,3}}. What is the sum of elements of the maximum sum rectangle?
a) 3
b) 6
c) 12
d) 18
Answer: c
Clarification: Since all the elements of the 2×3 matrix are positive, the maximum sum rectangle is the matrix itself and the sum of elements is 12.

6. Consider the 2×2 matrix {{-1,-2},{-3,-4}}. What is the sum of elements of the maximum sum rectangle?
a) 0
b) -1
c) -7
d) -12
View Answer

Answer: b
Clarification: Since all the elements of the 2×2 matrix are negative, the maximum sum rectangle is {-1}, a 1×1 matrix containing the largest element. The sum of elements of the maximum sum rectangle is -1.

7. Consider the 3×3 matrix {{2,1,-3},{6,3,4},{-2,3,0}}. What is the sum of the elements of the maximum sum rectangle?
a) 13
b) 16
c) 14
d) 19

Answer: c
Clarification: The complete matrix represents the maximum sum rectangle and it’s sum is 14.

8. What is the time complexity of the brute force implementation of the maximum sum rectangle problem?
a) O(n)
b) O(n²)
c) O(n³)
d) O(n⁴)
View Answer

Answer: d
Clarification: The time complexity of the brute force implementation of the maximum sum rectangle problem is O(n⁴).

9. The dynamic programming implementation of the maximum sum rectangle problem uses which of the following algorithm?
a) Hirschberg’s algorithm
b) Needleman-Wunsch algorithm
c) Kadane’s algorithm
d) Wagner Fischer algorithm

Answer: c
Clarification: The dynamic programming implementation of the maximum sum rectangle problem uses Kadane’s algorithm.

10. Consider the following code snippet:

int max_sum_rectangle(int arr[][3],int row,int col)
{
      int left, right, tmp[row], mx_sm = INT_MIN, idx, val;
      for(left = 0; left < col; left++)
      {
           for(right = left; right < col; right++)
           {
               if(right == left)
               {
                   for(idx = 0; idx < row; idx++)
                     tmp[idx] = arr[idx][right];
               }
               else
               {
                   for(idx = 0; idx < row; idx++)
                      tmp[idx] += arr[idx][right];
               }
               val = kadane_algo(tmp,row);
               if(val > mx_sm)
                  ______;
           }
      }
      return mx_sm;
}

Which of the following lines should be inserted to complete the above code?
a) val = mx_sm
b) return val
c) mx_sm = val
d) return mx_sm

Answer: c
Clarification: The line “mx_sm = val” should be inserted to complete the above code.

11. What is the time complexity of the following dynamic programming implementation of the maximum sum rectangle problem?

int max_sum_rectangle(int arr[][3],int row,int col)
{
      int left, right, tmp[row], mx_sm = INT_MIN, idx, val;
      for(left = 0; left < col; left++)
      {
           for(right = left; right < col; right++)
           {
               if(right == left)
               {
                   for(idx = 0; idx < row; idx++)
                     tmp[idx] = arr[idx][right];
               }
               else
               {
                   for(idx = 0; idx < row; idx++)
                      tmp[idx] += arr[idx][right];
               }
               val = kadane_algo(tmp,row);
               if(val > mx_sm)
                 mx_sm = val;
           }
      }
      return mx_sm;
}

a) O(row*col)
b) O(row)
c) O(col)
d) O(row*col*col)

Answer: d
Clarification: The time complexity of the above dynamic programming implementation of the maximum sum rectangle is O(row*col*col).

12. What is the space complexity of the following dynamic programming implementation of the maximum sum rectangle problem?

int max_sum_rectangle(int arr[][3],int row,int col)
{
      int left, right, tmp[row], mx_sm = INT_MIN, idx, val;
      for(left = 0; left < col; left++)
      {
           for(right = left; right < col; right++)
           {
               if(right == left)
               {
                   for(idx = 0; idx < row; idx++)
                     tmp[idx] = arr[idx][right];
               }
               else
               {
                   for(idx = 0; idx < row; idx++)
                      tmp[idx] += arr[idx][right];
               }
               val = kadane_algo(tmp,row);
               if(val > mx_sm)
                 mx_sm = val;
           }
      }
      return mx_sm;
}

a) O(row*col)
b) O(row)
c) O(col)
d) O(row*col*col)

Answer: b
Clarification: The space complexity of the above dynamic programming implementation of the maximum sum rectangle problem is O(row).

13. What is the output of the following code?

#include
#include
int max_num(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int kadane_algo(int *arr, int len)
{
      int ans, sum, idx;
      ans =0;
      sum =0;
      for(idx =0; idx < len; idx++)
      {
          sum = max_num(0,sum + arr[idx]);
          ans = max_num(sum,ans);
      }
      return ans;
}
int max_sum_rectangle(int arr[][5],int row,int col)
{
      int left, right, tmp[row], mx_sm = INT_MIN, idx, val;
      for(left = 0; left < col; left++)
      {
           for(right = left; right < col; right++)
           {
                if(right == left)
                {
                    for(idx = 0; idx < row; idx++)
                     tmp[idx] = arr[idx][right];
                }
                else
                {
                     for(idx = 0; idx < row; idx++)
                       tmp[idx] += arr[idx][right];
                }
                val = kadane_algo(tmp,row);
                if(val > mx_sm)
                mx_sm = val;
           }
      }  
      return mx_sm;
}
int main()
{
       int arr[2][5] ={{1, 2, -1, -4, -20}, {-4, -1, 1, 7, -6}};
       int row = 2, col = 5;
       int ans = max_sum_rectangle(arr,row,col);
       printf("%d",ans);
       return 0;
}

a) 7
b) 8
c) 9
d) 10

Answer: b
Clarification: The program prints the sum of elements of the maximum sum rectangle, which is 8.

14. What is the output of the following code?

#include
#include
int max_num(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int kadane_algo(int *arr, int len)
{
      int ans, sum, idx;
      ans =0;
      sum =0;
      for(idx =0; idx < len; idx++)
      {
          sum = max_num(0,sum + arr[idx]);
          ans = max_num(sum,ans);
      }
      return ans;
}
int max_sum_rectangle(int arr[][5],int row,int col)
{
      int left, right, tmp[row], mx_sm = INT_MIN, idx, val=0;
      for(left = 0; left < col; left++)
      {
           for(right = left; right < col; right++)
           {
               if(right == left)
               {
                   for(idx = 0; idx < row; idx++)
                      tmp[idx] = arr[idx][right];
               }
               else
               {
                   for(idx = 0; idx < row; idx++)
                      tmp[idx] += arr[idx][right];
               }
               val = kadane_algo(tmp,row);
               if(val > mx_sm)
               mx_sm = val;
           }
      }
      return mx_sm;
}
int main()
{
      int arr[4][5] ={{ 7,  1, -3, -6, -15},
                    { 10,  -6,  3,  -4,  11},
                    { -2, -3, -1,  2, -5},
                    { 3,  0,  1,  0,  3}};
      int row = 4, col = 5;
      int ans = max_sum_rectangle(arr,row,col);
      printf("%d",ans);
      return 0;
}

a) 17
b) 18
c) 19
d) 20

Answer: b
Clarification: The program prints the sum of elements of the maximum sum rectangle, which is 18.

Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) on “Route Cipher”.

1. What is route cipher?
a) a transposition cipher that performs encryption by following an imaginary pattern on a grid
b) a substitution cipher that performs encryption by following an imaginary pattern on a grid
c) a transposition cipher that performs encryption by following a zig zag pattern on a grid
d) a substitution cipher that performs encryption by following a zig zag pattern on a grid

Answer: a
Clarification: Route cipher is a transposition cipher. It encrypts the plain text by following an imaginary pattern on a grid. This pattern can vary from one version of route cipher to others.

2. Route cipher is an example of ____________
a) mono-alphabetic cipher
b) poly-alphabetic cipher
c) transposition cipher
d) additive cipher

Answer: c
Clarification: Route cipher is a transposition cipher. It falls under the category of transposition cipher as it encrypts the plain text by rearranging its letters.

3. Encryption in Route cipher is done ___________
a) by arranging the letters in a zig zag fashion in a table
b) by randomly arranging letters
c) by following an imaginary pattern drawn on a grid
d) by swapping adjacent letters
Answer: c
Clarification: Route cipher is a transposition cipher. It encrypts the plain text by following an imaginary pattern on a grid.

4. Which of the following ciphers are created by shuffling the letters of a word?
a) playfair cipher
b) route cipher
c) vigenere cipher
d) hill cipher
Answer: b
Clarification: In transposition cipher the letters of the given data are shuffled in a particular order, fixed by a given rule. Route cipher is the only transposition cipher out of the given options.

5. Route cipher is closely related to?
a) Autokey cipher
b) Hill cipher
c) Rail fence cipher
d) Columnar transposition cipher
Answer: c
Clarification: Route cipher is closely related to rail fence cipher. In rail fence cipher the plain text is written in a zig zag fashion in a grid whereas in route cipher the plain text is written horizontally.

6. Rail fence cipher is more secure as compared to route cipher?
a) true
b) false
Answer: b
Clarification: Rail fence is cipher is less secure than route cipher. It is because the key of route cipher not only defines the size of the grid but also the path that is to be followed.

7. Router cipher becomes less secure when we have to encrypt longer messages.
a) true
b) false
Answer: b
Clarification: The key of route cipher not only defines the size of grid but also the path that is to be followed. So longer the message is, the harder it becomes to guess the path.

8. What will be the plain text corresponding to cipher text “RSEADC” if with the number of columns are given to be 3 and route of reading is down the columns?
a) SACRED
b) DERSAC
c) REDSAC
d) SEDRAC

9. What will be the plain text corresponding to cipher text “SFNUFACT” if with number of columns are given to be 3 and route of reading is from the bottom right anti clockwise?
a) FACTSFUN
b) FACTFUNS
c) FUNSFACT
d) FUNFACTS

10. What will be the ciphered text if route cipher is used for encrypting the plain text “” with number of columns given to be 5 and route from the bottom right anti clockwise?
a) SUANNDFROY
b) SORAFUDYNN
c) YOFNASUNDRY
d)

11. What will be the ciphered text if route cipher is used for encrypting the plain text “” with a number of columns given to be 5 and route of reading is down the columns?
a) SUANNDFROY
b) SORAFUDYNN
c) SNAUDNORFY
d)

Data Structure Multiple Choice Questions on “Topological Sort”.

1. Topological sort can be applied to which of the following graphs?
a) Undirected Cyclic Graphs
b) Directed Cyclic Graphs
c) Undirected Acyclic Graphs
d) Directed Acyclic Graphs
Answer: d
Clarification: Every Directed Acyclic Graph has one or more topological ordering whereas Cyclic and Undirected graphs can’t be ordered topologically.

2. Most Efficient Time Complexity of Topological Sorting is? (V – number of vertices, E – number of edges)
a) O(V + E)
b) O(V)
c) O(E)
d) O(V*E)
Answer: a
Clarification: The topological sort algorithm has complexity same as Depth First Search. So, DFS has a complexity O(V+E).

3. In most of the cases, topological sort starts from a node which has __________
a) Maximum Degree
b) Minimum Degree
c) Any degree
d) Zero Degree
Answer: d
Clarification: Topological sort starts with a node which has zero degree. If multiple such nodes exists then it can start with any node.

4. Which of the following is not an application of topological sorting?
a) Finding prerequisite of a task
b) Finding Deadlock in an Operating System
c) Finding Cycle in a graph
d) Ordered Statistics

Answer: d
Clarification: Topological sort tells what task should be done before a task can be started. It also detects cycle in the graph which is why it is used in the Operating System to find the deadlock. Ordered statistics is an application of Heap sort.

5. Topological sort of a Directed Acyclic graph is?
a) Always unique
b) Always Not unique
c) Sometimes unique and sometimes not unique
d) Always unique if graph has even number of vertices

Answer: c
Clarification: The topological sort of a graph can be unique if we assume the graph as a single linked list and we can have multiple topological sort order if we consider a graph as a complete binary tree.

6. Topological sort can be implemented by?
a) Using Depth First Search
b) Using Breadth First Search
c) Using Depth and Breadth First Search
d) Using level ordered search

Answer: c
Clarification: We can implement topological sort by both BFS and DFS. In BFS, we use queue as data structure and in DFS, we use Linked list (if recursive) or Stack (if not recursive) as data structure.

7. Topological sort is equivalent to which of the traversals in trees?
a) Pre-order traversal
b) Post-order traversal
c) In-order traversal
d) Level-order traversal

Answer: a
Clarification: In pre-order traversal of trees, we process the root first and then child from left to right.

8. A man wants to go different places in the world. He has listed them down all. But there are some places where he wants to visit before some other places. What application of graph can he use to determine that?
a) Depth First Search
b) Breadth First Search
c) Topological Sorting
d) Dijkstra’s Shortest path algorithm
Answer: c
Clarification: As the definition of topological sorting suggests, it is the way to do tasks in prescribed order. So, if he does topological sorting, it will be easy for him to recognize what should be the order to visit different places.

9. When the topological sort of a graph is unique?
a) When there exists a hamiltonian path in the graph
b) In the presence of multiple nodes with indegree 0
c) In the presence of single node with indegree 0
d) In the presence of single node with outdegree 0
Answer: a
Clarification: A hamiltonian path exists in a Directed Acyclic Graph when all pairs of consecutive vertices are in sorted order and are connected by edges. In such a case, there exists a unique topological sorting order.

Data Structures & Algorithms Multiple Choice Questions on “Exponential Search”.

1. Exponential search algorithm requires which of the following condition to be true?
a) array should be sorted
b) array should have not be sorted
c) array should have a less than 128 elements
d) array should be partially sorted

Answer: a
Clarification: Exponential sort requires the input array to be sorted. The algorithm would fail to give the correct result if array is not sorted.

2. Which of the following searching algorithm is used with exponential sort after finding the appropriate range?
a) Linear search
b) Binary search
c) Jump search
d) Fibonacci Search

Answer: b
Clarification: In exponential search, we first find a range where the required elements should be present in the array. Then we apply binary search in this range.

3. Exponential search has ____________
a) neither an exponential space complexity nor exponential time complexity
b) exponential time complexity but a linear space complexity
c) exponential space complexity but a linear time complexity
d) both exponential time and space complexity

Answer: a
Clarification: Exponential search has neither an exponential space complexity nor exponential time complexity. It is named exponential search because it searches for an element in an exponential manner.

4. Choose the correct while loop statement from the following that finds the range where are the element being search is present (x is the element being searched in an array arr of size n)?
a)

while (i 
b) 
while (i 
c) 
while (arr[i] 
d) 
while (i 
Answer: a
Clarification: In exponential search we first find the range where the element being searched can be present before applying binary search. We do this by comparing the value of element under search with the array elements present at the positions 1,2,4,8….n. 

 
 


	
5. What is the time complexity of exponential sort?
a) O(n)
b) O(2n)
c) O(n log n)
d) O(log n)
Answer: d
Clarification: In exponential search, we first find a range where the required elements should be present in the array. Then we apply binary search in this range. This takes O(log n) time in the worst case.
6. What is the auxiliary space requirement of an exponential sort when used with iterative binary search?
a) O(n)
b) O(2n)
c) O(1)
d) O(log n)
Answer: c
Clarification: Exponential search does not require any auxiliary space for finding the element being searched. So it has a constant auxiliary space O(1).
7. What is the auxiliary space requirement of the exponential sort when used with recursive binary search?
a) O(n)
b) O(2n)
c) O(1)
d) O(log n)
Answer: d
Clarification: Exponential search requires an auxiliary space of log n when used with recursive binary search. This space is required for the recursion call stack space.
8. Which of the following searching algorithm is fastest?
a) jump search
b) exponential search
c) linear search
d) all are equally fast
Answer: b
Clarification: Exponential search has the least time complexity (equal to log n) out of the given searching algorithms. This makes exponential search preferable in most cases.
9. In which of the following case jump search will be preferred over exponential search?
a) jumping backwards takes significantly more time than jumping forward
b) jumping forward takes significantly more time than jumping backwards
c) when the given array is very large in size
d) when the given array is very small in size
Answer: a
Clarification: Jump search only needs to jump backwards once, while an exponential search can jump backwards up to log n times. Thus jump search will be preferred if jumping backwards is expensive.
10. Best case of the exponential search will have time complexity of?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
Answer: a
Clarification: Best case of the exponential search will be when the first element of the array is the element that is being searched. In this case, only one comparison will be required. Thus it will have a time complexity of O(1).
11. Which of the following code correctly represent exponential search?
a)


	

int expSearch(int arr[], int n, int x) 
{ 
	if (arr[0] == x) 
		return 0; 
	int i = 1; 
	while (i < n && arr[i] <= x) 
		i = i*2; 
 
return binarySearch(arr, i/2, min(i, n-1), x);
//applies binary search in the calculated range
}







b)







int expSearch(int arr[], int n, int x) 
{ 
	if (arr[0] == x) 
		return 0; 
	int i = 1; 
	while (i < n && arr[i] <= x) 
		i = i*2; 
	return binarySearch(arr, i, min(i, n-1), x);
//applies binary search in the calculated range
}







c)







int expSearch(int arr[], int n, int x) 
{ 
 
	if (arr[0] == x) 
		return 0; 
 
 
	int i = 1; 
	while (i < n && arr[i] <= x) 
		i = i/2; 
 
return binarySearch(arr, i/2, min(i, n-1), x);
//applies binary search in the calculated range
}







d)







int expSearch(int arr[], int n, int x) 
{ 
	if (arr[0] == x) 
		return 0; 
 
	int i = 1; 
	while (i < n && arr[i] <= x) 
		i = i*2; 
 
return binarySearch(arr, i/2, max(i, n-1), x); 
//applies binary search in the calculated range
}







Answer: a
Clarification: In exponential search we first find a range where the required element should be present in the array. Then we apply binary search in this range.
 
 
12. Jump search has a better time complexity than the exponential search.
a) True
b) False

Answer: b
Clarification: The worst case time complexity of jump search and exponential searches are O(n1/2) and O(log n) respectively. So exponential search is better in terms of time complexity.
13. Exponential search performs better than binary search when the element being searched is present near the starting point of the array.
a) True
b) False

Answer: a
Clarification: Exponential search first finds the range where binary search needs to be applied. So when the element is present near the starting point of the array then exponential search performs better than standard binary search.
14. Choose the incorrect statement about exponential search from the following.
a) Exponential search is an in place algorithm
b) Exponential search has a greater time complexity than binary search
c) Exponential search performs better than binary search when the element being searched is present near the starting point of the array
d) Jump search has a greater time complexity than an exponential search

Answer: b
Clarification: Time complexity of exponential search and binary search are the same. But exponential search performs better than binary search when the element being searched is present near the starting point of the array.
15. Which of the following is not an alternate name of exponential search?
a) Logarithmic search
b) Doubling search
c) Galloping search
d) Struzik search

Answer: a
Clarification: Logarithmic search is not an alternate name of the exponential search. Some alternate names of exponential search are Doubling search, Galloping search and Struzik search.
 and Answers.

Data Structures & Algorithms Multiple Choice Questions on “LSD Radix Sort”.

1. Which of the following is the distribution sort?
a) Heap sort
b) Smooth sort
c) Quick sort
d) LSD radix sort

Answer: d
Clarification: In Distribution sort the inputted values are distributed to multiple intermediate structures which are then combined and placed on the output. And LSD radix sort distributes values into buckets based on the digits within values, so it is a distribution sort.

2. What is the worst case time complexity of LSD radix sort?
a) O(nlogn)
b) O(wn)
c) O(n)
d) O(n + w)
Answer: b
Clarification: Time complexity of LSD radix sort depends upon the word size and the number on items. It runs in O(wn) time in worst case, where n is the number of inputted elements and w is the number of digits in the largest number.

3. LSD radix sort requires _____ passes to sort N elements.
a) (w/logR)
b) N(w/logR)
c) (w/log(RN))
d) (wN/log(N))

Answer: a
Clarification: LSD radix sort sorts the N elements in (w/logR) passes where w is the number of digits in largest number and R(radix) is extra space required for performing the sorting operation.

4. Which of the following is false?
a) LSD radix sort is an integer sorting algorithm
b) LSD radix sort is a comparison sorting algorithm
c) LSD radix sort is a distribution sort
d) LSD radix sort uses bucket sort

Answer: b
Clarification: LSD radix sort uses bucket sort for grouping the keys based on the digits at that value. And as it grouped the keys based on the digits at that values, it is integer sorting algorithm.

5. Which of the following sorting algorithm is stable?
a) Heap sort
b) Selection sort
c) In-place MSD radix sort
d) LSD radix sort
Answer: d
Clarification: In LSD radix sort after sorting the multiple elements with the same key will be in the same order as they were in the input array. So LSD radix sort is stable sort.

6. LSD radix sort is faster than comparison sorts.
a) True
b) False

Answer: b
Clarification: LSD radix sort is faster than comparison sorts when the word size is less than logn. But LSD radix sort runs slowly for elements with larger word size and smaller radix.

7. Which of the following should be used to sort a huge database on a fixed-length key field?
a) Insertion sort
b) Merge sort
c) LSD radix sort
d) Quick sort
Answer: c
Clarification: LSD radix requires only w passes to sort a fixed-length string, where w is a length of the strings. So, LSD radix sort is best suited to sort a huge database on a fixed-length key field.

8. Which of the following is a combination of LSD and MSD radix sorts?
a) Forward radix sort
b) 3-way radix quick sort
c) Trie base radix sort
d) Flash sort

Answer: a
Clarification: Forward radix sort combines the advantages of LSD and MSD radix sort. Forward radix sort inspects a complete horizontal strip at a time just like LSD radix sort.

9. Which of the following is true for the LSD radix sort?
a) works best for variable length strings
b) accesses memory randomly
c) inner loop has less instructions
d) sorts the keys in left-to-right order

Answer: b
Clarification: LSD radix sort sorts the keys in right-to-left order, working with Least Significant Digit first. The inner loop has a lot of instructions and LSD radix sort is used to sort fixed-length strings.

10. LSD radix sort is in-place sorting algorithm.
a) False
b) True

Answer: a
Clarification: LSD radix is not an in-place sorting algorithm. It needs extra memory to store the elements in bucket and its worst case space complexity is O(w + R).

and Answers.