32 + Interview Questions in DATA-STRUCTURES-&-ALGORITHMS IN GENERAL AWARENESS Page 1 InterviewSolution

1.	What is the minimal Hamming distance between any two correct codewords?(a) 1(b) 2(c) 3(d) 4
Answer» The correct option is (c) 3 To explain: Since we use a generalized version of Hamming(7, 4) code, the minimal hamming distance is 3. It cannot correct burst errors.

Discussion

2.	What is the message length ‘k’ of a Hamming(7,4) code?(a) 2^r-1(b) 2^r-r+1(c) 2^r-r-1(d) 2^r+1-r
Answer» Right answer is (c) 2^r-r-1 Easiest explanation - Hamming codes are a class of binary linear codes, hence r>=2. For a hamming(7,4) code, the message length ‘k’ is 2^r-r-1 where r is the parity bit. Here, r=3.

Discussion

3.	What is the total block length ‘n’ of a Hamming code?(a) 2^r(b) 2^r-1(c) 2^r-1-1(d) 2^r+1
Answer» Correct option is (b) 2^r-1 The best I can explain: Hamming codes are a class of binary linear codes, hence r>=2. For a hamming(7, 4) code, the block length ‘n’ is 2^r-1 where r is the parity bit. Here, r=3.

Discussion

4.	Who invented Hamming codes?(a) Richard Hamming(b) Ross Hamming(c) Shannon(d) Huffman
Answer» Right choice is (a) Richard Hamming The best explanation: Richard W. Hamming invented hamming codes in Bell Telephone Laboratory to minimize the errors in punched card readers. Huffman invented huffman codes. Shannon invented Shannon-Fanno codes.

Discussion

5.	A two-out-of-five code consists of _________(a) Two 0s and three 1s(b) Three 0s and two 1s(c) Four 0s and one 1s(d) One 0s and four 1s
Answer» The correct option is (b) Three 0s and two 1s Best explanation: A two-out-of-five code consists of three 0s and two 1s. Hence, it contains ten possible combinations to represent digits from 0-9.

Discussion

6.	Halting problem is an example for?(a) decidable problem(b) undecidable problem(c) complete problem(d) trackable problem
Answer» Correct option is (b) undecidable problem Easiest explanation - Halting problem by Alan Turing cannot be solved by any algorithm. Hence, it is undecidable.

Discussion

7.	________ is the mechanism of sending data bits multiple times to ensure consistency.(a) Repetition(b) Duplication(c) Mirroring(d) Redundancy
Answer» Correct option is (a) Repetition The best I can explain: Repeating data bits multiple times is done to ensure consistency. If the data bit to be sent is a 1, a n=3 repetition code will send 111. If the bits are not the same, an error has occurred.

Discussion

8.	To which of the following class does a CNF-satisfiability problem belong?(a) NP class(b) P class(c) NP complete(d) NP hard
Answer» Correct choice is (c) NP complete The best explanation: The CNF satisfiability problem belongs to NP complete class. It deals with Boolean expressions.

Discussion

9.	How many steps are required to prove that a decision problem is NP complete?(a) 1(b) 2(c) 3(d) 4
Answer» Right option is (b) 2 Easiest explanation - First, the problem should be NP. Next, it should be proved that every problem in NP is reducible to the problem in question in polynomial time.

Discussion

10.	Problems that cannot be solved by any algorithm are called?(a) tractable problems(b) intractable problems(c) undecidable problems(d) decidable problems
Answer» Right answer is (c) undecidable problems The explanation is: Problems cannot be solved by any algorithm are called undecidable problems. Problems that can be solved in polynomial time are called Tractable problems.

Discussion

11.	How many conditions have to be met if an NP- complete problem is polynomially reducible?(a) 1(b) 2(c) 3(d) 4
Answer» The correct choice is (b) 2 To explain: A function t that maps all yes instances of decision problems D1 and D2 and t should be computed in polynomial time are the two conditions.

Discussion

