Recursion
Trees
Sorting & Comparisons
Loop invariants & searching
Concurrency
100

This specific code within a recursive function is one of the components of the function and usually acts on one special input value. Without it, the recursive function runs indefinitely. 

What is the base case?
100

Identify an example of a leaf, parent and child, a subtree, the root

 1

 /\

2  3

/\    \

4 5     7


Leaf: 4, 5, or 7

Example Parent and Child: 4 as a child to 2

Example Subtree: 2, 4, 5

Root: 1

100

This is a divide-and-conquer algorithm that divides the input array into two halves, recursively sorts each half, and then merges the sorted halves to obtain the final sorted array.

What is merge sort?

100

This is a condition a condition [among program variables] that is necessarily true immediately before and immediately after each iteration of a loop. (Note that this says nothing about its truth or falsity part-way through an iteration.)

What is a loop variant?

100

This is a synchronization construct that allows multiple threads to wait at a specific point until all participating threads have reached that point.

What is a barrier?

200

Explain the space complexity, in Big O notation, of a recursive function countNodes(node) that traverses a binary tree. Assume n is the number of nodes in the tree.

What is O(n) where h is the height of the tree? 

200

What is the minimum and maximum possible height of a binary tree of size 10?



Min: 4
Max: 9


200

Given some properties about an array to be sorted and performance constraints, this sorting algorithm would be most appropriate if only a couple of elements are out of order.

What is insertion sort?

200

These four questions make up the 'loopy questions' also known as the loop checklist (Explain each question in your own words and describe what they mean for designing and verifying loops)

  • Does it start right? Initializes loop variables to start the loop correctly.
  • Does it maintain the invariant: Verifies that the loop invariant holds true during each iteration.
  • Does it make progress? Ensures the loop condition will become false eventually, preventing infinite loops.
  • Does it end right?: Describes the expected state or outcome after the loop finishes executing.
200

This condition variable is provided by the Object class and wakes up all threads that are waiting on the same object, giving them a chance to resume execution

What is notifyAll()?

300

During the execution of a recursive function fibonacci(n), draw the call stack when n = 5. Alternatively, state the maximum depth of recursion reached during the computation of fibonacci(n).

fibonacci(5)

fibonacci(4)

fibonacci(3)

fibonacci(2)

fibonacci(1)

fibonacci(0)

What is a max depth of 5?

300

This property must hold true for all nodes in a balanced binary search tree to ensure logarithmic height.

What is that the height difference between the left and right subtrees of any node is at most 1?

300

These two following sorting algorithms are considered stable because they preserve the relative order of elements with equal values.

What is Insertion sort and merge sort



300

Describe the linear and binary search algorithms in your own words.

Linear Search: Iteratively checks each element in a sequence (e.g., array) from start to end until finding the target value.
Binary Search: Divides the search interval in half with each step, comparing the target value to the middle element. If the middle element matches the target, the search ends;

300

Given these two sequences can deadlock occur? If yes, propose an alteration to one of the sequences.  

Deadlock can occur if these processes happen simultaneously.
Swapping step 4 and step 5 in process 2 would help the processes avoid deadlock because the resources are acquired in the same order.

400

Implement a recursion function to calculate the nth number in a fibonacci sequence



int fibonacci(int n, int curr, int prev) {

        if (n == 1 || n == 2) {

            return curr; // Base case: fibonacci(1) and fibonacci(2) are 1

        }

        return fibonacci(n - 1, curr + prev, curr); // Recursive call

}



400

What is the postorder traversal of the tree below/drawn on the board? 

        1

       / \

     2    3

    / \     \

 4     5      6 


What is 4,5,2,6,3,1?

400

Given a loop invariant, determine whether it is consistent with the outer loop of selection sort, the outer loop of insertion sort, an insertion procedure for insertion sort, or a partitioning algorithm for quicksort.

for (int i = 0; i < array.length - 1; i++) {

    int minIndex = i;

    // Inner loop invariant for finding the minimum element

    for (int j = i + 1; j < array.length; j++) {

        if (array[j] < array[minIndex]) {

            minIndex = j;

        }

    }

    // Swap elements to place the minimum at the beginning

    int temp = array[i];

    array[i] = array[minIndex];

    array[minIndex] = temp;

}


Loop invariant for the outer loop of selection sort

400

You are given Java code for a loop with missing pieces How would you correct and complete the loop to ensure correctness?

