Select Page
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages
Filter by Categories
nmims post
Objective Type Set
Online MCQ Assignment
Question Solution
Solved Question
Uncategorized

# Multiple choice question for engineering

## Set 1

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) All of the mentioned

Answer: b [Reason:] 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 [Reason:] 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 [Reason:] 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<stdio.h>
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 [Reason:] 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(N2)
d) O(S*N)

Answer: d [Reason:] 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(N2)
d) O(S*N)

Answer: b [Reason:] 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

Answer: c [Reason:] 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

Answer:b [Reason:] 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 [Reason:] 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 CAN be achieved using these coins?
a) 15
b) 16
c) 17
d) All of the mentioned

Answer: e [Reason:] Sums can be achieved as follows: 15 = {5,5,5} 16 = {3,3,5,5} 17 = {3,7,7} Thus, all the sums can be achieved.

11. What is the output of the following program?

```#include<stdio.h>
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 [Reason:] 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<stdio.h>
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 [Reason:] The program prints the minimum number of coins required to get a sum of 14, which is 4.

## Set 2

1. Depth First Search is equivalent to which of the traversal in the Binary Trees?
a) Pre-order Traversal
b) Post-order Traversal
c) Level-order Traversal
d) In-order Traversal

Answer: a [Reason:] In Depth First Search, we explore all the nodes aggressively to one path and then backtrack to the node. Hence, it is equivalent to the pre-order traversal of a Binary Tree.

2. Time Complexity of DFS is? (V – number of vertices, E – number of edges)
a) O(V + E)
b) O(V)
c) O(E)
d) None of the mentioned

Answer: a [Reason:] The Depth First Search explores every node once and every edge once (in worst case), so it’s time complexity is O(V + E).

3. The Data structure used in standard implementation of Breadth First Search is?
a) Stack
b) Queue
d) None of the mentioned

Answer: a [Reason:] The Depth First Search is implemented using recursion. So, stack can be used as data structure to implement depth first search.

4. The Depth First Search traversal of a graph will result into?
b) Tree
c) Graph with back edges
d) None of the mentioned

Answer: b [Reason:] The Depth First Search will make a graph which don’t have back edges (a tree) which is known as Depth First Tree.

5. A person wants to visit some places. He starts from a vertex and then wants to visit every vertex till it finishes from one vertex, backtracks and then explore other vertex from same vertex. What algorithm he should use?
a) Depth First Search
b) Breadth First Search
c) Trim’s algorithm
d) None of the mentioned

Answer: a [Reason:] This is the definition of the Depth First Search. Exploring a node, then aggressively finding nodes till it is not able to find any node.

6. What can be the applications of Depth First Search?
a) For generating topological sort of a graph
b) For generating Strongly Connected Components of a directed graph
c) Detecting cycles in the graph
d) All of the mentioned

Answer: d [Reason:] Depth First Search can be applied to all of the mentioned problems.

7. When the Depth First Search of a graph is unique?
a) When the graph is a Binary Tree
b) When the graph is a Linked List
c) When the graph is a n-ary Tree
d) None of the mentioned

Answer: b [Reason:] When Every node will have one successor then the Depth First Search is unique. In all other cases, when it will have more than one successor, it can choose any of them in arbitrary order.

8. Regarding implementation of Depth First Search using stacks, what is the maximum distance between two nodes present in the stack? (considering each edge length 1)
a) Can be anything
b) 0
c) At most 1
d) Insufficient Information

Answer: a [Reason:] In the stack, at a time, there can be nodes which can differ in many levels. So, it can be the maximum distance between two nodes in the graph.

9. In Depth First Search, how many times a node is visited?
a) Once
b) Twice
c) Equivalent to number of indegree of the node
d) None of the mentioned

Answer: c [Reason:] In Depth First Search, we have to see whether the node is visited or not by it’s ancestor. If it is visited, we won’t let it enter it in the stack.

## Set 3

1. What is a dequeue?
a) A queue with insert/delete defined for both front and rear ends of the queue
b) A queue implemented with a doubly linked list
c) A queue implemented with both singly and doubly linked lists
d) None of the mentioned

Answer: a [Reason:] A dequeue or a double ended queue is a queue with insert/delete defined for both front and rear ends of the queue.

2. Select the function which performs insertion at the front end of the dequeue?
a)

```public void function(Object item)
{
Node temp = new Node(item,null);
if(isEmpty())
{
temp.setNext(trail);
}
else
{
Node cur = head.getNext();
temp.setNext(cur);
}
size++;
}```

b)

```public void function(Object item)
{
Node temp = new Node(item,null);
if(isEmpty())
{
temp.setNext(trail);
}
else
{
Node cur = head.getNext();
temp.setNext(cur);
}
size++;
}```

c)

```public void function(Object item)
{
Node temp = new Node(item,null);
if(isEmpty())
{
Node cur = head.getNext();
temp.setNext(cur);
}
else
{
temp.setNext(trail);
}
size++;
}```

d) None of the mentioned

Answer: a [Reason:] Create a new node, if the current list is empty, the ‘head’ points to this node and this new node points to ‘trail’. Otherwise, ‘head’ points to the new node and this in turn points to the current first element(head.getNext()).

3. What is the functionality of the following piece of code?

```public void function(Object item)
{
Node temp=new Node(item,trail);
if(isEmpty())
{
temp.setNext(trail);
}
else
{
while(cur.getNext()!=trail)
{
cur=cur.getNext();
}
cur.setNext(temp);
}
size++;
}```

a) Insert at the front end of the dequeue
b) Insert at the rear end of the dequeue
c) Fetch the element at the rear end of the dequeue
d) Fetch the element at the front end of the dequeue

Answer: b [Reason:] If the list is empty, this new node will point to ‘trail’ and will be pointed at by ‘head’. Otherwise, traverse till the end of the list and insert the new node there.

4. What are the applications of dequeue?
a) A-Steal job scheduling algorithm
b) Can be used as both stack and queue
c) To find the maximum of all sub arrays of size k
d) All of the mentioned

Answer: d [Reason:] All of the mentioned can be implemented with a dequeue.

5. Which of the following can be used to delete an element from the front end of the queue?
a)

```public Object deleteFront() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = temp;
Object e = temp.getEle();
size--;
return e;
}
}```

b)

```public Object deleteFront() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = temp.getNext();
Object e = temp.getEle();
size--;
return e;
}
}```

c)

```public Object deleteFront() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = temp.getNext();
Object e = temp.getEle();
size--;
return e;
}
}```

d) None of the mentioned

Answer: b [Reason:] Have two pointers, one(temp) pointing to the first element and the other(cur) pointing to the second element. Make the ‘head’ point to the second element, this removes all reference for ‘temp’.

6. Which of the following can be used to delete an element from the rear end of the queue?
a)

```public Object deleteRear() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = temp;
while(temp.getNext() != trail)
{
temp = temp.getNext();
cur = cur.getNext();
}
Object e = temp.getEle();
cur.setNext(trail);
size--;
return e;
}
}```

b)

```public Object deleteRear() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = head;
while(temp != trail)
{
temp = temp.getNext();
cur = cur.getNext();
}
Object e = temp.getEle();
cur.setNext(trail);
size--;
return e;
}
}```

c)

```public Object deleteRear() throws emptyDEQException
{
if(isEmpty())
throw new emptyDEQException("Empty");
else
{
Node temp = head.getNext();
Node cur = head;
while(temp.getNext()!=trail)
{
temp = temp.getNext();
cur = cur.getNext();
}
Object e = temp.getEle();
cur.setNext(trail);
size--;
return e;
}
}```

d) None of the mentioned

Answer: c [Reason:] Traverse till the end of the list with a pointer ‘temp’ and another ‘cur’ which is trailing behind temp, make ‘cur’ point to trail, this removes all reference for ‘temp’.

7. What is the time complexity of deleting from the rear end of the dequeue implemented with a singly linked list?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

Answer: c [Reason:] Since a singly linked list is used, first you have to traverse till the end, so the complexity is O(n).

8. After performing these set of operations, what does the final list look contain?

```InsertFront(10);
InsertFront(20);
InsertRear(30);
DeleteFront();
InsertRear(40);
InsertRear(10);
DeleteRear();
InsertRear(15);
display();```

a) 10 30 10 15
b) 20 30 40 15
c) 20 30 40 10
d) 10 30 40 15

Answer: d [Reason:] A careful tracing of the given operation yields the result. 10 20 10 20 10 30 10 30 10 30 40 10 30 40 10 10 30 40 10 30 40 15

## Set 4

1. Which of the following is false about a doubly linked list?
a) We can navigate in both the directions
b) It requires more space than a singly linked list
c) The insertion and deletion of a node take a bit longer
d) None of the mentioned

Answer: d [Reason:] A doubly linked list has two pointers ‘left’ and ‘right’ which enable it to traverse in either direction. Compared to singly liked list which has only a ‘next’ pointer, doubly linked list requires extra space to store this extra pointer. Every insertion and deletion requires manipulation of two pointers, hence it takes a bit longer time.

2. Given the Node class implementation, select one of the following that correctly inserts a node at the tail of the list.

```public class Node
{
protected int data;
protected Node prev;
protected Node next;
public Node(int data)
{
this.data = data;
prev = null;
next = null;
}
public Node(int data, Node prev, Node next)
{
this.data = data;
this.prev = prev;
this.next = next;
}
public int getData()
{
return data;
}
public void setData(int data)
{
this.data = data;
}
public Node getPrev()
{
return prev;
}
public void setPrev(Node prev)
{
this.prev = prev;
}
public Node getNext
{
return next;
}
public void setNext(Node next)
{
this.next = next;
}
}
public class DLL
{
protected Node tail;
int length;
public DLL()
{
head = new Node(Integer.MIN_VALUE,null,null);
tail = new Node(Integer.MIN_VALUE,null,null);
length = 0;
}
}```

a)

```public void insertRear(int data)
{
Node node = new Node(data,tail.getPrev(),tail);
node.getPrev().setNext(node);
tail.setPrev(node);
length++;
}```

b)

```public void insertRear(int data)
{
Node node = new Node(data,tail.getPrev(),tail);
node.getPrev().getPrev().setNext(node);
tail.setPrev(node);
length++;
}```

c)

```public void insertRear(int data)
{
Node node = new Node(data,tail.getPrev(),tail);
node.getPrev().setNext(tail);
tail.setPrev(node);
length++;
}```

d)

```public void insertRear(int data)
{
Node node = new Node(data,head,tail);
node.getPrev().setNext(node);
tail.setPrev(node);
length++;
}```

Answer: a [Reason:] First create a new node whose ‘prev’ points to the node pointed to by the ‘prev’ of tail. The ‘next’ of the new node should point to tail. Set the ‘prev’ of tail to point to new node and the ‘prev’ of new node to point to the new node.

3. What is a memory efficient double linked list?
a) Each node has only one pointer to traverse the list back and forth
b) The list has breakpoints for faster traversal
c) An auxiliary singly linked list acts as a helper list to traverse through the doubly linked list
d) None of the mentioned

Answer: a [Reason:] Memory efficient doubly linked list has been proposed recently which has only one pointer to traverse the list back and forth. The implementation is based on pointer difference.

4. Which of the following piece of code removes the node from a given position?
a)

```public void remove(int pos)
{
if(pos<0 || pos>=size)
{
System.out.println("Invalid position");
return;
}
else
{
return;
if(pos == 0)
{
tail = null;
}
else
{
Node temp = head;
for(int i=1; i<position; i++)
temp = temp.getNext();
}
temp.getNext().setPrev(temp.getPrev());
temp.getPrev().setNext(temp.getNext());
}
size--;
}```

b)

```public void remove(int pos)
{
if(pos<0 || pos>=size)
{
System.out.println("Invalid position");
return;
}
else
{
return;
if(pos == 0)
{
tail = null;
}
else
{
Node temp = head;
for(int i=1; i<position; i++)
temp = temp.getNext();
}
temp.getNext().setPrev(temp.getNext());
temp.getPrev().setNext(temp.getPrev());
}
size--;
}```

c)

```public void remove(int pos)
{
if(pos<0 || pos>=size)
{
System.out.println("Invalid position");
return;
}
else
{
return;
if(pos == 0)
{
tail = null;
}
else
{
Node temp = head;
for(int i=1; i<position; i++)
temp = temp.getNext().getNext();
}
temp.getNext().setPrev(temp.getPrev());
temp.getPrev().setNext(temp.getNext());
}
size--;
}```

d) None of the mentioned

Answer: a [Reason:] If the position to be deleted is not the head, advance to the given position and manipulate the previous and next pointers of next and previous nodes respectively.

5. How do you calculate the pointer difference in a memory efficient double linked list?
a) head xor tail
b) pointer to previous node xor pointer to next node
c) pointer to previous node – pointer to next node
d) pointer to next node – pointer to previous node

Answer: b [Reason:] The pointer difference is calculated using option b.

6. What is the time complexity of inserting a node in a doubly linked list?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(1)

Answer: c [Reason:] In the worst case, the position to be inserted maybe at the end of the list, hence you have to traverse through the entire list to get to the correct position, hence O(n).

7. How do you insert a node at the beginning of the list?
a)

```public class insertFront(int data)
{
Node node = new Node(data, head, head.getNext());
node.getNext().setPrev(node);
size++;
}```

b)

```public class insertFront(int data)
{
Node node = new Node(data, head, head);
node.getNext().setPrev(node);
size++;
}```

c)

```public class insertFront(int data)
{
Node node = new Node(data, head, head.getNext());
size++;
}```

d)

```public class insertFront(int data)
{
Node node = new Node(data, head, head.getNext());
node.getNext().setPrev(node);
size++;
}```

Answer: a [Reason:] The new node’s previous pointer will point to head and next pointer will point to the current next of head.

8. Consider the following doubly linked list: head-1-2-3-4-5-tail
What will be the list after performing the given sequence of operations?

```	Node temp = new Node(6,head,head.getNext());
Node temp1 = new Node(0,tail.getPrev(),tail);
temp.getNext().setPrev(temp);
tail.setPrev(temp1);
temp1.getPrev().setNext(temp1);```

Answer: c [Reason:] The given sequence of operations perform addition of nodes at the head and tail of the list.

9. What is the functionality of the following piece of code?

```public int function()
{
Node temp = tail.getPrev();
tail.setPrev(temp.getPrev());
temp.getPrev().setNext(tail);
size--;
return temp.getItem();
}```

a) Return the element at the tail of the list but do not remove it
b) Return the element at the tail of the list and remove it from the list
c) Return the last but one element from the list but do not remove it
d) Return the last but one element at the tail of the list and remove it from the list

Answer: b [Reason:] The previous and next pointers of the tail and the last but one element are manipulated, this suggests that the last node is being removed from the list.

10. Consider the following doubly linked list: head-1-2-3-4-5-tail
What will be the list after performing the given sequence of operations?

```	Node temp = new Node(6,head,head.getNext());
temp.getNext().setPrev(temp);
Node temp1 = tail.getPrev();
tail.setPrev(temp1.getPrev());
temp1.getPrev().setNext(tail);```

Answer: b [Reason:] A new node is added to the head of the list and a node is deleted from the tail end of the list.

## Set 5

1. Which of the following is/are property/properties of a dynamic programming problem?
a) Optimal substructure
b) Overlapping subproblems
c) Greedy approach
d) Both optimal substructure and overlapping subproblems

Answer: d [Reason:] A problem that can be solved using dynamic programming possesses overlapping subproblems as well as optimal substructure properties.

2. If an optimal solution can be created for a problem by constructing optimal solutions for its subproblems, the problem possesses ____________ property.
a) Overlapping subproblems
b) Optimal substructure
c) Memoization
d) Greedy

Answer: b [Reason:] Optimal substructure is the property in which an optimal solution is found for the problem by constructing optimal solutions for the subproblems.

3. If a problem can be broken into subproblems which are reused several times, the problem possesses ____________ property.
a) Overlapping subproblems
b) Optimal substructure
c) Memoization
d) Greedy

Answer: a [Reason:] Overlapping subproblems is the property in which value of a subproblem is used several times.

4. If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called _____________
a) Dynamic programming
b) Greedy
c) Divide and conquer
d) Recursion

Answer: c [Reason:] In divide and conquer, the problem is divided into smaller non-overlapping subproblems and an optimal solution for each of the subproblems is found. The optimal solutions are then combined to get a global optimal solution. For example, mergesort uses divide and conquer strategy.

5. When dynamic programming is applied to a problem, it takes far less time as compared to other methods that don’t take advantage of overlapping subproblems.
a) True
b) False

Answer: a [Reason:] Dynamic programming calculates the value of a subproblem only once, while other methods that don’t take advantage of the overlapping subproblems property may calculate the value of the same subproblem several times. So, dynamic programming saves the time of recalculation and takes far less time as compared to other methods that don’t take advantage of the overlapping subproblems property.

6. A greedy algorithm can be used to solve all the dynamic programming problems.
a) True
b) False

Answer: b [Reason:] A greedy algorithm gives optimal solution for all subproblems, but when these locally optimal solutions are combined it may NOT result into a globally optimal solution. Hence, a greedy algorithm CANNOT be used to solve all the dynamic programming problems.

7. In dynamic programming, the technique of storing the previously calculated values is called ___________
a) Saving value property
b) Storing value property
c) Memoization
d) Mapping

Answer: c [Reason:] Memoization is the technique in which previously calculated values are stored, so that, these values can be used to solve other subproblems.

8. When a top-down approach of dynamic programming is applied to a problem, it usually _____________
a) Decreases both, the time complexity and the space complexity
b) Decreases the time complexity and increases the space complexity
c) Increases the time complexity and decreases the space complexity
d) Increases both, the time complexity and the space complexity

Answer: b [Reason:] The top-down approach uses the memoization technique which stores the previously calculated values. Due to this, the time complexity is decreased but the space complexity is increased.

9. Which of the following problems is NOT solved using dynamic programming?
a) 0/1 knapsack problem
b) Matrix chain multiplication problem
c) Edit distance problem
d) Fractional knapsack problem