All Flashcards

What are the general steps for writing a recursive function?

Identify the base case(s). 2. Define the recursive call to solve a smaller subproblem. 3. Ensure the recursive call moves towards the base case.

What are the steps of the binary search algorithm?

Find the middle element. 2. Compare the target to the middle element. 3. If target equals middle, return index. 4. If target is less than middle, search the left half. 5. If target is greater than middle, search the right half. 6. Repeat until found or search space is empty.

What are the main steps of the merge sort algorithm?

Divide the array into two halves. 2. Recursively sort the two halves. 3. Merge the sorted halves.

What does the following code output?

java
public int factorial(int n) {
  if (n == 0) {
    return 1;
  } else {
    return n * factorial(n-1);
  }
}
System.out.println(factorial(4));

Identify the error in the following code:

java
public int factorial(int n) {
  return n * factorial(n-1);
}

Missing base case, which will cause a stack overflow error.

What does the following code output?

java
public void traverseArray(int[] array, int index) {
  if (index == array.length) {
    return;
  }
  System.out.println(array[index]);
  traverseArray(array, index + 1);
}
int[] arr = {1, 2, 3};
traverseArray(arr, 0);

1 2 3

What does the following code output?

java
public int binarySearch(int[] array, int target, int low, int high) {
  if (low > high) {
    return -1;
  }
  int mid = (low + high) / 2;
  if (array[mid] == target) {
    return mid;
  } else if (target < array[mid]) {
    return binarySearch(array, target, low, mid - 1);
  } else {
    return binarySearch(array, target, mid + 1, high);
  }
}
int[] arr = {2, 4, 6, 8, 10};
System.out.println(binarySearch(arr, 6, 0, arr.length - 1));

Identify the potential issue in the following binary search code:

java
int mid = (low + high) / 2;

Integer overflow can occur if low + high exceeds the maximum integer value. Using mid = low + (high - low) / 2; is a safer alternative.

Predict the output of the following code:

java
public int mystery(int n) {
  if (n <= 0) {
    return 0;
  } else {
    return n + mystery(n - 2);
  }
}
System.out.println(mystery(5));

What is the output of the following code?

java
public int recursiveMethod(int num) {
 if (num == 0)
 return 1;
 else
 return num * recursiveMethod(num - 1);
}
System.out.println(recursiveMethod(3));

What is the output of the following code?

java
public int method(int num) {
 if (num == 5)
 return 5;
 else
 return num + method(num + 1);
}
System.out.println(method(2));

What is the output of the following code?

java
public int method(int num) {
 if (num == 0)
 return 0;
 else
 return 1 + method(num / 2);
}
System.out.println(method(8));

What is the output of the following code?

java
public int method(int num) {
 if (num == 0)
 return 0;
 else
 return 1 + method(num - 1);
}
System.out.println(method(4));

What are the differences between recursion and iteration?

Recursion: Solves problems by breaking them into smaller, self-similar subproblems. Can be more elegant for some problems. | Iteration: Solves problems by repeating a block of code until a condition is met. Generally more efficient in terms of speed and memory.

What are the differences between linear search and binary search?

Linear Search: Checks each element sequentially. Works on unsorted arrays. | Binary Search: Repeatedly divides the search interval in half. Requires a sorted array.

What are the key differences between iterative and recursive binary search?

Iterative Binary Search: Uses loops to narrow the search space. More efficient in terms of memory usage. | Recursive Binary Search: Calls itself with smaller sub-arrays. Can be more concise and easier to read for some programmers.