Explore topic-wise InterviewSolutions in .

Right option is (a) Hashing

Easy explanation - The basic PRINCIPLE employed in RABIN Karp algorithm is hashing. In the GIVEN text EVERY substring is converted to a hash value and compared with the hash value of the PATTERN.

Correct answer is (b) O(n LOG n)

Easiest explanation - The worst case TIME complexity of tree sort DEPENDS on whether the tree used in the implementation is balanced or not. If the tree is balanced then the worst case complexity is O(n log n).

The correct OPTION is (b) shell sort

Explanation: Shell sort is a variation of insertion sort. It has a BETTER RUNNING time in practical APPLICATIONS.

The correct ANSWER is (c) bucket sort

Easiest EXPLANATION - Bucket sort can also be CONSIDERED as a comparison BASED sort. It is because it can also be implemented with comparisons.

Correct OPTION is (B) Radix sort has better cache performance than quick sort

To explain: Quick sort has a better cache performance than radix sort. Radix sort also takes more SPACE as COMPARED to quick sort.

Right OPTION is (b) DIMINISHING increment sort

Easiest explanation - Shell sort is also known as diminishing increment sort since each pass is defined by an increment H such that only the records which are h units APART will be sorted.

Correct answer is (a) it has a low SPACE complexity

To explain: Tree sort has a linear time complexity O(n) which makes it inefficient. This the MAIN reason why sorting ALGORITHMS LIKE quick sort, HEAP sort etc. are preferred over it.

The correct CHOICE is (b) False

The explanation is: The time complexity of tree SORT is AFFECTED when implemented with an unbalanced tree or a balanced tree. In case of a balanced tree it is O(n LOG n) and in case of unbalanced tree it is O(n^2).

Right answer is (d) using ordinary BST

Explanation: Out of the given options TREE SORT has the highest worst CASE TIME complexity with ordinary BST as it may not be balanced in every case. Whereas all other options have SELF balancing BST.

The correct choice is (c) TREE sort

The BEST I can explain: Out of the given options tree sort is the only ALGORITHM which is not in place. It is because the auxiliary SPACE required by tree sort is O(n).

The correct answer is (c) when implemented with a splay tree as BST

The best explanation: Tree SORT BECOMES an adaptive sort when it is implemented with a splay tree as a BST. In such a case the best case TIME complexity is better than (N LOG n).

Right answer is (C) O(n^2)

For explanation: The worst CASE time COMPLEXITY of TREE sort depends on whether the tree USED in the implementation is balanced or not. If the tree is unbalanced then the worst case complexity is O(n^2).

Correct answer is (b) O(N)

The best I can explain: TREE sort requires auxiliary SPACE for maintaining a binary search tree. So the auxiliary space COMPLEXITY of tree sort is O(n).

Right ANSWER is (b) O(N log n)

Best EXPLANATION: As on an average every element takes log n time for insertion in a binary SEARCH tree so for n elements O(n log n) time will be REQUIRED on an average.

Correct ANSWER is (a) tree SORT

The explanation is: In tree sort, we need to compare elements as we insert them in the binary search tree. THUS it QUALIFIES as a comparison BASED sort.

Right answer is (b) tree SORT

The BEST explanation: Tree sort makes use of a BINARY search tree. It is because every time when a BST is traversed in an in order fashion it gives a sorted output.

Right answer is (C) Tree sort

For explanation: Out of the given OPTIONS Tree sort is the only algorithm which is STABLE. It is because the elements with identical values appear in the same ORDER in the output ARRAY as they were in the input array.

The CORRECT choice is (a) in ORDER traversal

The best I can EXPLAIN: Tree sort uses a binary search tree for sorting the given elements. FIRST a BST is formed by using the input data elements and then the BST is traversed in an in order FASHION which gives a sorted output.

Correct answer is (a) True

Easiest EXPLANATION - Tree sort does not require the entire INPUT data at the beginning itself in order to sort the array. It rather creates a partial solution in every STEP, so future elements are not required to be CONSIDERED. Hence it is an ONLINE sorting algorithm.

The correct ANSWER is (c) binary search TREE

To EXPLAIN: Tree sort uses a binary search tree for sorting the given ELEMENTS. Tree sort can also be performed by using an unbalanced binary search tree.

The correct option is (a) true

Easiest explanation - Insertion sort does not require the entire INPUT DATA in the beginning itself in ORDER to sort the array. It rather creates a partial solution in every step, so future elements are not required to be CONSIDERED. HENCE it is an online sorting algorithm.

