Category: Data Structures & Algorithms Objective Questions

Data Structures & Algorithms Multiple Choice Questions on “Euclid’s Algorithm”.

1. Euclid’s algorithm is used for finding ___________
a) GCD of two numbers
b) GCD of more than three numbers
c) LCM of two numbers
d) LCM of more than two numbers

Answer: a
Clarification: Euclid’s algorithm is basically used to find the GCD of two numbers. It cannot be directly applied to three or more numbers at a time.

2. Who invented Euclid’s algorithm?
a) Sieve
b) Euclid
c) Euclid-Sieve
d) Gabriel lame
Answer: b
Clarification: Euclid invented Euclid’s algorithm. Sieve provided an algorithm for finding prime numbers. Gabriel lame proved a theorem in Euclid’s algorithm.

3. If 4 is the GCD of 16 and 12, What is the GCD of 12 and 4?
a) 12
b) 6
c) 4
d) 2

Answer: c
Clarification: Euclid’s algorithm states that the GCD of two numbers does not change even if the bigger number is replaced by a difference of two numbers. So, GCD of 16 and 12 and 12 and (16-12)=4 is the same.

4. Which of the following is not an application of Euclid’s algorithm?
a) Simplification of fractions
b) Performing divisions in modular arithmetic
c) Solving quadratic equations
d) Solving diophantine equations

Answer: c
Clarification: Solving quadratic equations is not an application of Euclid’s algorithm whereas the rest of the options are mathematical applications of Euclid’s algorithm.

5. The Euclid’s algorithm runs efficiently if the remainder of two numbers is divided by the minimum of two numbers until the remainder is zero.
a) True
b) False

Answer: a
Clarification: The Euclid’s algorithm runs efficiently if the remainder of two numbers is divided by the minimum of two numbers until the remainder is zero. This improvement in efficiency was put forth by Gabriel Lame.

6. According to Gabriel lame, how many steps does Euclid’s algorithm require to solve a problem?
a) Less than five times the number of digits
b) More than five times the number of digits
c) Less than two times the number of digits
d) More than two times the number of digits

Answer: a
Clarification: The Euclid’s algorithm requires less than five times the number of digits. It runs by dividing two numbers. It stops when a remainder zero is reached.

7. Which of the following is the correct mathematical application of Euclid’s algorithm?
a) Determination of prime numbers
b) Lagrange’s four square theorem
c) Cauchy-Euler theorem
d) Residue theorem

Answer: b
Clarification: Lagrange’s four square theorem is one of the mathematical applications of Euclid’s algorithm and it is the basic tool for proving theorems in number theory. It can be generalized into other types of numbers like the Gaussian integers.

8. If GCD of two numbers is 1, then the two numbers are said to be ________
a) Co-prime numbers
b) Prime numbers
c) Composite numbers
d) Rational numbers

Answer: a
Clarification: If GCD of two numbers is 1, they are called as co-prime or relatively prime numbers. It does not mean that they are prime numbers. They don’t have any prime factors in common.

9. What is the total running time of Euclid’s algorithm?
a) O(N)
b) O(N log M)
c) O(N log N)
d) O(log N +1)

Answer: a
Clarification: The total running time of Euclid’s algorithm according to Lame’s analysis is found to be O(N).

10. Euclidean algorithm does not require the calculation of prime factors.
a) True
b) False
View Answer

Answer: a
Clarification: Euclid’s algorithm does not require the calculation of prime factors. We derive the answer straight away using formula. And also, factorization is complex.

11. What is the formula for Euclidean algorithm?
a) GCD (m,n) = GCD (n, m mod n)
b) LCM(m,n)=LCM(n, m mod n)
c) GCD(m,n,o,p) = GCD (m, m mod n, o, p mod o)
d) LCM (m,n,o,p) = LCM (m, m mod n, o, p mod o)

Answer: a
Clarification: The formula for computing GCD of two numbers using Euclidean algorithm is given as GCD (m,n)= GCD (n, m mod n). It is used recursively until zero is obtained as a remainder.

12. What is the total running time of the binary GCD algorithm?
a) O(N)
b) O(N²)
c) O(log N)
d) O(N log N)

Answer: b
Clarification: Binary GCD algorithm is a sub division of Euclidean algorithm with more faster operations. Its running time is given by O(N²).

13. What is the GCD of 20 and 12 using Euclid’s algorithm?
a) 8
b) 2
c) 4
d) 6

