Category: Data Structures & Algorithms Objective Questions

Data Structures & Algorithms Multiple Choice Questions on “Pseudorandom Number Generators”.

1. What is pseudo random number generator?
a) an algorithm that generates random numbers with help of mathematical formula
b) an algorithm that generates random numbers according to user activity
c) an algorithm that generates random numbers according to time
d) an algorithm that generates random numbers with help of user input
Answer: a
Clarification: A pseudo random number generator generates random numbers with the help of a mathematical formula. We can seed the random number generator with a different value everytime if we want unique random numbers to be generated.

2. What should be the return type of rand() function?
a) int
b) float
c) long
d) double

Answer: a
Clarification: The return type of rand () is int. It can generate random numbers from 0 to RAND_MAX.

3. What is the purpose of using function srand()?
a) to set the seed of rand() function
b) to generate random numbers
c) to enable rand() function
d) to improve efficiency of rand()

Answer: a
Clarification: The function srand() sets the seed of rand(). It can be used to generate a unique set of random numbers every time.

4. What is the range of rand()?
a) 0 to RAND_MAX
b) 0 to infinity
c) 0 to 2147483647
d) 0 to 32767
View Answer

Answer: a
Clarification: The function rand() generates random numbers in the range 0 to RAND_MAX. The value of RAND_MAX is minimum 32,767.

5.What is the correct formula for generating random numbers in the range (lower,upper) using rand()?
a) rand() % (upper – lower)
b) rand() + lower
c) (rand()%(upper-lower)) + lower
d) (rand()%(upper-lower+1)) + lower

Answer: d
Clarification: The correct formula for generating random numbers in the range (lower,upper) using rand() is (rand()%(upper-lower+1)) + lower. The function rand() generates random numbers in the range 0 to RAND_MAX.

6. Which of the following will generate random numbers in the range 1-100 (both inclusive)?
a) rand() % 100
b) rand() % 101
c) (rand() % (101)) + 1
d) (rand() % (100)) + 1

Answer: d
Clarification: Formula for generating random numbers in the range (lower,upper) using rand() is (rand()%(upper-lower+1)) + lower. So the correct answer will be (rand() % (100)) + 1.

7. What is the minimum value of RAND_MAX possible in any implementation?
a) 0
b) 32767
c) 2147483647
d) 128

Answer: b
Clarification: The value of RAND_MAX varies according to implementation. But it is guaranteed to be at least 32767.

8. Function rand() generates unique random numbers every time.
a) true
b) false

Answer: b
Clarification: Function rand() does not generate unique random numbers every time. For achieving this we have to use srand() along with rand().

9. What is the default value of seed if function rand() is called before srand()?
a) srand(0)
b) srand(1)
c) srand(time(null))
d) srand(-1)

Answer: b
Clarification: If srand() is not called before the call to the function rand() then the value of seed is taken as srand(1) by default. We should use srand() before rand() in order to use our own seed.

10. Pseudo random number generators can be used for data encryption.
a) true
b) false

Answer: b
Clarification: Pseudo random number generators cannot be used for data encryption as the random numbers generated by them are predictable. For data encryption the numbers should be absolutely unpredictable.

11. Predict the output of the following code.

#include  
int main() 
{ 
     srand(0); 
     printf("%dn", rand()); 
     return 0; 
}

a) compilation error
b) random number between 0 to RAND_MAX
c) cannot be predicted
d) 0

Answer: b
Clarification: The function rand() generates random numbers in the range 0 to RAND_MAX. The function srand() seeds rand(). We get unique set of random numbers if rand() is seeded with a different value every time.

12. Which header file contains the function rand() in C language?
a) stdlib
b) iostream
c) stdio
d) time
Answer: a
Clarification: In C language the header file stdlib contains the function rand(). It generates pseudo random numbers.

13. Predict the output of the following code.

#include  
int main() 
{ 
     srand(0); 
     printf("%dn", rand()%50); 
     return 0; 
}

a) compilation error
b) random number between 0 to 50 (both inclusive)
c) random number between 0 to 51 (both inclusive)
d) random number between 0 to 49 (both inclusive)

Answer: d
Clarification: Formula for generating random numbers in the range (lower,upper) using rand() is (rand()%(upper-lower+1)) + lower. So the given code will generate random numbers between 0 to 49.

