Module 2: Searching and sorting algorithms

Knowledge Check: Advanced data structures

Practice Assignment

1. Given the following code snippet, which method would be the most efficient for iterating through the HashMap to print student IDs and names?

  • Use the entrySet() method and iterate directly through the entries.
  • Use the keySet() method and retrieve values with get().
  • Use a traditional for loop with an index to iterate through the keys.
  • Use the values() method to iterate through the values only.

2. In a TreeMap, how are the entries sorted by default?

  • By the natural ordering of the keys.
  • By the values in the map.
  • By the hash codes of the keys.
  • By the insertion order.

3. Given the following code, which method of LinkedHashMap do you use to check if a specific student has borrowed a book, and how would you get the title of that book?

  • Use the containsKey() method and retrieve the book using get().
  • Use the put() method to update the student’s borrowed book.
  • Use the entrySet() method and loop through the entries.
  • Use the remove() method and print the book title.

4. Which data structures would you use to maintain a sorted order of keys?

  • ArrayList
  • HashMap
  • LinkedHashMap
  • TreeMap

5. Which of the following statements about a HashMap is correct?

  • It sorts entries based on natural key order.
  • It does not maintain any order of its entries.

  • It automatically removes the least recently used entry.
  • It maintains insertion order.

Knowledge Check: Linear and binary search

Practice Assignment

6. You need to find a specific bug in an unsorted list of reports, so you need to check them one by one. What is the time complexity of this linear search?

  • O(n)
  • O(1)
  • O(n log⁡ n)
  • O(log⁡ n)

7. You’re developing a search feature for an e-commerce website where customers can quickly find products by name. To implement a binary search for this, what must be true about the product list?

  • The array must contain unique elements only.
  • The array must be in descending order.
  • The array must be unsorted.
  • The array must be sorted.

8. How does the number of comparisons in binary search grow with the size of the array?

  • Quadratically
  • Logarithmically
  • Constantly
  • Linearly

9. You have a long list of unsorted emails and need to find one particular message. Due to time constraints and the dynamic nature of the list, sorting is not an option. Which search algorithm is more efficient for this large, unsorted dataset that cannot be sorted?

  • Binary search
  • Linear search

  • Neither is efficient.
  • Both are equally efficient.

10. In binary search, what happens when the target element is equal to the middle element?

  • Return the index of the middle element.
  • Restart the search from the beginning.
  • Continue searching in the left half.
  • Continue searching in the right half.

Knowledge Check: Bubble, Insertion, and Selection Sort

Practice Assignment

11. Koa is implementing the Bubble Sort algorithm to organize a list of his daily step counts over five days. He wants to sort the list in descending order from the day he took the most steps to the day he took the fewest. However, his code isn't sorting the list correctly. Can you identify what's wrong with Koa's code?

  • Not quite. The outer loop is correctly set to run from 0 to steps.length – 1.
  • The inner loop should iterate from counter1 instead of 0.

  • The swapping logic inside the if statement is incorrect.
  • The condition in the if statement should be steps[counter2] > steps[counter2 + 1].

12. Maria is implementing Insertion Sort to organize a list of book titles by character length (i.e., ascending order). Help her complete the code by filling in the missing statement. What condition should replace the comment /* Missing condition */?

  • counter2 >= 0 && books[counter2].length() >= key.length()

  • counter2 > 0 && books[counter2].length() > key.length()
  • counter2 >= 0 && books[counter2].length() > key.length()
  • counter2 >= 0 && books[counter2].length() < key.length()

13. Caleb is organizing items for packing, and he needs to select the smallest item first to place in a specific order. He decides to use Selection Sort but is uncertain whether it's the most efficient choice. Given an almost-sorted list, why might Selection Sort not be the best choice?

  • It will perform in O(n) time on nearly sorted lists.
  • It has a worst-case time complexity of O(n2),regardless of the list’s initial order.
  • Selection Sort is more memory-efficient than Insertion Sort.
  • It’s better suited for large datasets than Bubble Sort.

