Sorting
public static void sortingMethod(int[] array) {
int n = array.length;
for (int i = 1; i < n; i++) {
int key = array[i];
int j = i - 1;
// Move elements of the array that are greater than the key
// one position ahead of their current position
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = key;
}
}
What is the name of this type of sorting algorithm?
Insertion Sort
public static int searchAlgorithm(int[] array, int target) {
int left = 0; // Starting index
int right = array.length - 1; // Ending index
while (left <= right) {
// Calculate the middle index
int mid = left + (right - left) / 2; // Avoids overflow for large indices
// Check if the target is at the mid index
if (array[mid] == target) {
return mid; // Target found, return its index
}
// If target is smaller, search in the left half
if (array[mid] > target) {
right = mid - 1;
}
// If target is larger, search in the right half
else {
left = mid + 1;
}
}
return -1; // Target not found
}
What is the name of this searching algorithm?
Binary Search
The main difference between the declaration of ArrayLists and Arrays is...
What is ArrayLists has <> and Arrays has []?
public static void shellSort(int[] array) {
int n = array.length;
// Start with a large gap, then reduce the gap
for (int gap = n / 2; gap > 0; gap /= 2) {
// Perform a gapped insertion sort for this gap size
for (int i = gap; i <= n; i++) {
// Save the current element and find its correct position
int temp = array[i];
int j;
// Shift earlier elements of the gap-sorted subarray
// to make space for the current element
for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
array[j] = array[j - gap];
}
// Place the current element at its correct position
array[j] = temp;
}
}
}
What is the mistake with this code?
for (int i = gap; i < n; i++)
public static int jumpSearch(int[] array, int target) {
int n = array.length;
// Calculate the optimal block size to jump
int step = (int) Math.sqrt(n);
int prev = 0;
// Find the block where the target element is present
while (array[Math.min(step, n) - 1] < target) {
prev = step;
step += Math.sqrt(n);
if (prev >= n) {
return -1; // Target not found
}
}
// Perform a linear search in the identified block
while (array[prev] < target) {
prev++;
if (prev == Math.min(step, n)) {
return -1; // Target not found
}
}
// If the target is found
if (array[prev] == target) {
return prev;
}
return -1; // Target not found
}
What is the mistake in this code?
step += (int)Math.sqrt(n);
Suppose you are given the following ArrayList declaration:
ArrayList<Integer> nums = new ArrayList<>();nums.add(5);nums.add(10);
nums.add(15);nums.add(20);nums.add(25);
What will be the contents of nums after executing the following code?
for (int i = 0; i < nums.size(); i++) {
if (nums.get(i) % 10 == 0) {
nums.remove(i);i--; // Adjust index after removal
}}nums.add(2, 100);nums.add(nums.size() - 1, 50);
What is.... [5, 15, 100, 50, 25]?
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
// Find the pivot index
int pivotIndex = partition(array, low, high);
// Recursively sort the elements before and after the pivot
quickSort(array, low, pivotIndex - 1);
quickSort(array, pivotIndex + 1, high);
}
}
// Method to partition the array
public static int partition(int[] array, int low, int high) {
// Choose the rightmost element as the pivot
int pivot = array[high];
int i = low; // Pointer for the smaller element
for (int j = low; j < high; j++) {
// If the current element is smaller than or equal to the pivot
if (array[j] <= pivot) {
i++; // Increment the pointer
// Swap the elements at i and j
swap(array, i, j);
}
}
// Place the pivot element at the correct position
swap(array, i + 1, high);
return i + 1; // Return the pivot index
}
// Method to swap two elements in the array
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
What is the mistake?
int i = low - 1;
public static int interpolationSearch(int[] array, int target) {
int low = 0;
int high = array.length - 1;
while (low <= high && target => array[low] && target <= array[high]) {
// Estimate the position using the interpolation formula
int pos = ((target - array[low]) * (high - low)) / (array[high] - array[low]);
// Check if the target is at the estimated position
if (array[pos] == target) {
return pos;
}
// If target is larger, target is in the upper part
if (array[pos] < target) {
low = pos + 1;
}
// If target is smaller, target is in the lower part
else {
high = pos - 1;
}
}
return -1; // Target not found
}
What is the mistake with this code?
int pos = low + ((target - array[low]) * (high - low)) / (array[high] - array[low]);
Consider the following method, which takes an ArrayList of integers as a parameter:
public static int countSpecialEvens(ArrayList<Integer> list) {
int count = 0;
for (int i = 0; i < list.size(); i++) {
if (list.get(i) % 2 == 0 && i
% 2 == 1) { // Check if the number is even and its index is odd
count++;
}
}
return count;
}
If the method is called with the following ArrayList:
ArrayList<Integer> nums = new ArrayList<>();
nums.add(8);
nums.add(14);
nums.add(3);
nums.add(22);
nums.add(17);
nums.add(6);
What will be the return value of countEvens(nums)?
What is 3?
public static void heapSort(int[] array) {
int n = array.length;
// Build a max-heap (rearrange the array)
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(array, n, i);
}
// One by one extract elements from the heap
for (int i = n - 1; i >= 0; i--) {
// Move current root (max element) to the end
int temp = array[0];
array[0] = array[i];
array[i] = temp;
// Call heapify on the reduced heap
heapify(array, i, 0);
}
}
// Method to heapify a subtree rooted at index i
private static void heapify(int[] array, int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left child
int right = 2 * i + 2; // right child
// If left child is larger than root
if (left < n && array[left] > array[largest]) {
largest = left;
}
// If right child is larger than the largest so far
if (// Missing code) {
largest = right;
}
// If largest is not root
if (largest != i) {
int swap = array[i];
array[i] = array[largest];
array[largest] = swap;
// Recursively heapify the affected subtree
heapify(array, n, largest);
}
}
Write the missing line of code.
right < n && array[right] > array[largest]
public static void dfs(int[][] graph, int start) {
int n = graph.length; // Number of vertices in the graph
boolean[] visited =
new boolean[n]; // Array to track visited nodes
// Call DFS with a recursive helper method
dfsRecursive(graph, start, visited);
}
// Recursive helper method for DFS
public static void dfsRecursive(int[][] graph, int node, boolean[] visited) {
// Mark the current node as visited
visited[node]=true;System.out.print(node + " "); // Process the current node
// Visit all the adjacent vertices of the current node
for (int i = 0; i < graph.length; i++) {/* If an adjacent node has not been visited, recursively call DFS */if (/* Missing code */) {dfsRecursive(graph, i, visited);}}}
Write the missing line of code.
graph[node][i] == 1 && !visited[i]
Suppose you have the following code:
ArrayList<String> words = new ArrayList<>();
words.add("cat");
words.add("dog");
words.add("bird");
words.add("fish");
words.add("lion");
What will be printed by the following code snippet?
for (int i = 0; i < words.size(); i++) {
if (words.get(i).length() == 3) {
words.set(i, words.get(i) + "s"); // Add "s" to words with 3 letters
}
}
words.add(2, "tiger");
words.remove(4);
words.remove(words.size() - 1); // Remove the last element
System.out.println(words);
What is... [cats, dogs, tiger, bird]?