This is a set of multiple choice questions, provided entirely for your self-assessment, and is based on the the most fundamental aspects of data structure and algorithms. The level of the questions is no more than that of what one would encounter in an introductory Data Structures class.

Some of these data structures might be new to some of you. Do read about them and alongside, try to attempt the questions - treat it as an opportunity to learn something new!

Question 1.

Which of these is the worst case time complexity of the Binary Search algorithm on a sorted array - and cannot be expressed in lower order terms ?

(a) O(n)
(b) O(n log n)
(c) O(n²)
(d) O(n³)
(e) O(log n)

Question 2.

Which of these is the worst case time complexity of Insertion Sort - and cannot be expressed in lower order terms ?
(a) O(n)
(b) O(n log n)
(c) O(n²)
(d) O(n³)
(e) O(log n)

Question 3.

Which of these data structures is commonly used while implementing a Cache for a Web Application?

(a) Doubly Linked List
(b) Hash Map
(c) Heap
(d) Cyclic Linked List

Question 4.

Which of these falls into the category of Probabilistic Data Structures?

(a) Array
(b) Linked List
(c) Cyclic Linked List
(d) Binary Search Tree
(e) Bloom Filters

Question 5.

A given block of text has N characters in it. In this block of text, we need to find all occurrences of a pattern with P characters. Which of the following statements is true?
(P < N)

(a) It is not possible to accomplish this with an algorithm which performs better than a time complexity of O(NP) in the worst case.
(b) It is not possible to accomplish this with an algorithm which performs better than a time complexity of O(N²) in the worst case.
(c) It is not possible to accomplish this with an algorithm which performs better than a time complexity of O(P²) in the worst case.
(d) It is possible to accomplish this with an algorithm which performs the task in a time complexity of O(N+P) in the worst case.

Question 6.

The XOR Linked List is most similar in functionality to a:
(a) Singly Linked List (b) Doubly Linked List
(c) Circular Linked List

Question 7.

Which of these, is the main advantage offered by the XOR Linked List, when compared to its functional equivalent among the three options (a), (b), (c) in the previous question (Q6) ?

(a) Same functionality, but lower time complexity of traversals.
(b) Same functionality, but lower memory requirements.
(c) Same functionality, but lower time and memory complexity.

Question 8.

Which of the following is an advantage of Skip Lists over regular Linked Lists?
(a) Insertion of elements is faster.
(b) Lookup is faster.
(c) Both insertion and lookup are faster.

Question 9.

Which of these is the worst case time complexity for finding the height of a binary search tree - and cannot be expressed in lower order terms ?

(a) O(n)
(b) O(n log n)
(c) O(n²)
(d) O(n³)
(e) O(log n)

Question 10.

Which of these is the worst case time complexity for finding the largest element in a max-heap - and cannot be expressed in lower order terms ?

(a) O(n)
(b) O(n log n)
(c) O(n²)
(d) O(n³)
(e) O(1)

Answer Format

Replace the blanks (represented by three consecutive hyphens) with the appropriate letter ('a','b','c','d' or 'e') for each of the questions. Then, hit the submit button.

Do not add any leading, trailing or intermediate spaces.
In case you are unsure about the answer, you can use the letter 'x'.
Your answer should contain ten lines, answering sequentially, all of the questions 1 to 10.

For example: (Please note that these are NOT the correct answers and this example is meant only for the purpose of explaining the format)

1:a  
2:b  
3:c  
4:d  
5:e  
6:a  
7:b  
8:x  
9:d  
10:a     

Explanation

The candidate has concluded that the correct answer the Question 1 is option 'a', the correct answer to Question 2 is option 'b' and so on. He/she does not know the answer to Question 8, hence uses the character 'x'.

Scoring

Your score is proportional to the number of answers (indicated by the letter options) identified correctly by you.