12.	Problems that can be solved in polynomial time are known as?(a) intractable(b) tractable(c) decision(d) complete
Answer» The correct answer is (b) tractable The best I can explain: Problems that can be solved in polynomial time are known as tractable. Problems that cannot be solved in polynomial time are intractable.

Discussion

13.	How many stages of procedure does a non-deterministic algorithm consist of?(a) 1(b) 2(c) 3(d) 4
Answer» Correct option is (b) 2 The best I can explain: A non-deterministic algorithm is a two-stage procedure- guessing stage and verification stage.

Discussion

14.	What is meant by the power set of a set?(a) subset of all sets(b) set of all subsets(c) set of particular subsets(d) an empty set
Answer» The correct answer is (b) set of all subsets Easiest explanation - Power set of a set is defined as the set of all subsets. Ex- if there is a set S={1,3} then power set of set S will be P={{},{1},{3}{1,3}}.

Discussion

15.	The choice of polynomial class has led to the development of an extensive theory called ________(a) computational complexity(b) time complexity(c) problem complexity(d) decision complexity
Answer» Right choice is (a) computational complexity Easiest explanation - An extensive theory called computational complexity seeks to classify problems according to their inherent difficulty.

Discussion

16.	What is a subset sum problem?(a) finding a subset of a set that has sum of elements equal to a given number(b) checking for the presence of a subset that has sum of elements equal to a given number and printing true or false based on the result(c) finding the sum of elements present in a set(d) finding the sum of all the subsets of a set
Answer» The correct option is (b) checking for the presence of a subset that has sum of elements equal to a given number and printing true or false based on the result Best explanation: In subset sum problem check for the presence of a subset that has sum of elements equal to a given number. If such a subset is present then we print true otherwise false.

Discussion

17.	Who invented the inclusion-exclusion principle to solve the Hamiltonian path problem?(a) Karp(b) Leonard Adleman(c) Andreas Bjorklund(d) Martello
Answer» Correct option is (c) Andreas Bjorklund The best I can explain: Andreas Bjorklund came up with the inclusion-exclusion principle to reduce the counting of number of Hamiltonian cycles.

Discussion

18.	Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently?(a) branch and bound(b) iterative improvement(c) divide and conquer(d) greedy algorithm
Answer» Correct answer is (a) branch and bound For explanation: The Hamiltonian path problem can be solved efficiently using branch and bound approach. It can also be solved using a backtracking approach.

Discussion

19.	For a graph of degree three, in what time can a Hamiltonian path be found?(a) O(0.251^n)(b) O(0.401^n)(c) O(0.167^n)(d) O(0.151^n)
Answer» The correct answer is (a) O(0.251^n) Easy explanation - For a graph of maximum degree three, a Hamiltonian path can be found in time O(0.251^n).

Discussion

20.	How many Hamiltonian paths does the following graph have?(a) 1(b) 2(c) 0(d) 3
Answer» The correct option is (c) 0 The best I can explain: The above graph has no Hamiltonian paths. That is, we cannot traverse the graph with meeting vertices exactly once.

Discussion

21.	How many Hamiltonian paths does the following graph have?(a) 1(b) 2(c) 3(d) 4
Answer» The correct choice is (a) 1 Explanation: The above graph has only one Hamiltonian path that is from a-b-c-d-e.

Discussion

22.	Under what condition any set A will be a subset of B?(a) if all elements of set B are also present in set A(b) if all elements of set A are also present in set B(c) if A contains more elements than B(d) if B contains more elements than A
Answer» Right option is (b) if all elements of set A are also present in set B Easy explanation - Any set A will be called a subset of set B if all elements of set A are also present in set B. So in such a case set A will be a part of set B.

Discussion

23.	Which of the following problems is similar to that of a Hamiltonian path problem?(a) knapsack problem(b) closest pair problem(c) travelling salesman problem(d) assignment problem
Answer» Correct option is (c) travelling salesman problem Easy explanation - Hamiltonian path problem is similar to that of a travelling salesman problem since both the problem traverses all the nodes in a graph exactly once.

