CodeFights – Search Algorithms Quiz Answers

Wiki Pages for Some Algorithms:

Knuth–Morris–Pratt algorithm

Boyer–Moore string search algorithm

Rabin–Karp algorithm

Binary Search

Ternary Search

1)What type of search algorithm is used in this representation?

Binary Search

2) Determine which of the following famous search algorithms is most appropriate to solve this problem:

We have a very big log file data consisting of N characters (N is too big), and system administrators need to make sure that there are no hidden system anomalies. All they need to do is complete a step by step comparison – without using hash functions, and figure out if the pattern consisting of M characters is part of the log file data.

Knuth-Morris-Pratt

3) Let’s assume we have a data structure, like a hash table, that uses linked lists to contain the data of each bucket. Then, assume we replace these linked lists with a balanced binary search tree. Now each bucket’s data is stored in its own tree.

Also, suppose that regardless of the number of data values, the number of buckets on the table remain fixed. Moreover, in this current problem we don’t care how fast the given hash function is.

Determine the worst case running time to search an item in the table consisting of N data items.

Θ(logN)

4) Given a sorted list of N integers, what is the running time for finding the smallest element in the list greater than or equal to the given number A.

O(LogN)

5) What search pattern do you notice in this image?

Knuth–Morris–Pratt

6) Let’s assume we have a distribution of N double values ordered in a format as presented in the image below. Note that we have only one maximum, which is located between the values of A and B. What would be the best technique for finding the maximum value of that distribution?

Ternary search

 

7) A sorted array contains all even numbers from 2 to 256. For fun, let’s assume that you don’t know that there are only even numbers in that array and how elements are distributed. But you do know the number of elements and that the array is sorted. In order to determine if the number 45 is in the list, how many items should you examine (in the worst case) before deciding that 45 is not present?

8

8) What’s the best search algorithm for determining if a given set of patterns is contained within a larger list of items?

Rabin–Karp

9) You have a list A consisting of N integers ranging from 1 to N+1 such that there are no duplicates in the list, but there is one missing element. Which of the following expressions can successfully find the missing integer?

A0 XOR A1 … XOR AN-1 XOR 1 XOR 2 … XOR N+1

10) What type of search pattern do you notice here:

Boyer–Moore

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s