14. Which of the following code will generate unique random numbers every time?
a)

#include  
int main() 
{ 
     srand(0); 
     printf("%dn", rand()%50); 
     return 0; 
}

b)

#include  
int main() 
{ 
     srand(time(0)); 
     printf("%dn", rand()%50); 
     return 0; 
}

c)

#include  
int main() 
{ 
    srand(1); 
    printf("%dn", rand()%50); 
    return 0; 
}

d)

#include  
int main() 
{
     printf("%dn", rand()%50); 
     return 0; 
}

Answer: b
Clarification: The function rand() generates random numbers in the range 0 to RAND_MAX. The function srand() seeds rand(). We get a unique set of random numbers if rand() is seeded with a different value every time. This can be achieved by using srand(time(0)).

15. Which of the following code will give an error?
a)

#include  
int main() 
{ 
     printf("%dn", srand()); 
     return 0; 
}

b)

#include  
int main() 
{ 
     srand(time(0)); 
     printf("%dn", rand()%50); 
     return 0; 
}

c)

#include  
int main() 
{ 
     srand(1); 
     return 0; 
}

d)

#include  
int main() 
{
     printf("%dn", rand()%50); 
     return 0; 
}

Answer: a
Clarification: The function rand() generates random numbers in the range 0 to RAND_MAX. The function srand() seeds rand(). So we get an error if we try to print srand().

Data Structure Multiple Choice Questions on “Recursion”.

1. Recursion is a method in which the solution of a problem depends on ____________
a) Larger instances of different problems
b) Larger instances of the same problem
c) Smaller instances of the same problem
d) Smaller instances of different problems

Answer: c
Clarification: In recursion, the solution of a problem depends on the solution of smaller instances of the same problem.

2. Which of the following problems can’t be solved using recursion?
a) Factorial of a number
b) Nth fibonacci number
c) Length of a string
d) Problems without base case

Answer: d
Clarification: Problems without base case leads to infinite recursion call. In general, we will assume a base case to avoid infinite recursion call. Problems like finding Factorial of a number, Nth Fibonacci number and Length of a string can be solved using recursion.

3. Recursion is similar to which of the following?
a) Switch Case
b) Loop
c) If-else
d) if elif else

Answer: b
Clarification: Recursion is similar to a loop.

4. In recursion, the condition for which the function will stop calling itself is ____________
a) Best case
b) Worst case
c) Base case
d) There is no such condition

Answer: c
Clarification: For recursion to end at some point, there always has to be a condition for which the function will not call itself. This condition is known as base case.

5. What will happen when the below code snippet is executed?

void my_recursive_function()
{
   my_recursive_function();
}
int main()
{
   my_recursive_function();
   return 0;
}

a) The code will be executed successfully and no output will be generated
b) The code will be executed successfully and random output will be generated
c) The code will show a compile time error
d) The code will run for some time and stop when the stack overflows

Answer: d
Clarification: Every function call is stored in the stack memory. In this case, there is no terminating condition(base case). So, my_recursive_function() will be called continuously till the stack overflows and there is no more space to store the function calls. At this point of time, the program will stop abruptly.

6. What is the output of the following code?

void my_recursive_function(int n)
{
    if(n == 0)
    return;
    printf("%d ",n);
    my_recursive_function(n-1);
}
int main()
{
    my_recursive_function(10);
    return 0;
}

a) 10
b) 1
c) 10 9 8 … 1 0
d) 10 9 8 … 1

Answer: d
Clarification: The program prints the numbers from 10 to 1.

7. What is the base case for the following code?

void my_recursive_function(int n)
{
     if(n == 0)
     return;
     printf("%d ",n);
     my_recursive_function(n-1);
}
int main()
{
     my_recursive_function(10);
     return 0;
}

a) return
b) printf(“%d “, n)
c) if(n == 0)
d) my_recursive_function(n-1)
Answer: c
Clarification: For the base case, the recursive function is not called. So, “if(n == 0)” is the base case.

8. How many times is the recursive function called, when the following code is executed?

void my_recursive_function(int n)
{
     if(n == 0)
     return;
     printf("%d ",n);
     my_recursive_function(n-1);
}
int main()
{
     my_recursive_function(10);
     return 0;
}

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