Discussion

24.	What is the time complexity for finding a Hamiltonian path for a graph having N vertices (using permutation)?(a) O(N!)(b) O(N! * N)(c) O(log N)(d) O(N)
Answer» Right choice is (b) O(N! * N) To explain: For a graph having N vertices traverse the permutations in N! iterations and it traverses the permutations to see if adjacent vertices are connected or not takes N iterations (i.e.) O(N! * N).

Discussion

25.	Hamiltonian path problem is _________(a) NP problem(b) N class problem(c) P class problem(d) NP complete problem
Answer» Correct choice is (d) NP complete problem The explanation is: Hamiltonian path problem is found to be NP complete. Hamiltonian cycle problem is also an NP- complete problem.

Discussion

26.	Who formulated the first ever algorithm for solving the Hamiltonian path problem?(a) Martello(b) Monte Carlo(c) Leonard(d) Bellman
Answer» The correct choice is (a) Martello For explanation: The first ever problem to solve the Hamiltonian path was the enumerative algorithm formulated by Martello.

Discussion

27.	Which of the following is true about the time complexity of the recursive solution of set partition problem?(a) It has an exponential time complexity(b) It has a linear time complexity(c) It has a logarithmic time complexity(d) it has a time complexity of O(n2)
Answer» The correct choice is (a) It has an exponential time complexity The explanation is: Set partition problem has both recursive as well as dynamic programming solution. The recursive solution has an exponential time complexity as it will require to check for all subsets in the worst case.

Discussion

28.	In what time can the Hamiltonian path problem can be solved using dynamic programming?(a) O(N)(b) O(N log N)(c) O(N^2)(d) O(N^2 2^N)
Answer» Correct option is (d) O(N^2 2^N) The best explanation: Using dynamic programming, the time taken to solve the Hamiltonian path problem is mathematically found to be O(N^2 2^N).

Discussion

29.	Which of the following is true about the time complexity of the recursive solution of the subset sum problem?(a) It has an exponential time complexity(b) It has a linear time complexity(c) It has a logarithmic time complexity(d) it has a time complexity of O(n2)
Answer» Correct option is (a) It has an exponential time complexity Easiest explanation - Subset sum problem has both recursive as well as dynamic programming solution. The recursive solution has an exponential time complexity as it will require to check for all subsets in worst case.

Discussion

30.	What is the set partition problem?(a) finding a subset of a set that has sum of elements equal to a given number(b) checking for the presence of a subset that has sum of elements equal to a given number(c) checking whether the set can be divided into two subsets of with equal sum of elements and printing true or false based on the result(d) finding subsets with equal sum of elements
Answer» The correct option is (c) checking whether the set can be divided into two subsets of with equal sum of elements and printing true or false based on the result Explanation: In set partition problem we check whether a set can be divided into 2 subsets such that the sum of elements in each subset is equal. If such subsets are present then we print true otherwise false.

Discussion

31.	The worst-case efficiency of solving a problem in polynomial time is?(a) O(p(n))(b) O(p( n log n))(c) O(p(n^2))(d) O(p(m log n))
Answer» Correct answer is (a) O(p(n)) The explanation is: The worst-case efficiency of solving an problem in polynomial time is O(p(n)) where p(n) is the polynomial time of input size.

Discussion

32.	What is the worst case time complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?(a) O(n)(b) O(sum)(c) O(n^2)(d) O(sum*n)
Answer» Right choice is (d) O(sumn) To explain: Set partition problem has both recursive as well as dynamic programming solution. The dynamic programming solution has a time complexity of O(nsum) as it as a nested loop with limits from 1 to n and 1 to sum respectively.

Discussion

Explore topic-wise InterviewSolutions in .

What is the minimal Hamming distance between any two correct codewords?(a) 1(b) 2(c) 3(d) 4

What is the message length ‘k’ of a Hamming(7,4) code?(a) 2^r-1(b) 2^r-r+1(c) 2^r-r-1(d) 2^r+1-r

