Explore topic-wise InterviewSolutions in .

Right answer is (a) NTH catalan NUMBER

Best EXPLANATION: The number of ways will be maximum when all the possible parenthesizations result in a TRUE value. The number of possible parenthesizations is GIVEN by the nth catalan number.

The CORRECT CHOICE is (d) nth catalan number

To explain: The nth Catalan number gives the total number of WAYS of parenthesizing an expression with n + 1 terms.

Right ANSWER is (c) 2

The EXPLANATION is: The EXPRESSION can be parenthesized as (T & F) ∧ TorT & (F ∧ T), so that the OUTPUT is T.

The correct choice is (c) 2

To EXPLAIN: The expression can be PARENTHESIZED as T & (F | T) and (T & F) | T so that the output is T.

The correct choice is (d) Dynamic programming, Recursion and Brute FORCE

Easiest EXPLANATION - Dynamic programming, Recursion and Brute force can be USED to SOLVE the Boolean parenthesization PROBLEM.

The CORRECT option is (c) n

Easiest EXPLANATION - The sum will be MINIMUM when all the FACES SHOW a value 1. The sum in this case will be n.

Correct choice is (c) 2

For EXPLANATION: The sum of 11 can be achieved when the dice show {6, 5} or {5, 6}.

The correct answer is (c) 216

Easy EXPLANATION - The TOTAL number of PERMUTATIONS that can be OBTAINED is 6 * 6 * 6 = 216.

Correct answer is (B) f*f*f…N times

The explanation is: Each die can take f values and there are n dice. So, the total NUMBER of permutations is f*f*f…n times.

The CORRECT OPTION is (d) Brute force, RECURSION and Dynamic Programming

The best I can explain: Brute force, Recursion and Dynamic Programming can be used to solve the DICE throw problem.

Right option is (a) 16

To EXPLAIN: The SUM of all the elements of the ARRAY is 32. So, the sum of all the elements of each partition should be 16.

Right choice is (d) {5, 3} & {4, 2, 1}

The best explanation: For S1 = {5, 3} and S2 = {4, 2, 1}, SUM(S1) – sum(S2) = 1, which is the OPTIMAL SOLUTION.

The correct choice is (C) When the sum of elements is odd

To explain: When the sum of all the elements is odd, it is not POSSIBLE to have TWO SUBSETS with EQUAL sum.

The correct CHOICE is (d) Dynamic programming, Recursion, Brute force

The best explanation: All of the mentioned METHODS can be USED to SOLVE the balanced partition PROBLEM.

The correct option is (c) KADANE’s ALGORITHM

The explanation is: The dynamic PROGRAMMING implementation of the MAXIMUM sum rectangle problem uses Kadane’s algorithm.

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

EASY explanation - The time complexity of the brute force IMPLEMENTATION of the maximum SUM RECTANGLE problem is O(n^4).

The correct choice is (C) 14

Easy explanation - The complete MATRIX REPRESENTS the maximum SUM rectangle and it’s sum is 14.

Correct option is (b) -1

The explanation is: Since all the ELEMENTS of the 2×2 matrix are NEGATIVE, the maximum SUM rectangle is {-1}, a 1×1 matrix containing the largest element. The sum of elements of the maximum sum rectangle is -1.

Right CHOICE is (a) True

The explanation is: If a matrix contains all non-zero ELEMENTS with at LEAST one positive and at least on negative element, then the sum of elements of the maximum sum RECTANGLE cannot be zero.

Right choice is (a) When all the elements are negative

To explain: When all the elements of a MATRIX are positive, the MAXIMUM sum RECTANGLE is the 2D matrix itself.

Right choice is (d) BRUTE force, RECURSION, Dynamic programming

The EXPLANATION is: Brute force, Recursion and Dynamic programming can be used to find the submatrix that has the maximum sum.

(d) Brute force, Recursion, Dynamic PROGRAMMING

Brute force, Recursion, and Dynamic programming can be USED to FIND the submatrix that has the maximum sum.

The CORRECT choice is (B) Longest COMMON subsequence PROBLEM

Easiest explanation - A variation of longest common subsequence can be used to solve the minimum number of insertions to FORM a palindrome problem.

The CORRECT answer is (a) 0