Answer: c
Clarification: GCD(m,n)=GCD(n, m mod n)
GCD(20,12)=GCD( 12,8)
= GCD(8,4)
= GCD(4,0) = 4.

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

1. Is Best First Search a searching algorithm used in graphs.
a) True
b) False

Answer: a
Clarification: Best First Search is a searching algorithm used in graphs. It explores it by choosing a node by heuristic evaluation rule. It is used in solving searching for related problems.

2. Who described this Best First Search algorithm using heuristic evaluation rule?
a) Judea Pearl
b) Max Bezzel
c) Franz Nauck
d) Alan Turing

Answer: a
Clarification: The best first search algorithm using heuristic evaluation rule or function was proposed by an Israeli – American computer scientist and philosopher Judea Pearl.

3. Which type of best first search algorithm was used to predict the closeness of the end of path and its solution?
a) Greedy BFS
b) Divide and Conquer
c) Heuristic BFS
d) Combinatorial
Answer: a
Clarification: The greedy best first search algorithm was used to predict the closeness of the end of the path and its solution by some of the computer scientists.

4. What is the other name of the greedy best first search?
a) Heuristic Search
b) Pure Heuristic Search
c) Combinatorial Search
d) Divide and Conquer Search

Answer: b
Clarification: The greedy best first search algorithm was used to predict the closeness of the end of the path and its solution by some of the computer scientists. It is also known as Pure Heuristic Search.

5. Which algorithm is used in graph traversal and path finding?
a) A*
b) C*
c) D*
d) E*

Answer: a
Clarification: In computer science A* algorithm is used in graph traversal and path finding. It is a process of node finding in between a path. It is an example of the best first search.

6. Which algorithm is used to find the least cost path from source node to destination node?
a) A* BFS
b) C* BFS
c) D* BFS
d) B* BFS

Answer: d
Clarification: In computer science, B* algorithm is used to find the least cost path between the source node and the destination node. It is an example of the best first search.

7. Which of the following is an example of Best First Search algorithm?
a) A*
b) B*
c) C*
d) Both A* and B*

Answer: d
Clarification: In computer science, A* algorithm is used in graph traversal and path finding. It is a process of node finding in between a path. B* algorithm is used to find the least cost path between the source node and the destination node.

8. Which of the following is the greedy best first search?
a) Pure Heuristic Search
b) A*
c) B*
d) Both A* and B*

Answer: a
Clarification: Pure Heuristic Search is also called greedy best first search while A* and B* search algorithms are not greedy best first search.

9. Which of the following scientists didn’t publish A* algorithm?
a) Peter Hart
b) Nils Nilsson
c) Bertram Raphael
d) Hans Berliner

Answer: d
Clarification: Peter Hart Nils Nilsson Bertram Raphael are the three scientists of SRI International who first published the A* search algorithm which uses heuristics for better performance. Hans Berliner published B* algorithm.

10. Who published the B* search algorithm?
a) Peter Hart
b) Nils Nilsson
c) Bertram Raphael
d) Hans Berliner

Answer: d
Clarification: Hans Berliner was a Computer Science professor who first published the B* search algorithm in 1979. While Peter Hart Nils Nilsson Bertram Raphael are the three scientists of SRI International who first published the A* search algorithm which uses heuristics for better performance.

Data Structures & Algorithms Multiple Choice Questions on “Properties of Bipartite Graphs”.

1. Which type of graph has no odd cycle in it?
a) Bipartite
b) Histogram
c) Cartesian
d) Pie
Answer: a
Clarification: The graph is known as Bipartite if the graph does not contain any odd length cycle in it. Odd length cycle means a cycle with the odd number of vertices in it.

2. What type of graph has chromatic number less than or equal to 2?
a) Histogram
b) Bipartite
c) Cartesian
d) Tree
Answer: b
Clarification: A graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. The smallest number of graphs needed to color the graph is chromatic number.

3. Which of the following is the correct type of spectrum of the bipartite graph?
a) Symmetric
b) Anti – Symmetric
c) Circular
d) Exponential

Answer: a
Clarification: The spectrum of the bipartite graph is symmetric in nature. The spectrum is the property of graph that are related to polynomial, Eigen values, Eigen vectors of the matrix related to graph.

4. Which of the following is not a property of the bipartite graph?
a) No Odd Cycle
b) Symmetric spectrum
c) Chromatic Number Is Less Than or Equal to 2
d) Asymmetric spectrum

