23 + Interview Questions in Greedy Algorithms in Data Structures & Algorithms Ii Page 1 InterviewSolution

1.	How many printable characters does the ASCII character set consists of?(a) 120(b) 128(c) 100(d) 98I have been asked this question in an interview for internship.The doubt is from Greedy Algorithms topic in chapter Greedy Algorithms of Data Structures & Algorithms II
Answer» Right ANSWER is (C) 100 Best explanation: Out of 128 characters in an ASCII SET, roughly, only 100 characters are PRINTABLE while the rest are non-printable.

Discussion

2.	What is the running time of the Huffman algorithm, if its implementation of the priority queue is done using linked lists?(a) O(C)(b) O(log C)(c) O(C log C)(d) O(C^2)The question was posed to me in a national level competition.This intriguing question originated from Greedy Algorithms in division Greedy Algorithms of Data Structures & Algorithms II
Answer» Correct answer is (d) O(C^2) The EXPLANATION is: If the implementation of the PRIORITY QUEUE is done using LINKED lists, the running time of HUFFMAN algorithm is O(C^2).

Discussion

3.	What is the running time of the Huffman encoding algorithm?(a) O(C)(b) O(log C)(c) O(C log C)(d) O( N log C)This question was addressed to me during a job interview.This intriguing question originated from Greedy Algorithms in chapter Greedy Algorithms of Data Structures & Algorithms II
Answer» Correct option is (c) O(C log C) The BEST EXPLANATION: If we MAINTAIN the trees in a priority queue, ordered by weight, then the RUNNING time is GIVEN by O(C log C).

Discussion

4.	The type of encoding where no character code is the prefix of another character code is called?(a) optimal encoding(b) prefix encoding(c) frequency encoding(d) trie encodingThis question was posed to me in a job interview.My query is from Greedy Algorithms topic in section Greedy Algorithms of Data Structures & Algorithms II
Answer» Right answer is (B) PREFIX encoding Explanation: Even if the CHARACTER CODES are of different lengths, the encoding where no character code is the prefix of another character code is CALLED prefix encoding.

Discussion

5.	An optimal code will always be present in a full tree.(a) true(b) falseI had been asked this question at a job interview.The origin of the question is Greedy Algorithms in division Greedy Algorithms of Data Structures & Algorithms II
Answer» Right choice is (a) true The BEST explanation: An OPTIMAL TREE will always have the property that all nodes are either leaves or have two children. Otherwise, nodes with ONE child could move up a level.

Discussion

6.	What will be the cost of the code if character ci is at depth di and occurs at frequency fi?(a) cifi(b) ∫cifi(c) ∑fidi(d) fidiThe question was asked during an interview.The query is from Greedy Algorithms topic in chapter Greedy Algorithms of Data Structures & Algorithms II
Answer» The correct choice is (C) ∑fidi The best I can EXPLAIN: If character ci is at depth DI and occurs at FREQUENCY fi, the cost of the codeword obtained is ∑fidi.

Discussion

7.	From the following given tree, what is the computed codeword for ‘c’?(a) 111(b) 101(c) 110(d) 011I got this question in an interview for job.This intriguing question comes from Greedy Algorithms in division Greedy Algorithms of Data Structures & Algorithms II
Answer» CORRECT answer is (c) 110 Explanation: By recording the path of the node from root to leaf, ASSIGNING left branch as 0 and RIGHT branch as 1, the codeword for c is 110.

Discussion

8.	From the following given tree, what is the code word for the character ‘a’?(a) 011(b) 010(c) 100(d) 101This question was posed to me in exam.This intriguing question originated from Greedy Algorithms topic in chapter Greedy Algorithms of Data Structures & Algorithms II
Answer» Right CHOICE is (a) 011 The best I can explain: By RECORDING the path of the node from root to leaf, the code WORD for character ‘a’ is found to be 011.

Discussion

9.	The code length does not depend on the frequency of occurrence of characters.(a) true(b) falseI got this question in final exam.The question is from Greedy Algorithms in section Greedy Algorithms of Data Structures & Algorithms II
Answer» Right option is (B) false Best explanation: The code length DEPENDS on the frequency of occurrence of characters. The more FREQUENT the CHARACTER OCCURS, the less is the length of the code.

Discussion

10.	In Huffman coding, data in a tree always occur?(a) roots(b) leaves(c) left sub trees(d) right sub treesThis question was posed to me in semester exam.The origin of the question is Greedy Algorithms in chapter Greedy Algorithms of Data Structures & Algorithms II
Answer» CORRECT ANSWER is (b) leaves Easiest explanation - In Huffman ENCODING, data is always stored at the leaves of a tree inorder to COMPUTE the codeword EFFECTIVELY.

Discussion

11.	How many bits are needed for standard encoding if the size of the character set is X?(a) log X(b) X+1(c) 2X(d) X^2The question was posed to me in an online interview.Origin of the question is Greedy Algorithms in section Greedy Algorithms of Data Structures & Algorithms II
Answer» Correct answer is (a) LOG X Easy explanation - If the size of the CHARACTER set is X, then [log X] BITS are needed for REPRESENTATION in a standard encoding.

