All Flashcards
How is Binary Search applied in real-world scenarios?
Searching for a word in a dictionary, finding a contact in a sorted phone book, searching for a value in a sorted database index.
How is Merge Sort applied in real-world scenarios?
External sorting of large datasets that don't fit in memory, sorting large files, used in various sorting algorithms in databases.
How is Linear Search applied in real-world scenarios?
Searching for an item in a small, unsorted list, finding a specific file in a directory.
How is Insertion Sort applied in real-world scenarios?
Sorting a hand of playing cards, sorting small datasets, used as a subroutine in more complex sorting algorithms.
How is Selection Sort applied in real-world scenarios?
Although not very efficient, it can be used in scenarios where memory usage is a primary concern due to its in-place sorting nature.
What are real-world applications of recursion?
File system traversal, parsing complex data structures (like XML or JSON), implementing tree-based algorithms, and solving problems that can be broken down into smaller, self-similar subproblems.
How are sorting algorithms used in databases?
Sorting is essential for indexing data, optimizing query performance, and presenting data in a structured manner.
How are searching algorithms used in databases?
Searching algorithms are used to efficiently locate specific records within a database, enabling quick retrieval of information.
How are sorting algorithms used in search engines?
Search engines use sorting algorithms to rank search results based on relevance, ensuring that the most relevant results appear at the top of the page.
How are searching algorithms used in search engines?
Search engines use searching algorithms to quickly locate web pages that match a user's search query.
What does the following code output?
java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
Collections.sort(arr);
System.out.println(arr);
[1, 2, 5, 8, 9]
Identify the error in the following code:
java
public static int recursiveBinarySearch(ArrayList<Integer> array, int n, int left, int right) {
int middle = (left + right) / 2;
if (left > right) { return -1; }
else if (n == array.get(middle)) { return middle; }
else if (n < array.get(middle)) { recursiveBinarySearch(array, n, left, middle - 1); }
else if (n > array.get(middle)) { recursiveBinarySearch(array, n, middle + 1, right); }
}
The recursive calls don't return a value. Should be return recursiveBinarySearch(...).
What does the following code output?
java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
recursiveInsertionSort(arr, 0);
System.out.println(arr);
Assuming recursiveInsertionSort is correctly implemented.
[1, 2, 5, 8, 9]
What does the following code output?
java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
recursiveSelectionSort(arr, 0);
System.out.println(arr);
Assuming recursiveSelectionSort is correctly implemented.
[1, 2, 5, 8, 9]
What does the following code output?
java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
mergeSort(arr);
System.out.println(arr);
Assuming mergeSort is correctly implemented.
[1, 2, 5, 8, 9]
What does the following code output?
java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
int index = recursiveLinearSearch(arr, 8, 0);
System.out.println(index);
2
What does the following code output?
java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 5, 8, 9));
int index = recursiveBinarySearch(arr, 5, 0, arr.size() - 1);
System.out.println(index);
2
Identify the error in the following code:
java
public static int recursiveLinearSearch(ArrayList<Integer> array, int n, int startingIndex) {
if (array.get(startingIndex) == n) { return startingIndex; }
else if (startingIndex == array.size() - 1) { return -1; }
else { recursiveLinearSearch(array, n, startingIndex); }
}
The recursive call does not increment startingIndex, leading to infinite recursion. Should be recursiveLinearSearch(array, n, startingIndex + 1).
What does the following code output?
java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
int index = recursiveLinearSearch(arr, 10, 0);
System.out.println(index);
-1
What does the following code output?
java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 5, 8, 9));
int index = recursiveBinarySearch(arr, 10, 0, arr.size() - 1);
System.out.println(index);
-1
What are the differences between Linear Search and Binary Search?
Linear Search: Works on unsorted lists, O(n) time complexity. Binary Search: Requires sorted lists, O(log n) time complexity.
What are the differences between Insertion Sort and Selection Sort?
Insertion Sort: Builds sorted array incrementally, adaptive. Selection Sort: Finds the minimum element in each iteration, not adaptive.
What are the differences between Insertion Sort and Merge Sort?
Insertion Sort: Simple, in-place, O(n^2) time complexity. Merge Sort: More complex, requires extra space, O(n log n) time complexity.
What are the differences between Selection Sort and Merge Sort?
Selection Sort: Simple, in-place, O(n^2) time complexity. Merge Sort: More complex, requires extra space, O(n log n) time complexity.
What are the differences between iterative and recursive Linear Search?
Iterative: Uses loops, generally more efficient in terms of memory. Recursive: Uses function calls, can be more concise, but may lead to stack overflow.
What are the differences between iterative and recursive Binary Search?
Iterative: Uses loops, generally more efficient in terms of memory. Recursive: Uses function calls, can be more concise, but may lead to stack overflow.
What are the differences between iterative and recursive Insertion Sort?
Iterative: Uses loops, generally more efficient in terms of memory. Recursive: Uses function calls, can be more concise, but may lead to stack overflow.
What are the differences between iterative and recursive Selection Sort?
Iterative: Uses loops, generally more efficient in terms of memory. Recursive: Uses function calls, can be more concise, but may lead to stack overflow.
What are the differences between iterative and recursive Merge Sort?
Iterative: Uses loops, generally more efficient in terms of memory. Recursive: Uses function calls, can be more concise, but may lead to stack overflow.
When is Merge Sort preferred over Insertion Sort?
Merge Sort is preferred for larger datasets due to its O(n log n) time complexity, while Insertion Sort is better for small datasets or nearly sorted data.