Data Structures & Algorithms test (Intermediate)

Sample questions

5 sample questions from the Data Structures & Algorithms test, with the answers. Samples are taken out of the live test, so you will not meet these when you sit it.

1. Which of the following is true about when to choose KMP over brute-force for substring search?

   1. KMP is preferred when the pattern is fixed and needs to be searched multiple times in the same text.
   2. Brute-force is preferred when the text is very large and the pattern is very small.
   3. KMP is preferred when the text is very small and the pattern is very large.
   4. Brute-force is preferred when the pattern is fixed and needs to be searched multiple times in the same text.

   Answer: A. KMP is preferred when the pattern is fixed and needs to be searched multiple times in the same text.

   KMP (Knuth-Morris-Pratt) is preferred over brute-force substring search when the pattern is fixed and needs to be searched multiple times in the same text because it avoids rechecking characters that have already been matched, achieving linear time complexity. Brute-force methods, on the other hand, may have higher time complexity in such cases.

2. Under what conditions would insertion sort be preferred over merge sort, and vice versa?

   1. Insertion sort is preferred when stability is required, while merge sort is preferred for nearly sorted data.
   2. Insertion sort is preferred for small datasets or nearly sorted data, while merge sort is preferred for large datasets or when stability is required.
   3. Insertion sort is preferred for large datasets, while merge sort is preferred for small datasets.
   4. Insertion sort is preferred for unsorted data, while merge sort is preferred for sorted data.

   Answer: B. Insertion sort is preferred for small datasets or nearly sorted data, while merge sort is preferred for large datasets or when stability is required.

   Insertion sort has a best-case time complexity of O(n) when the input is already nearly sorted, making it efficient for small or nearly sorted datasets. However, its worst-case time complexity is O(n^2), which makes it inefficient for large datasets. Merge sort, on the other hand, has a consistent O(n log n) time complexity in all cases and is stable, making it a better choice for large datasets or when stability is required.

3. A hash table with 1000 elements has a capacity of 1250. The load factor is currently 0.8. What is the appropriate action to take?

   1. The load factor is 0.8, so the hash table should be resized to a smaller capacity.
   2. The load factor is 0.8, so the hash table should be completely replaced with a different data structure.
   3. The load factor is 0.8, so no action is required.
   4. The load factor is 0.8, so the hash table should be resized to a larger capacity.

   Answer: D. The load factor is 0.8, so the hash table should be resized to a larger capacity.

   The load factor is calculated as the number of elements divided by the capacity of the hash table. When the load factor exceeds a threshold (usually 0.7 or 0.8), resizing the hash table is recommended to maintain efficiency and reduce collisions. In this case, the load factor is 0.8, which is at the threshold, so resizing to a larger capacity is the correct action.

4. Which of the following is a correct approach to optimizing the space complexity in dynamic programming problems with overlapping subproblems?

   1. The space cannot be optimized further and must always be O(n).
   2. The space can be optimized to O(1) by using a bottom-up approach and overwriting previous values.
   3. The space can be optimized to O(1) by using a recursive approach with memoization.
   4. The space can be optimized to O(1) by using a top-down approach and memoizing values.

   Answer: B. The space can be optimized to O(1) by using a bottom-up approach and overwriting previous values.

   In dynamic programming, space optimization is often achieved by using a bottom-up approach and reusing variables instead of storing the entire DP table. This is especially common in problems like the Fibonacci sequence or the minimum coin change problem, where only the previous values are needed to compute the current value. Options that suggest using additional data structures or keeping the full table are not optimized for space.

5. What is the time complexity of a standard binary tree traversal (such as in-order, pre-order, or post-order) in terms of the number of nodes, n?

   1. O(log n)
   2. O(n^2)
   3. O(n)
   4. O(n log n)

   Answer: C. O(n)

   A binary tree traversal (such as in-order, pre-order, or post-order) visits every node in the tree exactly once. Since each node is visited once, the time complexity is O(n), where n is the number of nodes in the tree. This is true for all standard traversal methods, regardless of the tree's structure (balanced or unbalanced).