Here are two questions that I remember from the CPSC320 Final.

Divide and conquer

Majority element

Design an divide and conquer algorithm to determine whether an integer x is a majority element (appears more than len(A)/2 of times) of a sorted integer array A.

public static boolean isMajority(int[] A, int x, int n) {
	int i = firstOccurrence(A, x, 1, n);
	// x doesn't appear in A
	if (i < 0 || i >= n) {
		return false;
	}
	// check if x is present more than n/2 times
	if ((i + n/2 < n) && (A[i + n/2] == x)) {
		return true;
	}
	return false;
}

// O(log(n))
public static int firstOccurrence(int[] A, int x, int lo, int hi) {
	int mid = (lo + hi) / 2;
	if (lo > hi) {
		return lo;
	} else if (lo == mid) {
		return mid;
	} else if (A[mid-1] < x && A[mid] == x) {
		return mid;
	} else if (x > A[mid]) {
		return firstOccurrence(A, x, mid+1, hi);
	} else {
		return firstOccurrence(A, x, lo, mid-1);
	}
}

GeeksforGeeks link

Dynamic programming

Word break

Problem description: GeeksforGeeks

  1. Given a greedy algorithm: Start from the beginning and work to the end, once we find a substring that can be splitted, split after it. Does this algoritm work?

    No. The greedy algorithm doesn’t work.

    If we have valid words: “a”, “bb”, “bbb”

    Can we split “bbba”?

    Greedy will split like this: “bb” “ba” (“ba” is not word)
    but actually can split: “bbb” “a”

  2. Give a DP solution to the problem

Recurrence:

canSplit(str) := True 	If isWord(str)
              := isWord(str[:i]) and canSplit(str[i:])	Otherwise

def isWord(str):
	if str in ["a", "tea", "at", "ate", "cup", "eat"]:
		return True
	else:
		return False

def canSplit(str):
	if (isWord(str)): return True
	ans = False
	for i in range(len(str)):
		ans |= (isWord(str[:i]) and canSplit(str[i:]))
		if ans: break
	return ans

def dp(str):
	T = [False]*(len(str)+1)
	T[0] = True
	for i in range(1, len(str)+1):
		for j in range(i):
			if T[j] and isWord(str[j:i]):
				T[i] = True
				break
	return T[len(str)]

Online Judge