All Flashcards
What is Binary Search?
A search algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half.
What is Merge Sort?
A divide-and-conquer sorting algorithm that divides the input array into smaller sub-arrays, recursively sorts them, and then merges the sorted sub-arrays.
What is Recursion?
A programming technique where a function calls itself in order to solve a problem.
What is a Base Case?
The condition that stops a recursive function from calling itself infinitely.
What is Linear Search?
A searching algorithm that sequentially checks each element of a list until a match is found or the entire list has been searched.
What is Insertion Sort?
A sorting algorithm that builds the final sorted array one item at a time by repeatedly inserting the next element into its correct position within the already sorted portion of the array.
What is Selection Sort?
A sorting algorithm that repeatedly finds the minimum element from the unsorted portion of the array and places it at the beginning.
What is an ArrayList?
A resizable array implementation of the List interface in Java.
What is an Index?
The position of an element within an array or ArrayList, starting from 0.
What is a Sublist?
A contiguous portion of a list or array.
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.