// Precondition: array is not null and contains elements

// Loop Invariant: The elements before current index are not equal to the target

// Postcondition: index is the position of the target in the array or -1 if not found

int[] array = {5, 2, 7, 1, 9};

int target = 7;

int index = -1;

for (int i = 0; i < _______ ; i++) {

    if (_________ ) {

        index = ___;

        break;

    }

}


// Precondition: array is not null and contains elements

// Loop Invariant: The elements before current index are not equal to the target

// Postcondition: index is the position of the target in the array or -1 if not found

int[] array = {5, 2, 7, 1, 9};

int target = 7;

int index = -1;

for (int i = 0; i < array.length; i++) {

    if (array[i] == target) {

        index = i;

        break;

    }

}


400

Write code to execute a function on a new thread using Java's Thread class API.

Runnable task = () -> {

    // Code to be executed on a new thread

    System.out.println("Task executed on thread: " + Thread.currentThread().getName());

};

Thread thread = new Thread(task);

thread.start();


500

Write a recursive method 'int sumDigits(int number)' that returns the sum of the digits of a given number. The method should sum the digits of the number until only a single digit remains.

Example: Input: 1234

Output: 1 (because 1 + 2 + 3 + 4 = 10, then 1 + 0 = 1) Implement the 'sumDigits' method.



 public static int sumDigits(int number) {

        if (number < 10) {

            return number;

        }

        int sum = number % 10 + sumDigits(number / 10);

        return sum < 10 ? sum : sumDigits(sum);

    }



500

Turn getHeight() into an instance method in the TreeNode class. 

Hint: have a public function called getHeight that calls a private recursive function, both in the TreeNode class

Hint: You can utilize Math.max()


public int getHeight() {

        return getHeightRecursive(this);

}

private static int getHeightRecursive(TreeNode node) {

        if (node == null) {

            return 0; // Base case: empty subtree has height 0

        }

        int leftHeight = getHeightRecursive(node.left);

        int rightHeight = getHeightRecursive(node.right);

        return Math.max(leftHeight, rightHeight) + 1;

}

500

Given a class with two observers, declare and implement a Comparator that orders instances of the class first by one observable, then, in the case of a tie, by the other.

import java.util.Comparator;public class MyClassComparator implements Comparator<MyClass> {

    @Override

    public int compare(MyClass obj1, MyClass obj2) {

//code here
}    

import java.util.Comparator;

public class MyClassComparator implements Comparator<MyClass> {

    @Override

    public int compare(MyClass obj1, MyClass obj2) {

        if (obj1.getObservable1() != obj2.getObservable1()) {

            return Integer.compare(obj1.getObservable1(), obj2.getObservable1());

        } else {

            return Integer.compare(obj1.getObservable2(), obj2.getObservable2());

        }

    }

}


500

Implement a method binarySearch in Java that performs a binary search on a sorted array of integers. Define and explain the loop invariant that ensures correctness throughout the binary search algorithm. Return -1 if the target is not within the array.

public class BinarySearchExample {

    // Method to perform binary search on a sorted array of integers

    public static int binarySearch(int[] array, int target) {

        int low = 0;

        int high = array.length - 1;


        // Loop invariant: The target, if present, is within the range [low, high]

        while (low <= high) {

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


            // If target is found at mid, return mid index

            if (array[mid] == target) {

                return mid;

            } else if (array[mid] < target) {

                // If target is greater, ignore left half

                low = mid + 1;

            } else {

                // If target is smaller, ignore right half

                high = mid - 1;

            }

        }


        // Target not found in the array

        return -1;

    }

}

500

Complete the implementation of the Counter class by adding synchronization blocks to the increment and decrement methods to protect the counter from concurrent access issues.

public class Counter {

    private int count;


    public Counter(int initialValue) {

        this.count = initialValue;

    }


    public void increment() {

        // _______________ (this) {

            count++;

        }

    }


    public void decrement() {

       __________________ {

            count--;

        }

    }


    public int getCount() {

        return count;

    }

}


public class Counter {

    private int count;

    public Counter(int initialValue) {

        this.count = initialValue;

    }

    public synchronized void increment() {

        // Synchronized block to increment the counter

        synchronized (this) {

            count++;

        }

    }


    public synchronized void decrement() {

        // Synchronized block to decrement the counter

        synchronized (this) {

            count--;

        }

    }


    public synchronized int getCount() {

        return count;

    }

}