Answer: d
Clarification: A graph is known to be bipartite if it has odd length cycle number. It also has symmetric spectrum and the bipartite graph contains the total chromatic number less than or equal to 2.

5. Which one of the following is the chromatic number of bipartite graph?
a) 1
b) 4
c) 3
d) 5

Answer: a
Clarification: A graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. The smallest number of graphs needed to color the graph is the chromatic number.

6. Which graph has a size of minimum vertex cover equal to maximum matching?
a) Cartesian
b) Tree
c) Heap
d) Bipartite

Answer: d
Clarification: The Konig’s theorem given the equivalence relation between the minimum vertex cover and the maximum matching in graph theory. Bipartite graph has a size of minimum vertex cover equal to maximum matching.

7. Which theorem gives the relation between the minimum vertex cover and maximum matching?
a) Konig’s Theorem
b) Kirchhoff’s Theorem
c) Kuratowski’s Theorem
d) Kelmans Theorem

Answer: a
Clarification: The Konig’s theorem given the equivalence relation between the minimum vertex cover and the maximum matching in graph theory. Bipartite graph has a size of minimum vertex cover equal to maximum matching.

8. Which of the following is not a property of perfect graph?
a) Compliment of Line Graph of Bipartite Graph
b) Compliment of Bipartite Graph
c) Line Graph of Bipartite Graph
d) Line Graph

Answer: d
Clarification: TThe Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph is known as a perfect graph in graph theory. Normal line graph is not a perfect graph whereas line perfect graph is a graph whose line graph is a perfect graph.

9. Which of the following graphs don’t have chromatin number less than or equal to 2?
a) Compliment of Line Graph of Bipartite Graph
b) Compliment of Bipartite Graph
c) Line Graph of Bipartite Graph
d) Wheel graph

Answer: d
Clarification: The perfect bipartite graph has chromatic number 2. Also, the Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph is known as perfect graph in graph theory. Wheel graph Wn has chromatin number 3 if n is odd and 4 if n is even.

10. Which of the following has maximum clique size 2?
a) Perfect graph
b) Tree
c) Histogram
d) Cartesian

Answer: a
Clarification: The perfect bipartite graph has clique size 2. Also, the clique size of Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph is 2.

11. What is the chromatic number of compliment of line graph of bipartite graph?
a) 0
b) 1
c) 2
d) 3

Answer: c
Clarification: The perfect bipartite graph has chromatic number 2. So the Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph has chromatic number 2.

12. What is the clique size of the line graph of bipartite graph?
a) 0
b) 1
c) 2
d) 3

Answer: c
Clarification: The perfect bipartite graph has clique size 2. So the clique size of Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph is 2.

13. It is possible to have a negative chromatic number of bipartite graph.
a) True
b) False

Answer: b
Clarification: A graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. The smallest number of graphs needed to color the graph is the chromatic number. But the chromatic number cannot be negative.

14. Every Perfect graph has forbidden graph characterization.
a) True
b) False

Answer: a
Clarification: Berge theorem proves the forbidden graph characterization of every perfect graphs. Because of that reason every bipartite graph is perfect graph.

15. Which structure can be modelled by using Bipartite graph?
a) Hypergraph
b) Perfect Graph
c) Hetero Graph
d) Directed Graph

Answer: a
Clarification: A combinatorial structure such as Hypergraph can be made using the bipartite graphs. A hypergraph in graph theory is a type of graph in which edge can join any number of vertices.

Data Structure online test on “Largest and Smallest Number in an Array using Recursion”.

1. Which of the following methods can be used to find the largest and smallest element in an array?
a) Recursion
b) Iteration
c) Both recursion and iteration
d) No method is suitable
Answer: c
Clarification: Both recursion and iteration can be used to find the largest and smallest element in an array.

2. Consider the following iterative code snippet to find the largest element:

int get_max_element(int *arr,int n)
{
      int i, max_element = arr[0];
      for(i = 1; i < n; i++)
          if(________)
          max_element = arr[i];
      return max_element;
}

Which of the following lines should be inserted to complete the above code?
a) arr[i] > max_element
b) arr[i] < max_element
c) arr[i] == max_element
d) arr[i] != max_element
Answer: a
Clarification: The line “arr[i] > max_element” should be inserted to complete the above code snippet.

3. Consider the following code snippet to find the smallest element in an array:

int get_min_element(int *arr, int n)
{
      int i, min_element = arr[0];
      for(i = 1; i < n; i++)
        if(_______)
          min_element = arr[i];
      return min_element;
}