Answer: c
Clarification: The recursive function is called 11 times.

9. What does the following recursive code do?

void my_recursive_function(int n)
{
     if(n == 0)
     return;
     my_recursive_function(n-1);
     printf("%d ",n);
}
int main()
{
     my_recursive_function(10);
     return 0;
}

a) Prints the numbers from 10 to 1
b) Prints the numbers from 10 to 0
c) Prints the numbers from 1 to 10
d) Prints the numbers from 0 to 10

Answer: c
Clarification: The above code prints the numbers from 1 to 10.

10. Which of the following statements is true?
a) Recursion is always better than iteration
b) Recursion uses more memory compared to iteration
c) Recursion uses less memory compared to iteration
d) Iteration is always better and simpler than recursion

Answer: b
Clarification: Recursion uses more memory compared to iteration because every time the recursive function is called, the function call is stored in stack.

11. What will be the output of the following code?

int cnt=0;
void my_recursive_function(int n)
{
     if(n == 0)
     return;
     cnt++;
     my_recursive_function(n/10);
}
int main()
{
     my_recursive_function(123456789);
     printf("%d",cnt);
     return 0;
}

a) 123456789
b) 10
c) 0
d) 9

Answer: d
Clarification: The program prints the number of digits in the number 123456789, which is 9.

12. What will be the output of the following code?

void my_recursive_function(int n)
{
    if(n == 0)
    {
         printf("False");
	   return;
    }
    if(n == 1)
    {
         printf("True");
         return;
    }
    if(n%2==0)
    my_recursive_function(n/2);
    else
    {
         printf("False");
         return;
    }
 
}
int main()
{
     my_recursive_function(100);
     return 0;
}

a) True
b) False

Answer: b
Clarification: The function checks if a number is a power of 2. Since 100 is not a power of 2, it prints false.

13. What is the output of the following code?

int cnt = 0;
void my_recursive_function(char *s, int i)
{
     if(s[i] == ' ')
        return;
     if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u')
     cnt++;
     my_recursive_function(s,i+1);
}
int main()
{
     my_recursive_function("thisisrecursion",0);
     printf("%d",cnt);
     return 0;
}

a) 6
b) 9
c) 5
d) 10

Answer: a
Clarification: The function counts the number of vowels in a string. In this case the number is vowels is 6.

14. What is the output of the following code?

void my_recursive_function(int *arr, int val, int idx, int len)
{
    if(idx == len)
    {
         printf("-1");
         return ;
    }
    if(arr[idx] == val)
    {
         printf("%d",idx);
         return;
    }
    my_recursive_function(arr,val,idx+1,len);
}
int main()
{
     int array[10] = {7, 6, 4, 3, 2, 1, 9, 5, 0, 8};
     int value = 2;
     int len = 10;
     my_recursive_function(array, value, 0, len);
     return 0;
}

a) 3
b) 4
c) 5
d) 6
Answer: b
Clarification: The program searches for a value in the given array and prints the index at which the value is found. In this case, the program searches for value = 2. Since, the index of 2 is 4(0 based indexing), the program prints 4.

and Answers.

Data Structure Multiple Choice Questions on “Search an Element in an Array using Recursion – 1”.

1. Which of the following techniques can be used to search an element in an unsorted array?
a) Iterative linear search
b) Recursive binary search
c) Iterative binary search
d) Normal binary search
Answer: a
Clarification: Iterative linear search can be used to search an element in an unsorted array.
Note: Binary search can be used only when the array is sorted.

2. Consider the array {1,1,1,1,1}. Select the wrong option?
a) Iterative linear search can be used to search for the elements in the given array
b) Recursive linear search can be used to search for the elements in the given array
c) Recursive binary search can be used to search for the elements in the given array
d) No method is defined to search for an element in the given array

Answer: d
Clarification: Iterative linear search, Recursive linear search and Recursive binary search can be applied to search for an element in the above given array.

3. What does the following code do?

#include
int search_num(int *arr, int num, int len)
{
     int i;
     for(i = 0; i < len; i++)
     if(arr[i] == num)
      return i;
     return -1;
}
int main()
{
      int arr[5] ={1,2,3,4,5},num=3,len = 5;
      int indx = search_num(arr,num,len);
      printf("Index of %d is %d",num,indx);
      return 0;
}

