Explore topic-wise InterviewSolutions in .

Right option is (B) ARRAY is sorted and has uniform distribution of values

For explanation: Interpolation search is an improvement over a binary search for the case when array is sorted and has uniformly DISTRIBUTED values. Binary search PERFORMS better when the values are not distributed uniformly.

The CORRECT answer is (a) true

Easiest explanation - The AUXILIARY SPACE complexity required by naive pattern searching algorithm is O(1). So it QUALIFIES as an in place algorithm.

Correct OPTION is (B) O(m)

Easy explanation - Z ALGORITHM is an efficient PATTERN searching algorithm as it searches the pattern in linear time. It an auxiliary space of O(m) for maintaining Z array.

Correct option is (a) O(N + m)

Explanation: Z algorithm is an efficient pattern SEARCHING algorithm as it searches the pattern in LINEAR time. It has a time COMPLEXITY of O(m + n) where m is the LENGTH of text and n is the length of the pattern.

Correct CHOICE is (c) O(m)

The EXPLANATION is: KMP algorithm is an efficient pattern searching algorithm. It has a time complexity of O(m) where m is the LENGTH of text.

Correct OPTION is (b) FOUND

Explanation: A sub string is a subset of another string. So “FOUND” is the only POSSIBLE sub string out of the given OPTIONS.

Correct choice is (b) high = pos – 1, LOW remains unchanged

For explanation: When the element being SEARCHED is lower than the value at the calculated position then in that CASE we update high and low remains unaltered. Updated value of high is high = pos – 1.

The correct choice is (B) False

For EXPLANATION: The worst CASE time complexity of interpolation search and exponential search are O(n) and O(log n) respectively. So exponential search is better when the worst case scenario is considered.

The correct OPTION is (B) linear search

Best explanation: Out of the given OPTIONS linear search is the only SEARCHING algorithm which can be applied to arrays which are not sorted. It has a time COMPLEXITY of O(n) in the worst case.

The correct choice is (c) O(N)

To explain: When an array has NON uniformly distributed values then in that case the algorithm of INTERPOLATION search fails to work efficiently. As a RESULT, it has a time COMPLEXITY of O(n) in such a case.

Right CHOICE is (c) O(1)

Explanation: Interpolation SEARCH does not REQUIRE any auxiliary SPACE for finding the element being searched. So it has a CONSTANT auxiliary space O(1).

The correct OPTION is (b) O(log log n)

Easy EXPLANATION - Interpolation search goes to different positions in the array depending on the value being SEARCHED. It is an improvement over binary search and has a TIME COMPLEXITY of O(log log n).

Correct option is (c) when array is sorted but the values increases exponentially

The explanation is: In case of NON uniform distribution of values the time COMPLEXITY of INTERPOLATION search is O(n) whereas the average time complexity of jump search is O(n^1/2). So in such a case jump search has a better performance.

The correct option is (B) Binary search

The best I can EXPLAIN: Interpolation search is a variation of binary search which gives the best RESULT when the array has uniformly distributed values. Interpolation search goes to DIFFERENT POSITIONS depending on the value being searched whereas binary search always goes to the middle element.

Right answer is (d) ARRAY should be sorted and the VALUES should be uniformly distributed

The BEST I can explain: Desirable condition for INTERPOLATION search is that the array should be sorted and the values should be uniformly distributed. The ALGORITHM would fail to give the correct result if array is not sorted.

Correct option is (a) Logarithmic search

The EXPLANATION is: Logarithmic search is not an ALTERNATE NAME of the exponential search. Some alternate names of exponential search are DOUBLING search, Galloping search and Struzik search.

Right option is (b) Exponential search has a greater TIME complexity than BINARY search

Easiest explanation - Time complexity of exponential search and binary search are the same. But exponential search performs better than binary search when the element being SEARCHED is present near the starting point of the ARRAY.

Correct answer is (a) True

To EXPLAIN: EXPONENTIAL search first finds the range where binary search needs to be APPLIED. So when the ELEMENT is present NEAR the starting point of the array then exponential search performs better than standard binary search.

The correct answer is (d) O(log n)

The BEST explanation: EXPONENTIAL search requires an auxiliary SPACE of log n when used with recursive binary search. This space is REQUIRED for the RECURSION call stack space.

Right CHOICE is (c) O(1)

BEST explanation: Exponential search does not require any AUXILIARY space for finding the ELEMENT being SEARCHED. So it has a constant auxiliary space O(1).

Right option is (b) False

Easy EXPLANATION - The TIME complexity of jump SEARCH is O(n^1/2) in WORST and average case. It is due to the FACT that size of optimal jump is n^1/2.

Correct choice is (C) n^1/2

For explanation: Total NUMBER of comparisons required will be n/k + k-1 in WORST case. This function will be minimum for k=n^1/2. So this value of jump will be the best for IMPLEMENTING jump search.

Right choice is (c) k-1

Explanation: Worst CASE occurs when the element being searched is present just after the element that has been COMPARED while MAKING the LAST jump. So, in this case k-1 COMPARISONS will have to be made.

The CORRECT ANSWER is (b) n/k

The best EXPLANATION: WORST case occurs when the value to be searched is in the last section of the array. So, in this case the NUMBER of jumps will be n/k.

Right ANSWER is (b) linear SEARCH takes place in the BACKWARD DIRECTION

Best explanation: First an element having value greater than the element being searched is found. After this linear search is performed in a backward direction.

Correct ANSWER is (c) element having value greater than that of the REQUIRED element is found

Easiest explanation - In jump search algorithm jumps are MADE until element having value greater than the value of element being searched is found. After this linear search is PERFORMED in backwards direction.

Correct ANSWER is (a) array should be sorted

Easiest explanation - JUMP sort REQUIRES the INPUT array to be sorted. The algorithm WOULD fail to give the correct result if array is not sorted.

Correct OPTION is (d) Jump search starts from the index 0 even though specified index is k

Best explanation: Linear search has O(n) COMPLEXITY and Binary search has O(logn) complexity, in Jump search you have to jump backwards only once, HENCE it is preferable if jumping backwards is COSTLY. Jump search starts from index k (specified index) and SEARCHES for the element. It won’t start searching from index 0.

Correct choice is (B) BEGIN from the kth item, where k is the step size

Explanation: This GIVES a very SLIGHT improvement as you are skipping the first k elements.

Correct choice is (B) O(LOGN)

The best explanation: T(n) = T(n/2) + THETA(1)

USING the divide and conquer MASTER theorem, we get the time complexity as O(logn).

Correct ANSWER is (a) 90 and 99

Explanation: Trace the input with the binary search ITERATIVE code.

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

Best explanation: After each call in the RECURSIVE algorithm, the SIZE of n is REDUCED by 1. Therefore the OPTIMAL solution is T(n-1)+c.

Correct CHOICE is (a) When the size of the dataset is low

The best EXPLANATION: It is USED when the size of the dataset is low as its runtime is O(n) which is more when compared to the binary search O(logn).

Correct choice is (a) O(N)

Explanation: In the worst CASE scenario, there MIGHT be a need of CALLING the stack n TIMES. Therfore O(n).

The correct choice is (c) Linear SEARCH(Iterative) is FASTER

The EXPLANATION is: The Iterative algorithm is faster than the latter as recursive algorithm has overheads like calling FUNCTION and REGISTERING stacks repeatedly.