The best I can explain: The GIVEN string is ALREADY a palindrome. So, no INSERTIONS are REQUIRED.

Right option is (b) 1

Explanation: The STRING can be CONVERTED to “efgfe” by inserting “F” or to “egfge” by inserting “g”. Thus, only one insertion is REQUIRED.

The ANSWER is: 1

 The string can be converted to “efgfe” by INSERTING “f” or to “egfge” by inserting “g”. Thus, only ONE insertion is REQUIRED.

Correct choice is (b) False

The best explanation: In the worst case, the MINIMUM number of insertions to be made to CONVERT the STRING into a palindrome is equal to length of the string MINUS one. For example, consider the string “abc”. The string can be CONVERTED to “abcba” by inserting “a” and “b”. The number of insertions is two, which is equal to length minus one.

Right answer is (d) Non palindromic STRING

The best EXPLANATION: In string of length one, string with all same characters and a palindromic string the no of INSERTIONS is ZERO since the strings are already palindromes. To convert a non-palindromic string to a palindromic string, the minimum length of string to be added is 1 which is greater than all the other above cases. Hence the minimum no of insertions to form palindrome is maximum in non-palindromic strings.

The CORRECT answer is (d) Both recursion and DYNAMIC programming

Easy explanation - Dynamic programming and recursion can be USED to SOLVE the problem.

Right ANSWER is (b) O(n)

The explanation is: The SPACE COMPLEXITY of the above dynamic programming implementation of the assembly line scheduling problem is O(n).

The CORRECT option is (b) O(n)

To EXPLAIN: The time complexity of the above dynamic programming IMPLEMENTATION of the assembly line scheduling problem is O(n).

Right option is (c) 2

Best explanation: In the dynamic programming implementation of the assembly line scheduling problem, 2 lookup tables are required one for storing the MINIMUM time and the other for storing the assembly line NUMBER.

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

The BEST I can EXPLAIN: In the BRUTE force algorithm, all the possible ways are calculated which are of the order of 2^n.

Right CHOICE is (d) All of the mentioned

Easy EXPLANATION - All of the above mentioned methods can be USED to solve the assembly LINE scheduling PROBLEM.

The correct option is (a) DYNAMIC programming

The best I can explain: The space complexities are as FOLLOWS:

Dynamic programming: O(n)

RECURSION: O(1)

Binomial coefficients: O(1).

Correct option is (B) Binomial coefficients

For explanation: The time complexities are as follows:

DYNAMIC PROGRAMMING: O(n^2)

RECURSION: Exponential

Binomial coefficients: O(n).

The correct option is (d) RECURSION, Binomial Coefficients, DYNAMIC programming

The BEST I can explain: All of the mentioned methods can be used to FIND the NTH Catalan number.

Correct OPTION is (d) CREATION of head and tail for a given number of tosses

The best explanation: Counting the number of Dyck words, Counting the number of expressions containing n pairs of parenthesis, Counting the number of ways in which a convex POLYGON can be cut into triangles by connecting vertices with straight lines are the APPLICATIONS of Catalan numbers where as creation of head and tails for a given number of tosses is an application of Pascal’s TRIANGLE.

Right choice is (d) 43

The explanation is: Catalan NUMBERS are given by: (2N!)/((n+1)!n!).

For n = 0, we get C0 = 1.

For n = 3, we get C3 = 5.

For n = 4, we get C4 = 14.

For n = 5, we get C3 = 42.

Correct ANSWER is (C) O(mn)

Best EXPLANATION: The space complexity of the above Wagner–Fischer algorithm is O(mn).

The CORRECT ANSWER is (C) O(mn)

The BEST I can explain: The time complexity of the Wagner–Fischer algorithm is O(mn).

Right choice is (d) WEDNESDAY & thursday

The EXPLANATION is: The edit distances are 2, 4, 4 and 5 respectively. Hence, the MAXIMUM edit distance is between the strings wednesday and thursday.

Right choice is (b) 2

Easy explanation - The string “ABCD” can be changed to “acbd” by substituting “b” with “C” and “c” with “b”. THUS, the EDIT distance is 2.

Right choice is (c) Edit distance between TWO STRINGS

The explanation is: Wagner–Fischer ALGORITHM is USED to find the edit distance between two strings.