14. Emily's Bubble Sort implementation sorts items but makes more swaps than necessary. What could be done to reduce unnecessary swaps in Bubble Sort?

  • Check if any swaps were made in the last pass and stop if none were.
  • Decrease the length of the array after each pass.
  • Move the largest unsorted element to the end in each pass.
  • Use a counter to track the number of swaps and stop after 10 swaps.

15. Lina manually sorts her playing cards using Insertion Sort. What is the "key" in the Insertion Sort algorithm?

  • The card she is sorting compared to rest of the cards in the sorted portion.
  • The first element in the sorted portion.
  • The last element in the list.
  • The smallest element in the list.

Knowledge check: Merge Sort and Quick Sort

Practice Assignment

16. To complete the following Merge Sort method, what merge function logic should you follow to merge two sorted halves? Pay attention to the TODO section of the merge method, where you would need to write the logic for merging two sorted subarrays.

  • Use recursion to merge the elements back together.
  • Swap elements directly in the original array.
  • Create temporary arrays for the two halves, then merge them back into the original array in sorted order.
  • Use a temporary array and compare values one by one.

17. What is the pivot selection strategy in the given Quick Sort implementation?

  • Last element as pivot.
  • Random element as pivot.
  • First element as pivot.
  • Middle element as pivot.

18. What’s wrong with the following Quick Sort implementation?

  • The pi (partition index) value is calculated incorrectly.
  • The partition method is missing a return statement.
  • The first recursive call should be quickSort(arr, low, pi – 1).
  • The array should be reversed before sorting.

19. In Merge Sort, what is the role of the merge() function?

  • Combining two sorted subarrays into one sorted array.

  • Swapping elements in the array.
  • Splitting the array into two halves recursively.
  • Selecting the pivot element.

20. What is wrong with the following Merge Sort implementation, specifically in the merge() method?

  • The for loops on line 8 and line 11 are missing braces {}.
  • The comparison on line 16 should be leftArr[i] <= rightArr[j] to make the sorting stable.
  • The if (leftArr[i] < rightArr[j]) comparison on line 16 should be leftArr[i] > rightArr[j].
  • The temporary arrays leftArr and rightArr should be merged directly into the original array using recursion.

Module Quiz: Searching and sorting algorithms

Practice Assignment

21. To complete the following Merge Sort method, what merge function logic should you follow to merge two sorted halves? Pay attention to the TODO section of the merge method, where you would need to write the logic for merging two sorted subarrays.

  • Use a temporary array and compare values one by one.
  • Use recursion to merge the elements back together.
  • Swap elements directly in the original array.
  • Create temporary arrays for the two halves, then merge them back into the original array in sorted order.

22. What is the pivot selection strategy in the given Quick Sort implementation?

  • Last element as pivot.
  • Random element as pivot.
  • First element as pivot.
  • Middle element as pivot.

23. What’s wrong with the following Quick Sort implementation?

  • The array should be reversed before sorting.
  • The first recursive call should be quickSort(arr, low, pi – 1).

  • The partition method is missing a return statement.
  • The pi (partition index) value is calculated incorrectly.

24. In Merge Sort, what is the role of the merge() function?

  • Combining two sorted subarrays into one sorted array.
  • Selecting the pivot element.
  • Splitting the array into two halves recursively.
  • Swapping elements in the array.

25. What is wrong with the following Merge Sort implementation, specifically in the merge() method?

  • The for loops on line 8 and line 11 are missing braces {}.
  • The temporary arrays leftArr and rightArr should be merged directly into the original array using recursion.
  • The comparison on line 16 should be leftArr[i] <= rightArr[j] to make the sorting stable.
  • The if (leftArr[i] < rightArr[j]) comparison on line 16 should be leftArr[i] > rightArr[j].

Leave a Reply