Discussion

12.	Which bit is reserved as a parity bit in an ASCII set?(a) first(b) seventh(c) eighth(d) tenthThe question was posed to me by my college professor while I was bunking the class.This is a very interesting question from Greedy Algorithms topic in chapter Greedy Algorithms of Data Structures & Algorithms II
Answer» The correct ANSWER is (c) eighth The best I can explain: In an ASCII character set, seven BITS are RESERVED for character REPRESENTATION while the eighth bit is a parity bit.

Discussion

13.	Which of the following algorithms is the best approach for solving Huffman codes?(a) exhaustive search(b) greedy algorithm(c) brute force algorithm(d) divide and conquer algorithmI had been asked this question by my school teacher while I was bunking the class.Query is from Greedy Algorithms topic in division Greedy Algorithms of Data Structures & Algorithms II
Answer» The CORRECT answer is (B) greedy ALGORITHM Easy explanation - Greedy algorithm is the best approach for solving the Huffman codes problem since it GREEDILY SEARCHES for an optimal solution.

Discussion

14.	Given items as {value,weight} pairs {{60,20},{50,25},{20,5}}. The capacity of knapsack=40. Find the maximum value output assuming items to be divisible and nondivisible respectively.(a) 100, 80(b) 110, 70(c) 130, 110(d) 110, 80I got this question in an online quiz.Question is taken from Greedy Algorithms in portion Greedy Algorithms of Data Structures & Algorithms II
Answer» CORRECT OPTION is (d) 110, 80 The best I can EXPLAIN: Assuming items to be divisible- The value/weight ratio are {3, 2, 4}.So we include third and first items wholly. So, now only 15 units of volume are left for SECOND item. So we include it partially. Final volume = 20+60+50x(15/25)=80+30=110 Assuming items to be indivisible- In this case we will have to leave ONE item due to insufficient capacity. Final volume = 60 + 20 = 80.

Discussion

15.	The result of the fractional knapsack is greater than or equal to 0/1 knapsack.(a) True(b) FalseI got this question in an interview for internship.Question is taken from Greedy Algorithms in portion Greedy Algorithms of Data Structures & Algorithms II
Answer» Correct choice is (a) True To explain: As fractional knapsack GIVES extra liberty to include the object PARTIALLY which is not possible with 0/1 knapsack, thus we get better RESULTS with a fractional knapsack.

Discussion

16.	The main time taking step in fractional knapsack problem is ___________(a) Breaking items into fraction(b) Adding items into knapsack(c) Sorting(d) Looping through sorted itemsThis question was posed to me in homework.My question comes from Greedy Algorithms topic in division Greedy Algorithms of Data Structures & Algorithms II
Answer» The CORRECT option is (c) Sorting Explanation: The main time TAKING STEP is to sort the ITEMS according to their value/weight ratio. It DEFINES the time complexity of the code.

Discussion

17.	Given items as {value,weight} pairs {{40,20},{30,10},{20,5}}. The capacity of knapsack=20. Find the maximum value output assuming items to be divisible.(a) 60(b) 80(c) 100(d) 40The question was posed to me in an internship interview.I want to ask this question from Greedy Algorithms in division Greedy Algorithms of Data Structures & Algorithms II
Answer» CORRECT answer is (a) 60 Easiest explanation - The value/weight ratio are-{2,3,4}. So we include the SECOND and THIRD items wholly into the knapsack. This LEAVES only 5 units of volume for the first item. So we include the first item partially. Final value = 20+30+(40/4)=60.

Discussion

18.	Fractional knapsack problem can be solved in time O(n).(a) True(b) FalseI got this question during an online interview.Enquiry is from Greedy Algorithms in section Greedy Algorithms of Data Structures & Algorithms II
Answer» The CORRECT choice is (a) True The best I can explain: It is possible to solve the problem in O(n) TIME by ADAPTING the ALGORITHM for finding weighted MEDIANS.

Discussion

19.	Time complexity of fractional knapsack problem is ____________(a) O(n log n)(b) O(n)(c) O(n^2)(d) O(nW)This question was posed to me in semester exam.I need to ask this question from Greedy Algorithms in section Greedy Algorithms of Data Structures & Algorithms II
Answer» Correct answer is (a) O(n log n) The best I can explain: As the main TIME taking a step is of sorting so it DEFINES the time complexity of our code. So the time complexity will be O(n log n) if we USE QUICK sort for sorting.

Discussion

20.	Which of the following statement about 0/1 knapsack and fractional knapsack problem is correct?(a) In 0/1 knapsack problem items are divisible and in fractional knapsack items are indivisible(b) Both are the same(c) 0/1 knapsack is solved using a greedy algorithm and fractional knapsack is solved using dynamic programming(d) In 0/1 knapsack problem items are indivisible and in fractional knapsack items are divisibleThe question was asked by my school teacher while I was bunking the class.The query is from Greedy Algorithms in portion Greedy Algorithms of Data Structures & Algorithms II
Answer» Correct ANSWER is (d) In 0/1 knapsack problem items are indivisible and in fractional knapsack items are divisible The EXPLANATION is: In fractional knapsack problem we can partially include an item into the knapsack WHEREAS in 0/1 knapsack we have to EITHER include or exclude the item wholly.

