# 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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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^{2})

d) O(S*N)

### View Answer

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^{2})

d) O(S*N)

### View Answer

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

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

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

## 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

### View Answer

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

### View Answer

3. The Data structure used in standard implementation of Breadth First Search is?

a) Stack

b) Queue

c) Linked List

d) None of the mentioned

### View Answer

4. The Depth First Search traversal of a graph will result into?

a) Linked List

b) Tree

c) Graph with back edges

d) None of the mentioned

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

## 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

### View Answer

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); head.setNext(temp); } else { Node cur = head.getNext(); temp.setNext(cur); head.setNext(temp); } size++; }

b)

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

c)

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

d) None of the mentioned

### View Answer

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

public void function(Object item) { Node temp=new Node(item,trail); if(isEmpty()) { head.setNext(temp); temp.setNext(trail); } else { Node cur=head.getNext(); 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

### View Answer

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

### View Answer

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(); head.setNext(cur); 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(); head.setNext(cur); 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(); head.setNext(temp); size--; return e; } }

d) None of the mentioned

### View Answer

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

### View Answer

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(n^{2})

### View Answer

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

### View Answer

## 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

### View Answer

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 head; protected Node tail; int length; public DLL() { head = new Node(Integer.MIN_VALUE,null,null); tail = new Node(Integer.MIN_VALUE,null,null); head.setNext(tail); 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++; }

### View Answer

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

### View Answer

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 { if(head == null) return; if(pos == 0) { head = head.getNext(); if(head == null) 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 { if(head == null) return; if(pos == 0) { head = head.getNext(); if(head == null) 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 { if(head == null) return; if(pos == 0) { head = head.getNext(); if(head == null) 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

### View Answer

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

### View Answer

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)

### View Answer

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); head.setNext(node); size++; }

b)

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

c)

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

d)

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

### View Answer

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); head.setNext(temp); temp.getNext().setPrev(temp); tail.setPrev(temp1); temp1.getPrev().setNext(temp1);

a) head-0-1-2-3-4-5-6-tail

b) head-1-2-3-4-5-6-tail

c) head-6-1-2-3-4-5-0-tail

d) head-0-1-2-3-4-5-tail

### View Answer

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

### View Answer

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()); head.setNext(temp); temp.getNext().setPrev(temp); Node temp1 = tail.getPrev(); tail.setPrev(temp1.getPrev()); temp1.getPrev().setNext(tail);

a) head-6-1-2-3-4-5-tail

b) head-6-1-2-3-4-tail

c) head-1-2-3-4-5-6-tail

d) head-1-2-3-4-5-tail

### View Answer

## 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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

6. A greedy algorithm can be used to solve all the dynamic programming problems.

a) True

b) False

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

10. Which of the following problems should be solved using dynamic programming?

a) Mergesort

b) Binary search

c) Longest common subsequence

d) Quicksort