Which of the following lines should be inserted to complete the above code?
a) arr[i] > min_element
b) arr[i] < min_element
c) arr[i] == min_element
d) arr[i] != min_element
Answer: b
Clarification: The line “arr[i] < min_element” should be inserted to complete the above code.

4. What is the output of the following code?

#include
int get_max_element(int *arr,int n)
{
      int i, max_element = arr[0];
      for(i = 1; i < n; i++)
        if(arr[i] > max_element)
          max_element = arr[i];
      return max_element;
}
int get_min_element(int *arr, int n)
{
      int i, min_element = arr[0];
      for(i = 1; i < n; i++)
        if(arr[i] < min_element)
          min_element = arr[i];
      return min_element;
}
int main()
{
     int n = 7, arr[7] = {5,2,4,7,8,1,3};
     int max_element = get_max_element(arr,n);
     int min_element = get_min_element(arr,n);
     printf("%d %d",max_element,min_element);
     return 0;
}

a) 5 3
b) 3 5
c) 8 1
d) 1 8

Answer: c
Clarification: The program prints the values of the largest and the smallest elements in the array, which are 8 and 1 respectively.

5. What is the output of the following code?

#include
int get_max_element(int *arr,int n)
{
      int i, max_element = arr[0];
      for(i = 1; i < n; i++)
        if(arr[i] > max_element)
          max_element = arr[i];
      return max_element;
}
int get_min_element(int *arr, int n)
{
      int i, min_element;
      for(i = 1; i < n; i++)
        if(arr[i] < min_element)
          min_element = arr[i];
      return min_element;
}
int main()
{
     int n = 7, arr[7] = {1,1,1,0,-1,-1,-1};
     int max_element = get_max_element(arr,n);
     int min_element = get_min_element(arr,n);
     printf("%d %d",max_element,min_element);
     return 0;
}

a) 1 -1
b) -1 1
c) 1 Garbage value
d) Depends on the compiler
Answer: c
Clarification: Since the min_element variable is not initialised, some compilers will auto initialise as 0 which produces -1 as output whereas some compilers won’t initialise automatically. In that case, the result will be a garbage value hence the output depends on the compiler.

6. What is the time complexity of the following iterative implementation used to find the largest and smallest element in an array?

#include
int get_max_element(int *arr,int n)
{
      int i, max_element = arr[0];
      for(i = 1; i < n; i++)
        if(arr[i] > max_element)
          max_element = arr[i];
      return max_element;
}
int get_min_element(int *arr, int n)
{
      int i, min_element;
      for(i = 1; i < n; i++)
        if(arr[i] < min_element)
          min_element = arr[i];
      return min_element;
}
int main()
{
     int n = 7, arr[7] = {1,1,1,0,-1,-1,-1};
     int max_element = get_max_element(arr,n);
     int min_element = get_min_element(arr,n);
     printf("%d %d",max_element,min_element);
     return 0;
}

a) O(1)
b) O(n)
c) O(n²)
d) O(n/2)
View Answer

Answer: b
Clarification: The time complexity of the above iterative implementation used to find the largest and the smallest element in an array is O(n).

7. Consider the following recursive implementation to find the largest element in an array.

int max_of_two(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int recursive_max_element(int *arr, int len, int idx)
{
      if(idx == len - 1)
      return arr[idx];
      return _______;
}

Which of the following lines should be inserted to complete the above code?
a) max_of_two(arr[idx], recursive_max_element(arr, len, idx))
b) recursive_max_element(arr, len, idx)
c) max_of_two(arr[idx], recursive_max_element(arr, len, idx + 1))
d) recursive_max_element(arr, len, idx + 1)

Answer: c
Clarification: The line “max_of_two(arr[idx], recursive_max_element(arr, len, idx + 1))” should be inserted to complete the above code.

8. What is the output of the following code?

#include
int max_of_two(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_of_two(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int recursive_max_element(int *arr, int len, int idx)
{
      if(idx == len - 1)
      return arr[idx];
      return max_of_two(arr[idx], recursive_max_element(arr, len, idx + 1));
}
int recursive_min_element(int *arr, int len, int idx)
{
      if(idx == len - 1)
      return arr[idx];
      return min_of_two(arr[idx], recursive_min_element(arr, len, idx + 1));
}
int main()
{
    int n = 10, idx = 0, arr[] = {5,2,6,7,8,9,3,-1,1,10};
    int max_element = recursive_max_element(arr,n,idx);
    int min_element = recursive_min_element(arr,n,idx);
    printf("%d %d",max_element,min_element);
    return 0;
}

a) -1 10
b) 10 -1
c) 1 10
d) 10 1