a) Search and returns the index of all the occurrences of the number that is searched
b) Search and returns the index of the first occurrence of the number that is searched
c) Search and returns of the last occurrence of the number that is searched
d) Returns the searched element from the given array

Answer: b
Clarification: The code finds the index of the first occurrence of the number that is searched.

4. What is the output of the following code?

#include
int search_num(int *arr, int num, int len)
{
     int i;
     for(i = 0; i < len; i++)
     if(arr[i] == num)
        return i;
     return -1;
}
int main()
{
      int arr[5] ={1,3,3,3,5},num=3,len = 5;
      int indx = search_num(arr,num,len);
      printf("Index of %d is %d",num,indx);
      return 0;
}

a) Index of 3 is 0
b) Index of 3 is 1
c) Index of 3 is 2
d) Index of 3 is 3

Answer: b
Clarification: The program prints the index of the first occurrence of 3, which is 1.

5. What is the time complexity of the following code used to search an element in an array?

#include
int search_num(int *arr, int num, int len)
{
     int i;
     for(i = 0; i < len; i++)
     if(arr[i] == num)
        return i;
     return -1;
}
int main()
{
      int arr[5] ={1,3,3,3,5},num=3,len = 5;
      int indx = search_num(arr,num,len);
      printf("Index of %d is %d",num,indx);
      return 0;
}

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

Answer: b
Clarification: The time complexity of the above code used to search an element in an array is O(n).

6. Consider the following recursive implementation of linear search:

#include
int recursive_search_num(int *arr, int num, int idx, int len)
{
     if(idx == len)
     return -1;
     if(arr[idx] == num)
       return idx;
     return __________;
}
int main()
{
      int arr[5] ={1,3,3,3,5},num=2,len = 5;
      int indx = recursive_search_num(arr,num,0,len);
      printf("Index of %d is %d",num,indx);
      return 0;
}

Which of the following recursive calls should be added to complete the above code?
a) recursive_search_num(arr, num+1, idx, len);
b) recursive_search_num(arr, num, idx, len);
c) recursive_search_num(arr, num, idx+1, len);
d) recursive_search_num(arr, num+1, idx+1, len);

Answer: c
Clarification: The recursive call “recursive_search_num(arr, num, idx+1, len)” should be added to complete the above code.

7. What is the output of the following code?

#include
int recursive_search_num(int *arr, int num, int idx, int len)
{
     if(idx == len)
     return -1;
     if(arr[idx] == num)
       return idx;
     return recursive_search_num(arr, num, idx+1, len);
}
int main()
{
      int arr[8] ={1,2,3,3,3,5,6,7},num=5,len = 8;
      int indx = recursive_search_num(arr,num,0,len);
      printf("Index of %d is %d",num,indx);
      return 0;
}

a) Index of 5 is 5
b) Index of 5 is 6
c) Index of 5 is 7
d) Index of 5 is 8
View Answer

Answer: a
Clarification: The program prints the index of 5, which is 5.

8. How many times is the function recursive_search_num() called when the following code is executed?

#include
int recursive_search_num(int *arr, int num, int idx, int len)
{
     if(idx == len)
     return -1;
     if(arr[idx] == num)
     return idx;
     return recursive_search_num(arr, num, idx+1, len);
}
int main()
{
      int arr[8] ={1,2,3,3,3,5,6,7},num=5,len = 8;
      int indx = recursive_search_num(arr,num,0,len);
      printf("Index of %d is %d",num,indx);
      return 0;
}

a) 5
b) 6
c) 7
d) 8

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

9. What is the time complexity of the following recursive implementation of linear search?

#include
int recursive_search_num(int *arr, int num, int idx, int len)
{
     if(idx == len)
     return -1;
     if(arr[idx] == num)
     return idx;
     return recursive_search_num(arr, num, idx+1, len);
}
int main()
{
      int arr[8] ={1,2,3,3,3,5,6,7},num=5,len = 8;
      int indx = recursive_search_num(arr,num,0,len);
      printf("Index of %d is %d",num,indx);
      return 0;
}

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

Answer: b
Clarification: The time complexity of the above recursive implementation of linear search is O(n).