The correct answer is (d) it has no significant advantage

The best I can EXPLAIN: Recursive INSERTION sort has no significant advantage over ITERATIVE insertion sort. It is just a different WAY to IMPLEMENT the same.

Correct answer is (c) log N

The best explanation: Binary insertion sort makes log n comparisons in the WORST case. WHEREAS the STANDARD VERSION makes n comparisons in the worst case.

The correct answer is (a) True

Easy explanation - Binary INSERTION sort does not require the ENTIRE input data at the beginning itself in order to sort the ARRAY. It rather creates a partial solution in every step, so future elements are not required to be CONSIDERED. Hence it is an online sorting algorithm.

The correct option is (C) it makes less NUMBER of COMPARISONS

Easy EXPLANATION - Binary insertion sort makes less number of comparisons as compared to the standard version of insertion sort. Binary insertion sort makes log n comparisons in the worst case as compared to n comparisons made in the standard version.

Right choice is (c) Bubble sort

The best EXPLANATION: Out of the given options bubble sort is the only ALGORITHM which is STABLE. It is because the elements with identical values appear in the same order in the output ARRAY as they were in the input array.

Right answer is (c) T(n) = T(n-1) + n

The best EXPLANATION: The recurrence RELATION of the code of recursive bubble sort is T(n) = T(n-1) + n. It can be solved by the method of SUBSTITUTION and is FOUND to be equal to n^2.

The CORRECT choice is (c) sinking sort

The best explanation: Bubble sort is also referred to as sinking sort. It CONTINUOUSLY compares the VALUE of adjacent elements as it traverses through an ARRAY and swaps the elements which are out of order.

The CORRECT ANSWER is (d) it has no significant advantage

For explanation: RECURSIVE bubble sort has no significant advantage over ITERATIVE bubble sort. It is just a different WAY to implement the same.

Right answer is (c) O(INFINITY)

The EXPLANATION is: There is no upper bound to the WORST case of this algorithm. It can go on to TAKE a very large amount of time if the array has many elements. So the worst case of this algorithm can be taken as O(infinity).

The correct answer is (B) O(n)

EASY explanation - Best case time complexity of permutation sort occurs when the INPUT array is already sorted. So in such a case we only NEED to check whether all the elements are sorted which can be done in O(n) time.

The CORRECT answer is (a) generating random permutations of its INPUT

To explain: Permutation sort algorithm successively GENERATES permutations of its input. This process is repeated until the SORTED VERSION of the array is found.

Correct option is (c) DONKEY SORT

The best I can explain: Permutation sort is also known by names like stupid sort, MONKEY sort, BOGO sort, SLOW sort and shotgun sort. These names are particularly chosen due to its inefficient algorithm.

The CORRECT answer is (d) O(n^2.7)

Easiest explanation - The recurrence relation of stooge sort is given as T(n) = 3T(2/3n) + O(1). It is found to be equal to O(n^2.7) USING the master’s THEOREM.

The correct choice is (b) false

Easy explanation - Stooge sort is not a stable SORTING algorithm. It is because the ELEMENTS with identical VALUES do not appear in the same order in the OUTPUT array as they were in the input array.

Correct answer is (a) true

Easiest explanation - Stooge sort is an example of a COMPARISON based SORTING algorithm. This is because it compares the value of elements PRESENT in a LIST in order to sort them.

Correct answer is (d) compare FIRST and last element of the array

Easy explanation - The first step in the algorithm of STOOGE SORT is to compare the first and last element of the array and SWITCH them if found out of order. In the second step stooge sort is APPLIED on the first 2/3 elements of the array.

The correct choice is (d) it has the same time complexity in any CASE

For explanation: Stooge SORT has the same time complexity under any case. It is given by the recurrence relation T(n) = 3T(2/3n) + O(1).

Correct answer is (d) T(n) = 3T(2/3n) + O(1)

The best explanation: In stooge sort recursion is applied to 2/3 part of the ARRAY 3 TIMES. Rest of the PORTION of code has a constant time complexity. So the overall recurrence relation becomes T(n) = 3T(2/3n) + O(1).

The CORRECT answer is (b) stooge sort

To explain: Stooge sort requires the use of recursion for IMPLEMENTING its algorithm. On the other hand, the sorting algorithms GIVEN in the remaining options use iterative METHODS.