Answer: b
Clarification: The program prints the values of the largest and the smallest element in the array, which are 10 and -1 respectively.

9. What is the time complexity of the following recursive implementation used to find the largest and the smallest element in an array?

#include
int max_of_two(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_of_two(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int recursive_max_element(int *arr, int len, int idx)
{
      if(idx == len - 1)
      return arr[idx];
      return max_of_two(arr[idx], recursive_max_element(arr, len, idx + 1));
}
int recursive_min_element(int *arr, int len, int idx)
{
      if(idx == len - 1)
      return arr[idx];
      return min_of_two(arr[idx], recursive_min_element(arr, len, idx + 1));
}
int main()
{
    int n = 10, idx = 0, arr[] = {5,2,6,7,8,9,3,-1,1,10};
    int max_element = recursive_max_element(arr,n,idx);
    int min_element = recursive_min_element(arr,n,idx);
    printf("%d %d",max_element,min_element);
    return 0;
}

a) O(1)
b) O(n)
c) O(n²)
d) O(n³)
View Answer

Answer: b
Clarification: The time complexity of the above recursive implementation used to find the largest and smallest element in an array is O(n).

10. How many times is the function recursive_min_element() called when the following code is executed?

int min_of_two(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int recursive_min_element(int *arr, int len, int idx)
{
      if(idx == len - 1)
      return arr[idx];
      return min_of_two(arr[idx], recursive_min_element(arr, len, idx + 1));
}
int main()
{
     int n = 10, idx = 0, arr[] = {5,2,6,7,8,9,3,-1,1,10};
     int min_element = recursive_min_element(arr,n,idx);
     printf("%d",min_element);
     return 0;
}

a) 9
b) 10
c) 11
d) 12
View Answer

Answer: b
Clarification: The function recursive_min_element() is called 10 times when the above code is executed.

11. What is the output of the following code?

#include
int max_of_two(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_of_two(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int recursive_max_element(int *arr, int len, int idx)
{
      if(idx == len - 1)
      return arr[idx];
      return max_of_two(arr[idx], recursive_max_element(arr, len, idx + 1));
}
int recursive_min_element(int *arr, int len, int idx)
{
      if(idx == len - 1)
      return arr[idx];
      return min_of_two(arr[idx], recursive_min_element(arr, len, idx + 1));
}
int main()
{
     int n = 5, idx = 0, arr[] = {1,1,1,1,1};
     int max_element = recursive_max_element(arr,n,idx);
     int min_element = recursive_min_element(arr,n,idx);
     printf("%d %d",max_element,min_element);
     return 0;
}

a) 1 1
b) 0 0
c) compile time error
d) runtime error

Answer: a
Clarification: The program prints the values of the largest and the smallest element in the array, which are 1 and 1.

and Answers.

Data Structure Multiple Choice Questions on “Coin Change Problem”.

1. You are given infinite coins of denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using ____________
a) Greedy algorithm
b) Dynamic programming
c) Divide and conquer
d) Backtracking

Answer: b
Clarification: The coin change problem has overlapping subproblems(same subproblems are solved multiple times) and optimal substructure(the solution to the problem can be found by finding optimal solutions for subproblems). So, dynamic programming can be used to solve the coin change problem.

2. Suppose you have coins of denominations 1, 3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm NOT produce an optimal answer?
a) 20
b) 12
c) 6
d) 5

Answer: c
Clarification: Using the greedy algorithm, three coins {4,1,1} will be selected to make a sum of 6. But, the optimal answer is two coins {3,3}.

3. Suppose you have coins of denominations 1,3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm produce an optimal answer?
a) 14
b) 10
c) 6
d) 100

Answer: d
Clarification: Using the greedy algorithm, three coins {4,1,1} will be selected to make a sum of 6. But, the optimal answer is two coins {3,3}. Similarly, four coins {4,4,1,1} will be selected to make a sum of 10. But, the optimal answer is three coins {4,3,3}. Also, five coins {4,4,4,1,1} will be selected to make a sum of 14. But, the optimal answer is four coins {4,4,3,3}. For a sum of 100, twenty-five coins {all 4’s} will be selected and the optimal answer is also twenty-five coins {all 4’s}.

4. Fill in the blank to complete the code.