Data Structure MCQs on “Maximum Sum of Continuous Subarray – 2”.

1. Which line should be inserted in the blank to complete the following dynamic programming implementation of the maximum sub-array sum problem?

#include
int max_num(int a,int b)
{
      if(a> b)
	 return a;
      return b;
}
int maximum_subarray_sum(int *arr, int len)
{
      int sum[len], idx;
      sum[0] = arr[0];
      for(idx = 1; idx < len; idx++)
	 sum[idx] = _______________________;
      int mx = sum[0];
      for(idx = 0; idx < len; idx++)
	 if(sum[idx] > mx)
	     mx =sum[idx];
	 return mx;
}
int main()
{
      int arr[] = {-2, -5, 6, -2, 3, -1, 0,-5, 6}, len = 9;
      int ans = maximum_subarray_sum(arr, len);
      printf("%d",ans);
      return 0;
}

a) max_num(sum[idx – 1] + arr[idx], arr[idx])
b) sum[idx – 1] + arr[idx].
c) min_num(sum[idx – 1] + arr[idx], arr[idx])
d) arr[idx].

Answer: a
Clarification: The array “sum” is used to store the maximum sub-array sum. The appropriate way to do this is by using:
sum[idx] = max_num(sum[idx – 1] + arr[idx], arr[idx]).

2. What is the time complexity of the following dynamic programming algorithm used to find the maximum sub-array sum?

#include
int max_num(int a,int b)
{
      if(a> b)
	 return a;
      return b;
}
int maximum_subarray_sum(int *arr, int len)
{
      int sum[len], idx;
      sum[0] = arr[0];
      for(idx = 1; idx < len; idx++)
	 sum[idx] = max_num(sum[idx - 1] + arr[idx], arr[idx]);
      int mx = sum[0];
      for(idx = 0; idx < len; idx++)
	 if(sum[idx] > mx)
	     mx =sum[idx];
	 return mx;
}
int main()
{
      int arr[] = {-2, -5, 6, -2, 3, -1, 0,-5, 6}, len = 9;
      int ans = maximum_subarray_sum(arr, len);
      printf("%d",ans);
      return 0;
}

a) O(n)
b) O(logn)
c) O(nlogn)
d) O(n²)
View Answer

Answer: a
Clarification: The time complexity of the above dynamic programming algorithm used to solve maximum sub-array sum is O(n).

3. What is the space complexity of the following dynamic programming algorithm used to find the maximum sub-array sum?

#include
int max_num(int a,int b)
{
      if(a> b)
	 return a;
      return b;
}
int maximum_subarray_sum(int *arr, int len)
{
      int sum[len], idx;
      sum[0] = arr[0];
      for(idx = 1; idx < len; idx++)
	 sum[idx] = max_num(sum[idx - 1] + arr[idx], arr[idx]);
      int mx = sum[0];
      for(idx = 0; idx < len; idx++)
	 if(sum[idx] > mx)
	     mx =sum[idx];
	 return mx;
}
int main()
{
      int arr[] = {-2, -5, 6, -2, 3, -1, 0,-5, 6}, len = 9;
      int ans = maximum_subarray_sum(arr, len);
      printf("%d",ans);
      return 0;
}

a) O(n)
b) O(1)
c) O(n!)
d) O(n²)

Answer: a
Clarification: The above dynamic programming algorithm uses space equal to the length of the array to store the sum values. So, the space complexity is O(n).

4. Consider the following code snippet. Which property is shown by line 4 of the below code snippet?

1. int sum[len], idx;
2. sum[0] = arr[0];
3. for(idx = 1; idx < len; idx++)
4.	  sum[idx] = max(sum[idx - 1] + arr[idx], arr[idx]);
5. int mx = sum[0];
6. for(idx = 0; idx < len; idx++)
7.	 if(sum[idx] > mx)
8.		mx =sum[idx];
9. return mx;

a) Optimal substructure
b) Overlapping subproblems
c) Both overlapping subproblems and optimal substructure
d) Greedy substructure

Answer: a
Clarification: The current sum (i.e. sum[idx]) uses the previous sum (i.e. sum[idx – 1]) to get an optimal value. So, line 4 shows the optimal substructure property.

5. Consider the following code snippet:

1. int sum[len], idx;
2. sum[0] = arr[0];
3. for(idx = 1; idx < len; idx++)
4.	  sum[idx] = max(sum[idx - 1] + arr[idx], arr[idx]);
5. int mx = sum[0];
6. for(idx = 0; idx < len; idx++)
7.	 if(sum[idx] > mx)
8.		mx =sum[idx];
9. return mx;

Which method is used by line 4 of the above code snippet?
a) Divide and conquer
b) Recursion
c) Both memoization and divide and conquer
d) Memoization

Answer: d
Clarification: The array “sum” is used to store the previously calculated values, so that they aren’t recalculated. So, line 4 uses the memoization technique.

6. Find the maximum sub-array sum for the following array:
{3, 6, 7, 9, 3, 8}
a) 33
b) 36
c) 23
d) 26

Answer: b
Clarification: All the elements of the array are positive. So, the maximum sub-array sum is equal to the sum of all the elements, which is 36.

7. What is the output of the following program?

#include
int max_num(int a,int b)
{
     if(a> b)
	return a;
     return b;
}
int maximum_subarray_sum(int *arr, int len)
{
     int sum[len], idx;
     sum[0] = arr[0];
     for(idx = 1; idx < len; idx++)
	sum[idx] = max_num(sum[idx - 1] + arr[idx], arr[idx]);
     int mx = sum[0];
     for(idx = 0; idx < len; idx++)
	if(sum[idx] > mx)
	   mx =sum[idx];
     return mx;
}
int main()
{
     int arr[] = {-20, 23, 10, 3, -10, 11, -5},len = 7;
     int ans = maximum_subarray_sum(arr, len);
     printf("%d",ans);
     return 0;
}

a) 27
b) 37
c) 36
d) 26

Answer: b
Clarification: The program prints the value of maximum sub-array sum, which is 37.

8. What is the value stored in sum[4] after the following program is executed?

#include
int max_num(int a,int b)
{
      if(a> b)
	  return a;
      return b;
}
int maximum_subarray_sum(int *arr, int len)
{
      int sum[len], idx;
      sum[0] = arr[0];
      for(idx = 1; idx < len; idx++)
	   sum[idx] = max_num(sum[idx - 1] + arr[idx], arr[idx]);
      int mx = sum[0];
      for(idx = 0; idx < len; idx++)
	  if(sum[idx] > mx)
	      mx =sum[idx];
      return mx;
}
int main()
{
      int arr[] = {-2, 14, 11, -13, 10, -5, 11, -6, 3, -5},len = 10;
      int ans = maximum_subarray_sum(arr, len);
      printf("%d",ans);
      return 0;
}

a) 28
b) 25
c) 22
d) 12

Answer: c
Clarification: After the program is executed the value stored in sum[4] is 22.
Note: You are asked to find the value stored in sum[4] and NOT the output of the program.

and Answers.

Data Structure Multiple Choice Questions on “Dice Throw Problem”.

1. You are given n dice each having f faces. You have to find the number of ways in which a sum of S can be achieved. This is the dice throw problem. Which of the following methods can be used to solve the dice throw problem?
a) Brute force
b) Recursion
c) Dynamic programming
d) Brute force, Recursion and Dynamic Programming
Answer: d
Clarification: Brute force, Recursion and Dynamic Programming can be used to solve the dice throw problem.

2. You have n dice each having f faces. What is the number of permutations that can be obtained when you roll the n dice together?
a) n*n*n…f times
b) f*f*f…n times
c) n*n*n…n times
d) f*f*f…f times
Answer: b
Clarification: Each die can take f values and there are n dice. So, the total number of permutations is f*f*f…n times.

3. You have 3 dice each having 6 faces. What is the number of permutations that can be obtained when you roll the 3 dice together?
a) 27
b) 36
c) 216
d) 81
Answer: c
Clarification: The total number of permutations that can be obtained is 6 * 6 * 6 = 216.

4. You have 2 dice each of them having 6 faces numbered from 1 to 6. What is the number of ways in which a sum of 11 can be achieved?
a) 0
b) 1
c) 2
d) 3

Answer: c
Clarification: The sum of 11 can be achieved when the dice show {6, 5} or {5, 6}.