What is the total block length ‘n’ of a Hamming code?(a) 2^r(b) 2^r-1(c) 2^r-1-1(d) 2^r+1

Who invented Hamming codes?(a) Richard Hamming(b) Ross Hamming(c) Shannon(d) Huffman

A two-out-of-five code consists of _________(a) Two 0s and three 1s(b) Three 0s and two 1s(c) Four 0s and one 1s(d) One 0s and four 1s

Halting problem is an example for?(a) decidable problem(b) undecidable problem(c) complete problem(d) trackable problem

________ is the mechanism of sending data bits multiple times to ensure consistency.(a) Repetition(b) Duplication(c) Mirroring(d) Redundancy

To which of the following class does a CNF-satisfiability problem belong?(a) NP class(b) P class(c) NP complete(d) NP hard

How many steps are required to prove that a decision problem is NP complete?(a) 1(b) 2(c) 3(d) 4

Problems that cannot be solved by any algorithm are called?(a) tractable problems(b) intractable problems(c) undecidable problems(d) decidable problems

How many conditions have to be met if an NP- complete problem is polynomially reducible?(a) 1(b) 2(c) 3(d) 4

Problems that can be solved in polynomial time are known as?(a) intractable(b) tractable(c) decision(d) complete

How many stages of procedure does a non-deterministic algorithm consist of?(a) 1(b) 2(c) 3(d) 4

What is meant by the power set of a set?(a) subset of all sets(b) set of all subsets(c) set of particular subsets(d) an empty set

The choice of polynomial class has led to the development of an extensive theory called ________(a) computational complexity(b) time complexity(c) problem complexity(d) decision complexity

Who invented the inclusion-exclusion principle to solve the Hamiltonian path problem?(a) Karp(b) Leonard Adleman(c) Andreas Bjorklund(d) Martello

Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently?(a) branch and bound(b) iterative improvement(c) divide and conquer(d) greedy algorithm

For a graph of degree three, in what time can a Hamiltonian path be found?(a) O(0.251^n)(b) O(0.401^n)(c) O(0.167^n)(d) O(0.151^n)

How many Hamiltonian paths does the following graph have?(a) 1(b) 2(c) 0(d) 3

How many Hamiltonian paths does the following graph have?(a) 1(b) 2(c) 3(d) 4

Under what condition any set A will be a subset of B?(a) if all elements of set B are also present in set A(b) if all elements of set A are also present in set B(c) if A contains more elements than B(d) if B contains more elements than A

Which of the following problems is similar to that of a Hamiltonian path problem?(a) knapsack problem(b) closest pair problem(c) travelling salesman problem(d) assignment problem

What is the time complexity for finding a Hamiltonian path for a graph having N vertices (using permutation)?(a) O(N!)(b) O(N! * N)(c) O(log N)(d) O(N)

Hamiltonian path problem is _________(a) NP problem(b) N class problem(c) P class problem(d) NP complete problem

Who formulated the first ever algorithm for solving the Hamiltonian path problem?(a) Martello(b) Monte Carlo(c) Leonard(d) Bellman

Which of the following is true about the time complexity of the recursive solution of set partition problem?(a) It has an exponential time complexity(b) It has a linear time complexity(c) It has a logarithmic time complexity(d) it has a time complexity of O(n2)

In what time can the Hamiltonian path problem can be solved using dynamic programming?(a) O(N)(b) O(N log N)(c) O(N^2)(d) O(N^2 2^N)

Which of the following is true about the time complexity of the recursive solution of the subset sum problem?(a) It has an exponential time complexity(b) It has a linear time complexity(c) It has a logarithmic time complexity(d) it has a time complexity of O(n2)

The worst-case efficiency of solving a problem in polynomial time is?(a) O(p(n))(b) O(p( n log n))(c) O(p(n^2))(d) O(p(m log n))

What is the worst case time complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?(a) O(n)(b) O(sum)(c) O(n^2)(d) O(sum*n)