Discussion

21.	What is the objective of the knapsack problem?(a) To get maximum total value in the knapsack(b) To get minimum total value in the knapsack(c) To get maximum weight in the knapsack(d) To get minimum weight in the knapsackI have been asked this question in an interview for internship.Enquiry is from Greedy Algorithms topic in section Greedy Algorithms of Data Structures & Algorithms II
Answer» Correct ANSWER is (a) To get MAXIMUM total value in the knapsack Explanation: The objective is to fill the knapsack of some GIVEN volume with different materials such that the value of SELECTED ITEMS is maximized.

Discussion

22.	Fractional knapsack problem is solved most efficiently by which of the following algorithm?(a) Divide and conquer(b) Dynamic programming(c) Greedy algorithm(d) BacktrackingI have been asked this question in semester exam.My doubt is from Greedy Algorithms topic in division Greedy Algorithms of Data Structures & Algorithms II
Answer» The CORRECT answer is (C) Greedy algorithm Easy EXPLANATION - Greedy algorithm is used to solve this problem. We first sort items ACCORDING to their value/weight ratio and then add item with highest ratio until we cannot add the next item as a whole. At the end, we add the next item as much as we can.

Discussion

23.	Fractional knapsack problem is also known as __________(a) 0/1 knapsack problem(b) Continuous knapsack problem(c) Divisible knapsack problem(d) Non continuous knapsack problemI have been asked this question during an online exam.The query is from Greedy Algorithms in portion Greedy Algorithms of Data Structures & Algorithms II
Answer» Right answer is (B) CONTINUOUS knapsack problem For explanation: Fractional knapsack problem is also CALLED continuous knapsack problem. Fractional knapsack is solved using dynamic programming.

Discussion

Explore topic-wise InterviewSolutions in .

How many printable characters does the ASCII character set consists of?(a) 120(b) 128(c) 100(d) 98I have been asked this question in an interview for internship.The doubt is from Greedy Algorithms topic in chapter Greedy Algorithms of Data Structures & Algorithms II

What is the running time of the Huffman encoding algorithm?(a) O(C)(b) O(log C)(c) O(C log C)(d) O( N log C)This question was addressed to me during a job interview.This intriguing question originated from Greedy Algorithms in chapter Greedy Algorithms of Data Structures & Algorithms II

An optimal code will always be present in a full tree.(a) true(b) falseI had been asked this question at a job interview.The origin of the question is Greedy Algorithms in division Greedy Algorithms of Data Structures & Algorithms II

What will be the cost of the code if character ci is at depth di and occurs at frequency fi?(a) cifi(b) ∫cifi(c) ∑fidi(d) fidiThe question was asked during an interview.The query is from Greedy Algorithms topic in chapter Greedy Algorithms of Data Structures & Algorithms II

From the following given tree, what is the computed codeword for ‘c’?(a) 111(b) 101(c) 110(d) 011I got this question in an interview for job.This intriguing question comes from Greedy Algorithms in division Greedy Algorithms of Data Structures & Algorithms II

From the following given tree, what is the code word for the character ‘a’?(a) 011(b) 010(c) 100(d) 101This question was posed to me in exam.This intriguing question originated from Greedy Algorithms topic in chapter Greedy Algorithms of Data Structures & Algorithms II

The code length does not depend on the frequency of occurrence of characters.(a) true(b) falseI got this question in final exam.The question is from Greedy Algorithms in section Greedy Algorithms of Data Structures & Algorithms II

In Huffman coding, data in a tree always occur?(a) roots(b) leaves(c) left sub trees(d) right sub treesThis question was posed to me in semester exam.The origin of the question is Greedy Algorithms in chapter Greedy Algorithms of Data Structures & Algorithms II

How many bits are needed for standard encoding if the size of the character set is X?(a) log X(b) X+1(c) 2X(d) X^2The question was posed to me in an online interview.Origin of the question is Greedy Algorithms in section Greedy Algorithms of Data Structures & Algorithms II

The result of the fractional knapsack is greater than or equal to 0/1 knapsack.(a) True(b) FalseI got this question in an interview for internship.Question is taken from Greedy Algorithms in portion Greedy Algorithms of Data Structures & Algorithms II

Fractional knapsack problem can be solved in time O(n).(a) True(b) FalseI got this question during an online interview.Enquiry is from Greedy Algorithms in section Greedy Algorithms of Data Structures & Algorithms II

Time complexity of fractional knapsack problem is ____________(a) O(n log n)(b) O(n)(c) O(n^2)(d) O(nW)This question was posed to me in semester exam.I need to ask this question from Greedy Algorithms in section Greedy Algorithms of Data Structures & Algorithms II