5. There are n dice with f faces. The faces are numbered from 1 to f. What is the minimum possible sum that can be obtained when the n dice are rolled together?
a) 1
b) f
c) n
d) n*f

Answer: c
Clarification: The sum will be minimum when all the faces show a value 1. The sum in this case will be n.

6. There are n dice with f faces. The faces are numbered from 1 to f. What is the maximum possible sum that can be obtained when the n dice are rolled together?
a) 1
b) f*f
c) n*n
d) n*f

Answer: d
Clarification: The sum will be maximum when all the faces show a value f. The sum in this case will be n*f.

7. There are 10 dice having 5 faces. The faces are numbered from 1 to 5. What is the number of ways in which a sum of 4 can be achieved?
a) 0
b) 2
c) 4
d) 8

Answer: a
Clarification: Since there are 10 dice and the minimum value each die can take is 1, the minimum possible sum is 10. Hence, a sum of 4 cannot be achieved.

8. Consider the following dynamic programming implementation of the dice throw problem:

#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
     int arr[num_of_dice + 1][S + 1];
     int dice, face, sm;
     for(dice = 0; dice <= num_of_dice; dice++)
         for(sm = 0; sm <= S; sm++)
           arr[dice][sm] = 0;
     for(sm = 1; sm <= S; sm++)
         arr[1][sm] = 1;
     for(dice = 2; dice <= num_of_dice; dice++)
     { 
         for(sm = 1; sm <= S; sm++)
         {
             for(face = 1; face <= num_of_faces && face < sm; face++)
                 arr[dice][sm] += arr[dice - 1][sm - face];
         }
     }
     return _____________;
}
int main()
{
     int num_of_dice = 3, num_of_faces = 4, sum = 6;
     int ans = get_ways(num_of_dice, num_of_faces, sum);
     printf("%d",ans);
     return 0;
}

Which of the following lines should be added to complete the above code?
a) arr[num_of_dice][S]
b) arr[dice][sm]
c) arr[dice][S]
d) arr[S][dice]

Answer: a
Clarification: The line arr[num_of_dice][S] completes the above code.

9. What is time complexity of the following dynamic programming implementation of the dice throw problem where f is the number of faces, n is the number of dice and s is the sum to be found?

#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
     int arr[num_of_dice + 1][S + 1];
     int dice, face, sm;
     for(dice = 0; dice <= num_of_dice; dice++)
         for(sm = 0; sm <= S; sm++)
           arr[dice][sm] = 0;
     for(sm = 1; sm <= S; sm++)
         arr[1][sm] = 1;
     for(dice = 2; dice <= num_of_dice; dice++)
     { 
         for(sm = 1; sm <= S; sm++)
         {
             for(face = 1; face <= num_of_faces && face < sm; face++)
                 arr[dice][sm] += arr[dice - 1][sm - face];
         }
     }
     return arr[num_of_dice][S];
}
int main()
{
     int num_of_dice = 3, num_of_faces = 4, sum = 6;
     int ans = get_ways(num_of_dice, num_of_faces, sum);
     printf("%d",ans);
     return 0;
}

a) O(n*f)
b) O(f*s)
c) O(n*s)
d) O(n*f*s)

Answer: d
Clarification: The time complexity of the above dynamic programming implementation is O(n*f*s).

10. What is space complexity of the following dynamic programming implementation of the dice throw problem where f is the number of faces, n is the number of dice and s is the sum to be found?

#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
     int arr[num_of_dice + 1][S + 1];
     int dice, face, sm;
     for(dice = 0; dice <= num_of_dice; dice++)
         for(sm = 0; sm <= S; sm++)
           arr[dice][sm] = 0;
     for(sm = 1; sm <= S; sm++)
         arr[1][sm] = 1;
     for(dice = 2; dice <= num_of_dice; dice++)
     { 
         for(sm = 1; sm <= S; sm++)
         {
             for(face = 1; face <= num_of_faces && face < sm; face++)
                 arr[dice][sm] += arr[dice - 1][sm - face];
         }
     }
     return arr[num_of_dice][S];
}
int main()
{
     int num_of_dice = 3, num_of_faces = 4, sum = 6;
     int ans = get_ways(num_of_dice, num_of_faces, sum);
     printf("%d",ans);
     return 0;
}

a) O(n*f)
b) O(f*s)
c) O(n*s)
d) O(n*f*s)

