Explore topic-wise InterviewSolutions in .

Right option is (B) 4

Easiest explanation - The empty STRING can be TRANSFORMED into “abcd” by inserting “a”, “b”, “c” and “d” at appropriate POSITIONS. Thus, the edit DISTANCE is 4.

The correct ANSWER is (B) 4

The best explanation: “monday” can be converted to “tuesday” by replacing “m” with “t”, “o” with “u”, “n” with “e” and inserting “s” at the APPROPRIATE position. So, the edit distance is 4.

Correct OPTION is (c) When the two STRINGS are equal

For EXPLANATION: The EDIT distance will be zero only when the two strings are equal.

The CORRECT choice is (d) APPROXIMATE string matching, Spelling Correction and Similarity of DNA

All of the MENTIONED are the APPLICATIONS of the edit distance problem.

The CORRECT CHOICE is (c) Both dynamic programming and recursion

Best explanation: Both dynamic programming and recursion can be USED to solve the edit DISTANCE problem.

Correct option is (B) 2D dynamic PROGRAMMING

For EXPLANATION: Longest PALINDROMIC SUBSEQUENCE is an example of 2D dynamic programming.

Correct ANSWER is (a) True

The explanation is: A single CHARACTER of any string can ALWAYS be considered as a palindrome and its length is ONE.

Correct option is (b) O(2^n)

The BEST I can explain: In the BRUTE force ALGORITHM, all the subsequences are found and the length of the longest palindromic subsequence is calculated. This takes exponential TIME.

The CORRECT choice is (d) Some strings of length two

The explanation is: A STRING of length 2 for EG: ab is not a PALINDROME.

Right option is (d) Dynamic programming, Recursion, Brute FORCE

Best explanation: Dynamic programming, Recursion, Brute force can be USED to solve the longest PALINDROMIC subsequence PROBLEM.

Right option is (d) fgmna

Easy explanation - The LENGTH of the longest COMMON SUBSEQUENCE is 4. But ‘fgmna’ is not the longest common subsequence as its length is 5.

The correct option is (C) 7

For EXPLANATION: The LONGEST common subsequence is “PRTPQRS” and its LENGTH is 7.

The CORRECT option is (c) Both recursion and dynamic programming

For EXPLANATION: Both recursion and dynamic programming can be used to SOLVE the longest SUBSEQUENCE PROBLEM.

The CORRECT option is (d) Exponential

Easy explanation - The time COMPLEXITY of finding all the possible WAYS of multiplying a set of n MATRICES is given by (n-1)^th Catalan NUMBER which is exponential.

Right answer is (a) 18000

Easy EXPLANATION - The MINIMUM number of multiplications are 18000. This is the case when the MATRICES are PARENTHESIZED as (P*Q)*R.

Right answer is (B) False

For EXPLANATION: The KNAPSACK problem cannot be solved using the greedy ALGORITHM.

Right option is (c) O(2^n)

The BEST explanation: In the brute FORCE algorithm all the subsets of the items are found and the value of each subset is CALCULATED. The subset of items with the maximum value and a weight less than EQUAL to the maximum allowed weight gives the answer. The time taken to calculate all the subsets is O(2^n).

Right option is (b) You are STUDYING for an exam and you have to study N questions. The questions take {t1, t2, t3,…., tn} time(in hours) and carry {m1, m2, m3,…., mn} marks. You can study for a MAXIMUM of T hours. You can either study a question or leave it. Choose the questions in such a way that your score is maximized

The best explanation: In this CASE, questions are used instead of ITEMS. Each question has a score which is same as each item having a value. Also, each question takes a time t which is same as each item having a weight W. You have to maximize the score in time T which is same as maximizing the value using a bag of weight W.

The correct choice is (d) Brute force, Recursion and DYNAMIC Programming

Easy explanation - Brute force, Recursion and Dynamic Programming can be used to SOLVE the knapsack PROBLEM.

Correct ANSWER is (B) False

Easy explanation - CONSIDER the array {1,0,2,3,4}.

In this case, only ONE element is 0 but it is not possible to REACH the end of the array.

Right answer is (a) True

Easy explanation - CONSIDER the array {1,2,3,4,5}. It is possible to REACH the end in the following ways: {1 -> 2 -> 3 -> 5} or {1 -> 2 -> 4 -> 5}.

In both the cases the NUMBER of jumps is 3, which is minimum. Hence, it is possible to reach the end of the array in MULTIPLE ways using minimum number of jumps.

Correct choice is (d) RECURSION and Dynamic PROGRAMMING

Easy explanation - Both recursion and dynamic programming can be used to SOLVE MINIMUM number of jumps problem.

Right CHOICE is (B) False

For explanation: Consider a rod of length 3. The PRICES are {2,3,6} for lengths {1,2,3} respectively. The pieces {1,1,1} and {3} both give the maximum value of 6.

Right choice is (d) O(2^n)

The explanation is: The BRUTE force IMPLEMENTATION FINDS all the possible cuts. This takes O(2^n) TIME.

Correct OPTION is (d) Brute force, Dynamic programming and RECURSION

To explain: Brute force, Dynamic programming and Recursion can be used to SOLVE the rod cutting PROBLEM.

The correct option is (d) O(2^N)

For EXPLANATION: The time REQUIRED to find all the SUBSEQUENCES of a given sequence is 2^n, where ‘n’ is the NUMBER of elements in the sequence. So, the time complexity is O(2^n).

Correct option is (b) False

To explain: For a GIVEN SEQUENCE, it is POSSIBLE that there is more than one subsequence with the longest length.

Consider, the following sequence: {10,11,12,1,2,3}:

There are two longest increasing subsequences: {1,2,3} and {10,11,12}.

The CORRECT choice is (d) Recursion, Dynamic PROGRAMMING, Brute force

The best explanation: The LONGEST increasing subsequence PROBLEM can be solved using all of the mentioned methods.

Right option is (b) O(n)

EASY explanation - The TIME complexity of Kadane’s algorithm is O(n) because there is only ONE for loop which scans the entire ARRAY EXACTLY once.

Correct option is (b) {-1,-2,-3}

The best I can explain: KADANE’s algorithm doesn’t work for all NEGATIVE NUMBERS. So, the ANSWER is {-1,-2,-3}.

Correct CHOICE is (d) {-4,-3,-2,-1}

The best I can explain: Kadane’s algorithm works if the INPUT array contains at least ONE non-negative ELEMENT. Every element in the array {-4,-3,-2,-1} is negative. Hence Kadane’s algorithm won’t work.

Right choice is (b) Dynamic PROGRAMMING

To explain: Kadane’s ALGORITHM USES dynamic programming.

The CORRECT choice is (C) MAXIMUM sub-array sum

For explanation: Kadane’s ALGORITHM is used to find the maximum sub-array sum for a GIVEN array.

The CORRECT OPTION is (b) O(1)

The best explanation: The DIVIDE and conquer algorithm USES a constant SPACE. So, the space complexity is O(1).

Right CHOICE is (C) O(nlogn)

Best explanation: The TIME complexity of the divide and CONQUER algorithm used to find the MAXIMUM sub-array sum is O(nlogn).

Right choice is (d) Dynamic programming, naïve METHOD and Divide and conquer methods

The BEST explanation: Dynamic programming, naïve method and Divide and conquer methods can be used to solve the maximum SUB ARRAY sum problem.