Monthly Archives: March 2013

CodingBat: Java. Recursion-1, Part II

countHi:

public int countHi(String str) {
	if (str.length() < 2) return 0;
	if (str.substring(0, 2).equals("hi"))
		return 1 + countHi(str.substring(2));
	return countHi(str.substring(1));
}

changeXY:

public String changeXY(String str) {
	if (str.length() == 0) return str;
	if (str.charAt(0) == 'x') return "y" + changeXY(str.substring(1));
	return str.charAt(0) + changeXY(str.substring(1));
}

changePi:

public String changePi(String str) {
	if (str.length() < 2) return str;
	if (str.substring(0, 2).equals("pi"))
		return "3.14" + changePi(str.substring(2));
	return str.charAt(0) + changePi(str.substring(1));
}

noX:

public String noX(String str) {
	if (str.length() == 0) return "";
	if (str.charAt(0) == 'x') return noX(str.substring(1));
	return str.charAt(0) + noX(str.substring(1));
}

array6:

public boolean array6(int[] nums, int index) {
	if (nums.length == 0) return false;
	if (index == nums.length - 1) return nums[index] == 6;
	if (nums[index] == 6) return true;
	return array6(nums, index + 1);
}

array11:

public int array11(int[] nums, int index) {
	if (index == nums.length) return 0;
	if (nums[index] == 11) return 1 + array11(nums, index + 1);
	return array11(nums, index + 1);
}

array220:

public boolean array220(int[] nums, int index) {
	if (nums.length < 2 || index == nums.length - 1) return false;
	if (nums[index + 1] == nums[index] * 10) return true;
	return array220(nums, index + 1);
}

allStar:

public String allStar(String str) {
	if (str.length() <= 1) return str;
	return str.charAt(0) + "*" + allStar(str.substring(1));
}

pairStar:

public String pairStar(String str) {
	if (str.length() < 2) return str;
	if (str.charAt(0) == str.charAt(1))
		return str.charAt(0) + "*" + pairStar(str.substring(1));
	return str.charAt(0) + pairStar(str.substring(1));
}

endX:

public String endX(String str) {
	if (str.length() == 0) return str;
	if (str.charAt(0) == 'x')
		return endX(str.substring(1)) + "x";
	return str.charAt(0) + endX(str.substring(1));
}

CodingBat: Java. Recursion-1, Part I

Recursion is neat in theory and commonly leads to very clean code. Some people have a hard time understanding it, though. If you’ve ever encountered a recurrence relation in mathematics, then you already know everything there is to know about the “mind-bending” nature of recursive problems.

Otherwise, try this simple strategy. First, you may be tempted to think recursively about recursive functions. This may work with factorials, but for something more complex like, say, the Ackermann function, it’s a recipe for disaster. So, don’t do it! Instead, figure out what the base case consists of. The base case immediately returns a result. All other conditions eventually have to revert to the base case, which means that you’ll return “something” in addition to recursively calling the function, but with an input that brings you closer to the base case.

The first example, factorial, of CodingBat’s Recursion-1 section illustrates this strategy very well. All subsequent problems are rather similar.

All solutions were successfully tested on 24 March 2013.

factorial:

public int factorial(int n) {
	if (n <= 1) return 1;
	return n * factorial(n - 1);
}

bunnyEars:

public int bunnyEars(int bunnies) {
	if (bunnies == 0) return 0;
	return 2 + bunnyEars(bunnies - 1);
}

fibonacci:

public int fibonacci(int n) {
	if (n <= 1) return n;
	return fibonacci(n - 2) + fibonacci(n - 1);
}

bunnyEars2:

public int bunnyEars2(int bunnies) {
	if (bunnies == 0) return 0;
	if (bunnies % 2 == 1) return 2 + bunnyEars2(bunnies - 1);
	return 3 + bunnyEars2(bunnies - 1);
}

triangle:

public int triangle(int rows) {
	if (rows == 0) return 0;
	return rows + triangle(rows - 1);
}

sumDigits:

public int sumDigits(int n) {
	if (n == 0) return 0;
	return n % 10 + sumDigits(n / 10);
}

count7:

public int count7(int n) {
	if (n == 0) return 0;
	if (n % 10 == 7) return 1 + count7(n / 10);
	return count7(n / 10);
}

count8:

public int count8(int n) {
	if (n == 0) return 0;
	if (n >= 88 && n % 100 == 88) return 2 + count8(n / 10);
	if (n % 10 == 8) return 1 + count8(n / 10);
	return count8(n / 10);
}

powerN:

public int powerN(int base, int n) {
	if (n == 0) return 1;
	return base * powerN(base, n - 1);
}

countX:

public int countX(String str) {
	if (str.length() == 0) return 0;
	if (str.charAt(0) == 'x') return 1 + countX(str.substring(1));
	return countX(str.substring(1));
}

CodingBat: Java. AP-1, Part III

scoresSpecial:

public int scoresSpecial(int[] a, int[] b) {
	return largest(a) + largest(b);
}


public int largest(int[] array) {
	int result = 0;
	for (int i = 0; i < array.length; i++)
		if (array[i] % 10 == 0 && array[i] > result)
			result = array[i];
	return result;
}

sumHeights:

public int sumHeights(int[] heights, int start, int end) {
	int sum = 0;
	for (int i = start; i < end; i++)
		sum += Math.abs(heights[i] - heights[i + 1]);
	return sum;
}

sumHeights2:

public int sumHeights2(int[] heights, int start, int end) {
	int sum = 0;
	for (int i = start; i < end; i++)
		if (heights[i] < heights[i + 1])
			sum += (2 * Math.abs(heights[i] - heights[i + 1]));
		else
			sum += Math.abs(heights[i] - heights[i + 1]);
	return sum;
}

