InterviewSolution

Explore topic-wise InterviewSolutions in .

This section includes InterviewSolutions, each offering curated multiple-choice questions to sharpen your knowledge and support exam preparation. Choose a topic below to get started.

1.	Given input string = “ABCDABCATRYCARCABCSRT” and pattern string = “CAT”. Find the first index of the pattern match using quick search algorithm.(a) 2(b) 6(c) 11(d) 14The question was posed to me during an interview.I would like to ask this question from String Matching topic in chapter String Matching of Data Structures & Algorithms II
Answer» The correct option is (b) 6 The explanation is: By using quick SEARCH algorithm, the GIVEN INPUT text string is preprocessed and STARTS its search from the left most character and finds the first occurrence of the pattern at index=2.

2.	What character shift tables does Boyer-Moore’s search algorithm use?(a) good-character shift tables(b) bad-character shift tables(c) next-character shift tables(d) both good and bad character shift tablesThis question was posed to me in semester exam.My enquiry is from String Matching topic in section String Matching of Data Structures & Algorithms II
Answer» Right CHOICE is (d) both GOOD and bad character SHIFT tables Explanation: Boyer-Moore’s SEARCH algorithm USES both good and bad character shift tables whereas quick search algorithm uses only bad character shift tables.

3.	What is the worst case running time in searching phase of Boyer-Moore’s algorithm?(a) O(n)(b) O(log n)(c) O(m+n)(d) O(mn)The question was posed to me during an interview for a job.My question is based upon String Matching topic in chapter String Matching of Data Structures & Algorithms II
Answer» CORRECT option is (d) O(MN) The explanation is: If the pattern OCCURS in the text, the worst case running time of Boyer-Moore’s ALGORITHM is found to be O(mn).

4.	The searching phase in quick search algorithm has good practical behaviour.(a) true(b) falseI have been asked this question in quiz.Asked question is from String Matching in portion String Matching of Data Structures & Algorithms II
Answer» The correct option is (a) true To explain: During the searching PHASE, the comparison between pattern and text CHARACTERS can be done in any order. It has a quadratic worst CASE behaviour and good practical behaviour.

5.	Quick search algorithm starts searching from the right most character to the left.(a) true(b) falseThis question was addressed to me in my homework.This intriguing question originated from String Matching topic in chapter String Matching of Data Structures & Algorithms II
Answer» RIGHT answer is (b) false The best I can explain: Quick search ALGORITHM starts searching from the left most character to the right and it USES only bad character shift tables.

6.	What is the space complexity of quick search algorithm?(a) O(n)(b) O(log n)(c) O(m+n)(d) O(mn)This question was addressed to me in homework.I'd like to ask this question from String Matching in section String Matching of Data Structures & Algorithms II
Answer» The correct CHOICE is (a) O(N) The best I can explain: The space complexity of quick SEARCH ALGORITHM is MATHEMATICALLY found to be O(n) where n represents the input size.

7.	What character shift tables does quick search algorithm use?(a) good-character shift tables(b) bad-character shift tables(c) next-character shift tables(d) both good and bad character shift tablesI have been asked this question in an online quiz.I'm obligated to ask this question of String Matching topic in chapter String Matching of Data Structures & Algorithms II
Answer» CORRECT choice is (b) BAD-CHARACTER shift TABLES Easy explanation - Quick search algorithm uses only bad character shift tables and it is one of the reasons for its increased speed than Boyer-Moore’s algorithm.

8.	What is the time complexity of the Quick search algorithm?(a) O(n)(b) O(log n)(c) O(m+n)(d) O(mn)I have been asked this question in an online quiz.Enquiry is from String Matching topic in section String Matching of Data Structures & Algorithms II
Answer» CORRECT CHOICE is (c) O(m+n) Easiest explanation - The time complexity of the QUICK search algorithm was FOUND to be O(m+n) and is PROVED to be faster than Boyer-Moore’s algorithm.

9.	Which of the following algorithms formed the basis for the Quick search algorithm?(a) Boyer-Moore’s algorithm(b) Parallel string matching algorithm(c) Binary Search algorithm(d) Linear Search algorithmThe question was asked in a national level competition.My question is based upon String Matching in section String Matching of Data Structures & Algorithms II
Answer» The correct choice is (a) Boyer-Moore’s ALGORITHM Easiest EXPLANATION - Quick SEARCH algorithm was ORIGINALLY formed to overcome the drawbacks of Boyer-Moore’s algorithm and also for increased SPEED and efficiency.

10.	Which of the following is the fastest algorithm in string matching field?(a) Boyer-Moore’s algorithm(b) String matching algorithm(c) Quick search algorithm(d) Linear search algorithmThe question was asked in a national level competition.Asked question is from String Matching in portion String Matching of Data Structures & Algorithms II
Answer» Correct OPTION is (c) Quick search algorithm To explain: Quick search algorithm is the fastest algorithm in STRING matching field whereas Linear search algorithm SEARCHES for an element in an ARRAY of elements.

11.	Who created the Rabin Karp Algorithm?(a) Joseph Rabin and Michael Karp(b) Michael Rabin and Joseph Karp(c) Richard Karp and Michael Rabin(d) Michael Karp and Richard RabinI got this question during a job interview.My doubt is from String Matching topic in section String Matching of Data Structures & Algorithms II
Answer» CORRECT answer is (c) Richard Karp and Michael RABIN The EXPLANATION is: Rabin Karp algorithm was INVENTED by Richard Karp and Michael Rabin in the year 1987 for searching a pattern in the GIVEN string.