Answer: c
Clarification: The space complexity of the above dynamic programming implementation is O(n*s).

11. What is the output of the following code?

#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
     int arr[num_of_dice + 1][S + 1];
     int dice, face, sm;
     for(dice = 0; dice <= num_of_dice; dice++)
         for(sm = 0; sm <= S; sm++)
           arr[dice][sm] = 0;
     for(sm = 1; sm <= S; sm++)
         arr[1][sm] = 1;
     for(dice = 2; dice <= num_of_dice; dice++)
     {
         for(sm = 1; sm <= S; sm++)
         {
             for(face = 1; face <= num_of_faces && face < sm; face++)
                 arr[dice][sm] += arr[dice - 1][sm - face];
         }
     }
     return arr[num_of_dice][S];
}
int main()
{
     int num_of_dice = 3, num_of_faces = 4, sum = 6;
     int ans = get_ways(num_of_dice, num_of_faces, sum);
     printf("%d",ans);
     return 0;
}

a) 10
b) 12
c) 14
d) 16

Answer: a
Clarification: The output of the above code is 10.

12. What will be the value stored in arr[2][2] when the following code is executed?

#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
      int arr[num_of_dice + 1][S + 1];
      int dice, face, sm;
      for(dice = 0; dice <= num_of_dice; dice++)
         for(sm = 0; sm <= S; sm++)
           arr[dice][sm] = 0;
      for(sm = 1; sm <= S; sm++)
           arr[1][sm] = 1;
      for(dice = 2; dice <= num_of_dice; dice++)
      {
          for(sm = 1; sm <= S; sm++)
          {
              for(face = 1; face <= num_of_faces && face < sm; face++)
                  arr[dice][sm] += arr[dice - 1][sm - face];
          }
      }
      return arr[num_of_dice][S];
}
int main()
{
      int num_of_dice = 3, num_of_faces = 4, sum = 6;
      int ans = get_ways(num_of_dice, num_of_faces, sum);
      printf("%d",ans);
      return 0;
}

a) 0
b) 1
c) 2
d) 3
Answer: b
Clarification: The value stored in arr[2][2] is 1.

13. What is the output of the following code?

#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
     int arr[num_of_dice + 1][S + 1];
     int dice, face, sm;
     for(dice = 0; dice <= num_of_dice; dice++)
         for(sm = 0; sm <= S; sm++)
           arr[dice][sm] = 0;
     for(sm = 1; sm <= S; sm++)
         arr[1][sm] = 1;
     for(dice = 2; dice <= num_of_dice; dice++)
     {
         for(sm = 1; sm <= S; sm++)
         {
             for(face = 1; face <= num_of_faces && face < sm; face++)
                 arr[dice][sm] += arr[dice - 1][sm - face];
         }
     }
     return arr[num_of_dice][S];
}
int main()
{
     int num_of_dice = 4, num_of_faces = 6, sum = 3;
     int ans = get_ways(num_of_dice, num_of_faces, sum);
     printf("%d",ans);
     return 0;
}

a) 0
b) 1
c) 2
d) 3
Answer: a
Clarification: The minimum possible sum is 4. So, the output for sum = 3 is 0.

14. What is the output of the following code?

#include
int get_ways(int num_of_dice, int num_of_faces, int S)
{
      int arr[num_of_dice + 1][S + 1];
      int dice, face, sm;
      for(dice = 0; dice <= num_of_dice; dice++)
          for(sm = 0; sm <= S; sm++)
            arr[dice][sm] = 0;
      for(sm = 1; sm <= S; sm++)
         arr[1][sm] = 1;
      for(dice = 2; dice <= num_of_dice; dice++)
      {
          for(sm = 1; sm <= S; sm++)
          {
              for(face = 1; face <= num_of_faces && face < sm; face++)
                 arr[dice][sm] += arr[dice - 1][sm - face];
          }
      }
      return arr[num_of_dice][S];
}
int main()
{
      int num_of_dice = 2, num_of_faces = 6, sum = 5;
      int ans = get_ways(num_of_dice, num_of_faces, sum);
      printf("%d",ans);
      return 0;
}

a) 2
b) 3
c) 4
d) 5

Answer: c
Clarification: The output of the above code is 4.