Explore topic-wise InterviewSolutions in .

Right answer is (d) 4

The EXPLANATION is: 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.

Right CHOICE is (C) 13

Easiest explanation - 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.

Correct option is (B) 2

The BEST explanation: A SUM of 7 can be ACHIEVED by using a minimum of two COINS {3,4}.

Correct answer is (C) 5

Explanation: 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.

The correct CHOICE is (b) O(S)

For explanation: 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).

(d) O(S*N)

The TIME COMPLEXITY is O(S*N).

Correct CHOICE is (d) 100

The best I can explain: 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}.

The CORRECT option is (c) 6

Explanation: 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}.

The correct option is (b) Dynamic programming

Best EXPLANATION: 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.

The correct answer is (c) Longest common subsequence

For EXPLANATION: The longest common subsequence problem has both, optimal substructure and OVERLAPPING subproblems. Hence, DYNAMIC PROGRAMMING should be used the solve this problem.

The correct option is (d) Fractional KNAPSACK PROBLEM

Best explanation: The fractional knapsack problem is SOLVED using a GREEDY algorithm.

Right answer is (B) Decreases the time complexity and increases the SPACE complexity

The explanation is: 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.

Correct choice is (c) Memoization

Best explanation: Memoization is the TECHNIQUE in which previously CALCULATED values are stored, so that, these values can be USED to solve other SUBPROBLEMS.

Correct option is (b) False

The EXPLANATION is: 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.

Right choice is (a) True

The best EXPLANATION: 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.

Right choice is (c) DIVIDE and conquer

Best explanation: 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.

Correct answer is (a) OVERLAPPING subproblems

The best I can explain: Overlapping subproblems is the PROPERTY in which VALUE of a subproblem is used SEVERAL TIMES.

The correct OPTION is (b) Optimal substructure

Easiest explanation - Optimal substructure is the property in which an optimal solution is FOUND for the problem by CONSTRUCTING optimal SOLUTIONS for the SUBPROBLEMS.