#include
int main()
{
      int coins[10]={1,3,4},lookup[100000];
      int i,j,tmp,num_coins = 3,sum=100;
      lookup[0]=0;
      for(i = 1; i <= sum; i++)
      {
	   int min_coins = i;
	   for(j = 0;j < num_coins; j++)
	   {
	        tmp = i - coins[j];
	        if(tmp < 0)
	         continue;
	        if(lookup[tmp] < min_coins)
	       ______________;
	   }
	   lookup[i] = min_coins + 1;
      }
      printf("%d",lookup[sum]);
      return 0;
}

a) lookup[tmp] = min_coins
b) min_coins = lookup[tmp]
c) break
d) continue

Answer: b
Clarification: min_coins = lookup[tmp] will complete the code.

5. You are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the time complexity of a dynamic programming implementation used to solve the coin change problem?
a) O(N)
b) O(S)
c) O(N²)
d) O(S*N)
Answer: d
Clarification: The time complexity is O(S*N).

6. Suppose you are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the space complexity of a dynamic programming implementation used to solve the coin change problem?
a) O(N)
b) O(S)
c) O(N²)
d) O(S*N)

Answer: b
Clarification: To get the optimal solution for a sum S, the optimal solution is found for each sum less than equal to S and each solution is stored. So, the space complexity is O(S).

7. You are given infinite coins of denominations 1, 3, 4. What is the total number of ways in which a sum of 7 can be achieved using these coins if the order of the coins is not important?
a) 4
b) 3
c) 5
d) 6
View Answer

Answer: c
Clarification: A sum of 7 can be achieved in the following ways:
{1,1,1,1,1,1,1}, {1,1,1,1,3}, {1,3,3}, {1,1,1,4}, {3,4}.
Therefore, the sum can be achieved in 5 ways.

8. You are given infinite coins of denominations 1, 3, 4. What is the minimum number of coins required to achieve a sum of 7?
a) 1
b) 2
c) 3
d) 4
View Answer

Answer: b
Clarification: A sum of 7 can be achieved by using a minimum of two coins {3,4}.

9. You are given infinite coins of denominations 5, 7, 9. Which of the following sum CANNOT be achieved using these coins?
a) 50
b) 21
c) 13
d) 23

Answer: c
Clarification: One way to achieve a sum of 50 is to use ten coins of 5. A sum of 21 can be achieved by using three coins of 7. One way to achieve a sum of 23 is to use two coins of 7 and one coin of 9. A sum of 13 cannot be achieved.

10. You are given infinite coins of denominations 3, 5, 7. Which of the following sum CANNOT be achieved using these coins?
a) 15
b) 16
c) 17
d) 4

Answer: d
Clarification: Sums can be achieved as follows:
15 = {5,5,5}
16 = {3,3,5,5}
17 = {3,7,7}
we can’t achieve for sum=4 because our available denominations are 3,5,7 and sum of any two denominations is greater than 4.

11. What is the output of the following program?

#include
int main()
{
      int coins[10]={1,3,4},lookup[100];
      int i,j,tmp,num_coins = 3,sum=10;
      lookup[0]=0;
      for(i=1;i<=sum;i++)
      {
	    int min_coins = i;
	    for(j=0;j<num_coins;j++)
	    {
	         tmp=i-coins[j];
	         if(tmp<0)
	          continue;
	         if(lookup[tmp] < min_coins)
		 min_coins=lookup[tmp];
	    }
	    lookup[i] = min_coins + 1;
      }
      printf("%d",lookup[sum]);
      return 0;
}

a) 2
b) 3
c) 4
d) 5
Answer: b
Clarification: The program prints the minimum number of coins required to get a sum of 10, which is 3.

12. What is the output of the following program?

#include
int main()
{
      int coins[10]={1,3,4},lookup[100];
      int i,j,tmp,num_coins = 3,sum=14;
      lookup[0]=0;
      for(i=1;i<=sum;i++)
      {
	   int min_coins = i;
	   for(j=0;j<num_coins;j++)
	   { 
	         tmp=i-coins[j];
	         if(tmp<0)
		  continue;
	         if(lookup[tmp] < min_coins)
		 min_coins=lookup[tmp];
	   }
	   lookup[i] = min_coins + 1;
      }
      printf("%d",lookup[sum]);
      return 0;
}

a) 2
b) 3
c) 4
d) 5
Answer: c
Clarification: The program prints the minimum number of coins required to get a sum of 14, which is 4.

and Answers.

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.