bigHeights:

public int bigHeights(int[] heights, int start, int end) {
	int count = 0;
	for (int i = start; i < end; i++)
		if (Math.abs(heights[i] - heights[i + 1]) >= 5) count++;
	return count;
}

userCompare:

public int userCompare(String aName, int aId, String bName, int bId) {
	if (aName.compareTo(bName) < 0) return -1;
	if (aName.equals(bName)) {
		if (aId == bId) return 0;
		if (aId < bId) return -1;
	}
	return 1;
}

mergeTwo:

public String[] mergeTwo(String[] a, String[] b, int n) {
	String[] result = new String[n];
	int indexResult = 0;
	int indexA = 0;
	int indexB = 0;

	while (indexResult < n)
		if (a[indexA].compareTo(b[indexB]) < 0)
			result[indexResult++] = a[indexA++];
		else if (a[indexA].compareTo(b[indexB]) > 0)
			result[indexResult++] = b[indexB++];
		else { // identical strings
			result[indexResult++] = a[indexA++];
			indexB++;
		}
	return result;
}

commonTwo:

public int commonTwo(String[] a, String[] b) {
	int count = 0;
	String lastChecked = null;
	for (int i = 0; i < a.length; i++)
		if (!a[i].equals(lastChecked))
			for (int j = 0; j < b.length; j++)
				if (a[i].equals(b[j])) {
					count++;
					lastChecked = a[i];
					break;
				}
	return count;
}

CodingBat: Java. AP-1, Part II

hasOne:

public boolean hasOne(int n) {
	while (n > 0) {
		if (n % 10 == 1) return true;
		n = n / 10;
	}
	return false;
}

dividesSelf:

public boolean dividesSelf(int n) {
	int copyN = n;
	while (n > 0)
		if (n % 10 == 0) return false;
		else
			if (copyN % (n % 10) == 0) n /= 10;
			else return false;
	return true;
}

copyEvens:

public int[] copyEvens(int[] nums, int count) {
	int[] result = new int[count];
	int position = 0;

	for (int i = 0; i < nums.length; i++) {
		if (nums[i] % 2 == 0) {
			result[position] = nums[i];
			position++;
		}
		if (position == count) break;
	}
	return result;
}

copyEndy:

public int[] copyEndy(int[] nums, int count) {
	int[] result = new int[count];
	for (int i = 0, pos = 0; i < nums.length; i++) {
		if (nums[i] >= 0 && nums[i] <= 10 || nums[i] >= 90
				&& nums[i] <= 100) {
			result[pos] = nums[i];
			pos++;
		}
		if (pos == count) break;
	}
	return result;
}

matchUp:

public int matchUp(String[] a, String[] b) {
	int count = 0;
	for (int i = 0; i < a.length; i++)
		if (!a[i].equals("") && !b[i].equals("")
				&& a[i].charAt(0) == b[i].charAt(0))
			count++;
	return count;
}

scoreUp:

public int scoreUp(String[] key, String[] answers) {
	int sum = 0;
	for (int i = 0; i < answers.length; i++)
		if (answers[i] == key[i]) sum += 4;
		else if (!answers[i].equals("?")) sum -= 1;
	return sum;
}

wordsWithout:

public String[] wordsWithout(String[] words, String target) {
	int count = 0;
	for (int i = 0; i < words.length; i++)
		if (!words[i].equals(target)) count++;

	String[] result = new String[count];
	for (int i = 0, pos = 0; i < words.length; i++)
		if (!words[i].equals(target)) {
			result[pos] = words[i];
			pos++;
		}
	return result;
}

CodingBat: Java. AP-1, Part I

After the more demanding Array-3 section, AP-1 on CodingBat is much more relaxing as it reviews basic programming concepts, with a strong focus on array processing.

All solutions were successfully tested on 16 March 2013.

scoresIncreasing:

public boolean scoresIncreasing(int[] scores) {
	for (int i = 0; i <= scores.length - 2; i++)
		if (scores[i] > scores[i + 1]) return false;
	return true;
}

scores100:

public boolean scores100(int[] scores) {  
	for (int i = 0; i <= scores.length - 2; i++)
		if (scores[i] == 100 && scores[i + 1] == 100) return true;
	return false;
}

scoresClump:

public boolean scoresClump(int[] scores) {
	if (scores.length > 2) {
		for (int i = 0; i < scores.length - 2; i++) {
			if (scores[i + 2] - scores[i] <= 2)
				return true;
		}
	}
	return false;
}

scoresAverage:

public int scoresAverage(int[] scores) {
	int first = average(scores, 0, scores.length / 2);
	int second = average(scores, scores.length / 2, scores.length);
	return Math.max(first, second);
}

private int average(int[] scores, int start, int end) {
	int sum = 0;
	int count = 0;
	for (int i = start; i < end; i++) {
		sum += scores[i];
		count++;
	}
	return sum / count;
}

wordsCount:

public int wordsCount(String[] words, int len) {
	int count = 0;
	for (int i = 0; i < words.length; i++)
		if (words[i].length() == len) count++;
	return count;
}

wordsFront:

public String[] wordsFront(String[] words, int n) {
	String[] newWords = new String[n];
	for (int i = 0; i < n; i++)
		newWords[i] = words[i];
	return newWords;
}

wordsWithoutList:

public List wordsWithoutList(String[] words, int len) {
	List result = new ArrayList();
	for (int i = 0; i < words.length; i++)
		if (words[i].length() != len)
			result.add(words[i]);
	return result;
}