Midterm practice questions

Linked Lists

1. Write an algorithm to detect a cycle in a linked list.
2. Remove consecutive duplicate entries from a given linked list.
3. Get the k-th to the last element in the linked list (when the size of the list is not known/tracked).
4. Check if the linked list is a palindrome.
5. Reverse a singly-linked list non-recursively.

Stacks

1. Design a stack such that getMinimum() is O(1).
2. Given an array of characters formed with a’s and b’s. The string is marked with special character X, which represents the middle of the list. Check whether the string is palindrome or not.

Recursion

1. Write a recursive algorithm to perform x^n.
2. Write a recursive algorithm to count the number of 1s in a given binary representation.

Trees / Binary search trees

1. Given a binary search tree, print the elements in a new order, as suggested by the example shown below:

bst1

The expected output is: 10, 14, 2, 12, 25, 75, 8, 50, 15.
2. Find the nearest match of a given value in a binary search tree.
3. Write a function to check whether two binary trees are structurally identical.
4. Write a function to find the size of a BST.
5. Write a function to compute the sum of all elements in a BST.

Asymptotic Complexity analysis

1. For the sorting algorithm below, compare the time complexity for partitioning in the middle vs in the beginning.

List L; Sorted List L’; Size = n
Recursive function: SORT(L)
Basis: (n == 1) => L’ = L
Inductive: (n > 1) =>
 1. Split L into two non-empty sets L1 and L2.
 2. L1’ = SORT(L1); L2’ = SORT(L2)
 3. L’ = COMBINE(L1’, L2’)

2. Write down the Big-oh, Big-omega and Big-theta functions for f(n) = 0.5 n^3 + 2 n^2 + log n
3. For the following snippet of code, analyze the worst case complexity for the following code.

for (int i = 0; i < n; ++i) {
   for (int j = i+1; j < n; ++j) {
       if (A[i] == A[j]) {
          return true;
       }
   }
   return false;
}